I have a tree whose nodes are large strings. I don't really need to navigate the tree other than to follow the path from a node back to the root, so it suffices for each node to consist of the string and a pointer to its parent. I also need to be able to quickly find strings in the tree. The nodes of the tree themselves are not ordered, so this would require some sort of index. However, the strings are big enough that I would rather not duplicate them by storing them both in my tree and in my index.

I could implement both my tree and the index with a single std::map if the key for the map was the string and the mapped value was the pointer to its parent. However, I cannot figure out a way to write either of these types. My best guess would be something like this:

using Tree = std::map<std::string, typename Tree::const_iterator>;

or maybe:

using Node = std::pair<std::string const, typename Node const*>;
using Tree = std::map<std::string, Node const*>;

But these recursive type definitions don't compile. Is there any way to create this type in C ? Or a better way to do what I am trying to do?

CodePudding user response：

You can wrap the iterator in a type of your own and reference that type instead to avoid the recurisve type problem.

struct parent_iter {
    using iter_type = map<string, parent_iter>::const_iterator;

    iter_type iter;

    parent_iter() {}
    parent_iter(iter_type _iter) : iter(_iter) {}
};

using tree = map<string, parent_iter>;

CodePudding user response：

Your using Node definition doesn't compile, but an actual structure would:

struct Node {
    std::string const s;
    Node const* n;
};