I'm trying to use an std::list and an std::unordered_map to store a directed acyclic graph. Each list element stores a node key (unsigned) and its children. And the map stores, for each key, an iterator to the node in the list:

std::list<std::pair<unsigned, std::list<decltype(lst.begin())>>> lst;
std::unordered_map<unsigned, decltype(lst.begin())> nodemap;

But decltype(lst.begin()) in the declaration of lst results in a compile error since lst is not defined yet. Can I define lst another way ?

Edit: using std::vector<unsigned, std::list<unsigned>> vec would probably work, where list<unsigned> contains indexes into vec. Not sure whether sticking with the initial std::list is better or worse.

CodePudding user response：

Write classes. Within the definition of the class, it is an incomplete type, which means you can use pointers (or references) to it.

The children pointers can be non-owning, with the map owning all the nodes.

class Graph {
    struct Node {
        unsigned key;
        std::vector<Node *> children;
    };

    std::unordered_map<unsigned, Node> nodes;
public:
    // graph behaviours
};