【C++】第十一节—一文详解vector（使用+杨辉三角+深度剖析+模拟实现+细节详细补充）

（constructor）构造函数声明	接口说明
vector（）重点	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x); （重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

【补充】 initializer_list——vector的另一种构造方法

见下：initializer_list，用 {10,20,30} 去初始化 il 对象，此时这个 il 就是 initializer_list 类型，可以认为 initializer_list 是一个容器，只不过 initializer_list 支持用花括号去初始化

只不过这个容器只支持遍历，不支持修改

见下：initializer_list 底层的原理—在底层开一个数组，将括号内的数据拷贝到数组里面，这个 il 对象里面有两个指针指向这个数组空间

单参数的构造函数支持隐式类型转换，第一行其实是隐式类型转换，右边的其实是 initializer_list 类型的对象，不能直接给 vector 进行初始化，在语法逻辑上其实是用 initializer_list 去构造一个 vector 类型的临时对象，再将这个临时对象拷贝构造给v1，编译器在这样连续的构造加拷贝优化成了直接进行构造，第二行的就是直接构造

（2）vector的三种遍历方式总结——下标，迭代器，范围for

#include<iostream> #include<vector> using namespace std; int main() { vector<int> v1; vector<int> v2(10, 1); v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); //遍历 for (size_t i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; //迭代器 vector<int>::iterator it1 = v1.begin(); while (it1 != v1.end()) { cout << *it1 << " "; it1++; } cout << endl; //范围for for (auto e : v1) { cout << e << " "; } cout << endl; return 0; }

（3）vector iterator 的使用—迭代器

迭代器不一定就是指针，迭代器是像指针一样的类对象

iterator的使用	接口说明
begin+end	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin+rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

【补充】

string s1 和 vector<char> vs 的区别是什么？s1的结尾有\0，vs的结尾没有\0；我们前面学习了string，知道它们之间的成员接口有很大的区别不过，还有一个有意思的东西—vector<string> vstr，vector里面存储的是string类型的对象

直接隐式类型转换，不用创建string类的对象，单参数构造函数支持隐式类型转换，因为string支持const char* 的传字符串去构造一个string类的对象对于vector<string> vstr遍历的方式

范围for的遍历，是将vstr里面的变量拷贝赋值给左边的变量e，如果vector里面存的是int类型关系不大，但是如果是string类型的对象，调用拷贝构造代价就比较大，所以推荐第二种遍历方式—引用+const(不希望改变里面的值)

vstr[0]和vstr[0][0]，这个也比较有意思

vstr[0]——原来插入了两个string类的对象，vstr[0]下标为0的元素是s1（“张三”），+=的时候其实就是调用string的接口了，所以第一行和第二行代码是在“张三”的后面去尾插；vstr[0][0]——一个汉字是由两个字符构成，这里访问其实是‘张’的两个字符的前一个字符（这里涉及到编码表）

（4）vector 空间增长问题

空间容量	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve（重点）	改变vector的capacity

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。

【补充】 shrink_to_fit

不要轻易地去缩容

（5）vector的增删查改

vector增删查改	接口说明
push_back（重点）	尾插
pop_back（重点）	尾删
find	查找。（不是vector的成员接口）
insert	在 position 之前插入val
erase	删除指定位置的数据
swap	交换两个vector的数据空间
operator（重点）	像数组一样访问

insert，erase不支持下标插入删除，而是支持迭代器，其实也是间接的代替了下标的用法。不建议多用，插入和删除都是要整体挪动数据的。

（6）vector 迭代器失效的问题—重点

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、 assign、push_back等。

 #include <iostream> using namespace std; #include <vector> int main() { vector<int> v{ 1,2,3,4,5,6 }; auto it = v.begin(); // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容 // v.resize(100, 8); // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变 // v.reserve(100); // 插入元素期间，可能会引起扩容，而导致原空间被释放 // v.insert(v.begin(), 0); // v.push_back(8); // 给vector重新赋值，可能会引起底层容量改变 v.assign(100, 8); /* 出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释 放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块 已经被释放的空间，而引起代码运行时崩溃。 解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给 it重新赋值即可。 */ while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; }

