recursive stl map

Question

I'm trying to make a tree of maps (or just have values of a map point to another map), but I'm not too sure how to approach this. I found a discussion about this: http://bytes.com/topic/c/answers/131310-how-build-recursive-map but I'm a little confused on what's going on there.

For example, my key is a char, and my value is the next map. Here's the hypothetical declaration:

map< char, map< char, map< char.......>>>>>>>>>> root_map;

fundamentally you are doing things wrong. or may be wrong approach for your problem. Explain what is your problem statement here first than your approach to solve the problem — , Oct 15 '10 at 09:43
In the discussion you reference, they 'solved' the problem by disabling the type-checking that the compiler does. They told the compiler that each map stores as value a pointer to an unknown type and only the programmer knows that is should be a pointer to another map. — Bart van Ingen Schenau, Oct 15 '10 at 10:38
Thanks for explaining. It was kinda late when I posted this so I guess it was poorly phrased. — thomast.sang, Oct 23 '10 at 18:47
unfortunately c++ doesn't currently allow indefinite recursion in generic type definitions, although imho it should, I've been looking for that feature. But you can create a map of pointers to other objects (which can recursively indefinately be maps to other objects), and use RTTI to check which it actually is. — mo FEAR, Apr 24 '22 at 21:36
see [this](https://stackoverflow.com/questions/71315224/can-a-recursive-self-referential-template-using-pointers-be-instantiated-and-o), it might be related — mo FEAR, Apr 24 '22 at 21:49

score 2 · Answer 1 · answered Jan 18 '14 at 13:15

As idea, something like this:

struct CharMap {
    std::map<char,CharMap> map;
} root_map;

and use it like

root_map.map['a'].map['b'];

Probably you could make it more fancy with additional methods and operators on the CharMap that would eleminate the need of the .map when accessing your structure.

score 2 · Answer 2 · answered Nov 26 '14 at 18:47

2

Yes you can. In order for the map to do anything useful though, you're going to have to decorate it with methods (in this case, Set and Get).

#include <map>
#include <iostream>

class Clever : public std::map <int, Clever>
{
  public:
    Clever & Set (int i) { m_i = i; return *this; }
    int Get (void) { return m_i; }

  private:
    int m_i;
};

int main (void)
{
  Clever c;
  c[0][2][3].Set(5);

  std::cout << c[0][2][3].Get() << std::endl;

  return 0;
}

answered Nov 26 '14 at 18:47

QuestionC

10,006
4
26
44

*"Yes you can"* - Maybe not in old STL implementations. Isn't `Clever` an incomplete type? I'm reading [this answer](https://stackoverflow.com/a/60020723/7143595) and an [old article](https://drdobbs.com/the-standard-librarian-containers-of-inc/184403814) – MatG Nov 08 '22 at 09:36

score 2 · Answer 3 · answered Oct 15 '10 at 09:47

Maybe you're thinking of something like:

#include <iostream>
#include <map>

template <typename Key, typename Value>
struct Tree
{
    typedef std::map<Key, Tree> Children;

    Tree& operator=(const Value& value) { value_ = value; return *this; }

    Tree& operator[](const Key& key) { return children_[key]; }

    Children children_;
    Value value_;

    friend std::ostream& operator<<(std::ostream& os, const Tree& tree)
    {
        os << tree.value_ << " { ";
        for (typename Children::const_iterator i = tree.children_.begin();
                i != tree.children_.end(); ++i)
            os << i->first << " -> " << i->second << " | ";
        return os << '}';
    }
};

int main()
{
    Tree<int, std::string> t;
    t[1].children_[1] = "one,one";
    t[1].children_[9] = "one,nine";
    t[1] = "hmmm";
    std::cout << t << '\n';
}

I wouldn't really recommend it.

score 2 · Answer 4 · answered Oct 15 '10 at 10:22

2

I'm not excatly sure what you want to achieve, but when I hear "tree of maps" I think of the following:

class NodeData
{
    // Some stuff...
};

class TreeNode
{
public:
    NodeData* data;
    std::map<char, TreeNode*> children;
};

answered Oct 15 '10 at 10:22

Sebastian Negraszus

11,915
7
43
70

This was my original approach, and I ended up going back to this. Turns out I was just linking them wrong...thanks! – thomast.sang Oct 23 '10 at 18:46

recursive stl map

4 Answers4