std::vector

原文链接

vector是表示可以改变大小的数组的序列容器。

就像数组一样，vector对它的元素使用连续的存储空间，这意味着vector的元素可以通过指向它的常规指针上的偏移量来访问，并且效率与数组相同。但是与数组不同，vector的大小可以动态更改，其存储由容器自动处理。

vector在内部使用动态分配的数组存储其元素。插入新元素时，可能需要从新分配该数组以增加其大小，这意味着分配新数组并将所有元素移至该数组。就处理时间而言，这是一项相对耗时的任务，因此，每次将元素添加到容器时，vector都不会重新分配。
取而代之的是，vector容器可能会分配一些额外的存储空间以适应可能的增长，因此，该容器的实际容量可能会大于包含其元素（即其大小）所严格要求的存储容量。库可以实现不同的增长策略，以在内存使用和重新分配之间取得平衡，但是在任何情况下，重新分配应该只发生在对数增长的大小间隔上，以便在vector的末尾插入单个元素可以以摊销的恒定时间复杂度来提供。
因此，和数组相比，vector消耗更多的内存以换取以有效方式动态管理内存的能力。

与其他动态序列容器（deques，lists和forward_lists）相比，vector在访问其元素（就像数组）方面非常有效，并且从其末尾添加或删除元素也都相对高效。对于涉及在末尾以外的位置插入或删除元素的操作，vector的性能比其他方法要差，并且与lists和forward_lists相比，迭代器和引用一致性更差。