C++ STL容器总结之vector（超详细版）

桃扇骨 2023-07-05 13:26 1阅读 0赞

### 一、vector简介 ###

vector的中文翻译为向量，是一种C++ STL中的序列容器。它的是存储方式和C++语言本身提供的数组一样都是顺序存储，因此**vector的操作和数组十分相似**。但是和数组不一样的是，数组的存储空间是静态的，一旦配置了就不能改变，而**vector的存储空间是动态的，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素**，因此也被称为可变长数组。

### 二、vector存储机制 ###

vector的动态空间实现如下图所示，  
![1][]  
为了减少空间配置的时间代价，**通常vector配置的空间会比我们标注的需求量更大一些**，于是vector总的存储空间就如上图所示分成了两部分，其中工作空间是按我们标注的需求配置的，而备用空间就是额外配置的那一部分空间。

**当需要扩充的新的空间时，vector会优先使用备用空间**。例如我们现在要在末尾插入6，它会将  f i n i s h finish finish 迭代器指向的空间用于存储6，最后再调整  f i n i s h finish finish 迭代器的位置。  
![2][]当备用空间不足以存放要插入的元素时，**vector会在另外较大的空闲空间中配置一块大小为原来两倍的新空间**（由于不能保证原空间之后有足有的空闲空间，所以并不是直接在原空间后面接续），然后将原空间中的数据按顺序迁移到新空间，最后释放原来的存储空间。这一过程可以简单记忆为**重新配置、移动数据、释放原空间**。

下面是以“在备用空间用完的情况下插入新元素3”为例，用图片形式描述前后的存储空间变化。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]  
由于以上过程对使用者而言都是透明的，所以需要非常注意的一点是，**一旦vector的空间重新配置，所有指向原vector的迭代器都会失效！**

### 三、vector创建和初始化 ###

初始化比较简单，我们可以根据自己的使用需求来相应的初始化方法。

//vector头文件
    #include <vector>
    //创建一个空的vector
    vector<int> vec1;
    //创建一个有n个元素的vector，初始值都为0
    vector<int> vec2(n);
    //创建一个有n个元素的vector，并将它们值都初始化为x
    vector<int> vec3(n, x);
    //用vec3来初始化vec4，它们大小和元素的值都相同
    vector<int> vec4(vec3);

### 四、vector基本操作详解 ###

很多人不明白为什么要了解容器本身实现的原理，觉得学会怎么用就够了。其实，学了容器的实现原理会**对容器操作会有更加深刻的理解**，同时也会**对算法思想有或多或少的领悟**。

接下来，我们结合这张底层存储示意图仔细分析vector的基本操作。  
![4][]

*  迭代器  
    这里简单介绍下面将出现的两种比较陌生的迭代器：
    
     *   r e v e r s e \_ i t e r a t o r reverse\\\_iterator reverse\_iterator，称为反向迭代器，它的递增方向和我们常用的  i t e r a t o r iterator iterator 相反，例如  r i t + + rit++ rit\+\+表示指向的位置往左移。
     *   c o n s t \_ i t e r a t o r const\\\_iterator const\_iterator，它不能改变所指向的元素的值，但是可以再指向其他元素，和const关键词标注的  i t e r a t o r iterator iterator 刚好相反。

//获取第一个元素的迭代器，也就是图中的start
    vec.begin();
    
    //获取最后一个下个位置的迭代器，即图中的finish
    vec.end();
    
    //返回vector<T>::reverse_iterator类型迭代器，指向finish-1
    vec.rbegin();
    
    //返回vector<T>::reverse_iterator类型迭代器，指向start的前一个位置
    vec.rend();
    
    //c++11，返回vector<T>::const_iterator类型迭代器，位置同图中start
    vec.cbegin();
    
    //c++11，返回vector<T>::const_iterator类型迭代器，位置同图中finish
    vec.cend();

*  容量

//获取当前容量大小
    vec.size();
    
    //获取包括备用空间在内的总容量大小
    vec.capacity();
    
    //最大容量，即最多可以存储多少个当前类型元素
    vec.max_size();
    
    //判断vector是否为空，即判断start == finish
    vec.empty();
    
    //重新设置vector的容量，大小为n
    vec.resize(n);

