Two separate keys map to a single entry in a std::map
I'm working on a piece of code that has the objective of being a fast "search engine". I have entries in a file that need to be searchable after reading the whole file in. They need to be searchable by both the name of the entry, and it's offset from the beginning of the file. My problem is one of memory usage since there are millions of entries. Currently I am using two separate std::maps to store the data so that either search term can be specified. This leads to double storage of the data which is what I am trying to reduce.
I've used valgrind massif to find that a major part of the memory usage is the double storage of entries.
Note that by using shared pointers for the value payload (thus using the same entry object for both maps), you save the size of a payload. While you pay for two shared pointers, you'll still come out ahead for your specific structure.
(felt like drawing a diagram. The point, though, is that there is only one entry object in memory.)
This technuque good for that cases when insertion is not so often than fetch.
But algoritm is no so trivial, and you need to reassign offset2pos (possible
rebuild) each time you insert one or more elements.
In the answer above You need save per element:
std::string, uint16_t, 2 * Sptr, 4 * Mptr
In the my approuch :
std::string, uint16_t, Sptr, 2 * Mptr
Sptr - is smaprt pointer object internal pointer
Mptr - map binary three node left and right pointer