目录一. 认识 vector1.1 vector 的理解二. vector的使用2.1 vector 的构造2.2 vector 没有重载输入输出流2.3 vector 的迭代器使用2.3 其他函数接口2.3.1 reserve2.3.2 resize2.4 vector 的增删查改2.4.1 vector 的插入尾插 push_back插入 insert2.4.2 vector 的删除尾删 pop_back删除 erase2.4.3 vector 的查三. 实战演练118. 杨辉三角 - 力扣LeetCode136. 只出现一次的数字 - 力扣LeetCode四. 实现 vector4.1 vector 的迭代器失效问题4.1.1 insert4.1.2 erase4.2 vector 实现的一些问题4.2.1 vector 的拷贝4.2.2 迭代器区间构造4.2.3 默认构造4.2.4 typename4.3 具体实现代码一. 认识 vector前面我们解释过string类比STL诞生要早几年STL很多容器和string都具有相似性但是string的很多接口非常鸡肋而且数量多——一百多个接口博主也介绍过后面的STL借鉴了string而且取长补短接口数量大幅减少就比如今天我们要正式开始介绍的一个新的容器——vector。如下图所示是不是少了很多而且有没有感觉这些接口很眼熟没错和string非常相似在底层实现层面会有差异但是使用层面是差不多的类似于复用的思想这也就是为什么我们前面要花那么多的篇幅来详细介绍string类——后面的vector、list...都是差不多的。1.1 vector 的理解string是字符串vector则是一个改变数据的顺序容器其实对应的就是博主之前在用C语言实现初阶的数据结构里面实现过的顺序表。可以理解为C版本的顺序表。二. vector的使用2.1 vector 的构造vectorT v调用默认构造创建一个空 vector不创建任何元素size0。vectorT v(n)创建 n 个默认初始化的元素如果 T 是自定义类型会调用 T 的默认构造函数 n 次。vectorT v(n, val)创建 n 个值为 val 的元素如果 T 是自定义类型会调用 T 的拷贝构造函数 n 次。vectorT v(first, last)使用迭代器区间[first,last)中的元素初始化 vector复制该区间内的元素。vectorT v(other)调用拷贝构造用另一个 vector 的所有元素初始化新的 vector。#define _CRT_SECURE_NO_WARNINGS #includeiostream #includevector using namespace std; void test1_vector() { //拷贝构造 vectorint v1; //填充构造 vectorint v2(4); vectorint v3(5, 10); //区间构造 vectorint v4(v3.begin()1, v3.end()-1); //拷贝构造 vectorint v5(v4); //范围for for (auto ch : v3) { cout ch ; } cout endl; for (auto ch : v4) { cout ch ; } cout endl; //迭代器 vectorint::iterator it v4.begin(); while (it ! v4.end()) { cout *it ; it; } } int main() { test1_vector(); return 0; }2.2 vector 没有重载输入输出流//自己显式打印 void Print(const vectorint v) { for (size_t i 0; i v.size(); i) { cout v[i] ; } cout endl; }2.3 vector 的迭代器使用vector 的迭代器使用和 string 的迭代器使用几乎一模一样这里就不再过多介绍。#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); vectorint::iterator it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; return 0; }2.3 其他函数接口2.3.1 reservereserve(n)用于提前申请 vector 的容量空间当当前capacity小于 n 时会进行扩容使容量至少达到 n可能更大如果当前容量已经足够则不会发生变化。reserve只影响capacity不会改变size也不会创建元素因此调用后 vector 仍然为空只有后续push_back等操作才会添加元素。它常用于提前知道元素数量时减少多次扩容带来的开销。#define _CRT_SECURE_NO_WARNINGS #includeiostream #includevector using namespace std; void test2_vector() { vectorint v(10, 1); v.reserve(20); cout v.size() endl; cout v.capacity() endl; v.reserve(15); cout v.size() endl; cout v.capacity() endl; v.reserve(5); cout v.size() endl; cout v.capacity() endl; } int main() { test2_vector(); return 0; }2.3.2 resizeresize(n)用于改变 vector 的 size元素个数如果 n 小于当前 size则删除末尾多余元素并调用这些元素的析构函数如果 n 大于当前 size则在末尾新增元素新元素默认使用value_type()初始化也可以指定 val 让新增元素都拷贝 val。resize会改变容器实际内容必要时如果新的 size 超过当前 capacity会触发扩容它和reserve的区别是reserve只改变容量、不创建元素而resize会真正增加或删除元素。#define _CRT_SECURE_NO_WARNINGS #includeiostream #includevector using namespace std; void test2_vector() { vectorint v(10, 1); v.reserve(20); cout v.size() endl; cout v.capacity() endl; v.resize(15, 2); cout v.size() endl; cout v.capacity() endl; v.resize(25, 3); cout v.size() endl; cout v.capacity() endl; v.resize(5); cout v.size() endl; cout v.capacity() endl; } int main() { test2_vector(); return 0; }2.4 vector 的增删查改2.4.1 vector 的插入尾插 push_back#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); vectorint::iterator it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; dict.push_back(4); it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; return 0; }插入 insert#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); vectorint::iterator it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; dict.insert(dict.begin(), 5); dict.insert(dict.begin(),4, 5); dict.insert(dict.begin(), dict.begin(), dict.end()); vectorint::iterator _it dict.begin(); while (_it ! dict.end()) { cout *_it ; _it; } cout endl; return 0; }2.4.2 vector 的删除尾删 pop_back#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); vectorint::iterator it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; dict.pop_back(); it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; cout endl; return 0; }删除 erase#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); vectorint::iterator it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; dict.erase(dict.end()-1); it dict.begin(); while (it ! dict.end()) { cout *it ; it; } cout endl; return 0; }2.4.3 vector 的查vector 自身并没有 find() 成员函数但是我们可以使用标准库里的 find() 函数#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); dict.push_back(3); dict.push_back(5); dict.push_back(6); auto it find(dict.begin(), dict.end(), 5); if (it ! dict.end()) { cout *it endl; } else { cout 找不到 endl; } return 0; }三. 实战演练118. 杨辉三角 - 力扣LeetCodeclass Solution { public: vectorvectorint generate(int numRows) { vectorvectorint dict(numRows); vectorvectorint::iterator itdict.begin(); int i1; while(it!dict.end()) { (*it)vectorint(i,1); i; it; } for(int i2;inumRows;i) { for(int j1;j(dict[i]).size()-1;j) { dict[i][j]dict[i-1][j]dict[i-1][j-1]; } } return dict; } };136. 只出现一次的数字 - 力扣LeetCodeclass Solution { public: int singleNumber(vectorint nums) { vectorint tmpnums; int ans0; for(auto ch: tmp) { ans^ch; } return ans; } };四. 实现 vector4.1 vector 的迭代器失效问题迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对 指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器 底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即 如果继续使用已经失效的迭代器程序可能会崩溃)。4.1.1 insert会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。#includeiostream #includevector using namespace std; int main() { vectorint dict(3, 4); vectorint::iterator it dict.begin(); dict.insert(it, 10); dict.insert(it, 20); return 0; }vector::insert迭代器失效分两种情况如果插入时发生扩容由于底层空间被重新申请原来的地址全部改变因此所有迭代器都会失效如果没有扩容只是移动元素那么插入位置及其之后的元素地址发生变化所以这些迭代器失效而插入位置之前的迭代器仍然有效。4.1.2 erase//指定位置元素的删除操作--erase #include iostream using namespace std; #include vector int main() { int a[] { 1, 2, 3, 4 }; vectorint v(a, a sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vectorint::iterator pos find(v.begin(), v.end(), 3); // 删除pos位置的数据导致pos迭代器失效。 v.erase(pos); cout *pos endl; // 此处会导致非法访问 return 0; }使用erase后删除位置及其之后的迭代器会失效。虽然原迭代器保存的地址可能没有改变但它已经不再指向原来的元素因此不能继续使用需要使用erase的返回值重新获取有效迭代器。使用得当我们可以用 erase 连续删除数据#include iostream using namespace std; #include vector //删除偶数 int main() { int a[] { 1, 2, 3, 4 ,5,6,7,8,9,10 }; //迭代器区间构造 vectorint dict(a, a sizeof(a) / sizeof(a[0])); //迭代器遍历 vectorint::iterator it dict.begin(); while (it ! dict.end()) { if (*it % 2 0) { //更新迭代器it it dict.erase(it); } else { it; } } //遍历打印 for (auto ch : dict) { cout ch ; } cout endl; return 0; }4.2 vector 实现的一些问题4.2.1 vector 的拷贝我们在模拟实现 string 时通常使用 strcpy 拷贝字符串内容。对于 vector不能简单使用 memcpy 进行元素拷贝因为 memcpy 只是按字节复制不会调用对象的拷贝构造函数。当 vector 存储的是 string、list 等管理动态资源的类型时需要进行深拷贝调用拷贝构造或赋值运算符否则会导致多个对象管理同一份资源。4.2.2 迭代器区间构造vector 的迭代器区间构造要求两个迭代器类型可以作为一个有效区间使用迭代器指向的元素类型不一定要和 vector 存储类型完全相同只要元素类型能够转换为 vector 的存储类型即可。// 类模板的成员函数还可以继续是函数模板 templateclass InputIterator vector(InputIterator first, InputIterator last) { InputIterator it first; while (it ! last) { push_back(*it); it; } }4.2.3 默认构造当我们显式写构造函数时编译器就不会自己生成默认构造函数但是C11 提供了前置生成默认构造的方法//c 11前置生成默认构造 vector() default;4.2.4 typename在模板中当依赖于模板参数的嵌套名称dependent name可能既可以被解释为类型也可以被解释为静态成员变量时编译器默认不会把它当作类型需要使用typename显式告诉编译器它是一个类型。templateclass T void print_vector1(const vectorT v) { //不能在没有实例化的类模板里面取东西编译器分不清是类型还是静态成员变量 typename vectorT::const_iterator it v.begin(); while (it ! v.end()) { cout *it ; it; } }4.3 具体实现代码#define _CRT_SECURE_NO_WARNINGS #pragma once #includeiostream #includeassert.h #includevector #includestring.h using namespace std; namespace bit { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; ~vector() { if (this-_start ! nullptr) { delete[] this-_start; _start _finish _end_of_storage nullptr; } } //c 11前置生成默认构造 vector() default; /*vector() {}*/ vector(size_t n, const T v T()) { this-reserve(n); for (size_t i 0; i n; i) { this-push_back(v); } } // 类模板的成员函数还可以继续是函数模板 templateclass InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { this-push_back(*first); first; } } vector(const vectorT v) { this-reserve(v.size()); for (auto e : v) { push_back(e); } } void clear() { _finish _start; } //类里面可以用类名替代类型 //vectorT operator(vectorT v) vector operator(vector v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); return *this; } iterator begin() { return this-_start; } const_iterator begin()const { return this-_start; } iterator end() { return this-_finish; } const_iterator end()const { return this-_finish; } size_t size()const { return _finish - _start; } size_t capacity()const { return _end_of_storage - _start; } bool empty()const { return _start _finish; } void resize(size_t n, const T val T()) { if (n this-size()) { _finish _start n; } else { reserve(n); while (_finish _start n) { *_finish val; _finish; } } } void reserve(size_t n) { if (n this-capacity()) { size_t old_size this-size(); T* tmp new T[n]; //memcpy(tmp, _start, sizeof(T) * size()); for (size_t i 0; i old_size; i) { tmp[i] _start[i]; } delete[] this-_start; this-_start tmp; _finish _start old_size; _end_of_storage _start n; } } void push_back(const T x) { if (_finish ! _end_of_storage) { *_finish x; _finish; } else { reserve(this-capacity() 0 ? 4 : 2 * this-capacity()); *_finish x; _finish; } } void pop_back() { assert(!this-empty()); this-_finish--; } iterator insert(iterator pos, const T x) { assert(pos this-_start pos this-_finish); //迭代器失效 if (_finish _end_of_storage) { size_t index pos - _start; reserve(this-capacity() 0 ? 4 : 2 * this-capacity()); pos index _start; } iterator end this-_finish - 1; while (end pos) { *(end 1) *end; end--; } *pos x; this-_finish; return pos; } void erase(iterator pos) { assert(pos this-_start pos this-_finish); iterator it pos 1; while (it ! end()) { *(it - 1) *it; it; } this-_finish--; } T operator[](size_t pos) { assert(pos this-size()); return _start[pos]; } const T operator[](size_t pos)const { assert(pos this-size()); return _start[pos]; } private: iterator _startnullptr; iterator _finish nullptr; iterator _end_of_storage nullptr; }; templateclass T void print_vector1(const vectorT v) { for (auto ch : v) { cout ch ; } cout endl; //不能在没有实例化的类模板里面取东西编译器分不清是类型还是静态成员变量 typename vectorT::const_iterator it v.begin(); while (it ! v.end()) { cout *it ; it; } } void test_vector2() { vectorint vv; vv.push_back(1); vv.push_back(2); vv.push_back(3); vv.push_back(4); vv.insert(vv.begin() 2, 10); print_vector1(vv); cout endl; int x; cin x; auto pos find(vv.begin(), vv.end(), x); if (pos ! vv.end()) { posvv.insert(pos, 40); (*pos) 1; } print_vector1(vv); } }