系列文章目录
第零篇：从C到C++入门：C++有而C语言没有的基础知识总结-CSDN博客
第三篇：【C++闯关笔记】STL：string的学习和使用（万字精讲）-CSDN博客
第四篇：【C++闯关笔记】STL：vector的学习与使用-CSDN博客
目录
前言
从数据结构的本质来讲，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类。
作者水平有限，若文中出现缺漏的之处，还万望读者指出，共同进步。
读完点赞，手留余香~