标准库文档：C++ vector

基本介绍（可以跳过，只是一些原理介绍）

vector 是序列容器，表示可以改变大小的数组。就像数组一样，vector 为它们的元素使用连续的存储位置，这意味着它们的元素也可以使用指向其元素的常规指针上的偏移量来访问，并且与数组一样高效。但与数组不同，它们的大小可以动态变化，容器会自动处理它们的存储。

在内部，vector 使用动态分配的数组来存储它们的元素。这个数组可能需要重新分配，以便在插入新元素时增大大小，这意味着分配一个新数组并将所有元素移动到其中。就处理时间而言，这是一个相对昂贵的任务，因此，vector 不会在每次向容器添加元素时就重新分配。相反，vector 容器可能分配一些额外的存储空间以适应可能的增长，因此容器的实际容量可能大于包含其元素所需的存储空间(即它的大小)。

库可以实现不同的策略来平衡内存使用和重新分配的问题,但在任何情况下,重新分配应该只发生在对数生长间隔的大小,以便插入单个元素的向量可以提供平摊常数时间复杂度(见push_back方法)。因此，与数组相比，向量消耗更多的内存，以换取管理存储和有效地动态增长的能力。与其他动态序列容器(deques、lists和forward_lists)相比，vector 非常高效地访问它的元素(就像数组一样)，并且相对高效地从它的末尾添加或删除元素。对于涉及在非结尾位置插入或删除元素的操作，它们的性能比其他操作差，而且迭代器和引用的一致性比list和forward_lists差。

方法

1. 构造函数

  std::vector<int> first;                                // empty vector of ints
  std::vector<int> second (4,100);                       // four ints with value 100
  std::vector<int> third (second.begin(),second.end());  // iterating through second
  std::vector<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector<int> fifth (myints, myints + sizeof(myints)/sizeof(int));  //等价于third
  
  std::vector<int> sixth = {10,20,30,40}
  ====>
  first = {}
  seconde = {100,100,100,100}
  third = {100,100,100,100}
  forth = {100,100,100,100}
  fifth = {16,2,77,29}
  sixth = {10,20,30,40}

第一种方法是默认的,创建了一个空的vector；第二种方法是构造的4个值为100的int类型vector；第三种第四种都是复制的第二个；第五种等价于第三种，使用头指针和尾指针的形式来传值的。

2. 析构函数
   ~vector()
3. = 等号
   将新内容分配给容器，替换其当前内容，并相应地修改其大小。
4. Iterators:

    std::vector<int> myvector (5);  // 5 default-constructed ints
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';  //输出初始值

    int i=0;
    std::vector<int>::iterator rit = myvector.begin();
    for (; rit!= myvector.end(); ++rit)
        *rit = ++i;  //进行赋值
    std::cout << "my vector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';  //输出正向的数据{1，2，3，4，5}

    std::cout << "my vector contains:(reverse)";
    for (std::vector<int>::reverse_iterator rit = myvector.rbegin(); rit != myvector.rend(); ++rit)
        std::cout << ' ' << *rit;
    std::cout << '\n';  //输出反向的数据{5，4，，3，2，1}

    std::vector<int> myvector = {10,20,30,40,50};
    auto it = myvector.cbegin();
    vector<int>::iterator it2 = myvector.begin();
    *it2 = 12;
    // *it = 14; 会报错。
    for (;it!=myvector.end();++it){
        std::cout<<' '<<*it;
    }
    std::cout<<'\n'; // 输出{12，20，30，40，50}

5. Capacity
   其中 size 等等的类型都是std::vector<*>::size_type，成员类型size_type是无符号整数类型。

下面这些程序能让你更好的理解 .resize() 和 .capacity():

    std::vector<int> myvector;
    cout<<myvector.capacity()<<endl;  //0
    // set some initial content:
    for (int i=1;i<10;i++) myvector.push_back(i);   //1 2 3 4 5 6 7 8 9
    cout<<myvector.capacity()<<endl;  //16
    
    myvector.resize(5);
    cout<<myvector.capacity()<<endl;   //16
    std::cout << "myvector contains:";
    for (int i=0;i<myvector.size();i++)
        std::cout << ' ' << myvector[i];
    std::cout << '\n';  //1 2 3 4 5

    myvector.resize(8,100);
    std::cout << "myvector contains:";
    for (int i=0;i<myvector.size();i++)
        std::cout << ' ' << myvector[i];
    std::cout << '\n';  //1 2 3 4 5 100 100 100

    myvector.resize(12);
    std::cout << "myvector contains:";
    for (int i=0;i<myvector.size();i++)
        std::cout << ' ' << myvector[i];
    std::cout << '\n';  // 1 2 3 4 5 100 100 100 0 0 0 0

