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 can't declare a recursive structure.

The best you could probably do is have a map of map of pointer.

Answer 2

The problem is that your type definition for NamedNestedMap has no termination in its recursive structure. The template expansion for NamedNestedMap will be infinite and thus there is no way represent it in code.

Answer 3

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.

Answer 4

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 5

It sounds like you want to do something like this:

class Node {
    ...

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

Here, each Node has a map of "children" in a map, and this children can have children, and so-on.

Answer 6

You can't do it the way you present it, and you probably don't want to. The reason for this is that pairs in the map are stored by value. Do you want your whatever name-value table be copied into another container? I would go for a wrapper along the lines @strager and Pavel are proposing, optionally using smart pointers.

Answer 7

I guess you want to have a nested map of depth n:

template<class key_type, class val_type, int nest_depth>
struct nest
{
typedef std::map<key_type, typename nest<key_type, val_type, 
                nest_depth-1>::map_type> map_type;
};

template<class key_type, class val_type>
struct nest<key_type, val_type, 0>
{
    typedef std::map<key_type, val_type> map_type;
};

Use it like this:

nest<std::string, std::string, 2> nested_map;

Answer 8

This seems to compile for me:

#include <map>
#include <string>

struct RecMap
{
    std::map<std::string, RecMap> m;
};

int main()
{
    RecMap rec;
    rec.m["first"] = RecMap();
    rec.m["first"].m["second"] = RecMap();
}

Not 100% sure if it is legal (e.g can you have a class X that contains a vector<X> as a member?). The recursion isn't really infinite here, since eventually you'll run into a RecMap containing an empty map.

Edit: this article discusses the situation. Conclusion: undefined. Sorry.