📃博客主页： 小镇敲码人
💚代码仓库，欢迎访问
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌏 任尔江湖满血骨，我自踏雪寻梅香。 万千浮云遮碧月，独傲天下百坚强。 男儿应有龙腾志，盖世一意转洪荒。 莫使此生无痕度，终归人间一捧黄。🍎🍎🍎
❤️ 什么？你问我答案，少年你看，下一个十年又来了 💞 💞 💞

前言：上篇博客我们介绍了string容器的使用及其模拟实现，今天我们继续来看C++STL中的另外一个重要的容器vector的使用及其模拟实现。代码仓库自取

🌞 vector的使用介绍

由于STL中各个容器的使用和接口都比较相似，我们主要介绍vector与string这个容器不太一样的点。

🐕 vector容器的介绍

vector类似我们学习过的数据结构动态顺序表，只不过这里是使用c++语言描述的，它的空间随元素的增加可以动态的增长，不像普通的数组一样，空间是一个定值。

c++中的vector类是一个类模板，也就是我们在创建vector这个对象的时候，需要显式的传一个类型作为vector容器中存储的数据的类型。

🐕 vector容器的一些重要接口

🌿 构造函数

---

我们了解vector的构造函数后，就知道了如何来创建vector对象。c++98版本给出了4种构造方法。我们在string类的介绍中也谈到过，分别是无参数的默认构造、有参数的构造、使用迭代器来进行范围构造、拷贝构造。我们重点来看一下第二个构造函数。

代码演示：

#include<iostream>
#include<vector>using namespace std;
void Test1()
{vector<int> arr1(10);//构造一个大小为10的vector对象for (int i = 0; i < 10; ++i)cout << arr1[i] << endl;int arr2[10];for (int i = 0; i < 10; ++i)cout << arr2[i] << endl;
}
int main()
{Test1();return 0;
}

运行结果：

这是为什么呢？我们在创建vector对象的时候也没有给初值，这里为什么打印vector的10个元素全都初始化为了0呢，这是由于第二个构造函数的第二个参数有缺省值。

可以看到这里这个构造函数的第二个参数是代表n个元素初始化的值，这里如果不给就会给缺省值value_type()，这个value_type就是类的第一个模板参数。类型后面加括号，我们在学习类和对象时就知道，这是该类型的一个匿名对象，但是自定义类型可以理解，内置类型也有它的匿名对象吗？这里C++为了给缺省值方便，给内置类型也设置了匿名对象：
看下面这段代码：

#include<iostream>
#include<vector>using namespace std;
typedef int* pf;
void Test2()//内置类型的匿名对象
{cout << int() << endl;cout << float() << endl;cout << pf() << endl;cout << char() << endl;
}int main()
{Test2();return 0;
}

运行结果：

注意，如果是指针类型编译器会打印这个指针的地址，32为机器是4个字节（32bit位），以16进制形式打印也就是0x00000000.
可以看到，int、double是0，指针是空，char是\0。

🌿 迭代器的使用

像数组那样访问数据我们上面的代码已经演示过了，接下来来介绍一下vector使用迭代器访问数据：

迭代器也有两种访问，一种是范围for，另外一种是普通的按照迭代器（像指针一样的行为）去走。

c++11之后支持范围for，它的底层还是去调用迭代器的函数，begin() 和end，利用迭代器实现的：
我们可以通过反汇编来验证我们的结论：

代码演示：

#include<iostream>
#include<vector>using namespace std;void Test3()//迭代器访问
{vector<int> arr(10, 1);//创建vector对象vector<int>::iterator it = arr.begin();while(it != arr.end())//老老实实使用迭代器{cout << *it << endl;it++;}for (int val: arr)//范围for,交给编译器来做{cout << val << endl;}
}
int main()
{Test3();return 0;
}

运行结果：

• 注意：如果在使用范围for访问时，想要改变元素中的值，范围for里面的那个变量要带引用。

🌿 push_back和pop_back函数

这是vector中使用的比较多的函数，尾插和尾删：

使用起来也很简单：

