C++vector实用方法讲解和模拟实现

一vector引入vector 是 C 提供的、支持自动扩容的动态顺序表 本质是连续空间的动态数组。下面给几个比方方便大家理解 终极比方vector 自动扩容的快递箱子你可以把vector想象成一个可以无限变大、自带伸缩功能的智能储物箱它不是固定大小的纸箱而是你装多少东西它就自动变多大永远不会装不下也不会浪费太多空间。 比方 1vector 是动态水果篮子普通数组int a[10]固定大小的篮子只能装 10 个苹果多一个都塞不进。vector智能篮子你往里放苹果它不够大就自动变大永远能装。一句话定义vector 是一个能自动变大、自动缩小的动态数组。 比方 2vector 是可无限加页的笔记本普通数组只有 10 页纸写满就不能写了。vector写到最后一页自动加纸永远写不满。vector 就是一块连续的、可以随时变长变短的内存空间。 比方 3vector 是可以随时扩建的房子size()你现在住了几个人有效元素capacity()你房子总共能住几个人总容量push_back()来一个人住进去resize()改房间数量reserve()提前扩建房子预留空间vector 就是连续空间 自动扩容 方便增删改查下面我们将讲解vector的使用方法以及部分方法的代码模拟实现首先声明方法实现是封装在一个类模板中的部分函数实现会相互调用但所有的函数都会在本文种找到类的主要信息如下templateclass T class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; private: iterator _start nullptr; // 指向数据块的开始 iterator _finish nullptr; // 指向有效数据的尾 iterator _end_of_storage nullptr; // 指向存储容量的尾 };其中iterator是T*类型的别名_start,_finish,_end_of_storage都是iterator(自定义的迭代器类型分别指向动态数组的开始位置动态数组存储最后一个元素的下一个位置动态数组最大存储元素的下一个位置。二vector创建用vector创建类型为t的一位数组核心语法vectort 名字使用vector创建一维数组1.vectorintarr1;//创建一个不初始化的存放int类型的空vector2.vectorintarr2(10);//创建一个大小为十的不初始化存放int类型的vector3. vectorchararr3(10, c);//创建一个大小为十,全部元素初始化为‘c,存放char类型的vector4.vectorint arr4 { 1,2,3,4,5,6 };//初始化c风格数组的方法初始化5. vectorint arr[6];创建二维数组1.vectorvectorint arr5(5, vectorint(10, 1));//创建一个五行十列的数组并将其值全部初始化为12.vectorvectorint arr6 { {1,2,3},{4,5,6} };//使用初始化c风格数组的方式初始化3.vectorint arr7[10];//创建一个元素个数为10的vector数组每个vector元素大小未定4.vectorvectorint arr8[1][2];第二种方法创建二维数组并初始化还有一种操作for (int i 0; i 2; i)//初始化 { arr6.push_back(vectorint());//初始化一行 for (int j 0; j 3; j) { arr6[i].push_back(1);//初始化每一列 } }vector的创建是通过构造函数来实现的部分构造函数的功能类似于下面代码vector() default; vector(int n, const T value T())//构造函数中也可调用成员函数 //在构造函数调用之前对象就通过初始化列表实例化了 { reserve(n); while (_finish ! _end_of_storage) { *_finish value; _finish; } }vector也支持使用一另种容器对其初始化string s1hello world; vectorchar arr(s1.begin(),s1.end());只需要给构造函数的参数表传两个同一容器的迭代器注意是”左闭右开“对应的构造函数类似于templateclass InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } }也可以使用创建了的vector实例化对象初始化一个新对象vectorint arr{1,2,3}; vectorint arr1(arr);对应完成vector创建的复制构造函数类似于vector(const vectorT v) { reserve(v.size()); for (auto it : v) { push_back(it); } }由于后面在模拟实现部分方法种会用到两个函数和析构函数这里提前实现void swap(vectorT v) { std::swap(_start, v._start); std::swap(_end_of_storage, v._end_of_storage); std::swap(_finish, v._finish); } ectorT operator (vectorT v) { swap(v); return *this; } ~vector() { if (_start ! nullptr) { delete[]_start; _start _end_of_storage _finish nullptr; } }三vector的相关容量操作和判空void scan_vector() { vectorint arr(10, 1); for (int i 0; i arr.size(); i)//使用下标遍历 { cout arr[i] ; } cout endl; for (auto it : arr)//使用范围for遍历 { it * 2; } for (auto it arr.begin(); it arr.end(); it)//使用迭代器遍历 { cout *it ; } cout endl; cout arr大小(有效存储元素个数)为 arr.size() endl; cout arr的最大存储元素个数为arr.capacity() endl; arr.resize(20, 0); for (auto it arr.begin(); it arr.end(); it)//使用迭代器遍历 { cout *it ; } cout endl; arr.resize(5); cout arr修改后的大小为 arr.size() endl; cout arr:; for (auto it arr.begin(); it arr.end(); it)//使用迭代器遍历 { cout *it ; } cout endl; }begin返回初始位置迭代器end() 返回最后一个有效元素下一个位置的迭代器size():返回存储在vector中的有效元素的个数。capacity返回vector中的最大存储元素个数empty() : vector判空,是空返回true反之返回falsereserve用于手动扩容一般不常用编译器会自动扩容参数为指定的最大存储元素个数n扩容到nresize() :用于设置vector的有效元素的个数 参数表有两个参数第一个参数是指定的有效元素个数n第二个参数是一个符合vector存储的类型的值val。当n比有效元素个数小时vector会截断丢失下标超过包括n的数据当n比有效元素个数大时会保留原有数据并扩容到n将新开辟的空间存上val。相关方法模拟实现类似于const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } iterator begin() { return _start; } iterator end() { return _finish; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void reserve(size_t n)//_start指向新开空间的位置 //_finish指向新开空间相对于_start差old_size的位置 //_end_of_storage 指向_start差n的位置 { if (capacity() n)//扩容 { size_t old_size size(); iterator new_start new T[n];//开新空间 for (size_t i 0; i old_size; i)//拷贝原数据 { new_start[i] _start[i]; } delete[] _start;//释放旧空间 _start new_start; _end_of_storage _start n; _finish _start old_size; } } void resize(size_t n, const T value T()) { if (n size()) { reserve(n); while (_finish _start n) { *_finish value; _finish; } } else { _finish _start n; } } bool empty() { return _finish _start; }vector也可以像下标一样访问元素得益于【】运算符的重载///////////////access/////////////////////////////// T operator[](size_t pos) { assert(pos 0 pos size()); return _start[pos]; } const T operator[](size_t pos) const { assert(pos 0 pos size()); return _start[pos]; }四vector元素的插入与删除templateclass T void print(vectorT arr) { for (auto it arr.begin(); it arr.end(); it)//使用迭代器遍历 { cout *it ; } cout endl; } void modify_vector() { vectorint arr { 1,2,3 }; cout -------------尾插----------- endl; arr.push_back(4); print(arr); arr.push_back(5); print(arr); arr.push_back(6); print(arr); arr.push_back(7); print(arr); cout -----------尾删------------ endl; arr.pop_back(); print(arr); arr.pop_back(); print(arr); arr.pop_back(); print(arr); vectorint arr2 { 1,2,3,4,5,6,7,8,9,10 }; cout ----------指定位置插入和删除--------- endl; cout 从1,2,3,4,5,6,7,8,9,10 中将奇数删除并在后面插入1 endl; for (auto it arr2.begin(); it ! arr2.end(); it) { if (*it % 2 1) {//更新迭代器防止迭代器失效 itarr2.erase(it); itarr2.insert(it, 1); } } print(arr2); cout 新数组首元素是 arr2.front() 尾元素是 arr2.back() endl; arr2.clear(); coutarr的大小为arr.size()endl; }push_back(T a)尾插元素apop_back(): 尾删insert迭代器 posT a将pos即之后的元素向后移动一个位置在pos位置插入元素aerase(迭代器 pos将pos位置的元素删除将pos之后的元素向前移动一位。front() 获取首元素back()获取尾元素clear()清空vector相关方法类似于void push_back(const T x) { if (_finish _end_of_storage) { size_t newcapacity (capacity() 0 ? 4 : 2 * capacity()); reserve(newcapacity); } *_finish x; _finish; } void pop_back() { assert(_finish ! _start); _finish--; } iterator insert(iterator pos, const T x) { assert(pos _start pos _finish); size_t len pos - _start; if (_finish _end_of_storage)//扩容 { size_t newcapacity (capacity() 0 ? 4 : 2 * capacity()); reserve(newcapacity); pos _start len; // 扩容后更新迭代器位置 } for (iterator it _finish; it pos; --it) { *it *(it - 1); } *pos x; _finish; return pos; } iterator erase(iterator pos) { assert(pos _start pos _finish); for (iterator it pos 1; it _finish; it) { *(it - 1) *it; } _finish--; return pos; } void clear() { _finish _start; }五迭代器失效上文注释中提到了迭代器失效迭代器失效是指在顺序容器如vector中因容器内存扩容或元素移动导致原本合法的迭代器失去对原有效元素的指向进而引发访问越界、逻辑错误等未定义行为。1. insert 导致的迭代器失效扩容失效insert触发reserve扩容时容器会释放原连续内存空间并在新地址重新分配内存原迭代器指向已释放的非法地址直接失效。元素移动失效未扩容但执行元素后移操作迭代器指向的位置语义发生改变不再对应原逻辑位置。2. erase 导致的迭代器失效erase删除元素后后续元素会向前整体移动覆盖迭代器指向的位置不再对应原有效元素迭代器位置失效且删除操作无自动更新迭代器能力继续使用会产生逻辑错误。所以在使用insert,erase时要更新迭代器即用操作的迭代器接受insert,erase的返回值使操作erase的迭代器指向下一个元素操作insert的迭代器指向被插入元素的下一个。