Nested std::maps

Question

Supposed I have a type I'll call NamedNestedMap

std::map<std::string, std::map<std::string, NamedNestedMap> >

In this case each second (value) of the pair is the same kind or type as the parent object. What I can't figure out is how to declare it. This will allows a recursive algorithm to walk down thru the "tree" of maps.

The Value type is the same as the parent type, which at the point I need to reference it, isn't fully declared.

How do you declare something nested like this...

I can't even typedef the first one so that I can include it the second because it's incomplete

The recursion would look for something in the map, when it finds it, recurse on the value of that object. The algorithm part seems pretty straight forward, the declaration part is the stumper here. I'm not trying to iterate the map of maps, just use the map.find, recurse and use map.find again.

Answer 1

You'll have to use pointers (naturally, since otherwise the recursion will never terminate - you'll always need one more empty map):

struct NestedMap;
struct NestedMap : std::map<std::string, NestedMap*> {};

Naturally, you'd probably want to use shared_ptr or something like that to manage memory, rather than raw pointers.

Answer 2

Create a struct representing a node.

struct Node {
    std::map<std::string, Node *> children;
};

You can, of course, make it a class and hide the data and such.