c++ - 适用于（仅）插入和迭代的标准容器

Question

如果我只想插入很多（10.000-100.000）小（int、floats 和 doubles）项目然后迭代所有这些项目（顺序不重要），那么使用哪个 std 容器？（注：项目数量一开始是未知的）

我注意到 unsorted_set、list 和 forward_list 的插入时间为 O(1)，迭代时间为 O(n)。还有其他的也有这种复杂性吗？其中哪一个是最快的？（如果内存使用存在显着差异，我也会有兴趣了解它们。

（我只对标准容器感兴趣，而不是 Boost 或其他库的容器）

Answer 1

我的赌注是std::vector调用std::vector::reserve().

Answer 2

在我看来，这取决于你想对容器中的元素做什么。

• 如果要在某些位置插入元素，那么 list 是最快的，因为数组和向量必须将插入位置之后的所有项目都移动，向前一步。
• 另一方面，如果您想访问某个位置的项目，那么数组和向量会更快。

此外，除了这些之外，还有容器适配器以及队列、堆栈、priority_queue 等。

同样，这完全取决于您的实现以及您想要从元素容器中获得什么。

Answer 3

您问题中的所有类都具有您想要的最佳复杂性，但 std::vector 可能更快，特别是如果您知道要插入大约多少个元素，即您有一个可用的上限。

我想性能可能会因您的编译器、编译器版本和要插入的元素数量而异。很抱歉没有提供更具体的帮助。

Answer 4

向量可能是一个不错的选择。在内存消耗方面与数组相同。O(1) 插入（如果您在末尾插入）和 O(n) 迭代。它是最简单的容器，如果删除或随机插入不在您的列表中，它是一个不错的选择。