C++中列表和多集的区别

Question

在 C++ 中：

• 列表是可以按顺序包含非唯一值的集合

• 多重集是一个可以按顺序包含非唯一元素的集合

那么两者的具体区别是什么呢？为什么我会在另一个上使用？

我曾尝试在网上查找此信息，但大多数参考资料（例如 cplusplus.com）以不同的方式谈论这两个容器，因此差异并不明显。

Answer 1

从多集：

std::multiset是一个关联容器，其中包含一组已排序 的对象

搜索、插入和删除操作具有对数复杂性。

从列表：

std::list是一个容器，支持从容器中的任何地方进行恒定时间插入和移除元素

不支持快速随机访问

因此，如果您想要更快的搜索，请使用multiset。

为了更快地插入和移除：使用list.

Answer 2

最大的区别是std::list链表，std::multiset而是树结构（通常是 RB 树）。这意味着 a 中的元素访问std::listhas O(N)access 而 a std::multisethas O(logN)。

这也意味着一个迭代std::multiset从begin()到end()会给你整理数据，而迭代一个std::list会给你的数据被插入的顺序。