C++ STL列表与设置

Question

这两个中的哪一个对于随机插入和删除更快？我猜列表,将值作为关键字和套装似乎也很有吸引力.迭代整个容器的性能是否相似？

谢谢!

Answer 1

名单

1. 搜索(线性时间).
2. 插入,删除,移动(需要恒定时间).
3. 可以订购元素.
4. 可以对元素进行排序.
5. 元素可能重复.

组

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

Answer 2

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

考虑一下找到插入/删除点以便做出选择的努力.

Answer 3

首先考虑语义,然后考虑性能.

如果你有一组整数,并且你插入整数6,8,13,8,20,6和50,你最终会得到一个包含以下五个元素的集合: { 6, 8, 13, 20, 50 }.

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

所以你想要什么？将容器的速度与这种不同的语义进行比较是没有意义的.