C++ vector 和列表插入

Question

谁能知道为什么将元素插入列表中间会更快而不是将一个元素插入 vector 的中间？

我更喜欢使用 vector ，但我被告知如果可以的话使用列表。任何人都可以解释为什么？是否总是建议使用列表而不是 vector ？

Answer 1

如果我逐字回答这个问题，找到数组 (std::vector) 的中间是一个简单的操作，您将长度除以二，然后向上或向下舍入以获得索引。查找双向链表 (std::list) 的中间位置需要遍历所有元素。即使你知道它的大小，你仍然需要走过一半的元素。因此 std::vector 比 std::list 快，换句话说，一个是 O(1) 而另一个是 O(n)。

在已知位置插入需要打乱数组的相邻元素，并且只需链接另一个节点以获得双向链表，正如其他人在此处解释的那样。因此，复杂度为 O(1) 的 std::list 比复杂度为 O(n) 的 std::vector 更快。

总之，为了插入到正中间，我们有 O(1) + O(n) 的数组和 O(n) + O(1) 的双向链表，使得在中间插入 O(n ) 对于两种容器类型。不过，所有这些都忽略了 CPU 缓存和分配器速度之类的东西，它只是比较了“简单”操作的数量。总之，您需要弄清楚您是如何使用容器的。如果您真的经常在随机位置插入/删除，std::list 可能会更好。如果您很少这样做，然后只读取容器，那么 std::vector 可能会更好。如果你只有十个元素，那么所有的 O(x) 都可能毫无值(value)，你应该选择你最喜欢的那个。