Nested std :: maps

Question

Suppose I have a type that I will name NamedNestedMap

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

In this case, each second (value) of the pair has the same type or type as the parent. I cannot figure out how to announce this. This will allow the recursive algorithm to descend through the map tree.

The type of the value matches the type of the parent, which at the point where I need to refer is not fully declared.

How do you declare something nested like this ...

I can’t even print the first one so that I can turn it on the second because it is incomplete

A recursion will look for something on the map when it finds it, a recursion on the value of this object. Part of the algorithm looks pretty straightforward, part of the declaration is here. I am not trying to iterate over a map of maps, just use map.find, recurse and use map.find again.

Answer 1

You will need to use pointers (naturally, since otherwise the recursion will never end - you will always need another empty map):

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

Naturally, you probably want to use shared_ptr or something similar to manage memory, rather than using raw pointers.

Answer 2

Create a structure representing the node.

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

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

Answer 3

I assume 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 as follows:

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

Answer 4

You cannot declare a recursive structure.

The best you could do is to have a map pointer map.

Answer 5

The problem is that the definition of your type for NamedNestedMap has no termination in its recursive structure. The template extension for NamedNestedMap will be infinite and, therefore, its code will not be displayed in the code.

Answer 6

It looks like you want to do something like this:

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

Here, each Node has a “children” card on the map, and these children can have children, etc.

Answer 7

You cannot do it the way you imagine it, and you probably don't want it. The reason for this is that the pairs on the map are stored by value. Do you want your table of names and values ​​to be copied to another container? I would go for a wrapper along the lines of @strager and Pavel suggested using smart pointers.

Answer 8

This seems like a compilation 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 that this is legal (for example, can you have a class X containing vector<X> as a member?). The recursion here is not endless, as in the end you will come across a RecMap containing an empty map.

Edit: This article discusses the situation. Conclusion: undefined. Unfortunately.

Answer 9

I think creating a recursive structure can cause problems. Just use regular cards, for example:

 #include <map> #include <string> using namespace std; int main() { map<string, map<string, string> > nest; nest["first"]["second"] = "Hello nest!"; printf("%s\n", nest["first"]["second"].c_str()); return 0; } 

And here is the execution:

 $ g++ ./nest.cpp -o nest.out -ansi -pedantic -std=c++98 $ ./nest.out Hello nest! $