Declare a C++ std::list with elements that point to other elements in the list

Question

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.

Answer 1

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
};