circular dependent incomplete templated types

Sillydan 0
Viewed 36

I am trying to create a graph data-structure in an adjacency-map style, however I am running into some problems with circularly dependent structs. I have tried doing a forward declaration, but it doesn't seem to work. I keep getting invalid use of incomplete type node_collection<int>, which makes sense since I am forward declaring my types, but I would still like to get this working somehow.

#include <unordered_map>
#include <vector>
#include <iostream>

template<typename T> struct edge;
template<typename T> struct node;
template<typename T> using edge_collection = std::unordered_map<std::string, edge<T>>;
template<typename T> using edge_refference = typename edge_collection<T>::iterator;
template<typename T> using node_collection = std::unordered_map<std::string, node<T>>;
template<typename T> using node_refference = typename node_collection<T>::iterator;

template<typename T>
struct node {
    T data;
    std::vector<edge_refference<T>> outgoing_edges{};
    std::vector<edge_refference<T>> ingoing_edges{};
};

template<typename T>
struct edge {
    T data;
    node_refference<T> source;
    node_refference<T> target;
};

template<typename T>
struct graph {
    node_collection<T> nodes;
    edge_collection<T> edges;
};


int main() {
    graph<int> g{};
}

g++ main.cpp

What is really odd is that this works just fine when using clang on macos! I am only getting this issue on my linux PC.

incomplete-type g++ graph clang c++
1 Answers

The program is not guaranteed to compile, although the specification of the language is somewhat lacking in this area.

Your variable in main requires instantiation of graph<int>, which in turn requires instantiation of std::unordered_map<std::string, node<T>>.

std::unordered_map does not promise that it can be instantiated with incomplete types. Therefore instantiation of node<T> may also happen at this point.

Instantiation of node<T> requires in turn that edge_collection<T> be complete in order to access its ::iterator member to determine the type of node<T>'s member. But edge_collection<T> for the same reason as above may require instantiation of edge<T>. edge<T> in turn requires instantiation of node_collection<T> which is just std::unordered_map<std::string, node<T>> so that you now have circular dependence of the instantiations.

So you are just lucky if it happens to compile.

In practice compilers don't actually require that a class be complete when a member is accessed with :: as the standard requires, but allow lookup of any member that has been declared before the member declaration which caused the implicit instantiation requiring the lookup. However even with that more permissive behavior you would need to be lucky that iterator is declared in std::unordered_map before any use of the value type that would require it to be complete.

The only containers that the standard currently guarantees can be used this way with incomplete types are std::vector, std::list and std::forward_list (since C++17, none before).

Specifically for libstdc++ it seems that there is some intention to allow std::unordered_map to be usable with incomplete types, based on this commit, which is likely the reason that it works in GCC 12, but not GCC 11. If incomplete types were supported by std::unordered_map, then your program would be fine.

user177325220
Related