C++容器 vector

C++容器 vector 介绍

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

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

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

#include 

---

初始化

std::vector v1; 

默认初始化

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

std::vector v2(v1); 或者 std::vector v2 = v1;

拷贝初始化

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

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

列表中元素拷贝

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

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

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

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

std::vector v5(7);

默认值初始化

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

 std::vector v6(7,3);

指定值初始化

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

---

元素访问

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

#include 
#include 

int main()
{
    std::vector 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 
#include 

int main()
{
    std::vector 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 
#include 

int main()
{
    std::vector 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 
#include 

int main()
{
    std::vector 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()返回指向容器中第一个元素的正向迭代器；如果是 const 类型容器，在该函数返回的是常量正向迭代器。end()返回指向容器最后一个元素之后一个位置的正向迭代器；如果是 const 类型容器，在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。rbegin()返回指向最后一个元素的反向迭代器；如果是 const 类型容器，在该函数返回的是常量反向迭代器。rend()返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器，在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。cbegin()和 begin() 功能类似，只不过其返回的迭代器类型为常量正向迭代器，不能用于修改元素。cend()和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器，不能用于修改元素。crbegin()和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器，不能用于修改元素。crend()和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器，不能用于修改元素。

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

        这些成员函数通常是成对使用的，即 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 
#include 

int main()
{
    std::vector 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 
#include 

int main()
{
    std::vector 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 
#include 

int main()
{
    std::vector 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的成员函数 函数成员函数功能begin()返回指向容器中第一个元素的迭代器。end()返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。rbegin()返回指向最后一个元素的迭代器。rend()返回指向第一个元素所在位置前一个位置的迭代器。cbegin()和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。cend()和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。crbegin()和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。crend()和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。size()返回实际元素个数。max_size()返回元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。resize()改变实际元素的个数。capacity()返回当前容量。empty()判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。reserve()增加容器的容量。shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。operator[ ]重载了 [ ] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素。at()使用经过边界检查的索引访问元素。front()返回第一个元素的引用。back()返回最后一个元素的引用。data()返回指向容器中第一个元素的指针。assign()用新元素替换原有内容。push_back()在序列的尾部添加一个元素。pop_back()移出序列尾部的元素。insert()在指定的位置插入一个或多个元素。erase()移出一个元素或一段元素。clear()移出所有的元素，容器大小变为 0。swap()交换两个容器的所有元素。emplace()在指定的位置直接生成一个元素。emplace_back()在序列尾部生成一个元素。

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

std::vector 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 容器的元素可能已经被复制或移到了新的内存地址。所以后续再使用这些迭代器时，最好重新生成一下。

push_back()：在 vector 容器尾部添加一个元素

vector values{};
values.push_back(1);
values.push_back(2);
for (int i = 0; i < values.size(); ++i) {
    std::cout << values[i] << " ";            // 输出 1 2
}

emplace_back()：C++11 新增加的，其功能和 push_back() 相同，都是在 vector 容器的尾部添加一个元素

std::vector values{};
values.emplace_back(1);
values.emplace_back(2);
for (int i = 0; i < values.size(); i++) {
    std::cout << values[i] << " ";            // 输出 1 2
}

        这样看的话，emplace_back() 和 push_back()没有区别，既然它们实现的功能是一样的，那么 C++ 11 标准中为什么要多此一举呢？

        emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

        为了更清楚它们之间的区别，我们创建一个包含类对象的 vector 容器，如下所示：

#include  
#include  

class testDemo
{
public:
    testDemo(int num):num(num){
        std::cout << "调用构造函数" << std::endl;
    }
    testDemo(const testDemo& other) :num(other.num) {
        std::cout << "调用拷贝构造函数" << endl;
    }
    testDemo(testDemo&& other) :num(other.num) {
        std::cout << "调用移动构造函数" << std::endl;
    }
private:
    int num;
};

int main()
{
    std::cout << "emplace_back:" << std::endl;
    std::vector demo1;
    demo1.emplace_back(2);  
    std::cout << "push_back:" << std::endl;
    std::vector demo2;
    demo2.push_back(2);
}

        运行结果为：

emplace_back:
调用构造函数
push_back:
调用构造函数
调用移动构造函数

         在此基础上，我们尝试将 testDemo 类中的移动构造函数注释掉，再运行程序会发现，运行结果变为：

emplace_back:
调用构造函数
push_back:
调用构造函数
调用拷贝构造函数

        由此可以看出，push_back() 在底层实现时，会优先选择调用移动构造函数，如果没有才会调用拷贝构造函数。
        显然完成同样的 *** 作，push_back() 的底层实现过程比 emplace_back() 更繁琐，换句话说，emplace_back() 的执行效率比 push_back() 高。因此，在实际使用时，建议大家优先选用 emplace_back()。

insert()：在 vector 容器的指定位置插入一个或多个元素。该函数的语法格式有多种：

语法格式用法说明iterator insert(pos,elem)在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。iterator insert(pos,n,elem)在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,first,last) 在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。iterator insert(pos,initlist)在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。

#include  
#include  
#include  

int main()
{
    std::vector demo{1,2};
    // 第一种格式用法
    demo.insert(demo.begin() + 1, 3);      // {1,3,2}
    // 第二种格式用法
    demo.insert(demo.end(), 2, 5);         // {1,3,2,5,5}
    // 第三种格式用法
    std::arraytest{ 7,8,9 };
    demo.insert(demo.end(), test.begin(), test.end());    // {1,3,2,5,5,7,8,9}
    // 第四种格式用法
    demo.insert(demo.end(), { 10,11 });    // {1,3,2,5,5,7,8,9,10,11}

    for (int i = 0; i < demo.size(); i++) {
        std::cout << demo[i] << " ";       // 输出 1 3 2 5 5 7 8 9 10 11
    }

    return 0;
}

emplace() ：C++11 标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素。emplace() 每次只能插入一个元素，而不是多个。

iterator emplace (const_iterator pos, args...);

其中，pos 为指定插入位置的迭代器；args... 表示与新插入元素的构造函数相对应的多个参数，即被插入元素的构造函数需要多少个参数，那么在 emplace() 的第一个参数的后面，就需要传入相应数量的参数。该函数会返回表示新插入元素位置的迭代器。

#include 
#include 

int main()
{
    std::vector demo1{1,2};
    // emplace() 每次只能插入一个 int 类型元素
    demo1.emplace(demo1.begin(), 3);

    for (int i = 0; i < demo1.size(); i++) {
        std::cout << demo1[i] << " ";
    }

    return 0;
}

        insert() 和 emplace() 的区别和 push_back() 与 emplace_back() 的区别一样，通过 insert() 函数向 vector 容器中插入 testDemo 类对象，需要调用类的构造函数和移动构造函数（或拷贝构造函数）；而通过 emplace() 函数实现同样的功能，只需要调用构造函数即可。

        简单的理解，就是 emplace() 在插入元素时，是在容器的指定位置直接构造元素，而不是先单独生成，再将其复制（或移动）到容器中。因此，在实际使用中，推荐大家优先使用 emplace()。

pop_back()：删除 vector 容器中最后一个元素，该容器的大小（size）会减 1，但容量（capacity）不会发生改变。

#include 
#include 

int main()
{
    std::vector demo{ 1,2,3,4,5 };
    demo.pop_back();
    // 输出 dmeo 容器新的size
    std::cout << "size is :" << demo.size() << std::endl;           // size is :4
    // 输出 demo 容器新的容量
    std::cout << "capacity is :" << demo.capacity() << std::endl;   // capacity is :5

    for (int i = 0; i < demo.size(); i++) {
        std::cout << demo[i] << " ";                                // 1 2 3 4
    }

    return 0;
}

erase()：删除 vector 容器中指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器。该容器的大小（size）会减 1，但容量（capacity）不会发生改变。

iterator erase (pos);                                                                                                              pos 为指定被删除元素位置的迭代器，同时该函数会返回一个指向删除元素所在位置下一个位置的迭代器。

iterator erase (iterator first, iterator last);                                                                                  其中 first 和 last 是指定被删除元素区域的迭代器，同时该函数会返回指向此区域之后一个位置的迭代器。

#include 
#include 

int main()
{
    std::vector demo{ 1,2,3,4,5 };
    // 删除第二个元素
    auto iter = demo.erase(demo.begin() + 1);
    // 输出 dmeo 容器新的size
    std::cout << "size is :" << demo.size() << std::endl;           // size is :4
    // 输出 demo 容器新的容量
    std::cout << "capacity is :" << demo.capacity() << std::endl;   // capacity is :5

    for (int i = 0; i < demo.size(); i++) {
        std::cout << demo[i] << " ";                                // 1 3 4 5
    }
    // iter迭代器指向元素 3
    std::cout << endl << *iter << std::endl;                        // 3

    return 0;
}

#include 
#include 

int main()
{
    std::vector demo{ 1,2,3,4,5 };
    //删除第二、三个元素
    auto iter = demo.erase(demo.begin() + 1, demo.end() - 2);
    std::cout << "size is :" << demo.size() << std::endl;           // size is :3
    std::cout << "capacity is :" << demo.capacity() << std::endl;   // capacity is :5

    for (int i = 0; i < demo.size(); i++) {
        std::cout << demo[i] << " ";                                // 1 4 5
    }

    return 0;
}

        如果要删除容器中和指定元素值相同的所有元素，可以使用 remove() 函数，该函数定义在  头文件中。例如：

#include 
#include 
#include 

int main()
{
    std::vector demo{ 1,3,3,4,3,5 };
    // 前两个参数为指定被删除元素区域的迭代器，第三个参数为要删除的元素值
    auto iter = std::remove(demo.begin(), demo.end(), 3);
    std::cout << "size is :" << demo.size() << std::endl;           // size is :6
    std::cout << "capacity is :" << demo.capacity() << std::endl;   // capacity is :6

    // 输出剩余的元素
    for (auto first = demo.begin(); first < iter; ++first) {
        std::cout << *first << " ";                                 // 1 4 5
    }

    return 0;
}

在对容器执行完 remove() 函数之后，由于该函数并没有改变容器原来的大小和容量，因此无法使用之前的方法遍历容器，而是需要向程序中那样，借助 remove() 返回的迭代器完成正确的遍历。

remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。

        通过 remove() 函数删除掉 demo 容器中的多个指定元素，该容器的大小和容量都没有改变，其剩余位置还保留了之前存储的元素。通常remove()用于删除容器中指定元素时，常和 erase() 成员函数搭配使用，我们可以使用 erase() 成员函数删掉这些 "无用" 的元素：

#include 
#include 
#include 

int main()
{
    std::vector demo{ 1,3,3,4,3,5 };
    // 前两个参数为指定被删除元素区域的迭代器，第三个参数为要删除的元素值，返回指向最后一个元素下一个位置的迭代器
    auto iter = std::remove(demo.begin(), demo.end(), 3);
    // 在调用remove()函数之后调用erase()函数删除返回的迭代器之后的元素
    demo.erase(iter, demo.end());
    std::cout << "size is :" << demo.size() << std::endl;           // size is :3
    std::cout << "capacity is :" << demo.capacity() << std::endl;   // capacity is :6

    // 输出剩余的元素
    for (int i = 0; i < demo.size();i++) {
        cout << demo[i] << " ";                                     // 使用普通方法也可以输出 1 4 5
    }

    return 0;
}

clear() ：删除容器中所有的元素

#include 
#include 

int main()
{
    std::vectordemo{ 1,3,3,4,3,5 };
    // 删除容器中全部元素
    demo.clear();

    std::cout << "size is :" << demo.size() << std::endl;           // size is :0
    std::cout << "capacity is :" << demo.capacity() << std::endl;   // capacity is :6

    return 0;
}