CODEWITHSUNDEEP
c++stl
boatcoder
boatcoder

Reputation: 18107

Nested std::maps

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.

Upvotes: 4

Views: 9040

Answers (9)

Apollo
Apollo

Reputation: 1986

I think that creating a recursive structure can bring you problems. Just use normal maps, like this:

#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!
$

Upvotes: 0

UncleBens
UncleBens

Reputation: 41341

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.

Upvotes: 0

Georg Fritzsche
Georg Fritzsche

Reputation: 99034

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;

Upvotes: 5

Nikolai Fetissov
Nikolai Fetissov

Reputation: 84189

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.

Upvotes: 0

Laurence Gonsalves
Laurence Gonsalves

Reputation: 143234

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.

Upvotes: 2

Pavel Minaev
Pavel Minaev

Reputation: 101605

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.

Upvotes: 8

strager
strager

Reputation: 90042

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.

Upvotes: 6

Steve Guidi
Steve Guidi

Reputation: 20200

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.

Upvotes: 1

Loki Astari
Loki Astari

Reputation: 264531

You can't declare a recursive structure.

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

Upvotes: 2

Related Questions