*  元素访问  
    因为vector也是顺序存储，所以它进行元素的随机访问的时间复杂度也为  O ( 1 ) O(1) O(1)

//像数组一样用索引进行随机访问，例如vec[0]
    operator []
    
    //作用同上，增加异常处理，越界抛出out of range
    vec.at(index);
    
    //返回一个元素，即迭代器start指向的元素
    vec.front();
    
    //返回最后一个元素，即迭代器finish-1指向的元素
    vec.back();

*  修改操作操作  
    由于是顺序存储结构，随机插入或随机删除都会引起元素的移动（对末尾元素操作除外），因此它们的时间复杂度都是  O ( n ) O(n) O(n)。下图是删除元素的底层实现示意，可以用于帮助我们的理解，从图中也可以看出删除操作不会引起总空间的变化。  
    ![5][]

//元素的赋值值操作（类似于初始化）
    //将vec赋值为n个x
    vec.assign(n, x);
    //将[first, last)范围内的元素赋值给vec
    vec.assign(first, last);
    //传入参数为数组指针，将数组[0, n)中的元素赋值给vec
    vec.assign(array, array + n);
    
    //将新元素x插入到finish所在的位置，并将迭代器finish后移，时间复杂度为O(1)
    vec.push_back(x);
    
    //清除位于finish-1的元素，时间复杂度为O(1)
    vec.pop_back();
    
    //时间复杂度为O(n)，position表示插入位置的迭代器
    //在position插入新元素，其值为x
    vec.insert(position, x);
    //在position插入n个新元素，它们的值都为x
    vec.insert(position, n, x);
    
    //时间复杂度为O(n)，下列参数均为迭代器
    //清除某个特定位置的元素
    vec.erase(position);
    //清除[first, last)中的所有元素
    vec.erase(first, last);
    
    //交换vec和vec2中的所有元素，
    vec.swap(vec2);
    
    //清除所有的元素，事实上调用了erase(begin(), end())
    vec.clear();

*  遍历操作

//顺序遍历
    //最常用的方式
    for (int i = 0; i < vec.size(); i++) cout << vec[i] << endl;
    //利用迭代器
    vector<int>::iterator it;
    for (it = vec.begin(); it != vec.end(); i++) cout << *it << endl;
    //c++11
    for(auto x : vec) cout << x << endl;
    
    //逆序遍历
    //常用方式
    for (int i = size() - 1; i >= 0; i--) cout << vec[i] << endl;
    //利用反向迭代器
    vector<int>::reverse_iterator rit;
    for (rit = vec.rbegin(); rit != vec.rend(); rit++) cout << *rit << endl;

*  查找操作  
    这个操作主要是利用STL提供的  f i n d find find 函数。

#include <algorithm>
    //需要调用find函数，在[first, last)中查找x，返回的是迭代器
    vector<int>::iterator it = find(vec.begin(), vec.end(), x);
    //如果找到则输出YES，否则输出NO
    if (it != vec.end()) cout << "YES" << endl;
    else cout << "NO" << endl;

*  排序和翻转  
    主要是调用STL提供的  s o r t sort sort 和  r e v e r s e reverse reverse 函数。

#include <algorithm>
    //升序排序(默认)
    sort(vec.begin(), vec.end());
    sort(vec.begin(), vec.end(), less<int>());
    //降序排序
    sort(vec.begin(), vec.end(), greater<int>());
    
    //元素翻转
    reverse(vec.begin(), vec.end());

### 五、参考资料 ###

1.  [C++官方的vector文档][C_vector]
2.  《STL源码剖析》
3.  [个人混乱的实验代码][Link 1]

--------------------

既然都看到就这里了（我也终于写到这里了），希望你可以做到下面三点哦：

*  **点赞**，这是对作者辛苦写作的最低成本的鼓励。
 *  答应我，**把它学会！**（别扔进收藏夹吃灰）
 *  可以考虑**关注一波**，STL系列的文章会持续更新。

[1]: https://img-blog.csdnimg.cn/20200219230804596.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20200219232845337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200219235717879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[4]: https://img-blog.csdnimg.cn/20200220121338651.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[5]: https://img-blog.csdnimg.cn/20200220192505758.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[C_vector]: http://www.cplusplus.com/reference/vector/vector/
[Link 1]: https://paste.ubuntu.com/p/DDYBmWkt9r/