在数组/向量非常大的情况下,有没有一种很快的方式可以在任意位置插入数据?
如果我使用vector::insert,向量会移动我的项后面的所有项,这将需要很长时间。例如,如果向量有10亿个项,并且在向量中间执行此操作,那么向量将移动5亿个项目。
是否有一种有效的方式可以使用C样式/C++数组或向量完成此操作?
在数组/向量非常大的情况下,有没有一种很快的方式可以在任意位置插入数据?
如果我使用vector::insert,向量会移动我的项后面的所有项,这将需要很长时间。例如,如果向量有10亿个项,并且在向量中间执行此操作,那么向量将移动5亿个项目。
是否有一种有效的方式可以使用C样式/C++数组或向量完成此操作?
+---------------+
| CPU registers | ^
+---------------+ |
| L1 cache | |
| ... | | Less apacity
| LN cache | | Faster access
+---------------+ | More expensive hardware
| RAM | |
+---------------+
| HDD |
+---------------+
如图所示,层次结构是通过内存访问速度来组织的。但请注意,更快的速度意味着更昂贵的硬件,因此这就转化为了许多慢速访问内存和少量快速内存。
因此,提高程序性能的一种方法是将经常使用的数据保存在快速内存中,只有在必要时才去访问慢速内存(例如,程序请求未加载到快速内存中的数据)。
这正是硬件所做的,假设两种行为:
当然,内存是有限的,因此对于新数据的请求,将会覆盖之前所在的某个层次结构中的数据。
所以,这对于不同容器的性能为什么很重要呢?+---+ +---+ +---+
| 1 | --> | 2 | --> ... --> | N |
+---+ +---+ +---+
std::vector
是动态数组)是连续的内存块:+---+---+-----+---+
| 1 | 2 | ... | N |
+---+---+-----+---+
一般而言,std::vector
相对于 std::list
有许多优势:
std::list
不是缓存友好的,而“缓存友好性”在现代计算机性能方面非常重要。这导致了快速的插入/删除、快速的随机访问和快速的复制。malloc()
/free()
(即调用操作系统以获取/释放堆内存)需要很长时间。另一方面,动态数组只在平均情况下进行 O(logn) 次分配/释放操作。但这还不是全部:在一些情况下,必须优先选择 std::list
,即元素的复制/移动成本非常高的情况。std::vector
的性能取决于缓存中执行的廉价移位过程,但如果向量的元素具有某些昂贵的复制/移动语义,则根本没有任何好处,列表的性能比向量更好。
阅读 这篇文章 以获取更多关于该主题的信息。
C++向量实际上是带有智能调整大小的数组,如果需要在容器前面插入元素,则需要考虑其他东西,例如链表。但请记住,如果性能对您非常关键,则这样的其他容器通常不会在内存中连续,因此在遍历它们并跳转到内存时通常会遇到内存分页问题。这总是一个权衡。
std::list
也允许具有O(n)实现的size()
...)。 - sehestd::deque
而不是std::list
。 - chrislist<int> mylist
,则可以使用vector<int> myvector(mylist.begin(), mylist.end());
从中创建一个向量。 - Steve Jessop