🔥前言

我们来学习一个算法题中C++语言最火的一个容器——vector，学习vector容器的底层概念并且会使用构造和他的的常用方法，让我们深入了解vector容器然后刷些C++算法题充实自己吧！

vector容器的概念模型

vector容器是一个单端数组(一般默认前端是封闭的)

• 示意图
  

vector和数组的区别

• 普通数组是静态空间，而vector可以进行动态扩展
• 动态扩展过程

  并不是直接在原有空间中进行扩容，而是找到一个更大的空间，将原有数据拷贝到大空间内，并释放原有的空间

• vector容器的迭代器是支持随机访问的迭代器(功能强大)
  • 常用迭代器
    

    v.begin()和v.end()分别代表容器的第一个元素和最后一个元素的下一个位置；v.rbegin()和v.rend()则分别代表最后一个元素和第一个元素前面的位置；insert()用来把元素插入到容器内

vector容器的基本操作

包括构造方法、赋值、计算容量和大小、插入删除等

构造函数

• 创建vector容器的方法

函数原型：

• vector<T> v;其中T是泛型，用来存放数据类型，这是默认构造函数,较为常用
• vector(v.begin(),viend()); 将[v.begin(),v.end)前闭后开的区间内的元素拷贝给本身容器
• vector(n,elem);构造函数将n个elem值拷贝给本身容器
• vector(const vector &ans);拷贝构造函数

代码示例：

void printVector(vector<int>& v)
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
//vector容器构造
void test()
{
    vector<int>v1;//默认构造 无参构造
    for (int i = 0; i < 6; i++)
    {
        v1.push_back(i);
    }
    printVector(v1);

    //通过区间的方式进行构造
    vector<int>v2(v1.begin(), v1.end());
    printVector(v2);

    //n个elem方式构造
    vector<int>v3(6, 666);//6个666
    printVector(v3);

    //拷贝构造
    vector<int>v4(v3);
    printVector(v4);
}

tips：建议使用1、4两种构造函数

赋值操作

• 给vector容器赋值

函数原型：

• vector& operator=(const vector &ans);重载赋值操作符
• assign(be,en);将[be,en)区间内的数组拷贝赋值给自己
• assign(n,elem);将n个elem拷贝赋值给自己

代码示例：

//vector赋值
void PrintVector(vector<int>& v)
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
void test()
{
    vector<int>v1;
    for (int i = 0; i < 10;i++)
    {
        v1.push_back(i);
    }
    PrintVector(v1);

    //赋值 operator= 
    vector<int>v2;
    v2 = v1;
    PrintVector(v2);

    //assign
    vector<int>v3;
    v3.assign(v1.begin(), v1.end());//闭 开
    PrintVector(v3);

    //n个elem方式赋值
    vector<int>v4;
    v4.assign(6, 66);//6个66
    PrintVector(v4);
}

tips：vector赋值操作简单，直接使用等号和使用assign都可以

容量和大小

• 对vector容器的容量和大小操作

函数原型：

• empty();判断容器是否为空
• capacity();容器中的容量大小
• size();返回容器中元素的个数
• resize(int sum);重新指定容器长度为num，容器变长以默认值填充，容器变短则超出部分删除
• resize(int num,elem)同上，区别是默认值填充变为elem值填充

代码示例：

void test()
{
    vector<int>v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    if (v1.empty())
    {
        cout << "空" << endl;
    }
    else
    {
        cout << "不空" << endl;
    }
    cout << "v1的容量=" << v1.capacity() << endl;
    cout << "v1的大小=" << v1.size() << endl;
    //重新指定大小
    v1.resize(10,666);//利用重载版本，可以指定默认填充值
    v1.resize(5);
}

插入和删除

• 对vector容器进行插入、删除操作

函数原型：

• push_back(e);尾部插入元素e
• pop_back();删除最后一个元素
• insert(const_iterator pos,e);迭代器指向位置pos插入指定元素e
• insert(const_iterator pos,int count ,e);插入count个指定元素e
• erase(const_iterator pos);删除迭代器指向的元素
• erase(const_iterator begin,const_iterator end);删除迭代器从begin到end之间的元素
• clear();清空容器内所有元素

