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.