A cross between std::multimap and std::vector?

Question

I'm looking for a STL container that works like std::multimap, but has constant access time to random n-th element. I need this because I have such structure in memory that is std::multimap for many reasons, but items stored in it have to be presented to the user in a listbox. Since amount of data is huge, I'm using list box with virtual items (i.e. list control polls for value at line X).

As a workaround I'm currently using additional std::vector to store "indexes" into std::map, and I fill it like this:

std::vector<MMap::data_type&> vec;
for (MMap::iterator it = mmap.begin(); it != mmap.end(); ++it)
    vec.push_back((*it).second);

But this is not very elegant solution.

Is there some such containter?

Answer 1

What you need is: Boost Multi-Index

Answer 2

How many items are in that list, what type are the items of, and how often do you have to insert or delete in the middle of it? Depending on this, you might be fine with using a sorted std::vector<std::pair<key,value>> and using std::binary_search with a search predicate comparing only the keys.

Answer 3

On top of the requirements, it seems from your comments that you also plan to insert / delete items. I must admit 20 millions seems quite a lot.

Now, I understand the idea of polling, but have you consider something like unordered_multimap ? Instead of polling at a position, you can poll at a key in O(1) though with a slightly bigger overhead depending on the key type.

The main advantage is not to have to deal with keeping 2 contains in sync. Of course it does not work if you want the content sorted.

Thus, if you want the content sorted plus fast (not O(1)) access to a random position, you could consider B+Tree or Radix Tree. Their idea is to keep items in contiguous zones of memory, a few hundreds at a time.

That's just of the top of my head. Consider autopopulated answer's if you want a baked in solution :)

Answer 4

Try hash_multimap. Hashes offer roughly constant time. Hash_multimap is an extension in Visual Studio, and I'm fairly sure that GCC offers a similar extension too. There's hash somethings in Boost if you're desperate.