代码示例：

void PrintVector(vector<int>& v)
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

void test()
{
    vector<int>v1;
    //尾插法
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(50);

    //遍历
    PrintVector(v1);

    //尾删
    v1.pop_back();
    PrintVector(v1);

    //插入
    v1.insert(v1.begin(), 66);
    PrintVector(v1);

    v1.insert(v1.begin(), 2, 666);
    PrintVector(v1);

    //删除 参数也是迭代器
    v1.erase(v1.begin());
    //v1.erase(v1.begin(), v1.end());清空，同下
    PrintVector(v1);

    //清空
    v1.clear();
    PrintVector(v1);
}

数据存取

• 对vector中的数据进行存取操作

函数原型：

• at(int index);返回索引index指向的数据
• operator[];和普通数组取数据用法一致
• front();返回容器中第一个数据元素
• back();返回容器中最后一个数据元素

代码示例：

//vector容器 数据存取
void test()
{
    vector<int>v1;
    for (int i = 0; i < 6; i++)
    {
        v1.push_back(i);
    }    
    //利用[]访问数组中的元素
    for (int i = 0; i < v1.size(); i++)
    {
        cout << v1[i] << " ";
    }
    cout << endl;
    //利用at方式访问元素
    for (int i = 0; i < v1.size(); i++)
    {
        cout << v1.at(i) << " ";
    }
    cout << endl;
    //获取第一个元素
    cout << "第一个元素=" << v1.front() << endl;
    //获取最后一个元素
    cout << "最后一个元素=" << v1.back()<<endl;
}

tips：除了迭代器可以访问容器元素，利用at和[]也可以

互换容器

• 实现两个容器的元素互换
  • 可以利用匿名对象有效缩减容器容量

函数原型：

• swap(ans);将ans与本身的元素互换

代码示例：

//元素互换的基本使用不再赘述，就是交换容器，着重分享巧用的方面
void test()
{
    vector<int>v;
    for (int i = 0; i < 10000; i++)
    {
        v.push_back(i);
    }
    cout << "容量" << v.capacity() << endl;
    cout << "大小" << v.size() << endl;
    v.resize(3);//重新指定大小
    cout << "容量" << v.capacity() << endl;
    cout << "大小" << v.size() << endl;
    //巧用swap收缩内存
    vector<int>(v).swap(v);
    cout << endl;
    cout << "容量" << v.capacity() << endl;
    cout << "大小" << v.size() << endl;
}

我把上面最最要的一行代码进行解释：vector<int>(v).swap(v);

vector<int>(v)中的(v)其实是一个匿名对象利用拷贝构造将v容器的值存进这个“匿名容器”内，但是他的容量是很小的；随后调用swap(v)，把v容器本来的指向指到这个匿名容器，直接让匿名容器承担数以万计的容量，然后编译器自动销毁匿名对象，巧妙缩减了容器的容量。

预留空间

• 减少vector在动态扩展容量时的次数

函数原型：

• reserve(int len);容器预留len个元素长度，预留位置不初始化，元素不可访问

代码示例：

void test()
{
    //vector容器 预留空间
    vector<int>v1;
    v1.reserve(666666);
    int num = 0;//统计开辟次数
    int* p = NULL;
    for (int i = 0; i < 666666; i++)
    {
        v1.push_back(i);

        if (p != &v1[0])
        {
            p = &v1[0];
            num++;
        }
    }
    cout << num << endl;
}

统计开辟次数功能的解释：

前面讲到vector容器扩容的方式是找到大空间再拷贝，那么我们让一个指针指向容器第一个元素的地址。如果说num进行了自增操作，那就说明容器进行了扩容，这是因为找大空间肯定是要换容器地址的。因此num的最终大小就是容器扩容的次数，我的运行结果是34次，这是非常耗费时间的。因此利用v1.reserve(666666);先预留空间，这时候再次运行，结果就是1了，极大的提高了效率

📃结语

vector是STL最常用的容器之一，更是算法题中非常青睐的一个动态数组。建议大家反复观看并多刷题巩固，早日成为算法大佬，卷进大厂，文章开头也有刷题的链接，也都是免费的。那么让我们下篇博客不见不散!!!