简介

1. 向量是代表数组的序列容器，可以改变大小。就像数组一样，向量对其元素使用连续的存储位置，这意味着它们的元素也可以使用常规指针上的偏移量来访问其元素，而且和数组一样有效。但与数组不同的是，它们的大小可以动态变化，其存储由容器自动处理。
2. 在内部，向量使用一个动态分配的数组来存储其元素。这个数组可能需要重新分配，以便在插入新元素时增加其大小，这意味着要分配一个新的数组并将所有元素移到其中。就处理时间而言，这是一个相对昂贵的任务，因此，向量不会在每次向容器添加元素时重新分配。
3. 相反，向量容器可能会分配一些额外的存储，以适应可能的增长，因此容器的实际容量可能大于严格意义上的包含其元素所需的存储（即其大小）。库可以实现不同的增长策略，以平衡内存的使用和重新分配，但在任何情况下，重新分配应该只发生在对数增长的大小间隔，以便在向量的末端插入单个元素可以提供摊销的恒定时间复杂性（见push_back）。
4. 因此，与数组相比，向量消耗更多的内存来换取管理存储的能力，并以有效的方式动态增长。
5. 与其他动态序列容器（deques、lists和forward_lists）相比，向量在访问其元素时非常高效（就像数组一样），并且相对高效地从其末端添加或删除元素。对于涉及在末端以外的位置插入或删除元素的操作，它们的表现比其他的差，而且与list和forward_lists相比，它们的迭代器和引用也不太一致。

要点

• 无开销的随机访问
• 快速遍历；适合于线性搜索
• 以摊销后的恒定时间在末端插入
• 如果在头部或者随机位置的进行插入或删除操作占主导地位，可能会很慢
• 如果元素类型有很高的复制/分配成本，可能会很慢（重新排序的元素需要复制/移动它们）。
• 对于大量的值来说，可能会有很长的分配时间
• std::vector 是封装动态数组的顺序容器。
• std::pmr::vector 是使用多态分配器的模板别名。

例子1

vector内存布局

#include 
#include 
 
int main()
{
    std::vector v {2,4,5};
    v.push_back(6);
    v.pop_back();
    v[1] = 3;
    std::cout << v[2] << std::endl;
    
    for (int x : v) std::cout << x << ' ';
    std::cout << std::endl;
    
    v.reserve(8);
    v.resize(5, 0);
    for (int x : v) std::cout << x << ' ';
    std::cout << std::endl;
    
    std::cout << v.capacity() << std::endl;
    std::cout << v.size() << std::endl;
}

https://wandbox.org/nojs/gcc-head
https://wandbox.org/nojs/clang-head

例子2

#include 
#include 

using namespace std;
struct p2d {
    p2d(int x_, int y_): x{x_}, y{y_} {}
    int x, y;
};
 
int main()
{
    vector v { p2d{2,3} };
    // insert copy
    v.push_back( p2d{6,4} );
    // construct in place with
    // constructor ↓ ↓ arguments
    v.emplace_back(9,7);
    // iterator ↓ to first pos
    v.emplace(begin(v), 5,8);
    for (p2d x : v) std::cout << x.x << ' ' << x.y << std::endl;
}

例子3

#include 
#include 
  
int main()
{
    std::vector v {0,1,2,3,5,6};
    auto i = std::begin(v) + 3;

    //v.insert(i,8);
    //std::cout << *i;   // ERROR
    //v.erase(i);
    //std::cout << *i;  // ERROR
    std::cout << *i << std::endl;
    
    i = v.insert(i,8);
    std::cout << *i << std::endl;

    i = v.erase(i);  
    std::cout << *i << std::endl;

    for (int x : v) std::cout << x << ' ';
    std::cout <<  std::endl;
}