1. 前言
和string的学习不同
vector即要掌握它的用法
更要会自己去实现一个vector
本章重点:
熟悉STL库中vector的接口函数
自己实现一个简易vector类
本章只实现容量相关函数
和构造,析构,拷贝构造函数
注:vector其实就是顺序容器
string类只用考虑存储字符
然而vector中可以存储任一类型
所以vector的自我实现需要用模板
2. 熟悉vector的接口函数
还是借助老朋友:cplusplus来查阅文档
库中的vector的模板参数有两个
后一个是内存池,用来提升空间利用效率
对于现阶段的学习而言可有可无
2.1 vector的构造与拷贝构造
常见的构造有:
vector<int> v1; vector<int> v2(10,1); vector<int> v3(v2);
v2:构造并初始化10个值为1的顺序表
vector可以用迭代器区间初始化:
string str("abcdefg"); vector<string> vv(str.begin(),str.end());
2.2 vector迭代器的使用
和string一样,vector有正向和反向
两种迭代器,且使用方法和string相同
vector<int> vv{1,2,3,4,5,6}; vector<int>::iterator it = vv.begin(); while(it!=vv.end()) { cout<<*it; it++; }
2.3 vector空间相关函数
vector的空间相关的函数
和string的机会一模一样
如果你看了文档还不懂的话
可以先阅读此篇文章:string接口函数
2.4 vector的增删查改
push_back和pop_back
都是老朋友了,这里就不多说了
在介绍insert和erase之前
先来了解几个算法库的函数
2.41 find,swap和sort
这三个函数都在头文件:algorithm中
find函数:参数是一段迭代器区间
以及在此区间你需要查找的值
找到后返回这个值对应的迭代器位置
若找不到,则返回迭代器last
find的使用:
vector<int> vv{1,2,3,4,5,6,7,8,9}; auto pos = find(vv.begin(),vv.end(),5); cout<<*pos;
注:使用auto是为了简写迭代器也可以用
vector< int >::iterator替代
swap想必是大家的常客了
这里给它个面子,就不介绍它了
sort非常方便,它内部实现是快排
我们只需要传一个迭代器区间
就可以将整个区间排好序
sort的使用:
vector<int> vv{5,7,3,9,6,4,1,2,8}; sort(vv.begin().vv.end());
2.42 insert和erase
和string不同,vector的insert
的参数pos不是整型,而是迭代器
默认是在pos位置前插入一个数据
insert和find常常配合在一起使用
在整型5前面插入一个100:
vector<int> vv{1,2,3,4,5,6,7,8,9}; auto pos = find(vv.begin(),vv.end(),5); vv.insert(pos,100);
和string的erase不同,vector
的erase一次只删除一个数据
然而string如果使用缺省值就是
将全部数据删完
vector的erase甚至可以删除一段区间
删除顺序表中值为100的元素
vector<int> vv{1,2,3,4,5,6,7,8,9,100}; auto pos = find(vv.begin(),vv.end(),100); vv.erase(pos); //删除一个区间 vv.erase(vv.begin()+2,vv.end()-2);
2.43 随机访问operator[ ]
vector中最喜欢用的是[ ]
它支持随机访问,是否方便
operator[]的使用:
vector<int> vv{1,2,3,4,5,6,7,8,9}; for(int i=0;i<vv.size();i++) { cout<<vv[i]<<" "; }
3. vector的模拟实现
首先要关注的是成员变量
vector是顺序表,所以和实现C语言
时的顺序表一样,至少有三个参数
- 指向一段空间的指针
- 空间的有效大小
- 空间的实际大小
由于vector的迭代器就是普通指针
所以成员变量的类型其实是迭代器
template<class T> class vector { public: typedef T* iterator; private: iterator _start; iterator _finish; iterator _endof_storage;
这里使用迭代器作为三个参数的类型
是因为:求vector的size和capacity时
可以直接使用finish-start
也就是指针相减求出长度
成员变量和空间的关系:
3.1 vector容量相关函数
上来首先要考虑的容量相关的函数:
- size
- capacity
- empty
- resize
- reverse
前三个十分简单:
size_t size() const { return _finish - _start; } size_t capacity() const { return _endof_storage - _finish; } bool empty() const { return (size()==0); }
3.11 reverse函数
reverse只会改变capacity的大小
并不会改变size的大小
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T)*sz); for (size_t i = 0; i < sz; ++i) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } }
注:当n小于capacity时,不进行扩容
由于C++内存管理的new
无法像C语言的realloc一样原地扩容
所以必须先开辟n个空间,再将数据
拷贝到新空间,且释放旧空间
3.12 resize函数
resize即会改变size大小
也会改变capacity大小
resize要分三种情况:
- n大于capacity时
- n大于size小于capacity时
- n小于size时
它们的解决方案分别是:
直接套用reversezhu初始有效值不变,在此之后初始化新的内容直接将size缩小到n
void resize(size_t n, const T& val = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { // 初始化填值 while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } }
注:参数val=T()使用了匿名对象
C++将内置类型特殊处理过
int/char等等都被升级为了类
所以可以使用int()表示匿名对象
int tmp1 = int(); int tmp2 = int(10);
int的缺省值为0
3.2 vector的构造函数
- 首先最简单的无参构造:
vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {}
- 紧接着是带参的构造函数
我们跟着STL库的风格走:
vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n);//开辟n个空间 for (size_t i = 0; i < n; ++i) { push_back(val);//给初始值赋值 } }
- 最后是使用迭代器区间来构造
比如我想在顺序表中存放string类型:
string str("abcdefg"); vector<string> vv(str.begin(),str.end());
此时在模板类中还应该有一个模板
template <class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); ++first; } }
注:inputiterator取名是模仿STL的
你也可以取任一除了T的名字
3.3 vector的析构函数
vector的析构函数非常简单
只需要将空间释放
并且将各个指针置为空就行了
~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; }
3.4 vector的拷贝构造函数
拷贝构造的实现有很多种写法
大家可以先自己尝试一下
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endof_storage(nullptr) { reserve(v.size()); for (const auto& e : v) { push_back(e); } }
4. 总结以及拓展
vector模拟实现的全部代码我将在
下一篇文章中分享给大家
可以发现:STL的神奇之处在于
它把所有接口函数都做了统一化处理
每一个容器的接口函数的使用都相似
但是内部实现被这种封装隐藏起来了
进一步又体现了C++的三大特性:封装
并且C++实现了所有容器通用的算法库
比如sort和find都只需要传迭代器
然而所有容器都会被迭代器封装
所以一份代码就能实现对不同容器的操作
拓展题目:
熟悉了vector的基本使用
可以尝试解决一下下面几个问题:
留给大家当作小试牛刀了~
🔎 下期预告:迭代器失效和深浅拷贝问题 🔍
