How to create a recursive nested hashmap in C++?

Question

def recursiveDict():
   return collections.defaultdict(recursiveDict)

# I can create a dictionary like the following
dic = recursiveDict()
dic['a'] = 1
dic['a']['a'] = 1
dic['a']['a']['a'] = 1
dic['a']['a']['a']['a'] = 1
and so on....

I have returned to work with C++ after working for 4 years with Python and other dynamic languages. I wanted to be able to create a recursive nested list(like the one shown in the Python code above) maybe using the unordered_map or the map class.

I am unable to find a way to do that.

What I want to achieve is that the keys should be of char/string type but the value to be inserted should be of int type.

Please do let me know how can this be done.

The closest I have come to is this

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

and use it like

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

But what should I overload to get the exact syntax as above?

Thanks in advance.

Nothing like that is a part of the standard C++ library. You must implement this container yourself. It's certainly possible to do this, in C++, but this requires thorough understanding and knowledge of C++ containers, algorithms, and operator overloading. This can't be explained in one or two short paragraphs on Stackoverflow, this knowledge can only be learned [from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). Good luck! — Sam Varshavchik, May 01 '21 at 11:42
@SamVarshavchik , maybe there is something wrong with the way I have asked my question. I am well aware of all these concepts. But I don't know how to code this. I'll make the changes in the original question as well. — Sanskar Jethi, May 01 '21 at 12:00
You may find some inspiration from this library that implements a `Json` parser using this syntax. https://github.com/nlohmann/json See the examples here: https://github.com/nlohmann/json#examples — Galik, May 01 '21 at 12:03
Do you want each node to store **both** a char and a map, or only one of them? — HolyBlackCat, May 01 '21 at 12:08
@HolyBlackCat , I want all of them to store a char and a map. Only the last node should store a char and a value(maybe a char/int). — Sanskar Jethi, May 01 '21 at 12:09

score 2 · Accepted Answer · answered May 01 '21 at 12:26

Since you clarified that you are familiar with the basic concepts of operator overloading, I will sketch out a basic blueprint that you can follow to implement this syntax.

Your container will implement an operator[] overload that returns a helper object. Let's say that your container is called CharMap, and after all is said and done, your container stores ints.

class CharMap {

    struct key {

        key operator[](const std::string &);

        operator int();

        key &operator=(int n);
    };

public:

    key operator[](const std::string &);

};

This would allow, for example:

CharMap container;

container["A"]["B"]["C"]=5;

int n=container["D"]["E"]["F"};

CharMap::operator[] returns a key helper object. That object also implements its own operator[] overload that returns another key. Finally, the key object implemets an operator= overload so you can assign to it, or operator int() overload to return a value from the container.

It's obvious that the key would store, internally, a pointer to the CharMap's container that it came from, so that it can either update or return the appropriate value from the container. The key also keeps track of all the keys that have been used to create it, in a piecemeal fashion, internally. CharMap::key that records, internally, the first string. Then, its key::operator[] returns another key that records, internally, the original string and another one.

Once either operator[] or operator int() gets invoked, they'll use all the accumulated strings to do their job, in some form or fashion that you'll need to figure out.

There are also some questions of efficiency that may or may not be addressed. This approach implements your desired syntax, but depending on your situation it might require some fine tuning to optimize the underlying implementation to eliminate a bunch of internal copying and shuffling of things.

Also, a little bit of additional work is needed to implement proper const-correctness. But all of these are just implementation details, and this is how you can implement this kind of a syntax for accessing a container that's indexed by multiple strings.

Thank you @SamVarshavchik for this amazing solution. I just have one question: what is the difference between the key operator statement and just the operator statement. If `operator int();` is for the return value, why didn't you put it out of the struct? — Sanskar Jethi, May 01 '21 at 13:17
Got it. Sorry for the above question. key is just the return type! — Sanskar Jethi, May 01 '21 at 13:19

score 0 · Answer 2 · answered May 01 '21 at 12:37

I wanted to be able to create a recursive nested list(like the one shown in the Python code above)

I doubt whether you actually want to do this. Of course we don't know the details of what you're trying to use this for, but:

If you want your associative structure to be keyed by short strings, consider using an std::string key, e.g. std::unoredered_map<std::string, int>.
If you want your associative structure to be keyed only by sequences of K characters - use something like a struct key { char[K] data; } as your key (and perhaps add relevant methods / conversion operators for that key class), or perhaps std::array<char, K>.
etc.

What I doubt is that you really need to able to say "I am applying a key partially", plus not being able to think of the general hash and the partial key (e.g. a string prefix) as your "subhashmap".

PS - If performance is a concern, remember that std::unordered_map is rather slow. And std::string's as keys will also slow you down, since they usually store the string data on the heap, which means a bunch of de/allocation work and accesses to possibly-arbitrary places on the heap.

How to create a recursive nested hashmap in C++?

2 Answers2