C++ STL学习之【vector的模拟实现】 |
您所在的位置：网站首页 › vector的迭代器 › C++ STL学习之【vector的模拟实现】 |
C++ STL学习之【vector的模拟实现】
|
🌇前言 vector 是 STL 中的容器之一，其使用方法类似于数据结构中的 顺序表，得益于范型编程和 C++ 特性的加持，vector 更强大、更全能；在模拟实现 vector 时，还需要注意许多细枝末节，否则就很容易造成重复析构及越界访问  出自书籍《STL源码剖析》 侯捷著 本文重点： 深度拷贝、迭代器失效 🏙️正文vector 的结构比较特殊，成员变量为三个指针 #pragma once #include using std::cin; using std::cout; using std::endl; #include using std::string; namespace Yohifo { template class vector { public: typedef T value_type; typedef value_type* pointer; //指针 typedef const value_type* const_pointer; typedef value_type* iterator; //迭代器 typedef const value_type* const_iterator; typedef value_type& reference; //引用 typedef const value_type& const_reference; private: iterator _start; //指向起始位置 iterator _finish; //指向有效元素的下一个位置 iterator _end_of_storage; //指向可用空间的下一个位置 }; } 1、默认成员函数默认成员函数需要自己设计，因为涉及深浅拷贝问题 默认构造函数、带参构造函数、迭代器区间构造 //默认构造 vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} //带参构造 vector(size_t n, const T& value = T()) :vector() { reserve(n); //扩容 while (n--) push_back(value); //逐个尾插 } //额外版本，避免匹配上迭代器区间构造 vector(int n, const T& value = T()) :vector() { reserve(n); //扩容 while (n--) push_back(value); //逐个尾插 } //迭代器区间构造 template vector(InputIterator first, InputIterator last) :vector() { //考虑提前计算容量 InputIterator cur = first; int len = 0; while (cur != last) ++len, ++cur; reserve(len); while (first != last) push_back(*first), ++first; }注意： 在设计带参构造函数时，需要再额外提供一个 vector(int n, const T& value = T()) 版本，以防使用 vector v(10, 6) （构造对象，内容为10个6）优先匹配上迭代器构造，此时会造成 非法间接寻址 错误  此时多处用到了 匿名对象 作为缺省值 vector(size_t n, const T& value = T()); vector(int n, const T& value = T());因为 T 类型不确定，在设置缺省值时，只能使用 匿名对象 的方式 匿名对象 生命周期只有一行，但在被 const 修饰后，其生命周期会延长内置类型也能创建匿名对象，比如 int()、char() 是合法可用的带参构造、拷贝构造、迭代器区间构造等函数创建新对象前，需要先初始化，有多种初始化方法： 在定义成员变量后设置缺省值在创建新对象前手动进行初始化(初始化列表)调用 默认构造函数 进行初始化这里采用的是初始化列表调用 默认构造函数 初始化的方式 拷贝构造 //拷贝构造-传统写法 vector(const vector& v) :vector() { reserve(v.capacity()); //扩容 size_t pos = 0; while (pos < v.size()) *(_start + pos) = *(v.begin() + pos), ++pos; _finish = begin() + v.size(); } 拷贝构造-现代写法 //vector(const vector& v) // :vector() //{ // vector tmp(v.begin(), v.end()); //构造临时对象 // swap(tmp); //直接交换 //}拷贝构造对象前可以 先进行扩容，避免空间浪费； 采用逐个数据赋值拷贝的方式进行拷贝，因为 T 有可能是自定义类型，逐个赋值可以避免浅拷贝问题 比如 T 为 string 类型，实际调用时是这样的 this[pos] = v[pos]（string 对象，调用对应的赋值重载函数）注意： vector 的拷贝构造函数必须自己写，默认生成的是 浅拷贝 现代写法着重交换思想，利用迭代器区间构造出临时对象，再将临时对象 “交换” 给当前对象即可 这种方式有点窃取劳动成果的感觉~ 赋值重载 //赋值重载-传统写法 vector& operator=(const vector& v) { if (this != &v) { reserve(v.capacity()); //扩容 size_t pos = 0; while (pos < v.size()) *(_start + pos) = *(v.begin() + pos), ++pos; _finish = begin() + v.size(); } return *this; } 赋值重载-现代写法 //vector& operator=(vector tmp) //{ // swap(tmp); // return *this; //}赋值重载的传统写法与拷贝构造基本一致，赋值重载中不需要新建对象，因为是 “赋值” 注意： 赋值前，可以先判断两个对象是否为同一个，如果是，则不需要进行操作 析构函数 //析构函数 ~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; }_start 指向已开辟空间的首位置，可以直接进行空间释放 注意： 空间申请时，使用的是 new []，因此释放时需要使用 delete [] 1.1、经典问题：深度拷贝众多构造函数都离不开空间调整函数 reserve，所以这里提前进行学习，并且 reserve 在实现时会出现一个经典问题：深浅拷贝 void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); //需要先保存 _start 与 _finish 间的距离 pointer tmp = new value_type[n]; //开辟新空间 if (begin()) { //memcpy(tmp, begin(), size() * sizeof(T)); //不能直接移动 size_t pos = 0; while (pos < sz) { //调用自定义类型的赋值重载函数，完成深拷贝 *(tmp + pos) = *(begin() + pos); //深拷贝 pos++; } delete[] begin(); //释放原空间 } _start = tmp; //赋值新空间 _finish = _start + sz; _end_of_storage = _start + n; } }函数执行步骤： 判断 n 是否大于容量，大于才需要进行扩容保存有效元素数（大小），后面有用三步走：开辟新空间 -> 移动元素至新空间 -> 释放旧空间，更改指向注意： 在将旧空间中的数据移动至新空间时，不能直接通过 memcpy/memmove 的方式进行数据移动，因为这些库函数都是 浅拷贝，使用后会造成重复析构问题 举例：使用 memcpy 进行数据迁移 对象中已存在字符串 This is a string，现在进行空间调整  旧空间释放后，其 string 对象被释放，与此同时新空间中的 string 对象也将同步失效  程序运行结束时，调用析构函数进行空间释放（此时会调用 string 的析构函数进行字符串释放），因为旧空间与新空间中的成员皆为同一个，所以会出现 空间重复释放问题  改良：调具体对象的赋值重载函数进行深拷贝(赋值)，不再使用 memcpy 浅拷贝  实际上，拷贝构造、赋值重载、reserve 都需考虑深度拷贝的问题 一句话总结：对于自定义类型来说，在进行拷贝/赋值等操作时，调用对应的赋值重载函数即可 reserve 扩容时，发生了这些事情：  出自 《STL源码剖析》 2、迭代器相关vector 中的迭代器就是原生指针，如 begin() == _start、end() == _finish typedef T value_type; typedef value_type* iterator; //迭代器 typedef const value_type* const_iterator; //=====迭代器设计===== iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }注意： 需要提供两个迭代器版本，即 const 对象的 const 迭代器反向迭代器在后续文章中进行专门讲解利用前面的函数构造对象，在通过迭代器遍历对象，结果如下  3、容量相关3.1、查看容量直接通过迭代器获取值 //=====容量相关===== size_t size() const { return end() - begin(); } size_t capacity() const { return _end_of_storage - begin(); } bool empty() const { return begin() == end(); }3.2、容量调整可以调整容量(reserve)，也可以调整大小(resize) reserve 前面已经介绍过了，这里来看看 resize void resize(size_t n, const_reference val = value_type()) { if (n < size()) erase(begin() + n, end()); else insert(end(), n - size(), val); }操作步骤： 判断 n 是否大于大小如果小于，执行删除，区间为 [begin() + n, end()]如果小于或等于，就执行插入，区间为 [end(), n - size(), val]value_type 就是 T，缺省值为默认对象值 4、数据访问相关4.1、下标访问下标访问有两种方式：operator[] 和 at //=====数据访问===== reference operator[](size_t pos) { assert(pos >= 0 && pos < size()); return *(begin() + pos); } const_reference operator[](size_t pos) const { assert(pos >= 0 && pos < size()); return *(begin() + pos); } reference at(size_t pos) { return (*this)[pos]; } const_reference at(size_t pos) const { return (*this)[pos]; }at 复用 operator[] 的代码，确保函数的稳定性~ 4.2、首尾数据获取首尾数据也可以直接复用 operator[] reference front() { return (*this)[0]; } const_reference front() const { return (*this)[0]; } reference back() { return (*this)[size() - 1]; } const_reference back() const { return (*this)[size() - 1]; }测试结果如下：  5、修改相关5.1、首尾插删void push_back(value_type val)
{
if (size() == capacity())
reserve(capacity() == 0 ? 4 : capacity() * 2); //考虑容量为0的情况
*_finish++ = val; //在最后一个位置插入
}
void pop_back()
{
assert(!empty());
--_finish;
}注意： 尾插时，需要先判断容量是否足够，不够则需要扩容；同时因为容量默认从 0 开始，假若是第一次插入，需将容量扩容为 4 关于尾插，还有一个类似的拼接函数 assign，将某段区间或 n 个 val 值，拼接至对象后面 //=====数据修改===== template void assign(InputIterator first, InputIterator last) { //迭代器区间拼接 InputIterator cur = first; int len = 0; while (cur != last) ++len, ++cur; reserve(len); while (first != last) push_back(*first), ++first; } void assign(int n, const value_type& val) { reserve(n); //提前扩容 while (n--) push_back(val); }执行结果如下：  5.2、任意位置插删任意位置插删更为自由，同时也更加 “危险” iterator insert(iterator pos, const_reference val) { //先记录当前迭代器的位置 size_t sz = pos - begin(); if (size() == capacity()) reserve(capacity() == 0 ? 4 : capacity() * 2); //考虑容量为0的情况 pos = begin() + sz; //更新迭代器 iterator cur = end(); while (cur != pos) *cur = *(cur - 1), --cur; *cur = val; //插入数据 ++_finish; //尾向后移动 return pos; //返回新迭代器位置 } iterator insert(iterator pos, size_t n, const_reference val) { while (n--) pos = insert(pos, val), pos++; //正确写法 return pos; } iterator erase(iterator pos) { assert(pos >= begin() && pos < end()); iterator cur = pos; while (pos != end()) *pos = *(pos + 1), ++pos; --_finish; return cur; } iterator erase(iterator first, iterator last) { //迭代器区间删除 //两个结束条件：last == _finish //while (last != _finish) *first = *(last + 1), ++first, ++last; //错误写法 while (last != _finish) *first = *last, ++first, ++last; //正确写法 _finish = first; return _finish; }2023.5.16 更新 迭代器区间删除时，区间为 左闭右开，在进行数据覆盖时，需要写成 *first = *last 而非 *first = *(last + 1)，这样会导致删除出现问题  感谢大佬：LinAlpaca 指出错误 注意： insert 后迭代器 pos，需要及时更新 若产生扩容行为，迭代器 pos 将指向失效空间，这就是迭代器失效情况之一   迭代器失效时的具体表现：  这只是迭代器失效的其中一种情况：没有更新迭代器位置 5.3、经典问题：迭代器失效下面再来看一个迭代器失效场景 比如下标这段代码会运行失败 void TestVector3() { vector v; auto it = v.begin(); int val = 0; while (val < 100) v.insert(it++, val++); for (auto e : v) cout |
【本文地址】
今日新闻 |
推荐新闻 |