2. 指定位置元素的删除操作--erase

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end 的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

#include <iostream> using namespace std; #include <vector> int main() { int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vector<int>::iterator pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据，导致pos迭代器失效。 v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 return 0; }

以下代码的功能是删除vector中所有的偶数，请问那个代码是正确的，为什么？

#include <iostream> using namespace std; #include <vector> int main() { vector<int> v{ 1, 2, 3, 4 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } return 0; } int main() { vector<int> v{ 1, 2, 3, 4 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) it = v.erase(it); else ++it; } return 0; }

3. 注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了 int main() { vector<int> v{ 1,2,3,4,5 }; for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; auto it = v.begin(); cout << "扩容之前，vector的容量为: " << v.capacity() << endl; // 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效 v.reserve(100); cout << "扩容之后，vector的容量为: " << v.capacity() << endl; // 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会 // 虽然可能运行，但是输出的结果是不对的 while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; } //程序输出： //1 2 3 4 5 //扩容之前，vector的容量为: 5 //扩容之后，vector的容量为 : 100 //0 2 3 4 5 409 1 2 3 4 5 // 2. erase删除任意位置代码后，linux下迭代器并没有失效 // 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的 #include <vector> #include <algorithm> int main() { vector<int> v{ 1,2,3,4,5 }; vector<int>::iterator it = find(v.begin(), v.end(), 3); v.erase(it); cout << *it << endl; while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0; } //程序可以正常运行，并打印： //4 //4 5

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end // 此时迭代器是无效的，++it导致程序崩溃 int main() { vector<int> v{ 1,2,3,4,5 }; // vector<int> v{1,2,3,4,5,6}; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } for (auto e : v) cout << e << " "; cout << endl; return 0; } ======================================================== // 使用第一组数据时，程序可以运行 [sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11 [sly@VM - 0 - 3 - centos 20220114]$ . / a.out 1 3 5 ======================================================== = // 使用第二组数据时，程序最终会崩溃 [sly@VM - 0 - 3 - centos 20220114]$ vim testVector.cpp [sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11 [sly@VM - 0 - 3 - centos 20220114]$ . / a.out Segmentation fault

从上述三个例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。

4. 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效

#include <string> void TestString() { string s("hello"); auto it = s.begin(); // 放开之后代码会崩溃，因为resize到20会string会进行扩容 // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了 // 后序打印时，再访问it指向的空间程序就会崩溃 //s.resize(20, '!'); while (it != s.end()) { cout << *it; ++it; } cout << endl; it = s.begin(); while (it != s.end()) { it = s.erase(it); // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后 // it位置的迭代器就失效了 // s.erase(it); ++it; } }

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

理论结束，上图！

第一种迭代器失效——扩容引起的野指针

第二种迭代器失效——删除数据，导致数据位置挪动，it不再指向之前的位置了，it也失效了，因为it已经不是指向之前的位置了，可能会导致逻辑问题

1.3 vector OJ——杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

其实是用同一种类型的模版实例化出两种类型，一个是vector<int>，一个是vector<vector<int>>。

相比于C语言的动态开辟二维数组，用vector开辟二维数组来说，它们之间的效率相比，虽然vector需要多次调用operator[]这个函数，但是vector里面operator[]是内联函数，在函数调用处直接将函数体展开，就减少了在函数调用机制上花费的时间。

class Solution { public: vector<vector<int>> generate(int numRows) { //相当于n个val进行构造，每个val是一个默认构造的vector<int>类型的匿名对象 vector<vector<int>> vv(numRows,vector<int>()); for(size_t i = 0;i < vv.size();i++) { //对每行的vector<int>开空间+进行初始化 vv[i].resize(i+1,1); } //根据杨辉三角进行赋值操作 for(size_t i = 0;i < vv.size();i++) { //每一行的第一个位置和最后一个位置都是1，不需要改变 for(size_t j = 1;j < vv[i].size()-1;j++) { vv[i][j] = vv[i-1][j] + vv[i-1][j-1]; } } return vv; } };

二、vector深度剖析及模拟实现

尝试看源码（下面就是vector的一点点源码）先看框架连蒙带猜

2.1 std::vector的核心框架接口的模拟实现lrq::vector的一些问题

（1）reserve()中的size()问题

（2）注意迭代器失效的问题，翻看上面的第【6】有关细讲迭代器失效的问题（3）initialize_list（4）构造函数的int匹配问题

先实现了两个函数，一个是利用迭代器区间进行构造，一个是用n个val进行构造

但是当执行 vector<int> v3(10, 1)这句代码时，会出现下面的错误

此时这句代码匹配到迭代器区间构造的函数，而不是我们所期待匹配到第二个函数——用n个val构造的函数

why？

// vector<int> v3(10, 1);
// 第一个参数可以类型转换成size_t类型，第二个识别出T为int类型
// 但是但是！这两个实参对于上面那个函数模版会更加适配，直接推算出InputIterator为int类型，但是int类型不能进行解引用，所以此处报错

如何解决？——对于这种只有val为int类型时会出现的问题，那就直接来个现成的，有现成的就不会去匹配调用函数模版了

解决！

2.2 使用memcpy拷贝问题

现在向vector内插入string类型，此时没有扩容，此时运行结果没有报错，一切正常

void test_vector9() { vector<string> v1; v1.push_back("1111111111"); v1.push_back("1111111111"); v1.push_back("1111111111"); v1.push_back("1111111111"); for (auto e : v1) { cout << e << " "; } cout << endl; }

但是当我们再次插入，此时就需要扩容，结果运行出错

我们调试发现问题出在resever()问题上（自己尝试调试），我们来分析一下问题

修改之后的reserve() ：

void reserve(size_t n) { if (n > capacity()) { size_t oldsize = size(); T* tmp = new T[n]; if (_start) { //这里的memcpy只适用于内置类型和类似于Date日期类等的浅拷贝，但是遇到string类就不能只是简单的浅拷贝，需要深拷贝 //memcpy(tmp, _start, sizeof(T) * oldsize); for (size_t i = 0; i < oldsize; i++) { tmp[i] = _start[i];//自定义类型的赋值重载会完成深拷贝 } delete[] _start; } _start = tmp; _finish = tmp + oldsize; _endofstorage = _start + n; } }

问题解决，结果正确！

2.3 模拟实现vector源码

模版不支持分离编译到两个文件否则会报链接错误，具体原因后面的模版进阶会讲。前面的string我们并不是按照模版去写的，所以一个.cpp，一个.h

vector.h

#pragma once #include<assert.h> #include<iostream> using namespace std; namespace lrq { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; //初始化列表 vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} //initializer_list支持迭代器就支持范围for，看文档 vector(initializer_list<T> il) :_start(nullptr) , _finish(nullptr) ,_endofstorage(nullptr) { reserve(il.size()); for (auto& e : il)//如果是string类型用&减少拷贝，遍历il里面的数据，将数据插入 { push_back(e); } } ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } //v2(v1) //拷贝赋值，尽可能采用复用 vector(const vector<T>& v) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } } //类模版的成员函数，也可以是一个函数模版 template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); first++; } } vector(size_t n, const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(val); } } vector(int n, const T& val = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(val); } } void swap(vector<T>& tmp) { std::swap(_start, tmp._start); std::swap(_finish, tmp._finish); std::swap(_endofstorage, tmp._endofstorage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; } //迭代器 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } size_t size()const { return _finish - _start; } size_t capacity()const { return _endofstorage - _start; } T& operator[](size_t i) { assert(i < size()); return _start[i]; } const T& operator[](size_t i)const { assert(i < size()); return _start[i]; } /*void reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; _finish = tmp + size(); _start = tmp; _endofstorage = _start + n; } }*/ void reserve(size_t n) { if (n > capacity()) { size_t oldsize = size(); T* tmp = new T[n]; if (_start) { //这里的memcpy只适用于内置类型和类似于Date日期类等的浅拷贝，但是遇到string类就不能只是简单的浅拷贝，需要深拷贝 //memcpy(tmp, _start, sizeof(T) * oldsize); for (size_t i = 0; i < oldsize; i++) { tmp[i] = _start[i];//自定义类型的赋值重载会完成深拷贝 } delete[] _start; } _start = tmp; _finish = tmp + oldsize; _endofstorage = _start + n; } } bool empty() { return _finish == _start; } void push_back(const T& x) { if (_finish == _endofstorage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; _finish++; } void pop_back() { assert(!empty()); --_finish; } iterator insert(iterator pos, const T& x) { //判断pos位置是否合理 assert(pos >= _start && pos <= _finish); //扩容 if (_finish == _endofstorage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator i = _finish - 1; while (i >= pos) { *(i + 1) = *i; i--; } *pos = x; _finish++; return pos; } //erase返回删除位置的下一个位置 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator i = pos + 1; while (i < _finish) { *(i - 1) = *i; i++; } _finish--; return pos; } void resize(size_t n,T val = T())//内置类型也有默认构造，取决于T的类型，是哪种类型就是哪种类型的默认构造 { if (n <= size()) { _finish = _start + n; } else { reserve(n); while (_finish < _start + n) { *_finish = val; _finish++; } } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; void test_vector1() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); for (size_t i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; for (auto e : v1) { cout << e << " "; } cout << endl; v1.pop_back(); vector<int>::iterator it1 = v1.begin(); while (it1 != v1.end()) { cout << *it1 << " "; it1++; } cout << endl; } void test_vector2() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.insert(v1.begin()+2, 999); for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2 = { 1,2,3,4,5,6 };//用initializer_list类型进行初始化 for (auto e : v2) { cout << e << " "; } cout << endl; cout << typeid(vector<int>::iterator).name() << endl; } void test_vector3() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); for (auto e : v1) { cout << e << " "; } cout << endl; int x = 0; cin >> x; auto it = find(v1.begin(), v1.end(), x); if (it != v1.end()) { it = v1.insert(it, 10 * x); cout << *it << endl; } for (auto e : v1) { cout << e << " "; } cout << endl; } void test_vector4() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); for (auto e : v1) { cout << e << " "; } cout << endl; int x = 0; cin >> x; auto it = find(v1.begin(), v1.end(), x); if (it != v1.end()) { v1.erase(it); cout << *it << endl; } for (auto e : v1) { cout << e << " "; } cout << endl; } void test_vector5() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(4); for (auto e : v1) { cout << e << " "; } cout << endl; //删除所有的偶数 auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { //erase返回删除数据的下一个位置 //失效的迭代器，更新以后再去访问 it = v1.erase(it); } else { it++; } } for (auto e : v1) { cout << e << " "; } cout << endl; } void test_vector6() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(4); for (auto e : v1) { cout << e << " "; } cout << endl; v1.resize(15, 0); for (auto e : v1) { cout << e << " "; } cout << endl; } void test_vector7() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(4); vector<int> v2(v1); for (auto e : v2) { cout << e << " "; } cout << endl; } void test_vector8() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(4); for (auto e : v1) { cout << e << " "; } cout << endl; //用迭代器区间进行初始化 vector<int> v2(v1.begin(), v1.end()); for (auto e : v2) { cout << e << " "; } cout << endl; vector<int> v3(10, 1); for (auto e : v3) { cout << e << " "; } cout << endl; } void test_vector9() { vector<string> v1; v1.push_back("1111111111"); v1.push_back("1111111111"); v1.push_back("1111111111"); v1.push_back("1111111111"); v1.push_back("1111111111"); for (auto e : v1) { cout << e << " "; } cout << endl; } }

main.cpp——测试

#include"vector.h" int main() { lrq::test_vector9(); return 0; }

2.4 动态二维数组理解

// 以杨辉三角的前n行为例：假设n为5 void test2vector(size_t n) { // 使用vector定义二维数组vv，vv中的每个元素都是vector<int> bit::vector<bit::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]; } } }

bit::vector> vv(n); 构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素，如果n为5时如下所示：