C++ multimap like container to perform search on a part of a key

Question

I'd like to store data in some kind of key(some bitarray)->values(integers) mapping container. Bitarray can be up to 32bytes large (and probably it could be a constant size).

It could be a standard std::multimap of course.

std::multimap my_map;

But I have to search also for a part of a key (1 or 0 bits on several positions) and do not care about the rest of it. For example:

Insert into map:

• value 1 under the key b"1010001",
• value 2 under the key b"1010001",
• value 3 under the key b"1000001"
• value 4 under the key b"0000001"

Then I should receive values:

• 1, 2, 3 and 4 if I look for a b"0000001",
• 1, 2, and 3 if I look for a b"1000000",
• 1, and 2 if I look for a b"1010001"

It would be also a nice to have an ability for exact matching key-values.

How can I achieve it in the simplest(but still efficient) way in C++ supported by boost? I care about a performance (there could be up to millions of keys).

Answer 1

You would be better off using a prefix tree. You can easily modify the implementation to suit your need of only caring about certain parts of the key. In addition, search time is very fast.

For your example, the tree would have a height of 8 and you would explore the left subtree if the current bit in your key was a 0, and the right subtree if it was a 1. You can modify the implementation to not care about the zeros and return all results by branching (exploring both left and right subtrees) at each point where you are trying to match to a 0 in your search key.