#include<iostream>
#include<vector>using namespace std;void Test4()//尾插和尾删
{vector<int> arr;//创建arr对象for (int i = 0; i < 10; ++i)//尾插10个元素arr.push_back(i);for (auto& val : arr)cout << val << " ";cout << endl;arr.pop_back();//尾删arr.pop_back();//尾删for (auto& val : arr)cout << val << " ";
}
int main()
{Test3();return 0;
}

运行结果：

🌿 insert和erase

我们想在vector对象中进行头插和头删，或者在中间某个位置进行插入或者删除，还得借助这两个函数：

1. insert插入函数：

和string类中的insert函数类似，都是在某个迭代器前插入一个值或者一些值，也可以用迭代器实现范围插入。这个函数一般和find函数配合使用，find函数的作用是返回某个值的迭代器的值。

算法库<algorithm>中有通用的查找函数，我们的vector类好像没有额外提供。

我们用下面的代码来演示一下：

#include<iostream>
#include<vector>using namespace std;void Test5()//insert
{vector<int> arr(5, 1);//创建vector对象for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.insert(arr.begin() + 3, 12);//在arr.begin()+3位置前插入12for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.insert(arr.begin(),3,-1);//头插3个-1for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.insert(arr.end(), arr.begin(), arr.begin() + 2);//把arr这两个迭代器范围的值，尾插到arr中for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;
}
int main()
{Test5();return 0;
}

运行结果：

2.erase函数

实现了两个版本一个是直接删除pos位置的值，还有一个是删除某个范围的值。

代码演示：

#include<iostream>
#include<vector>using namespace std;void Test6()//erase
{vector<int> arr;for (int i = 0; i < 10; ++i)arr.push_back(i);for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.erase(arr.end()-1);//尾删for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.erase(arr.begin(),arr.end()-1);//[begin,end-1)for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;}int main()
{Test6();return 0;
}

运行结果：

区间删除，都是左闭右开。

🌿 迭代器失效问题及其解决办法

所谓迭代器失效问题，说白了就是由于插入或者删除某个值后，导致原先迭代器位置的地址（vector的迭代器也是原生指针）已经失效（不属于我们了或者不代表我们想要的那个含义），文字比较抽象，我们来看具体的例子：

🐞 扩容导致迭代器失效

这个很好理解，扩容之后，原先的地址空间不属于我们了，再去访问肯定会出问题：

#include<iostream>
#include<vector>using namespace std;void Test7()//扩容导致迭代器失效
{vector<int> arr(10,-1);auto it = arr.begin();arr.resize(100, 0);while(it != arr.end()){cout << *it << " ";it++;}
}
int main()
{Test7();return 0;
}

运行结果：

解决办法，重新给迭代器赋值一下即可：

🐞 删除数据导致迭代器失效

#include<iostream>
#include<vector>using namespace std;void Test8()//删除元素导致迭代器失效
{vector<int> arr(10, -1);auto it = arr.begin();arr.erase(arr.begin());//头删while (it != arr.end()){cout << *it << endl;it++;}
}
int main()
{Test8();return 0;
}

运行结果：

按理来说，删除一个元素后，后面的元素为挪动到相应的位置，迭代器的地址并没有失效，但是此时如果这个元素是最后一个元素，删除之后变成了end，那就出问题了，所以VS（LIUNX下不一定）为了防止这样的事情出现，删除任意一个元素后，原先的迭代器都会失效，要重新更新。

string也会有迭代器失效的问题，和vector类似。

🌞 vector的模拟实现

🐕 vector的成员变量

我们可以借助stl30的版本，来借鉴一下它是如何设计成员变量的：

我们不难知道，start就是我们vector类存储元素的起始迭代器，finish就类似end，end_of_storage是我们实际开的空间的结束地址。这里我们看源码还可以发现反向迭代器需要重新搞一个类模板出来，我们这里就不实现反向迭代器了。

🌿 基本框架

namespace my_vector
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return start;}iterator end(){return finish;}const_iterator begin() const{return start;}iterator end() const{return finish;}size_t size() const{return finish - start;}size_t capacity() const{return end_of_storage - start;}bool empty() const{vector():start(nullptr),finish(nullptr),end_of_storage(nullptr)//无参构造函数{};vector(size_t n, const T& val = T());vector(int n, const T& val = T());vector(const vector<T>& x);template <class InputIterator>vector(InputIterator first, InputIterator last);//函数模板，区间初始化vector& operator= (const vector<T>& x);//赋值运算符重载void resize(size_t n, const T& val = T());T& operator[] (size_t n);const T& operator[] (size_t n) const;	void push_back(const T& val);void pop_back();iterator insert(iterator position, const T& val);iterator erase(iterator position);void shrink_to_fit();void swap(vector& x);void clear();~vector();private:iterator start;iterator finish;iterator end_of_storage;};template<class T>void swap(vector<T>& x, vector<T>& y);
}

