c++ - std::vector 或 std::list 用于 std::unordered_map 存储桶?

标签 c++ list vector unordered-map

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

std::vector

  • 快速迭代元素
  • 如果需要将所有元素复制到新内存中而耗尽容量,则情况不佳

std::列表

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

最佳答案

即使不知道您的确切使用模式和工作负载,我也会说 std::vector 更好。大多数时候都是如此,我将在下面尝试解释原因。

  1. 大多数时候,您对哈希表进行的查找次数比插入次数多得多。查找需要对存储桶进行迭代,插入需要添加元素并可能调整大小。因此,针对更常见的用例进行优化更有意义。

  2. 每个插入内部都需要进行查找,因此您至少将进行与插入一样多的查找;通常更多。

  3. 大多数时候,每个存储桶的平均键数很少。这意味着使用小 vector 与小列表。调整小 vector 的大小(涉及元素的复制)会很快。

  4. vector “调整大小”通常不会经常发生,因此您不必非理性地害怕它。 (尽管您应该注意,当 vector 很小时,调整大小确实会更频繁地发生。对于我所知道的所有实现都是如此,但纠正/规避也很简单。)

  5. vector 上的迭代比列表上的迭代快很多很多

  6. 甚至调整 vector 大小和复制(或移动) vector 也可以与向列表中添加元素一样快(或几乎一样快)。

  7. 通过数据类型中适当的“移动”支持,调整 vector 大小的开销会变得更少。

  8. 您可以使用 vector 预先分配一定数量的元素,并且几乎完全消除存储桶中的所有大小调整。例如,如果您知道 99% 的存储桶将包含 3 个或更少的键,则可以为每个 vector 保留 3 或 4 个元素,并且忘记调整大小(几乎)。

  9. vector (特别是当它们的元素类型很小时)比链表更节省空间。 std::list 需要为每个元素保留两个额外的指针,这可能是一个巨大的开销(8-16 字节的元素为 50%-200%,具体取决于您是 32 位还是 64 位) .)

  10. 由于 vector 较小且在内存中连续,因此 vector 通常是一种更快、更好的数据结构。

  11. 最终,您必须在自己的代码库中并根据自己的工作负载和使用模式进行自己的测量和基准测试。如果没有这些的完整信息,没有人可以给你一个明确的答案。因此,如果您的元素非常大、不可移动的对象,并且您主要进行插入/删除和很少的查找,那么请继续使用链表。否则,请使用 vector 。

您可以看看this benchmark ,比较 vector 、列表和双端队列。它可能会进一步帮助您决定使用 vector !

关于c++ - std::vector 或 std::list 用于 std::unordered_map 存储桶?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22429719/

相关文章:

c++相当于列表的python追加方法

c++ - "result type must be constructible from value type of input range"创建 std::vector 时

C++ 在 std::vector 中搜索

c++ - 迷宫功能在检测已删除的墙壁方面不起作用

c++ - 读取表达式

python - 用于过滤与模式匹配的字符串列表的正则表达式

python - 如果 k 是空列表,k[ :0] means, 会做什么

java - java中的 vector 只包含对象?

c++ - OpenCV: ‘AlgorithmInfo’ 在构建 opencv_contrib 时未命名类型

c++ - 使用正则表达式查找多个字符串的第一个实例