CODEWITHSUNDEEP
c++stdvector
Milan Babuškov
Milan Babuškov

Reputation: 61098

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

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?

Upvotes: 3

Views: 494

Answers (4)

sbi
sbi

Reputation: 224039

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.

Upvotes: 3

Puppy
Puppy

Reputation: 146910

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.

Upvotes: 0

Matthieu M.
Matthieu M.

Reputation: 299740

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 :)

Upvotes: 2

James
James

Reputation: 25513

What you need is: Boost Multi-Index

Upvotes: 5

Related Questions