我的问题是关于vector::push_back的效果，我知道它在向量的末尾添加了一个元素，但是在底层发生了什么?
IIRC内存对象是以顺序的方式分配的，所以我的问题是vector::push_back是否只是在向量之后立即分配更多的内存，如果是这样，如果在该位置没有足够的空闲内存会发生什么?或者在"结束"中添加一个指针，使向量"跳"到它继续的位置?或者只是通过将其复制到另一个有足够空间的位置来重新分配，而旧的副本将被丢弃?或者是别的什么?
如果已经分配了足够的空间，则从现有的实参复制构造对象。当没有足够的内存时，向量将按照某种几何级数增长它的内部数据库缓冲区(每次新的大小将是k*old_size与k > 1 [1])，所有存在于原始缓冲区中的对象将被移动到到新的缓冲区。操作完成后，旧的缓冲区将被释放到系统中。
在前面的句子中，move不用于技术意义上的move-constructor/move-assignment，它们可以是moved或 copy 或任何等价的操作。
[1]增加一个因子k > 1确保push_back的平摊代价是常数。实际的常数不同的实现到另一个(Dinkumware使用1.5,gcc使用2)。摊余成本意味着即使时常push_back将非常昂贵(O(N)向量的大小),这种情况下很少发生,所有操作的成本在整个组插入线性插入的数量,因此每个插入平均固定成本)
当向量空间,它将使用它的分配器来保留更多的空间。
这是由分配器决定如何实现的。
然而，向量决定保留多少空间:标准保证向量容量至少以1.51的几何倍数增长(见注释)，从而防止由于重复的"小"分配而导致的糟糕性能。
关于元素的物理移动/复制:
- c++11兼容的实现将移动元素，如果它们支持移动赋值和构造
- 我知道的大多数实现(尤其是g++)只会对POD类型使用std::copy;POD类型的算法专门化确保它编译成(本质上)内存操作。这反过来又被编译成系统上最快的CPU指令(例如SSE2指令)
1我试图从n3242标准草案文档中找到参考引用，但此时我无法找到它
向量保证所有元素在内存中是连续的。
在内部，你可以把它定义为三个指针(或像指针一样的东西):
start: Points at the beginning of the allocated block.
final: Points one past the last element in the vector.
If the vector is empty then start == final
capacity: Points one past the end of allocated memory.
If final == capacity there is no room left.
当你推回。
- 如果final小于capacity:
- 新元素被复制到final 所指向的位置。
- final递增到下一个位置。
- 如果final与capacity相同，则vector已满
- 必须分配新内存。
- 编译器将分配
X*(capacity - start)*sizeof(t)字节。 - ，其中X通常是1.5到2之间的值。
- 然后将所有的值从旧内存缓冲区复制到新的内存缓冲区。
- 新值被添加到缓冲区
- 传输开始/结束/容量指针。
- 释放旧的缓冲区
当vector用完空间时，它被重新分配，所有的元素被复制到新的数组。旧数组将被销毁。
为了避免过多的分配，并使push_back()的平均时间保持在O(1)，重新分配需要将大小增加至少一个常数因子。(1.5和2是常见的)
当您调用vector::push_back时，结束指针与容量指针进行比较。如果有足够的空间容纳新对象，则调用placement new在可用空间中构造对象，并增加结束指针。
如果没有足够的空间，vector调用它的分配器为至少现有元素加上新元素分配足够的连续空间(不同的实现可能以不同的乘数增加分配的内存)。然后将所有现有元素加上新元素复制到新分配的空间。
std::vector overallocate -它通常会自动分配超过所需的内存。size不受此影响，但可以通过capacity进行控制。
std::vector将复制的所有内容。
std::vector分配的内存是原始的，没有按需调用构造函数，使用位置new。
所以，push_back做的是:
- 如果容量不足以容纳新元素，它将
- 分配新块
- 复制所有现有元素(通常使用复制构造函数)
- 增加一个
- 将新元素复制到新位置
如果您知道数组的最终大小，请先尝试vector::reserve内存。注意reserve和vector::resize不同。使用reserve，数组的vector::size()不会改变