C++ STL 列表与集合

C++ STL list vs set

提问by user240137

what of those two is faster for random insertions and deletions? I guess list, having the values as the keys as it is with sets seems to be attractive too though. Is performance similar for iterating over the whole container?

对于随机插入和删除，这两者中的哪一个更快？我想列表中，将值作为键与集合一样似乎也很有吸引力。迭代整个容器的性能是否相似？

Thanks!

谢谢！

回答by cpx

List

列表

1. Searching (linear time).
2. Inserting, deleting, moving (takes constant time).
3. Elements may be ordered.
4. Elements may be sorted.
5. Elements may be duplicate.

1. 搜索（线性时间）。
2. 插入、删除、移动（需要恒定时间）。
3. 元素可以被排序。
4. 元素可以被排序。
5. 元素可能是重复的。

Set

放

1. Searching (logarithmic in size).
2. Insert and delete (logarithimic in general).
3. Elements are un-ordered.
4. Elements are always sorted from lower to higher.
5. Elements are unique.

1. 搜索（大小为对数）。
2. 插入和删除（一般为对数）。
3. 元素是无序的。
4. 元素总是从低到高排序。
5. 元素是独一无二的。

回答by Hans Passant

std::list is O(1) for inserts and deletions. But you may well need O(n) to find the insertion or deletion point. std::set is O(log(n)) for inserts and deletions, it is usually implemented as a red-black tree.

std::list 对于插入和删除是 O(1)。但是您可能需要 O(n) 才能找到插入或删除点。std::set 是 O(log(n)) 插入和删除，它通常实现为红黑树。

Consider the effort to find the insert/delete point to make your choice.

考虑寻找插入/删除点以做出选择的努力。

回答by Daniel Daranas

First think about semantics, then about performance.

首先考虑语义，然后考虑性能。

If you have a set of integers, and you insert to it the integers 6, 8, 13, 8, 20, 6 and 50, you'll end up with a set containing the following five elements: { 6, 8, 13, 20, 50 }.

如果您有一组整数，并向其中插入整数 6、8、13、8、20、6 和 50，您将得到一个包含以下五个元素的集合： { 6, 8, 13, 20, 50 }.

If you do that with a list, you'll end up with a list containing the following seven elements: { 6, 8, 13, 8, 20, 6, 50 }.

如果你用一个列表来做这件事，你最终会得到一个包含以下七个元素的列表：{ 6, 8, 13, 8, 20, 6, 50 }.

So, what do you want? It doesn't make sense to compare the speed of containers with such different semantics.

所以你想要什么？用如此不同的语义来比较容器的速度是没有意义的。

回答by Dom

In an std::list, the insertion and deletion itself take a time in O(1), which means very fast, and above all means at a speed that does not depend on the number of elements in the list.

在 std::list 中，插入和删除本身需要 O(1) 的时间，这意味着非常快，最重要的是，它的速度不依赖于列表中的元素数量。

In an std::set, the insertion and deletion take time in O(log(N)), which means a bit slower if a lot of elements are contained in the set. The N in the expression O(log(N)) means the number of elements. Grosso modo, it means that the time taken by the operation is kind of proportional to the logarithm (the base does not matter here, since it is equivalent to multiplying by a constant, which is ignored in theoretical algorithm analysis) of the number of elements in the set.

在 std::set 中，插入和删除需要 O(log(N)) 的时间，这意味着如果 set 中包含很多元素，速度会慢一点。表达式 O(log(N)) 中的 N 表示元素的数量。Grosso modo，这意味着操作所花费的时间与元素数量的对数成正比（这里的底数无关紧要，因为它相当于乘以一个常数，在理论算法分析中被忽略）在集合中。

But it is vital to take into account the time taken for finding the element to remove. If you must search the container for the element to remove, which is most probably the case, then the std::list will take quite a long time for this search, which will be in O(N) (which means not fast, because the time is directly proportional to the number of elements, not the logarithm of it), while the std::set will take a time in O(log N) for the search.

但重要的是要考虑找到要删除的元素所花费的时间。如果您必须在容器中搜索要删除的元素（这很可能是这种情况），那么 std::list 将花费相当长的时间进行此搜索，这将是 O(N)（这意味着不快，因为时间与元素的数量成正比，而不是它的对数），而 std::set 将花费 O(log N) 的时间进行搜索。

Also note that those theoretical analyses become absolutely invalid for containers with very few elements, in which case the multiplying constants they hide become more important than the time function family it focuses on.

还要注意，对于元素很少的容器，这些理论分析变得绝对无效，在这种情况下，它们隐藏的乘法常数变得比它关注的时间函数族更重要。

To make it short: std::list => Slower for searching the element to delete; faster to delete it. std::set => Faster for searching the element to delete; less fast to delete it.

简而言之：std::list => 搜索要删除的元素较慢；更快地删除它。std::set => 更快地搜索要删除的元素；删除它的速度不快。

But for the whole operation, and for big number of elements, the std::set is better.

但是对于整个操作以及大量元素， std::set 更好。

You should also consider using hash tables. Good implementions of those are available in Boost, Qt, or C++0x. They do all these operations in time tending towards O(1) (which mean very very fast).

您还应该考虑使用哈希表。Boost、Qt 或 C++0x 中提供了这些的良好实现。他们及时完成所有这些操作，趋向于 O(1)（这意味着非常非常快）。

回答by Manuel

If you care about speed then you should probably use std::vector. std::listperforms one heap allocation every time an element is inserted and that's usually a bottleneck.

如果您关心速度，那么您可能应该使用std::vector. std::list每次插入元素时执行一次堆分配，这通常是一个瓶颈。

An exception is when individual items are very expensive to copy, or when you have an awful lot of them. In those cases a list is likely to perform better as it doesn't have to move items around when it's resized. A std::dequeis also a good option here, but you'll need to profile your application in order to decide between the two.

一个例外是当单个项目的复制成本非常高时，或者当您拥有大量项目时。在这些情况下，列表可能会表现得更好，因为它在调整大小时不必移动项目。Astd::deque在这里也是一个不错的选择，但您需要分析您的应用程序以便在两者之间做出决定。

Finally, use std::setonly if you need to keep your items sorted (or if you don't want repeated items). Otherwise it will be significantly slower than a list or vector.

最后，std::set仅当您需要对项目进行排序（或者如果您不想要重复的项目）时才使用。否则它会比列表或向量慢得多。

回答by Don Reba

You should measure performance yourself with realistic usage on realistic data. Check both typical and worst case performance.

您应该通过对真实数据的实际使用来衡量自己的性能。检查典型和最坏情况下的性能。

Although std::vector has O(N) time complexity for random insertion, std::set O(log(N)) and std::list O(1), std::vector performs best in many cases. Only if performance is not important enough to spend time measuring, go by the big-O complexity.

尽管 std::vector 对于随机插入、std::set O(log(N)) 和 std::list O(1) 的时间复杂度为 O(N)，但 std::vector 在许多情况下表现最佳。仅当性能不够重要而无法花时间进行测量时，才采用大 O 复杂度。

"If you're not measuring you're not engineering" (Rico Mariani)

“如果你不测量，你就不是工程”（里科·马里亚尼）