-
C++STL----＞vector
什么是vector
和学习string一样，我们也是通过官方的文档来看一看vector是怎么声明的
我们可以进一步对vector的声明做简化template
class vector 可以看到vector是一个类模板，结构上就是我们先前在数据结构初阶学习的动态顺序表。在插入一定的数据的时候会进行扩容。因此我们就可以知道vector的底层是一个连续的数组。
vector是怎么进行扩容的
STL有很多不同的版本，微软维护的版本是PJ版本，而Linux的g++维护的是SGI版。这两个版本的扩容设计的就不太相同。下面我们简单在两个平台下面测试一下：#include#include using namespace std; void test1() { vector<int>v(2); v.push_back(1); v.push_back(1); cout << v.capacity() << endl; //这一次插入就会发生扩容 v.push_back(2); cout << v.capacity() << endl; v.push_back(3); v.push_back(3); v.push_back(3); cout << v.capacity() << endl; } int main() { test1(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
可以发现，vs下面的vetor的扩容是按照1.5倍进行扩容的。我们切换到Linux下使用g++测试对应的扩容因子。
可以看到SGI版本下vector的扩容因子是2倍，也就是按照2倍扩容的。至于1.5倍和2倍扩容哪一个更好，我的观点是这两个扩容方案都非常优秀。
vector的迭代器
接下来我们来看一看vector的迭代器，和string的迭代器类似。vector的迭代器也是一个原生指针 那么我们简单来看一看vector的迭代器怎么使用#include#include using namespace std; void test() { vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); //使用迭代器访问 //迭代器的类型是vector ::iterator--->(T是实例化的类型) //auto it=v.begin();---->c++11支持这么做 vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } int main() { test(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
对于vector而言，掌握vector的迭代器非常重要！因为vector的insert和erase方法提供的只有迭代器版本的，没有下标版本的，所以掌握vector的迭代器非常重要!
vector的构造和常见接口的使用
接下来我们就来看一看vector的构造函数和常见接口的使用，和先前学习string一样，我们先从官方文档来了解：
先来看一看vector的构造函数
接着我们上手来使用几个构造函数void test3() { //默认构造一个空容器 vector<int>v1; //构造3个元素是5的vector vector<int>v2(3, 5); //迭代器区间构造 vector<int>v3(v2.begin(), v2.end()); //拷贝构造 vector<int>v4(v2); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
我们更多会用的是默认构造，迭代器区间构造，拷贝构造，而对于n个值是val的构造方式我们了解就可以了。
接下来我们再来看一看vector的常见的接口函数：
void test() { vector<int>v; //尾插元素 v.push_back(4); v.push_back(5); v.push_back(6); for (auto c : v) { cout << c << " "; } cout << endl; //尾删元素 v.pop_back(); for (auto c : v) { cout << c << " "; } cout << endl; //insert方法--->使用迭代器往指定位置前元素 v.insert(v.begin(), 3); for (auto c : v) { cout << c << " "; } cout << endl; //erase方法--->使用迭代器删除位置元素 v.erase(v.begin() + 1); for (auto c : v) { cout << c << " "; } cout << endl; } int main() { test(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
其实整个vector的设计和string的设计是比较类似的,这里就不在过多展开描述了。
vector的模拟实现和迭代器失效的问题
为了能够更好理解vector的底层结构，接下来我们模拟实现vector。模拟实现只是为了更好地了解底层，而不是造更好地vector使用
我们先来看看STL里面是怎么设计
可以看到vector里面封装了三个迭代器start:指向起始的位置
finish:指向有效数据的下一个位置
end_of_storage:指向能够存储最大有效数据接下来我们类比这个官方库来设计框架
#pragma once #include#include using namespace std; //和库里面的区分，封到一个命名空间里面 namespace chy { //vector是一个模板类 template<typename T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; iterator _finish; iterator _end_of_stroge; }; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
接下来，快速提供默认构造和size()还有capacity()接口以及begin(),end()
#pragma once #include#include using namespace std; //和库里面的区分，封到一个命名空间里面 namespace chy { //vector是一个模板类 template<typename T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector<T>() :_start(nullptr) ,_finish(nullptr) , _end_of_stroge(nullptr) {} size_t size()const { return _finish - _start; } size_t capacity()const { return _end_of_stroge - _start; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } private: iterator _start; iterator _finish; iterator _end_of_stroge; }; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
接下来我们就要写赋值运算符重载和拷贝构造函数。从前面string类的学习我们知道要实现成深拷贝。而关于深拷贝还有一种现代写法
//深拷贝现代写法--->构造临时对象，交换指针 void swap(vector<T>& v) { //交换_start,_finish,_end_of_stroge就可以了 std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_stroge, v._end_of_stroge); } //为了支持拷贝构造，需要一个迭代器区间构造版本的构造函数 template<typename InputIterator> vector<T>(InputIterator first, InputIterator last) :_start(nullptr) ,_finish(nullptr) ,_end_of_stroge(nullptr) { while (first != last) { push_back(*first); ++first; } } //拷贝构造 vector<T>(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _end_of_stroge(nullptr) { //构造临时对象 vector<T> tmp(v.begin(), v.end()); //交换资源 swap(tmp); //tmp生命周期结束，自动析构处理 } //赋值运算符重载 vector<T>& operator=(vector<T> v) { swap(v); return *this; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
常见的函数接口的模拟实现：
//n个val构造 vector<T>(size_t n, const T& val = T()) :_start(nullptr) ,_finish(nullptr) ,_end_of_stroge(nullptr) { reserve(n); for (size_t i = 0; i < n; ++i) { push_back(val); } } //提供这个版本是为了解决vectorv(int,int)的推演到迭代器构造的问题 vector<T>(int n, T val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_stroge(nullptr) { reserve(n); for (int i = 0; i < n; ++i) { push_back(val); } } void reserve(size_t n) { size_t sz = size(); size_t cp = capacity(); if (n > capacity()) { T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * size()); for (size_t i = 0; i < size(); ++i) { //一个一个拷贝 tmp[i] = _start[i]; } delete[] _start; } _start = tmp; } //size=_finish-start capacity=esg-start //tmp+_finish-tmp=_finish=nullptr _finish = _start + sz; _end_of_stroge = _start + n; } void push_back(const T& val) { /* if (_finish == _end_of_stroge) { size_t n_capacity = capacity() == 0 ? 2 : 2 * capacity(); reserve(n_capacity); } *_finish = val; ++_finish;*/ //复用insert insert(end(), val); } void resize(size_t n, T val = T()) { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish != _start + n) { *_finish = val; ++_finish; } } } void pop_back() { /*assert(_finish!=_start); _finish--;*/ //复用erase erase(end() - 1); } iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (_finish == _end_of_stroge) { size_t d = pos - _start; reserve(capacity() == 0 ? 2 : 2 * capacity()); pos = _start + d; } //扩容以后，面临迭代器失效的问题，所以要更新pos iterator end = _finish-1; while (end >= pos) { *(end+1) = *end; --end; } *pos = val; ++_finish; return pos; } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; } iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; } ~vector<T>() { if (_start) { delete[] _start; _finish = _start = _end_of_stroge = nullptr; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
这里细心的同学会发现，insert和erase是有返回值的。那么这个返回值有什么意义呢?这里就要牵扯到一个问题----->迭代器失效
我们先来看看insert方法的迭代器失效问题:
那么我们来看官方库是怎么解决迭代器失效的问题：
insert方法返回一个迭代器，这个返回的迭代器指向新插入的迭代器，所以我们也类比库里面设计迭代器
iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); //处理扩容带来的迭代器失效问题 if (_finish == _end_of_stroge) { size_t d = pos - _start; reserve(capacity() == 0 ? 2 : 2 * capacity()); pos = _start + d; } iterator end = _finish-1; while (end >= pos) { *(end+1) = *end; --end; } *pos = val; ++_finish; return pos; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
而erase方法也会有迭代器失效的问题。而相对于insert方法来说，erase方法仅仅只会存在语义上的失效，因为erase不会存在扩容的问题。
我们也同样通过官方文档来看一看怎么处理。
erase返回的迭代器指向删除位置后的第一个元素的位置
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
最后就是vector的析构函数：
~vector<T>() { //非空才处理 if (_start) { delete[] _start; _finish = _start = _end_of_stroge = nullptr; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
关于vector的一些知识就介绍到这里。如果有不足的地方希望能够指出，希望大家可以一起进步。
-
相关阅读:
Docker之数据卷&自定义镜像
EDA实验-----4*4矩阵键盘与数码管显示测试(Quartus ‖)
控价常用的几种方法
java实现朴素rpc
How about a push-type floor scrubber
【字符串函数内功修炼】strncpy + strncat + strncmp（二）
mybatis plus 常用方法
【uniapp】uniapp 引用 js 组件
Spring.Boot Web开发初始静态资源处理《课时九》
TensorFlow搭建LSTM实现时间序列预测（负荷预测）
- 原文地址：https://blog.csdn.net/qq_56628506/article/details/125881539
