iterator size

[suhrig]

Hello,

I just found your implementation of a HAT-tree map and already love it. I use strings as keys and structs as values, and it is faster than a std::map / std::unordered_map for my use case and more memory efficient. However, I noticed that the iterators are a lot bigger than that of a std::map: 72 bytes compared to just 8 bytes for an iterator of a std::map. My software needs to remember the locations of a ton of items, so the bigger the size of a single iterator, the more memory is consumed. With a std::map, I can instruct my software to remember the items using a vector of iterators. I can easily retrieve the keys using i->first and the values using i->second. When I use htrie_map, the vector of iterators grows substantially, because the individual iterators are so big. Is there a more memory efficient way to store a list of locations, which lets me retrieve both the key and the value? Are there more lightweight iterators? Or pointers to items of the htrie_map from which key and value can be reconstructed? Simple pointers to the values are not an option, because I also need the key.

Many thanks in advance,
Sebastian

[Tessil]

Hi,

Effectively I didn't really optimize the size of the iterators. It could be possible to reduce its size a bit but not by much I think.

Introducing a way to remember a position in a lightweight fashion and recreate an iterator from there could be a good way to go. It would still need at least 16 bytes on a 8-byte pointer platform, maybe more, as I need to at least remember the position in the hash map + the node containing the hash map.

I will see what can be done and come back to you.

Thibaut