介绍

        vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对C++普通数组的“升级版”。不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

        vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)。而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

        vector 容器以类模板 vector<T>（ T 表示存储元素的类型）的形式定义在 <vector> 头文件中，并位于 std 命名空间中。因此，在创建该容器之前，代码中需包含vector头文件：

#include <vector>

初始化

• std::vector<int> v1; 

默认初始化

此时，v1 是一个空的 vector 容器，size为0，表明容器中没有元素，而且capacity也返回0，意味着还没有分配内存空间。当添加第一个元素（比如使用 push_back() 函数）时，vector 会自动分配内存。
这种初始化方式适用于元素个数未知，需要在程序中动态添加的情况。

• std::vector<int> v2(v1); 或者 std::vector<int> v2 = v1;

拷贝初始化

两种方式等价，v2 初始化为 v1 的拷贝，v1 必须与 v2 类型相同，也就是同为int的 vector类型，v2 将具有和 v1 相同的容量和元素。

• std::vector<int> v3 = { 1, 2, 3, 4, 5, 6, 7 }; 或者 std::vector<int> v3 { 1, 2, 3, 4, 5, 6, 7 };

列表中元素拷贝

v3初始化为列表中元素的拷贝，列表中元素必须与v3的元素类型相容，本例中必须是与整数类型相容的类型，整形会直接拷贝，其他类型会进行类型转换。

• int a[5] = { 1,2,3,4,5 };
  std::vector<int> v4(a + 1, a + 4);

初始化为两个迭代器指定范围中元素的拷贝

将数组转换成vector，v4 初始化为两个迭代器指定范围中元素的拷贝，范围中的元素类型必须与 v4 的元素类型相容。
在本例中 v4 被初始化为{ 2, 3, 4 }，由于只要求范围中的元素类型与待初始化的容器的元素类型相容，因此迭代器来自不同的容器是可能的。例如，用一个 double的数组的范围来初始化 v4 是可行的。另外，由于构造函数只是读取范围中的元素进行拷贝因此使用普通迭代器还是 const迭代器来指出范围并没有区别。
这种初始化方法特别适合于获取一个序列的子序列。

• std::vector<int> v5(7);

默认值初始化

v5中将包含7个元素，每个元素进行缺省的值初始化，对于int，也就是被赋值为0。因此 v5 被初始化为包含7个0。
当程序运行初期元素大致数量可预知，而元素的值需要动态获取的时候，可采用这种初始化方式。

•  std::vector<int> v6(7,3);

指定值初始化

v6被初始化为包含7个int类型的元素，每个元素的值为3。圆括号 () 中的两个参数，既可以是常量，也可以用变量来表示

元素访问

        vector 容器可以向普通数组那样访问存储的元素，还可以对指定下标处的元素进行修改：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3,4,5};
    //获取容器中首个元素
    std::cout << values[0] << std::endl;        // 输出1
    //修改容器中下标为 0 的元素的值
    values[0] = values[1] + values[2] + values[3] + values[4];
    std::cout << values[0] << std::endl;        // 输出14

    return 0;
}

        容器名[n] 这种获取元素的方式，需要确保下标 n 的值不会超过容器的容量（可以通过 capacity() 成员函数获取），否则会发生越界访问的错误。 

        和 array 容器一样，vector 容器也提供了 at() 成员函数，当传给 at() 的索引会造成越界时，会抛出std::out_of_range异常。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3,4,5};
    //获取容器中首个元素
    std::cout << values.at(0) << std::endl;        // 输出1
    //修改容器中下标为 0 的元素的值
    values.at(0) = values.at(1) + values.at(2) + values.at(3) + values.at(4);
    std::cout << values.at(0) << std::endl;        // 输出14
    //下面这条语句会发生 out_of_range 异常
    //std::cout << values.at(5) << std::endl;

    return 0;
}

        除此之外，vector 容器还提供了 2 个成员函数，即 front() 和 back()，它们分别返回 vector 容器中第一个和最后一个元素的引用，通过利用这 2 个函数返回的引用，可以访问（或者修改）容器中的首尾元素。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3,4,5};
    std::cout << "values 首元素为：" << values.front() << std::endl;      // values 首元素为：1
    std::cout << "values 尾元素为：" << values.back() << std::endl;       // values 尾元素为：5
    //修改首元素
    values.front() = 10;
    std::cout << "values 新的首元素为：" << values.front() << std::endl;  // values 新的首元素为：10
    //修改尾元素
    values.back() = 20;
    std::cout << "values 新的尾元素为：" << values.back() << std::endl;   // values 新的尾元素为：20

    return 0;
}

        另外，vector 容器还提供了 data() 成员函数，该函数的功能是返回指向容器中首个元素的指针。通过该指针也可以访问或者修改容器中的元素：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3,4,5};
    //输出容器中第 3 个元素的值
    std::cout << *(values.data() + 2) << std::endl;        // 输出3
    //修改容器中第 2 个元素的值
    *(values.data() + 1) = 10;
    std::cout << *(values.data() + 1) << std::endl;        // 输出10

    return 0;
}

