我正在寻找一个像 std::multimap 一样工作的 STL 容器，但对随机第 n 个元素具有恒定的访问时间。我需要这个，因为出于多种原因，我在内存中有这样的结构 std::multimap ，但是存储在其中的项目必须在列表框中呈现给用户。由于数据量巨大，我使用带有虚拟项目的列表框（即列表控件轮询 X 行的值）。
作为一种解决方法，我目前正在使用额外的 std::vector 将“索引”存储到 std::map 中，并像这样填充它：
std::vector<MMap::data_type&> vec;
for (MMap::iterator it = mmap.begin(); it != mmap.end(); ++it)
vec.push_back((*it).second);
但这不是非常优雅的解决方案。
有这样的容器吗？
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?
发布评论
评论（4）
你需要的是：
Boost 多索引
What you need is:
Boost Multi-Index
该列表中有多少项，这些项的类型是什么，以及您需要在其中插入或删除的频率如何？根据这一点，您可能可以使用排序的
std::vector> 并使用std::binary_search带有仅比较键的搜索谓词。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 usingstd::binary_searchwith a search predicate comparing only the keys.除了要求之外，从您的评论看来您还计划插入/删除项目。我必须承认，2000万似乎是很多。
现在，我理解了轮询的想法，但是您是否考虑过类似
unordered_multimap的东西？您可以在 O(1) 中轮询某个键，而不是轮询某个位置，但根据键类型，开销会稍大一些。主要优点是不必处理保持 2 个包含同步的问题。当然如果你想对内容进行排序就不行了。
因此，如果您希望内容排序并快速（不是 O(1)）访问随机位置，您可以考虑 B+Tree 或 Radix Tree。他们的想法是将项目保存在连续的内存区域中，一次保存数百个。
这只是我的头顶想法。如果您想要一个内置的解决方案，请考虑自动填充的答案:)
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 :)
尝试 hash_multimap。哈希提供大致恒定的时间。 Hash_multimap 是 Visual Studio 中的一个扩展，我相当确定 GCC 也提供了类似的扩展。如果你绝望的话，Boost 里有一些哈希的东西。
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.