🐕 vector成员函数的模拟实现

这里vector涉及到模板的分文件编译，我们会在模板进阶里面谈到，所以这里我们就不再分文件写了，都放在.h文件中实现。

🌿 迭代器部分

这部分还是一如既往的很短，我们只实现了普通的迭代器和const的迭代器：

		typedef T* iterator;typedef const T* const_iterator;iterator begin(){return start;}iterator end(){return finish;}const_iterator begin() const{return start;}iterator end() const{return finish;}

构造函数部分

这里我们构造函数实现了5个版本，其中第3个构造函数是为了防止编译器去调用第5个构造函数，因为编译器再找不到现成的函数的时候会去使用第5个函数模板自己生成一份，这样就不是我们本意了。这个问题待会我们在测试的时候还会细说。

     vector():start(nullptr),finish(nullptr),end_of_storage(nullptr)//无参构造函数{};vector(size_t n, const T& val = T())//第一个参数是元素的个数，第二个是每个元素的值{resize(n, val);}vector(int n, const T& val = T())//第一个参数是元素的个数，第二个是每个元素的值{resize(n, val);}vector(const vector<T>& x)//拷贝构造{reserve(x.capacity());//扩容resize(x.size());//改变sizefor (int i = 0; i < x.size(); ++i)*(start + i) = *(x.start + i);}template <class InputIterator>vector(InputIterator first, InputIterator last)//函数模板，区间初始化{while (first != last){push_back(*first);first++;}}

这里其实还有一点就是在拷贝构造的时候为什么没有直接去使用内存拷贝函数memcpy，这是因为元素T的类型可以是自定义类型，如果直接使用值拷贝，就是浅拷贝，可能会引发多次析构的问题，如果使用赋值，就会去调用T的赋值运算符重载函数（假设T为自定义类型）。

🌿 和空间相关的函数

	   size_t size() const{return finish - start;}size_t capacity() const{return end_of_storage - start;}bool empty() const//判断vector是否为空，我们只需要看size是否为0即可{return start == finish;//return size() == 0;}void resize(size_t n, const T& val = T()){if (n > size())//如果n比当前的size大{reserve(n);//不管需不需要扩容，我们先调用这个函数再说，因为vector的这个reserve是不会缩容的while (finish < start + n)//把多出来的赋值为val{*(finish++) = val;}}else//否则，直接改finish{finish = start+n;}}void reserve(size_t n)//扩容函数{if (n > capacity())//如果需要扩容{T* tmp = new T[n];//重新开空间size_t old_size = size();//先保存之前的size()大小if (start)//如果start不为空{for (int i = 0; i < size(); ++i)//把之前的值赋值给新开的动态数组tmp[i] = *(start + i);delete[] start;//释放原来的空间}//更新相应的值start = tmp;finish = tmp + old_size;end_of_storage = tmp + n;}}void clear()//清理内容，但是不清理空间{finish = start;}void shrink_to_fit(){if (capacity() > size()){int n = size();T* tmp = new T[n];for (int i = 0; i < size(); ++i)tmp[i] = (*this)[i];if(start)delete[] start;start = tmp;finish = end_of_storage = tmp + n;}}~vector(){delete[] start;start = finish = end_of_storage = nullptr;}	

这里vector类中的reserve函数和string的有所不同，通过我们的测试，发现在VS的环境下，reserve函数不会缩容（无论size()为多少），所以我们自己实现的时候也就没有缩容。

缩容函数shrink_to_fit我们实现的逻辑就是让空间和元素的个数保持一致，stl 30版本也是类似的逻辑。

