最快的C++插入方法

Question

最快的C++插入方法

c++arraysvector

8

在数组/向量非常大的情况下，有没有一种很快的方式可以在任意位置插入数据？

如果我使用vector::insert，向量会移动我的项后面的所有项，这将需要很长时间。例如，如果向量有10亿个项，并且在向量中间执行此操作，那么向量将移动5亿个项目。

是否有一种有效的方式可以使用C样式/C++数组或向量完成此操作？

- Luka

5

如果这是性能问题，你可能需要考虑使用不同的容器。 - chris

数组有固定大小，因此您实际上无法将元素插入其中。 - juanchopanza

1

在一个向量中有五亿个项目，那确实是有些过分了。除非它们都是某种基本类型，否则你需要相当大的内存才能使其可行。 - cHao

@sehe 他说问题可能是内存。每个元素大小需要大约500MB的RAM。实际上，OP说了1b项，这意味着每个元素大小需要1GB RAM。这绝对不是小事。 - JBentley

当然，这是很多的RAM，但速度比RAM更重要。 - Luka

显示剩余9条评论

2个回答

2

C++向量实际上是带有智能调整大小的数组，如果需要在容器前面插入元素，则需要考虑其他东西，例如链表。但请记住，如果性能对您非常关键，则这样的其他容器通常不会在内存中连续，因此在遍历它们并跳转到内存时通常会遇到内存分页问题。这总是一个权衡。

- naumcho

2

我不建议在这里使用链表。它会增加相当大的开销，可能会使系统变得缓慢（即使在C++11之前，std::list也允许具有O(n)实现的size()...）。 - sehe

2

在进行前插入操作时，我可能会先考虑使用std::deque而不是std::list。 - chris

我现在正在设计这个函数，对于数组我还不确定会做什么，但我相信我只会在随机位置插入大量数据，然后稍后读取它们。这些数据也将会改变。 - Luka

我明白了，这个有简单的方法吗？ - Luka

@Luka：将列表复制到向量很容易。例如，如果您有一个list<int> mylist，则可以使用vector<int> myvector(mylist.begin(), mylist.end());从中创建一个向量。 - Steve Jessop

显示剩余6条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Manu343726 · Accepted Answer

理论上（具体来说是大O符号表示法），链表的插入和删除复杂度为O(1)，而动态数组的复杂度为O(n)，因为擦除/插入需要容器移位。

但这只是理论。计算机不仅仅是理论。在实践中，情况大不相同。

现代计算机的内存采用所谓的“内存层次结构”，即一组按速度排序的不同类型的内存设备：

+---------------+
| CPU registers |   ^
+---------------+   |
|   L1 cache    |   |
|      ...      |   |   Less apacity
|   LN cache    |   |   Faster access
+---------------+   |   More expensive hardware
|      RAM      |   |
+---------------+   
|      HDD      |
+---------------+

如图所示，层次结构是通过内存访问速度来组织的。但请注意，更快的速度意味着更昂贵的硬件，因此这就转化为了许多慢速访问内存和少量快速内存。
因此，提高程序性能的一种方法是将经常使用的数据保存在快速内存中，只有在必要时才去访问慢速内存（例如，程序请求未加载到快速内存中的数据）。

这正是硬件所做的，假设两种行为：

如果请求某个数据，那么可能在将来会请求与其相邻的数据。这被称为引用局部性。例如，考虑我们如何使用数组。
如果请求某个数据，那么它将来可能再次被请求。这被称为时间局部性。同样，反复迭代一个数组也是一个例子。

当然，内存是有限的，因此对于新数据的请求，将会覆盖之前所在的某个层次结构中的数据。

所以，这对于不同容器的性能为什么很重要呢？

还记得链表（std::list 是链表）是如何工作的吗？链表是一系列通过指针连接在一起的分离节点的链。

+---+     +---+             +---+
| 1 | --> | 2 | --> ... --> | N |
+---+     +---+             +---+

另一方面，动态数组（std::vector 是动态数组）是连续的内存块：

+---+---+-----+---+
| 1 | 2 | ... | N |
+---+---+-----+---+

正如我之前所说的，理论上，链表的插入/删除具有O（1）的复杂度，因为“只是改变指针”。但是请考虑一下如何访问内存来完成这个过程。你有没有注意到这个过程没有遵守空间局部性规则？因此会有很多缺失（缓存缺失），也就是请求新的内存超出快速内存范围，从而导致性能下降。

实际上，即使理论上说遍历链表的复杂度为O（n），在实践中，由于缓存缺失而连续产生性能损失。

现在考虑一下动态数组的工作原理：确实，插入/删除具有O（n）的复杂度，因为你必须将一个位置向数组的一侧移动一个位置，以便为新元素留出空隙，或者如果你要删除，则消除该空隙。

但是请记住，数组是一块连续的内存块，因此如果你正在使用它，那么该数组可能完全（或几乎部分）加载到快速内存中（空间局部性），因此移位过程非常快。

因此，可以看出，在现代架构中，动态数组比链表快得多。

一般而言，std::vector 相对于 std::list 有许多优势：

它更加缓存友好。正如我们所讨论的，std::list 不是缓存友好的，而“缓存友好性”在现代计算机性能方面非常重要。这导致了快速的插入/删除、快速的随机访问和快速的复制。
链表每次插入/删除都会进行一次动态内存操作。调用 malloc()/free()（即调用操作系统以获取/释放堆内存）需要很长时间。另一方面，动态数组只在平均情况下进行 O(logn) 次分配/释放操作。

但这还不是全部：在一些情况下，必须优先选择 std::list，即元素的复制/移动成本非常高的情况。std::vector 的性能取决于缓存中执行的廉价移位过程，但如果向量的元素具有某些昂贵的复制/移动语义，则根本没有任何好处，列表的性能比向量更好。

阅读这篇文章以获取更多关于该主题的信息。