vector容器迭代器用法

        vector 容器迭代器和 array 容器迭代器有很多相同之处，都是随机访问迭代器，并且 vector 模板类提供的操作迭代器的成员函数也和 array 容器一样。

        这些函数具体在容器中所指的位置如下图所示： 

        这些成员函数通常是成对使用的，即 begin()/end()、rbegin()/rend()、cbegin()/cend()、crbegin()/crend() 各自成对搭配使用。其中，begin()/end() 和 cbegin/cend() 的功能是类似的，同样 rbegin()/rend() 和 crbegin()/crend() 的功能是类似的。以上函数在实际使用时，其返回值类型都可以使用 auto 关键字代替，编译器可以自行判断出该迭代器的类型。

        vector 容器迭代器最常用的功能就是遍历访问容器中存储的元素。begin() 和 end() 成员函数分别用于指向「首元素」和「尾元素+1」的位置，下面程序演示了如何使用 begin() 和 end() 遍历 vector 容器并输出其中的元素：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3,4,5};
    auto first = values.begin();
    auto end = values.end();
    while (first != end)
    {
        std::cout << *first << " ";    // 输出values中元素 1 2 3 4 5
        ++first;
    }

    return 0;
}

        除此之外，C++ 11 新添加的 begin() 和 end() 全局函数也同样适用于 vector 容器，他们的作用和 vector 成员函数的 begin() 和 end() 相同，只是用法稍有不同，上面代码的7、8两行可以替换成下面两行：

auto first = std::begin(values);
auto end = std::end (values);

        rbegin() 和 rend() 成员函数为反向迭代器，分别表示指向最后一个元素和第一个元素前一个位置的随机访问迭代器。反向迭代器用于以逆序的方式遍历容器中的元素：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3,4,5};
    auto first = values.rbegin();
    auto end = values.rend();
    while (first != end)
    {
        std::cout << *first << " ";         // 逆序输出values中元素 5 4 3 2 1
        // 在使用反向迭代器进行 ++ 或 -- 运算时，++ 指的是迭代器向左移动一位
        // -- 指的是迭代器向右移动一位，即这两个运算符的功能也“互换”了。
        ++first;
    }
    return 0;
}

        对于空的 vector 容器来说，begin() 和 end() 成员函数返回的迭代器是相等的，即它们指向的是同一个位置。除此之外，vector 容器在申请更多内存的同时，容器中的所有元素可能会被复制或移动到新的内存地址，这会导致之前创建的迭代器失效。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values{1,2,3};
    std::cout << "values 容器首个元素的地址：" << values.data() << std::endl;    // values 容器首个元素的地址：0096DFE8
    auto first = values.begin();
    auto end = values.end();
    // 增加 values 的容量
    values.reserve(20);
    std::cout << "values 容器首个元素的地址：" << values.data() << std::endl;    // values 容器首个元素的地址：00965560

    // 运行下面的代码会程序会崩溃，因为vector对象在内存中移动了位置
    while (first != end) {
        std::cout << *first;
        ++first;
    }

    return 0;
}

        可以看到，values 容器在增加容量之后，首个元素的存储地址发生了改变，此时再使用先前创建的迭代器，显然是错误的。因此，为了保险起见，每当 vector 容器的容量发生变化时，我们都要对之前创建的迭代器重新初始化一遍：

// 在reverse()之后重新给迭代器赋值初始化，这样就可以正常使用迭代器了
first = values.begin();
end = values.end();

vector的成员函数

• reserve()：在创建好空容器的基础上，可以通过调用 reserve() 成员函数来增加容器的容量。

std::vector<double> values;
std::cout << values.capacity() << std::endl;        // 输出0

values.reserve(20);
std::cout << values.capacity() << std::endl;        // 输出20

        这样就设置了容器的内存分配，即至少可以容纳 20 个元素。注意，如果 vector 的容量在执行此语句之前，已经大于或等于 20 个元素，那么这条语句什么也不做；另外，调用 reserve() 不会影响已存储的元素，也不会生成任何元素，即 values 容器内此时仍然没有任何元素。

        还需注意的是，如果调用 reserve() 来增加容器容量，之前创建好的任何迭代器（例如开始迭代器和结束迭代器）都可能会失效，这是因为，为了增加容器的容量，vector<T> 容器的元素可能已经被复制或移到了新的内存地址。所以后续再使用这些迭代器时，最好重新生成一下。