我们在multiset中有哪些更好的功能不在向量中？

Question

为什么我们应该使用"多组"(因为我们知道"多组"可以保持重复键)

为什么我们不应该使用向量？

我们在向量中没有"多组"中有什么好的功能吗？(或其他容器,如矢量)

你知道"多套装"的特殊用法吗？

Answer 1

(从评论中移动/扩展)

我们在multiset中有哪些更好的功能不在向量中？

关键特性是快速(O(log N))查找"等效"(根据比较器)元素,以及根据比较器的隐式排序(插入时具有O(log N)成本)).

(这加上常用set功能,例如O(1)删除(在O(log N)搜索之后)和从未失效的引用)

multiset是一个相当"利基"的容器; 在编写C++ 10多年后,我认为我从未使用它(或者看到它被使用,FWIW).最有可能的是,它的存在很大程度上归功于map/ set<=> multimap/ multisetsymmetry.

set通常被认为是"不允许重复元素的容器",因此拥有一个允许重复的集合显然根本没有任何意义.然而,实际的观点set是允许根据某些标准快速(O(log n))查找对象,这关键地可能不考虑对象的完整内容.

让我们退后一步; 这有助于理解这?map只是?set伪装¹.特别是,您可以将a std::?map<K,V>视为a std::?set<pair<const K,V>,KeyComp>,哪个KeyComp是仅考虑first对²的(=键)部分的比较器- 顺便说一下,它恰好是什么std::?map::value_compare ; 你也会注意到它的类型std::?map::value_type确实如此std::pair<const K, V>.

因此,?map对于?set您希望通过某些尚未"在值本身内部"的键来索引值的常见情况,本质上是一种便利.

相反,密钥已经存储在值中 - 这通常是当我们通过某些属性索引现有数据时会发生的情况 - ?set可以使用自定义比较器,从而避免密钥的密钥复制. a ?map.

让我们考虑一个虚构的图书数据库; 你有一个大std::deque<std::unique_ptr<Book>>一个包含所有书籍对象,并要对其进行索引的author,并通过title快速查找.

在这种情况下,您可以multiset<Book *, CustomComp>为要索引的每个字段使用a ; 自定义比较器将实现<仅考虑指向元素的特定字段的运算符.

添加新书时,您只需将其添加deque到所有索引中; 删除书籍时,您必须将其从deque索引中删除.编辑需要先从索引中删除它,应用更改然后重新添加它(直接修改可能导致multiset实例的状态不一致,因为您可能正在改变存储对象之间的排序关系"背后" ).

这里完全没有一个允许重复元素的集合:它们只根据比较器重复,它只考虑一个字段; 拥有同一作者的多本书或具有相同标题的不同书籍是完全正常的.这里的要点不是"不允许重复",而是"通过某些键快速查找",就像我们使用的一样multimap,但不必在索引中保留密钥的额外副本.

笔记

1. 当我写作?set或?map我正在谈论"常规"和"多"变体时.值得注意的是,讨论的核心主要以相同的方式应用于unordered对应方,使用哈希函数更改比较器.
2. 当然,在进行查找时你必须提供一个伪second参数,这就是为什么使用a map更方便.