c++ - 哪个 STL 容器最能满足这些需求？

Question

我想要一些关于哪种 STL 容器最能满足以下需求的建议:

1. 该系列的生命周期相对较短。
2. 该集合包含指针。
3. 元素只在末尾添加。必须保持元素的顺序。
4. 元素的数量未知，可能从数百到数百万不等。只有在添加最后一个元素后才能知道该数字。
5. 我可能会多次迭代这些元素。
6. 添加所有元素后，我需要根据指针所指的对象对集合进行排序。
7. 排序后，我可能会多次迭代这些元素。
8. 之后，集合将被销毁。

不需要线程安全。

以下是我的想法:
list:需要为每个元素单独分配。更昂贵的遍历。
vector:需要随着集合的增长而重新分配。最佳排序和遍历性能。
deque:分配比 list 少，重新分配比 vector 少。我不知道关于排序的行为。

我目前正在使用列表。流程图在In which scenario do I use a particular STL container?带我到双端队列。

我对 STL 的了解很旧；我不知道自 2003 年以来添加的容器类型，所以也许有一些我从未听说过的非常适合的容器类型。

Answer 1

std::vector<T*>将根据讨论的要点成为获胜者。

不要害怕需要调整大小——只是 reserve()一个合理的数量(如果您的许多收藏都在附近，就说 500 个)。

vector<T*> 的排序性能也会很好。

每个 T 的分配和释放会很重要。注意这一点。例如，您可能想要分配数千个 T s 一次，以减少内存分配开销(并使其在最后释放所有内容更快)。这被称为“竞技场”或“游泳池”。您或许可以将 32 位相对指针存储到 arena 中，从而节省一半的指针存储空间。

当然，如果T很小，您可以考虑按值而不是指针存储它。