🌿 []访问函数

运算符重载中函数中的一种，vector的空间是连续存储的所以支持了operator []函数。实现逻辑很简单，将对应的指针解引用即可，注意指针应该在数组范围内，不能越界。

  	T& operator[] (size_t n){assert(n < size());return *(start + n);}const T& operator[] (size_t n) const{assert(n < size());return *(start + n);}

🌿 交换函数

类里面有一个交换函数，在类外面我们也实现了一个交换函数，和string类似，第二个swap函数放在类外面：

     void swap(vector& x)//复用库里面的swap函数，交换两者的变量的值{std::swap(x.finish, finish);std::swap(x.start, start);std::swap(x.end_of_storage,end_of_storage);}template<class T>void swap(vector<T>& x, vector<T>& y)//复用刚刚实现的类里面的swap函数{x.swap(y);}

赋值运算符重载函数

这个函数我们还是复用拷贝构造函数,然后调用类中的swap函数交换一下tmp和*this的内容。

	vector& operator= (const vector<T>& x)//赋值运算符重载{vector<T> tmp(x);swap(tmp);return *this;}

🌿 尾插和尾删函数

这两个函数在vector中使用的还算比较多。实现起来注意尾插的扩容逻辑即可，因为有时候会出现capacity为0的情况。

		void push_back(const T& val){if (finish < end_of_storage)//如果不需要扩容{*(finish++) = val;}else//如果需要扩容，就去复用reserve{size_t newcapacity = capacity() == 0 ? 4 : capacity() * 1.5;reserve(newcapacity);*(finish++) = val;}}void pop_back(){assert(start != finish);//数组不能没有元素finish--;}

🌿 插入和删除函数

尾插和尾删函数不能满足我们的所有需求，我们还实现了插入和删除函数：
插入的逻辑是把相应的值后挪，然后插入。删除的逻辑则是一直往前覆盖，直到pos位置停下，然后最后finish--。

       iterator insert(iterator position, const T& val){//删除的位置必须不能越界assert(position >= start);assert(position <= finish);size_t pos = position - start;//先保存position指针离start的相对位置，防止后面会迭代器失效reserve(size() + 1);//不管需不需要扩容，先去调用一下扩容函数，如果需要扩容就会扩容，不需要就什么也不干for (int i = size(); i > pos; --i)//把所有的值后挪动一位(*this)[i] = (*this)[i - 1];(*this)[pos] = val;//插入finish++;return start + pos;}iterator erase(iterator position){//删除的位置必须不能越界assert(position >= start);assert(position < finish);for (int i = position - start; i < size() - 1; ++i)//把pos位置后面的值往前覆盖(*this)[i] = (*this)[i+1];finish--;return position;//返回最后一个被删除位置的下一个新元素的迭代器}

🐕 vector的测试

构造函数的测试贯穿了整个测试函数，我们就不单独测试了。

🌿 测试访问

🐞 像数组一样使用[]访问

#include "vector.h"void Test1()
{my_vector::vector<int> arr1(10);//构造一个大小为10的vector对象for (int i = 0; i < 10; ++i)cout << arr1[i] << " ";cout << endl;int arr2[10];for (int i = 0; i < 10; ++i)cout << arr2[i] << " ";cout << endl;
}int main()
{Test1();
}

vector类型会去调用operator []函数：

运行结果：

🐞 迭代器访问

#include "vector.h"void Test3()//迭代器访问
{my_vector::vector<int> arr(10, 1);//创建vector对象my_vector::vector<int>::iterator it = arr.begin();while(it != arr.end())//老老实实使用迭代器{cout << *it << " ";it++;}cout << endl;for (int val: arr)//范围for,交给编译器来做{cout << val << " ";}
}int main()
{Test3();
}

运行结果：

这个地方我们之前埋了一个坑，在创建vector对象的时候，我们调用的是下面画框的构造函数：

如果没有这个函数存在，也不会去调用第一个而是会去调用下面这个函数模板生成的int函数：

因为编译器在只存在这个模板函数和size_t类型的构造函数的时候，不会去考虑那个size_t，因为涉及到隐式类型转换，而size_t没有负数，这一行为可能是危险的，所以编译器宁可使用下面的函数模板去自己生成一个int型的函数，但是这样一来问题就大了，因为我们的本意这个模板函数是迭代器区间构造，对一个int型进行解引用会报错的，我们把int型的那个函数屏蔽，发现编译器去调用那个函数模板的构造函数，然而这并非我们的本意：

如果我们把这个函数模板的区间构造函数注释掉，编译器才会不得不调用刚刚的size_t类型的函数，这也是模板的一个规则，有合适的现成的吃现成的，没现成看有没有合适的模板。

🌿 尾插和尾删

#include "vector.h"void Test4()//尾插和尾删
{my_vector::vector<int> arr;//创建arr对象for (int i = 0; i < 10; ++i)//尾插10个元素arr.push_back(i);for (auto& val : arr)cout << val << " ";cout << endl;arr.pop_back();//尾删arr.pop_back();//尾删for (auto& val : arr)cout << val << " ";
}int main()
{Test4();
}

运行结果：

🌿 插入函数

#include "vector.h"void Test5()//insert
{my_vector::vector<int> arr(5, 1);//创建vector对象for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.insert(arr.begin() + 3, 12);//在arr.begin()+3位置前插入12for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.insert(arr.begin(),-1);//头插1个-1for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;
}int main()
{Test5();
}

运行结果：

🌿 erase函数测试

#include "vector.h"void Test6()//erase
{my_vector::vector<int> arr;my_vector::vector<int> arr1;arr1 = arr;for (int i = 0; i < 10; ++i)arr.push_back(i);for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;arr.insert(arr.begin(),100);arr.erase(arr.end()-1);//尾删for (int val : arr)//范围for,交给编译器来做{cout << val << " ";}cout << endl;
}int main()
{Test6();
}

运行结果：

🌿 缩容和扩容函数测试

#include"vector.h"void Test9()//reserve
{my_vector::vector<int> arr;arr.reserve(10000);//扩容cout << arr.capacity() << endl;arr.reserve(10);//缩容，不会成功cout << arr.capacity() << endl;
}void Test10()//shrink_to_fit
{my_vector::vector<int> arr;arr.reserve(1000);cout << arr.capacity() << endl;arr.resize(99);arr.shrink_to_fit();cout << arr.capacity() << endl;
}int main()
{Test9();Test10();return 0;
}

运行结果：

🌿 其它函数（区间构造、clear、empty）测试

#include"vector.h"void Test11()//迭代器范围构造
{my_vector::vector<int> arr1(10, 1);//普通构造my_vector::vector<int> arr2(arr1.begin(), arr1.end());//区间构造for (auto& i : arr2)cout << i << " ";cout << endl;my_vector::vector<int> arr3(11,0);//创建arr3for (auto& i : arr3)cout << i << " ";cout << endl;arr3 = arr2;//赋值运算符重载for (auto& i : arr3)cout << i << " ";cout << endl;arr2[1] = 100;//更改第2个元素的值swap(arr1, arr2);for (auto& i : arr1)cout << i << " ";cout << endl;arr1.clear();//清除arr1的内容cout << arr1.capacity() << " " << arr1.size() << endl;cout << arr1.empty() << endl;
}
int main()
{Test11();return 0;
}

运行结果：

🌿 测试动态二维vector

这里二维的vector我们将其和二维数组联系起来理解就简单多了，外面的vector的数组存储的类型也是vector<元素类型>。二维数组是存储一维数组的数组，对应二维vector是存储一维vector的vector。
测试函数：

#include"vector.h"// 以杨慧三角的前n行为例：void Test12(size_t n)
{// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>my_vector::vector<my_vector::vector<int>> vv(n);// 将二维数组每一行中的vecotr<int>中的元素全部设置为1
for (size_t i = 0; i < n; ++i)vv[i].resize(i + 1, 1);
// 给杨慧三角出第一列和对角线的所有元素赋值for (int i = 2; i < n; ++i){for (int j = 1; j < i; ++j){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}for (int i = 0; i < n; ++i){for (auto i : vv[i])cout << i << " ";cout << endl;}
}
int main()
{Test12(10);return 0;
}

运行结果：