【C++】vector 类

目录vector 与 string 区别vector 的成员变量构造 析构 Construct Destructor迭代器 Iterators:容量 Capacity:元素访问 Element access:修改器 Modifiers:比较 relational operatorsvector 与 string 区别vector 与 string 比较相似但就不像 string 需要考虑字符串相关的问题vector 要真作区分的话string 更像char* 而 vector 类似其他整形浮点型的数组但是这么讲不完全准确vector是一个模板类每次需要调用 vector 都需要一个int 等等类型甚至可以用 vectorstring 。存储内容string专门存字符char代表字符串末尾自带\0vectorT泛型容器T 可以是任意类型int、对象等不限于字符没有末尾 \0。模板属性vector是类模板string是实例化好的具体类本质vectorchar的特化版本但不等同。功能侧重点string面向字符串操作支持、c_str()、查找子串、字符串比较等字符串专用接口。vector通用动态数组侧重增删元素没有字符串相关函数。size 含义string 的 size 是有效字符个数不计末尾\0 vector 的 size 是有效元素个数。使用场景string处理文本、字符串 vector存储任意类型一组数据。vector 的成员变量vector 的成员变量由三个模板类型指针构成分别指向数组三个位置头、内容尾 和容量尾 (注意应该是模板类的原因无法做到定义分离的情况都写在.h)namespace Youren { template class T//class Alloc allocatorT 这个与内存池相关目前实现比较简单的 vector 类即可 class vector { public: //必须知道的事项 // type 的重命名 以及 迭代器 typedef T value_type; typedef const T value_type; typedef T* iterator; typedef const T* const_iterator; // 引用 typedef value_type reference; typedef const value_type const_reference; //虽然 size_type 也要重命名但我还是比较用 size_t 习惯 private: iterator _start nullptr; // 内容开始位置 iterator _finish nullptr; // 内容末尾 iterator _end_of_storage nullptr; // 容量末尾 }; }构造 析构 Construct Destructorvector();//无传参 初始化 vector(size_t n, const value_type val value_type()); // 将 n 个 val 匿名对象 无传参默认为 0 template class InputIterator vector(InputIterator first, InputIterator last); //适配各种迭代器 list string 等 将其初始化为vectorInputIterator vector(const vector x); //复制拷贝构造 ~vector()//析构 reference operator(vector v)//运算符重载 构造1. vector无实数传参无需分配空间统一三个指针指向nullptrvector(){}2. 将 n 个 val 作为初始化vector(size_t n, const value_type val value_type()) // 目标 n 个 val val 是匿名对象 无传参默认为0 { if (n 0) { return; } //步骤开空间 写入内容 标记好位置 _start new value_type[n]; _finish _start n; _end_of_storage _start n; for (size_t i 0; i n; i) { _start[i] val; } }3. 将不同类型的变量对应位置的迭代器位置区间的变量/* false template class InputIterator vector(InputIterator first, InputIterator last) { size_t size_input last - first; _start new InputIterator[size_input]; _finish _start size_input; _end_of_storage _start size_input; for (size_t i 0; i size_input; i) { _start[i] first[i]; } } */ template class InputIterator vector(InputIterator first, InputIterator last) { for (InputIterator it first; it ! last; it) { push_back(*it); } }注意第一种写法是错误的只能适配部分的类型如果出现一些变化会导致类型野指针和计算容量出现问题等情况主要问题是第一种类型只对连续开辟空间适配对于非连续空间会导致计算空间出现问题例如list 就是典型的非连续空间的类类型。而却第一种写法可读性比较差第二种的写法比较简洁但要注意因为之中写法还是有缺点就是无法做到如图下操作。class Alloc allocatorT 与相关还无法实现4.拷贝构造vector(const vector x) { //开辟空间 _start new value_type[x.capacity()]; //cpy for (size_t i 0; i x.size(); i) { _start[i] x[i]; } //标记结束_finish _finish _start x.size(); // 标记 _end_of_storage _end_of_storage _start x.capacity(); }析构~vector() { if (_start ! nullptr) { for (iterator it _start; it ! _finish; it) { it-~value_type(); } delete[] _start; _start _finish _end_of_storage nullptr; } }析构得注意一下vector 是模板类可以对 string 等进行类类型的使用而在对应类型析构后析构不能直接析构要先析构成员每一个变量在析构内存进行空间释放运算符 重载现代写法void swap(vector v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } reference operator(vector v) { swap(v); return *this; }迭代器 Iterators://迭代器 iterator end() { return _finish; } iterator begin() { return _start; } const_iterator end() const { return _finish; } const_iterator begin() const { return _start; }功能说明begin()返回指向容器第一个有效元素的迭代器即内容头指针_start。通过它可以从头开始遍历容器中的元素。end()返回指向容器末尾之后位置的迭代器即内容尾指针_finish。它不指向任何有效元素通常作为遍历的结束标志配合begin()使用。const 版本const_iterator begin() const和const_iterator end() const用于只读访问在 const 对象上调用时返回const_iterator只能读取元素不能通过它修改元素内容。容量 Capacity://基本成员函数 //size capacity // 注意谁前谁后 size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } //判断是否为空 bool empty() const { return _start _finish; }功能说明size()返回当前有效元素个数通过内容尾指针_finish减去内容头指针_start得到即_finish - _start。capacity()返回当前容量即最多能容纳的元素个数通过容量尾指针_end_of_storage减去内容头指针_start得到即_end_of_storage - _start。empty()判断容器是否为空当内容头指针_start与内容尾指针_finish相等时返回 true表示没有有效元素。reserve resize 扩容 size修改//扩容 void reserve(size_t n 4) { if (n capacity()) { return; } else { if (capacity() ! 0) { n n 2 * capacity() ? n : 2 * capacity(); } //注意扩容时 vector 具有特殊性会 3 迭代器指针位置出现头 delete[] 同时删除时会导致 其他两个地址变成野指针 //申请新的地址空间 iterator new_start new value_type[n]; //记录就空间有效位置所占位置 size_t old_size size(); //cpy //尽量不要使用memcpy for (size_t i 0; i size(); i) { new_start[i] _start[i]; } //删除旧空间 for (size_t i 0; i size(); i) { _start[i].~value_type(); } delete[] _start; //换上新地址 并且依次配对地址 _start new_start; _finish _start old_size; _end_of_storage _start n; } } // 匿名对象 匿名对象不传参默认该类型相关 0 的数值; void resize(size_t n, value_type val value_type()) { if (n size()) { iterator it _finish - 1; for (; it ! _start n; it--) { it-~value_type(); } _finish it; } else if (n size()) { reserve(n); for (size_t i size(); i n; i) { _start[i] val; } _finish (n - size()); } }上面写的不一定与源代码的扩容一致但意思和算法能够实现目的即可reserve 和resize的目的与 string 中的别无二致。注意点发生扩容的时候会导致原先的记录的迭代器失效就是原先的指针变成野指针发生扩容时也需要更新迭代器可以预先储存好相对位置确保位置。元素访问 Element access:reference operator[](const size_t i) { assert(i size()); return _start[i]; } const_reference operator[](const size_t i) const { assert(i size()); return _start[i]; }功能说明operator[]通过下标i直接访问容器中第i个元素返回该元素的引用reference可用于读取或修改对应位置的元素。const 版本const_reference operator[](const size_t i) const用于只读访问在 const 对象上调用时返回const_reference只能读取元素不能通过它修改元素内容。越界检查两个版本都通过assert(i size())进行越界检查当下标i超出当前有效元素个数时触发断言帮助在调试阶段及时发现越界访问问题。flont 和 back 都与 begin 和 end 一致。at 与 operator[] 用法相同;修改器 Modifiers:void push_back(const value_type val);// 尾插入 1 个 val void pop_back();// 删除尾内容 void clear();// 全部内容删除 iterator insert(iterator position, const value_type val);// 指定位置插入 1 个 val void insert(iterator position, size_t n, const value_type val);// 指点位置插入 n 个 val iterator erase(iterator position);//删除指点位置 iterator erase(iterator first, iterator last);//删除对应区间实现原理原理都与string 都是相似的但是 vector 凡事涉及到删除相关的内容都需要调用析构注意这一点就可以。push_back , pop_back 和 clear//插入数值 void push_back(const value_type val) { //扩容 reserve(size() 1); new(_finish)value_type(val); _finish; } // void pop_back() { _finish--; _finish-~value_type(); } void clear() { for (iterator it _start; it ! _finish; it) { it-~value_type(); } _finish _start; }功能说明push_back()在容器末尾插入一个元素val。先调用reserve(size() 1)确保容量足够再通过new(_finish)value_type(val)在_finish位置原地构造新元素最后_finish更新内容尾指针。pop_back()删除容器末尾的一个元素。先将_finish前移一位再调用_finish-~value_type()析构该位置的元素避免内存泄漏。clear()清空容器中所有元素。遍历_start到_finish之间的每个元素并调用析构函数最后将_finish重置为_start使容器变为空状态。insert 插入iterator insert(iterator position, const value_type val) //插入在pos 的位置 pos 一个 val 原本的内容往后调整 { assert(_start position _finish position); //注意扩容可能带来迭代器失效 possiton 可能直接废了 size_t pos position - _start;//记录相对位置 reserve(size() 1); position _start pos; //移位 for (size_t i size(); i ! pos; i--) { _start[i] _start[i - 1]; } //插入 _finish; new(position)value_type(val); return position; } void insert(iterator position, size_t n, const value_type val) { if (n 0) { return; } assert(_start position _finish position); size_t pos position - _start; reserve(size() n); position _start pos; for (size_t i size() n - 1; i pos n; i--) { _start[i] _start[i - n]; } for (size_t i 0; i n; i) { new(position i)value_type(val); } _finish n; }注意在扩容会导致迭代器失效要时刻注意扩容导致原先的_start 发生改变position 的迭代器失效变成野指针要确保迭代器时刻进行修改需要保留一个相对位置 pos 的位置。template class InputIterator void insert(iterator position, InputIterator first, InputIterator last)void insert(iterator position, size_t n, const value_type val)涉及到一些类模板的相关知识如果这么写会导致这两个代码识别出现问题会导致编译器错乱的情况。编译器不会调用上面第二行的函数代码而是调用模板函数的代码。在标准库中 vector 中简单了解即可大概意思就是判断传输过来的是否是类对应的迭代器不是就调用其他的符合的函数是就调用该模板函数。就是限制只接收迭代器。template class _Iter, enable_if_t_Is_iterator_v_Iter, int 0 _CONSTEXPR20 iterator insert(const_iterator _Where, _Iter _First, _Iter _Last) { const pointer _Whereptr _Where._Ptr; auto _My_data _Mypair._Myval2; const pointer _Oldfirst _My_data._Myfirst; #if _ITERATOR_DEBUG_LEVEL 2 _STL_VERIFY( _Where._Getcont() _STD addressof(_My_data) _Whereptr _Oldfirst _My_data._Mylast _Whereptr, vector insert iterator outside range); #endif // _ITERATOR_DEBUG_LEVEL 2 _STD _Adl_verify_range(_First, _Last); auto _UFirst _STD _Get_unwrapped(_First); auto _ULast _STD _Get_unwrapped(_Last); const auto _Whereoff static_castsize_type(_Whereptr - _Oldfirst); if constexpr (_Is_cpp17_fwd_iter_v_Iter) { const auto _Length static_castsize_t(_STD distance(_UFirst, _ULast)); const auto _Count _STD _Convert_sizesize_type(_Length); _Insert_counted_range(_Where, _UFirst, _Count); #if _HAS_CXX20 } else if constexpr (forward_iterator_Iter) { const auto _Length _STD _To_unsigned_like(_RANGES distance(_UFirst, _ULast)); const auto _Count _Convert_sizesize_type(_Length); _Insert_counted_range(_Where, _UFirst, _Count); #endif // _HAS_CXX20 } else { _Insert_uncounted_range(_Where, _UFirst, _ULast); } return _Make_iterator_offset(_Whereoff); }erase 清除区域内容与 insert 相反先清理再移位。还是注意那个点vector 是类模板清除要考虑对对象进行析构。iterator erase(iterator position)//清除该位置内容 { assert(_start position _finish position); iterator it position; it-~value_type(); for (; it 1 ! _finish; it) { *it *(it 1); } _finish--; return position; } iterator erase(iterator first, iterator last) { assert(_start first first last last _finish); size_t pop last - first; for (iterator it first; it ! last; it) { it-~value_type(); } for (iterator it first; (it pop) ! _finish; it) { *it *(it pop); } _finish - pop; return first; }比较 relational operatorsbool operator(const vector rhs) const { bool infer false; if (size() rhs.size()) { infer true; for (size_t i 0; i size() infer; i) { if (_start[i] ! rhs[i]) { infer false; } } } return infer; } bool operator (const vector rhs) const { size_t min_size size() rhs.size() ? size():rhs.size(); for (size_t i 0; i min_size ; i) { if (_start[i] rhs[i]) { return true; } else if (_start[i] rhs[i]) { return false; } } return size() rhs.size(); } bool operator (const vector rhs) const { return rhs *this; } bool operator!(const vector rhs) const { return !(*this rhs); } bool operator(const vector rhs) const { return !(*this rhs); } bool operator(const vector rhs) const { return !(*this rhs); }26_9_22 vector · 浪子·悠仁/C 知识库 - 码云 - 开源中国感谢观看悠仁さん