下面这些程序能让你更好的理解 .reserve():

std::vector<int>::size_type sz;

  std::vector<int> foo;
  sz = foo.capacity();
  std::cout << "making foo grow:\n";
  for (int i=0; i<100; ++i) {
    foo.push_back(i);
    if (sz!=foo.capacity()) {
      sz = foo.capacity();
      std::cout << "capacity changed: " << sz << '\n';
    }
  }

  std::vector<int> bar;
  sz = bar.capacity();
  bar.reserve(100);   // this is the only difference with foo above
  std::cout << "making bar grow:\n";
  for (int i=0; i<100; ++i) {
    bar.push_back(i);
    if (sz!=bar.capacity()) {
      sz = bar.capacity();
      std::cout << "capacity changed: " << sz << '\n';
    }
  }

=======>
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
making bar grow:(reserve)
capacity changed: 100

下面这些代码能让你理解 .shrink_to_fit()

  std::vector<int> myvector (100);
  std::cout << "1. capacity of myvector: " << myvector.capacity() << '\n';

  myvector.resize(10);
  std::cout << "2. capacity of myvector: " << myvector.capacity() << '\n';

  myvector.shrink_to_fit();
  std::cout << "3. capacity of myvector: " << myvector.capacity() << '\n';

6. Modifiers

理解assign：

std::vector<int> first;
    std::vector<int> second;
    std::vector<int> third;

    first.assign (7,100);             // 7 ints with a value of 100

    std::vector<int>::iterator it;
    it=first.begin()+1;

    second.assign (it,first.end()-1); // the 5 central values of first

    int myints[] = {1776,7,4};
    third.assign (myints,myints+3);   // assigning from array.

    std::cout << "Size of first: " << int (first.size()) << '\n';
    std::cout << "Size of second: " << int (second.size()) << '\n';
    std::cout << "Size of third: " << int (third.size()) << '\n';

理解 insert:

    std::vector<int> myvector {1,2,3};
    std::vector<int>::iterator it;

    it = myvector.begin();
    it = myvector.insert ( it , 200 );

    myvector.insert (it,2,300); //在it指向的位置插入两个 300

    // "it" no longer valid, get a new one:
    it = myvector.begin();

    std::vector<int> anothervector (2,400);
    myvector.insert (it+2,anothervector.begin(),anothervector.end());

    int myarray [] = { 501,502,503 };
    myvector.insert (myvector.begin(), myarray, myarray+3);

    std::cout << "myvector contains:";
    for (it=myvector.begin(); it<myvector.end(); it++)
        std::cout << ' ' << *it;
    std::cout << '\n';

理解erase:

  std::vector<int> myvector;

  // set some values (from 1 to 10)
  for (int i=1; i<=10; i++) myvector.push_back(i);

  // erase the 6th element
  myvector.erase (myvector.begin()+5);

  // erase the first 3 elements:
  myvector.erase (myvector.begin(),myvector.begin()+3);

理解swap:

    std::vector<int> foo (3,100);   // three ints with a value of 100
    std::vector<int> bar (5,200);   // five ints with a value of 200

    foo.swap(bar);
    //foo contains: 200 200 200 200 200
    //bar contains: 100 100 100

理解clear():

   std::vector<int> myvector;
  myvector.push_back (100);
  myvector.push_back (200);
  myvector.push_back (300);

  std::cout << "myvector contains:";
  for (unsigned i=0; i<myvector.size(); i++)
    std::cout << ' ' << myvector[i];
  std::cout << '\n';  //{300,200,100}

  myvector.clear();
  myvector.push_back (1101);
  myvector.push_back (2202);

  std::cout << "myvector contains:";
  for (unsigned i=0; i<myvector.size(); i++)
    std::cout << ' ' << myvector[i];
  std::cout << '\n';  //{2202,1101}

理解emplace:

    std::vector<int> myvector = {10,20,30};
    auto it = myvector.emplace ( myvector.begin()+1, 100 );
    myvector.emplace ( it, 200 );
    myvector.emplace ( myvector.end(), 300 );

    std::cout << "myvector contains:";
    for (auto& x: myvector)
        std::cout << ' ' << x;
    std::cout << '\n';