代码之家 › 专栏 › 技术社区 › Milan BabuÅ¡kov

std::multimap和std::vector之间的交叉?

stdvector c++

Milan BabuÅ¡kov · 技术社区 · 14 年前

我正在寻找一个STL容器,它的工作方式类似于std::multimap,但对随机的n-th元素具有恒定的访问时间。我需要这个,因为我在内存中有这样的结构,出于许多原因,它是std::multimap,但是存储在其中的项必须在列表框中呈现给用户。由于数据量很大,所以我将列表框与虚拟项一起使用(即,对第x行的值进行列表控制轮询)。

作为解决方法,我目前使用附加的std::vector将“indexes”存储到std::map中,并按如下方式填充:

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

但这不是一个很好的解决方案。

有这样的集装箱吗?

4 回复 | 直到 14 年前

James 14 年前

你需要的是: Boost Multi-Index

sbi 14 年前

该列表中有多少项、项的类型以及在其中插入或删除的频率?根据这一点,您可以使用 std::vector<std::pair<key,value>> 并使用 std::binary_search 搜索谓词只比较键。

Matthieu M. 14 年前

除要求外,从您的评论中似乎还计划插入/删除项目。我必须承认,2000万似乎相当多。

现在,我明白了投票的概念,但是你有没有考虑过 unordered_multimap ?与在某个位置进行轮询不同,您可以在O(1)中的某个键进行轮询,但根据键类型的不同,开销稍微大一些。

主要的优势是不必处理保持2包含同步。当然,如果您希望对内容进行排序,它就不起作用。

因此,如果您希望内容排序加上快速(而不是O(1))访问随机位置,可以考虑使用B+树或基树。他们的想法是将项目保持在连续的内存区域中,一次几百个。

那只是我的头顶。如果你想要一个成熟的解决方案,考虑自动选择答案:)

Puppy 14 年前

尝试hash_multimap。哈希提供大致恒定的时间。hash_multimap是Visual Studio中的一个扩展,我相当肯定gcc也提供了类似的扩展。如果你不顾一切的话,会有一些东西在增加。

推荐文章

patrick · 从boost::绑定1和2占位符运行make失败。。。?

1 年前

rookie · 检查函数模板的所有参数包参数是否属于int

1 年前

ivaigult · -W转换和隐式字符串到布尔类型转换

1 年前

David Bien · declval<_Xp(&)()>()()-这在下面的上下文中意味着什么?

1 年前

khallad sayed · 在%上,C++表达式必须具有整型或无范围枚举类型

1 年前

rainer · 后台插入程序的初始化

1 年前

Community wiki · 以理智、安全和高效的方式复制文件

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Prakritish Ghosh · 现在显示正确输出的函数中的Infix到Postfix错误[重复]

1 年前

Ma Joonyoung · 粗粒度和细粒度链表的时间比较

1 年前