我正在寻找一个像 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);
但这不是很优雅的解决方案。
有这样的容器吗？
你需要的是： Boost Multi-Index
该列表中有多少项目，项目是什么类型，以及您必须多久在其中插入或删除一次？根据这一点，您可以使用 sortedstd::vector<std::pair<key,value>>并使用std::binary_search仅比较键的搜索谓词。
除了要求之外，您的评论似乎还计划插入/删除项目。我必须承认 2000 万似乎相当多。
现在，我理解了轮询的想法，但你有没有考虑过类似的事情unordered_multimap？您可以在 O(1) 中轮询一个键，而不是在一个位置轮询，但根据键类型的不同，开销会稍大一些。
主要优点是不必处理保持 2 个包含同步的问题。当然，如果您希望对内容进行排序，则它不起作用。
因此，如果您希望对内容进行排序并快速（不是 O(1)）访问随机位置，您可以考虑 B+Tree 或 Radix Tree。他们的想法是将项目保存在连续的内存区域中，一次几百个。
这只是我的想法。如果您想要一个烘焙解决方案，请考虑自动填充的答案:)
试试 hash_multimap。哈希提供大致恒定的时间。Hash_multimap 是 Visual Studio 中的一个扩展，我很确定 GCC 也提供了类似的扩展。如果你很绝望，Boost 中有一些东西。