【C++闯关笔记】STL：vector的学习与使用
系列文章目录
第零篇：从C到C++入门：C++有而C语言没有的基础知识总结-CSDN博客
第一篇：【C++闯关笔记】封装①：类与对象-CSDN博客
第二篇：【C++闯关笔记】封装②：友元与模板-CSDN博客
第三篇：【C++闯关笔记】STL：string的学习和使用（万字精讲）-CSDN博客
第四篇：【C++闯关笔记】STL：vector的学习与使用-CSDN博客
目录
系列文章目录
前言
一、vector是什么？
1.vector介绍
2.vector使用
1）vector的定义：构造函数
2）vector iterator 迭代器的使用
迭代器失效原因
3）vector增删查改
4）vector空间相关函数
二、模拟实现vector
1.构造函数模拟
1）默认构造函数
2）构造函数
3）拷贝构造函数
4）析构函数
2.迭代器的模拟实现
3.vector的增删查改
1）push_back
2）pop_back
3）insert
4）erase
5）swap
6）operator[ ]
4.vector空间相关函数
1）size
2）capacity
3）empty
4）reserve
5）resize
总结
前言
从数据结构的本质来讲，vector完全可以被理解为 C++ 版的、功能更强大的、高度自动化的顺序表。它们的核心特征都是：在内存中占用一段连续的存储空间，通过即索引在常数时间 O(1) 内访问任意元素。【数据结构】顺序表-CSDN博客
本文将按“能用、明理”两个维度介绍vector：首先是会用，详细介绍vector各种常见接口的使用方法，以求会用；然后再尝试模拟实现vector及其接口函数，以求理解vector的实际运行逻辑。
一、vector是什么？
C 语言的顺序表通常需要程序员手动管理，其基础形态就是一个结构体：
// C 风格顺序表
typedef struct {int* data; // 指向动态数组的指针size_t size; // 当前元素个数size_t capacity; // 总容量
} SeqList;接下来的所有操作：初始化、插入、删除、扩容、销毁……都需要程序员亲力亲为。而vector将这些工作全部封装了起来，给你提供了一个开箱即用还安全高效的“超级顺序表”。
1.vector介绍
1）vector是一种表示可变大小数组的序列容器。
2）就像数组一样，vector采用的连续存储空间来存储元素。
这意味着可以用下标对vector的元素进行访问，和数组一样高效。但不同于数组的定长，它的大小是可以动态改变的。
3）vector使用动态分配数组来存储它的元素。
当插入新元素时，如果这个vector“数组”剩余空间不足，就需要被重新分配空间大小。其做法是：分配一个新的数组，然后将全部元素移到这个数组。就时间消耗而言，这是一个代价较高的任务，所以每次按原大小的二倍扩容，防止频繁扩容增加时间消耗。
4）由于vector本质是个可动态增长的数组，所以vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低（因为在数组前边或中间插入数据，需要将后边数据挪出一个空位）。
综合上述对vector的介绍，再结合C++类的封装思想，其实我们已经能猜出vector的底层大概是如何分配的。
template<typename T>class vector{public:private:T* _date;size_t _size;size_t _capacity;};对比上面顺序表的C语言结构体，本质上它们几乎相同，现在大家应该就能理解为什么说“vector完全可以被理解为 C++ 版的、功能更强大的、高度自动化的顺序表”了。
（注意：上述代码仅通过vector介绍推测，非实际实现代码！这里只为帮读者先对vector有个认识。实际代码详见下方模拟实现vector）
既然脑海中对vector有了个大概的概念，接下来让我们学习vector各种接口的使用方法。
2.vector使用
注意包含头文件#intclude<vector>，using namespace std;
1）vector的定义：构造函数
vector常用的构造函数
| 造函数声明 | 接口说明 |
| vector( ) | 无参构造 |
| vector（size_t n, const value_type val ） | 构造并初始化n个val |
| vector (const vector& x); | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
示例
vector<int> v;vector<char> v1(5, 'a');vector<char> v2(v1);vector<char>v3(v1.begin(), v2.end());解释：vector使用了类模板，在实例化vector对象时加上<类型>就是告诉编译器，这个vector对象中存储什么类型的数据。
上面介绍了几种常用的构造方法，实际上vector的构造函数远不止这几种，有兴趣的同学可参看下图中描述的几种构造方法。
2）vector iterator 迭代器的使用
什么是迭代器呢？
这里可以将迭代器iterator 理解为封装过的指针，比如begin（）返回的就是vector对象存储数据的首地址。
| iterator的使用 | 接口说明 |
| begin( )与end( ); | begin( )获取第一个数据位置的iterator/const_iterator，end( ) 获取最后一个数据的下一个位置 的iterator/const_iterator |
| rbedin( )与rend( ); | rbegin( )获取最后一个数据位置的reverse_iterator，rend( )获取第一个数据前一个位置的 reverse_iterator |
细节注意：
end( )指向的是vector数组最后一个数据的下一个位置；rend( )获取第一个数据前一个位置.
使用示例
vector<int>v(5, 7);vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it;it++;}
迭代器失效原因
迭代器的主要作用就是让上层用户能够不用关心底层实现，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。所以迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，如果继续使用已经失效的迭代器， 程序可能会崩溃。
那么换句话说，引起其底层空间改变的操作，都有可能使得迭代器失效，比如：resize、reserve、insert、erase、 push_back等。
所以，在使用迭代器时最好养成即用即定义的习惯，不要使用之前定义好的迭代器，防止出现莫名bug。
3）vector增删查改
vector常用的几种增删查改函数
| vector增删查改 | 功能介绍 |
| push_back(type val) | 在尾部插入数据 |
| pop_back( ) | 删除尾部数据 |
| insert(iterator pos,type val) | 在pos位置之前插入val |
| erase(iterator pos) | 删除pos位置的数据 |
| swap(另一个vector对象) | 交换两个vector对象中的数据 |
| operator[ ] | 通过下标访问 |
使用示例
int main()
{vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);for (auto a : v)cout << a;cout << endl;v.pop_back();v.insert(v.begin(), 7);v.erase(v.end()-1);for (auto a : v)cout << a;cout << endl;vector<int> v1(3, 6);v1.swap(v);for (auto a : v)cout << a;cout << endl;for (int i = 0; i < v.size(); ++i)cout << v[i];return 0;
}
4）vector空间相关函数
经常使用的vector空间相关函数
| 函数名称 | 功能介绍 |
| size( ) | 返回vector对象中数据个数（已经使用了的空间） |
| capacity( ) | 返回vector对象所占有容量大小（总空间） |
| empty( ) | 判断对象是否为空，是返回true，不是返回false |
| resize(size_t n) | 更改vector的size为n |
| reserve(size_t n) | 更改vector的reserve为n |
细节注意：
①reserve的用法：如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够，这样就可以避免边插入边扩容导致效率低下的问题。
②不同版本的STL中capacity增长速率不同。如vs下capacity是按1.5倍增长的，g++是按2倍增长的。
③resize的大小若超过vector的capacity大小，那么resize还会起到扩容的作用。
使用示例
int main()
{vector<int> v(5, 6);cout << v.size() << ' ' << v.capacity() << endl;for (int a : v)cout << a;cout << endl;v.resize(3);for (int a : v)cout << a;cout << endl;while (!v.empty())v.pop_back();for (int a : v)cout << a;cout << endl;return 0;
}
二、模拟实现vector
在vector介绍部分，我们推测vector类大概为：
template<typename T>class vector{public:private:T* _date;size_t _size;size_t _capacity;};而实际上，库中实现vector类代码如下：
template<typename T>class vector{typedef T* iterator;public:private://指向首元素地址iterator _start;//指向最后一个元素的下一个地址iterator _finish;//指向分配空间的尾地址iterator _endofstorage;};实际上它们两种设计都是有效的，选择取决于你的偏好和需求。三个指针的设计更符合标准库的实现方式，与迭代器体系集成更好，可能在某些情况下有微小的性能优势。
本文选择尽量贴近实际库中的实现方式，也就是三个指针的设计模拟实现vector。
1.构造函数模拟
1）默认构造函数
//如果成员全是原生指针，编译器生成的默认构造函数不会初始化它们，
//这是未定义行为。所以必须手动初始化，避免野指针。
vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{ }2）构造函数
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){_start[i] = val; }_finish = _start + n;}通过迭代器赋值的构造函数
vector(const iterator begin, const iterator end):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (begin != end){push_back(*begin);begin++;}}3）拷贝构造函数
vector(const vector& p){int size = p.size();int capa = p.capacity();T* newca = new T[capa];for (int i = 0; i < size; ++i){newca[i] = p[i];}_start = newca;_finish = _start + size;_endofstorage = _start + capa;}4）析构函数
~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}2.迭代器的模拟实现
typedef T* iterator;iterator begin(){return _start;}iterator end(){return _finish;}iterator begin()const {return _start;}iterator end()const{return _finish;}3.vector的增删查改
1）push_back
void push_back(const T& x){if (_finish == _endofstorage){size_t newca = size() * 2 + 1;reserve(newca);}*_finish = x;_finish++;}2）pop_back
void pop_back(){if(!empty())_finish--;}3）insert
iterator insert(iterator pos, const T& x){if (pos >= _start && pos < _finish){if (_finish == _endofstorage){int temp =(int)(pos - _start);size_t newca = size() * 2;reserve(newca);pos = _start + temp;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;_finish++;}return pos;}为什么insert函数需要返回一个迭代器？
当你向vector中插入或删除元素时，很可能会导致内存重新分配（扩容）或元素位置移动。这会使所有指向该vector的迭代器、指针和引用失效（包括你用来指定位置的迭代器）。
返回一个新的迭代器，就是为了在被操作“搅动”过的容器中，为你提供一个有效的、可以继续使用的“路标”。
4）erase
iterator erase(iterator pos){if (pos >= _start && pos < _finish){iterator begin = pos+1;while (begin < _finish){*(begin - 1) = *begin;++begin;} _finish--;}return pos;}5）swap
void swap(const vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage());}直接交换两个vector对象的私有成员，简单高效。
6）operator[ ]
T& operator[](int i){return _start[i];}T& operator[](int i)const{return _start[i];}4.vector空间相关函数
1）size
size_t size(){//指针减法的本质：直接返回元素个数，而不是字节数。//编译器自动考虑了指针所指向类型的大小。return _finish - _start;}size_t size()const{return _finish - _start;}2）capacity
size_t capacity(){return _endofstorage - _start;}size_t capacity()const{return _endofstorage - _start;}3）empty
bool empty(){//if (size() != 0)return false;//else return true;return _finish == _start;}4）reserve
void reserve(size_t n){if (n < capacity())return; size_t oldSize = size();size_t newca= oldSize == 0 ? 16 : oldSize * 2;while (newca < n){newca *= 2;}T* newvec = new T[newca];if (_start){for (int i = 0; i < oldSize; ++i){newvec[i] = _start[i];}delete[]_start;}_start = newvec;_finish = _start + oldSize;_endofstorage = _start + newca;}5）resize
void resize(size_t n, const T& x = T()){size_t _size = size(), capa = capacity();if (n <= _size){_finish = _start + n;}else{if(n>capa)reserve(n);iterator temp = _start + n;while (_finish < temp){*_finish = x;_finish++;}}}总结
本文主要分为两阶段：
第一个阶段大致介绍了什么是vector类，然后说明相关类成员函数的用法，以及一些使用陷阱；
第二个阶段为模拟实现vector类。
作者水平有限，若文中出现缺漏的之处，还万望读者指出，共同进步。
读完点赞，手留余香~