是向量还是std::unordered_map：：列表？

Question

当两个键映射到std::ordered_map<T>中的同一个桶时，首选的数据结构是什么？我不确定是否最好使用std::vector<T> (在达到容量时需要复制所有元素，但需要快速迭代)还是使用易于添加新元素但迭代速度较慢的std::list<T>？

std：：向量

• 快速迭代元素
• 如果由于需要将所有元素复制到新内存中的容量不足，则会导致错误。

std:清单

• 快速添加/删除节点
• 不利于作为不连续内存中的元素进行迭代。

Answer 1

即使不知道确切的使用模式和工作负载，我还是认为std::vector更好。这在大多数情况下都是正确的，我将尝试解释为什么在下面。

1. 大多数情况下，对哈希表的查找要比插入多得多。查找需要对桶进行迭代，而插入则需要添加元素并可能调整大小。因此，对更常见的用例进行优化就更有意义了。
2. 每个insert内部都需要进行查找，因此您将至少拥有与insert相同的查找；通常情况下更多。
3. 大多数情况下，每个桶的平均键数都很低。这转化为使用一个小向量与一个小列表。调整一个小矢量的大小(这涉及元素的复制)将是快速的。
4. 这个向量“调整大小”通常不会经常发生，所以你不必非理性地害怕它。(尽管您应该注意到，当向量很小时，调整大小的情况确实会更频繁。)对于我所知道的所有实现来说都是这样，但是纠正/规避也是微不足道的。)
5. 向量上的迭代比列表上的迭代要快得多。很多。
6. 即使是调整大小和复制(或移动)向量，也可能与将元素添加到列表中一样快(或几乎一样快)。
7. 如果数据类型中有了适当的“移动”支持，调整矢量的大小就会减少开销。
8. 您可以使用向量预分配某些元素，并且几乎完全消除桶中的所有调整大小。例如，如果您知道99%的桶将包含3个或更少的键，则可以为每个向量保留3个或4个元素，而忘记调整大小(几乎)。
9. 向量(特别是当它们的元素类型较小时)比链表更节省空间。一个std::list需要为每个元素保留两个额外的指针，这可能是一个巨大的开销( 8-16字节的元素是50%-200%，这取决于您是32位还是64位)。
10. 由于向量的体积小，内存连续，因此通常是一种更快、更好的数据结构。
11. 最终，您必须在自己的代码库中并使用自己的工作负载和使用模式进行自己的测量和基准测试。没有人能给你一个明确的答案，没有完整的信息。因此，如果您的元素是非常大的、不可移动的对象，并且主要是插入/删除和很少查找，那么继续使用链接列表。否则，使用向量。

您可以查看这个基准，比较向量、列表和deque。它可能会进一步帮助您决定使用向量！