创意广告视频网站,北京建设部网站 信息中心,网站设计厂,seo网站买摘要#xff1a;vector 模拟实现讲解#xff08;附代码示例#xff09;#xff0c;隐藏的浅拷贝#xff0c;迭代器失效 在进行 vector 的模拟实现之前#xff0c;我们先粗略浏览一下 stl_vector.h 文件中的源码来确定模拟实现的大体框架。 这里提供一些粗略浏览源码的技巧…摘要vector 模拟实现讲解附代码示例隐藏的浅拷贝迭代器失效 在进行 vector 的模拟实现之前我们先粗略浏览一下 stl_vector.h 文件中的源码来确定模拟实现的大体框架。 这里提供一些粗略浏览源码的技巧 1.不要一行一行地看 2.先不要研究细节先看整体的框架类成员变量成员函数 3.理解的时候连蒙带猜再验证自己的猜测 ps.在已经模拟实现过 string类的前提下vector 的模拟实现的讲解在一些非必要的地方不多赘述直接给出代码示例。
框架
templateclass T
class vector
{
private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾(指向最后一个有效数据的下一个)iterator _endOfStorage nullptr; // 指向存储容量的尾
}; 首先同 string 类的匿名实现一样我们先创建一个自己的命名空间将 vector 的模拟实现在这个自定义的命名空间中以区分库中的vector。
1. Constructor and Destructor
不多赘述。示例如下。
#pragma oncenamespace Bottle
{templateclass Tclass vector{public:// construct and destroyvector(){}~vector(){delete[]_start;_start _finish _endOfStorage nullptr;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾(指向最后一个有效数据的下一个)iterator _endOfStorage; // 指向存储容量的尾};} 2. push_back
1这里需要顺便实现 size_t capacity()函数 和 size_t size()函数
2思路检查容量 → 插入数据 注意检查容量时如果是遵循两倍扩容的思路就需要注意容量为0的情况如果此时直接按两倍扩容会导致错误
代码示例 size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}//push_backvoid push_back(const T x){if (_finish _endOfStorage){//check capacitysize_t new_capacity capacity() 0 ? 4 : (capacity() * 2);reserve(new_capacity);}*(_finish) x;//push back_finish;}3. reserve
思路开新空间 → 拷贝数据到新空间 → 指向新空间ps.原则上只扩容不缩容
关于指向新空间这个操作需要注意的问题不同于 string类 的size数据是由成员变量存储起来的vector 的size是通过算两个指针之间的偏移量得出的。 如图所示当 _start 发生改变之后_finish ≠ _start size()而应该提前记录下 _finish 相对于 _start 的偏移量。
代码示例
//reserve void reserve(size_t n){if (n capacity()){T* tmp new T[n 1];//newsize_t sz size();memcpy(tmp, _start, sizeof(T) * size());//copydelete[]_start;_start tmp;_finish tmp sz;_endOfStorage tmp n;tmp nullptr;}} 4. Access
1operator[]
代码示例
//operatorr[]T operator[](const size_t pos){assert(pos size());return *(_start pos);}const T operator[](const size_t pos)const{assert(pos size());return *(_start pos);}
2iterator
迭代器实现之后就可以使用范围for了
代码示例 public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend()const{return _finish;} 5. resize 有模板(template)之后C对内置类型进行了升级即一切都是对象以前在C语言里面只有变量而在之后的C中是变量也是对象。e.g. int vi int(2);//该语句可看作调用默认构造函数用 ‘2’ 来构造一个 int 类型的对象 vi . (内置类型也会调用构造) 代码示例
//resizevoid resize(size_t n, const T value T()){if (n size()){//delete_finish _start n;}else{reserve(n);//check capacitysize_t len n - size();while (len--){*_finish value;_finish;//改变finish的指向就是改变size的大小}}} 6. insert
iterator insert(iterator pos, const T x){……}
string 模拟实现 的 insert 思路①检查 pos 位置的有效性②检查容量③挪动数据④插入数据strncpy。 特殊情况头插pos0 vector 思路①检查 pos 位置的有效性②检查容量③挪动数据④插入数据。 特殊情况头插pos0 区别 string中的挪动数据时比较的是下标和下标即 size_t 数据类型的比较头插时比较特殊下标不断变小的过程中可能会出现“-10” 的情况详情见string类模拟实现的文章 vector中挪动数据时比较的是迭代器和迭代器即 T* 因为这里迭代器的底层实现用的是原生指针数据类型的比较所以这里头插不属于特殊情况。但是这也由此引发了另外的问题——迭代器失效。 迭代器失效
① iterator pos 底层是指针。reserve 扩容之后原空间被释放而 pos 还指向原空间。所以我们需要获取 pos 相对于 _start 的偏移量。
② iterator pos 是传值传参。如下图所示。提醒这里也不适合用 传引用传参 (iterator pos)要引用只能是 const 引用 (const iterator pos)因为在类似 v.insert(v.begin(),数据) 的函数调用中begin()函数是传值返回则它的返回值具有常属性只能用 const 引用但 const 引用会使 pos 无法被修改则对于下图所示的迭代器是没有意义的 代码示例
//insertiterator insert(iterator pos, const T x){//check posassert(pos _start);assert(pos _finish);size_t len pos - _start;//偏移量//check capacityif (_finish _endOfStorage){reserve(capacity() 0 ? 4 : (capacity() * 2));pos _start len;//reserve之后更新pos}for (iterator end _finish; end pos; --end){*end *(end - 1);//move data}*pos x;//pos位置insert data_finish;return pos;} 7. erase
思路依次挪动数据覆盖
注意erase 同样会导致迭代器失效。
关于erase导致的迭代器失效 如下图删除数据中偶数的行为出错是因为 erase 导致的迭代器失效删除符合条件的元素之后数据的内容发生了改变就导致原本指向该元素被删除的这个元素的迭代器的指向是未知的当我们在 erase 之后再去使用这个迭代器行为也是位置的。 库里面的做法是 erase 函数会返回要删除的指定 pos 位置的元素的下一个元素的位置。
代码示例 iterator erase(iterator pos){//check posassert(pos _start);assert(pos _finish);//move datafor (iterator it pos 1; it _finish; it){*(it - 1) *(it);}--_finish;return pos;} 8. 隐藏的浅拷贝_reserve
memcpy隐藏的浅拷贝 from reserve如下图所示tip.如果这里运用 引用计数的浅拷贝就会很高效 由上图可知delete 释放空间对于自定义类型 string 会自动调用析构函数导致新空间指向已经被析构掉的空间。因此拷贝数据最好通过赋值操作来实现赋值会自动调用拷贝构造进行深拷贝。 代码示例
//reservevoid reserve(size_t n){if (n capacity()){T* tmp new T[n 1];//newsize_t sz size();for (size_t i 0; i sz; i)//copy{tmp[i] *(_start i);}//memcpy(tmp, _start, sizeof(T) * size());//copydelete[]_start;_start tmp;_finish tmp sz;_endOfStorage tmp n;tmp nullptr;}}9. Copy Constructor
思路 1初始化成员变量 2reserve 3拷贝数据push_back
代码示例
//copy constructorvector(const vectorT v)//copy constructor:_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(v.capacity());for (size_t i 0; i v.size(); i){push_back(v[i]);}}10. 赋值重载
现代写法同 string类 的模拟实现详情见 string类 模拟实习的文章。
代码示例 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//赋值重载vectorT operator(vectorT v){swap(v);return *this;} 11. 其他构造函数重载
注意自己写了构造函数之后编译器不会在生成再生成默认构造所以在构造函数中必须要有一个默认构造函数。
1)template class InputIteratorvector (InputIterator first, InputIterator last); templateclass InputIteratorvector(InputIterator first, InputIterator last){size_t len last - first;reserve(len);for (size_t i 0; i len; i){*(_start i) *(first i);}_finish _start len;_endOfStorage _finish;}
2)vector (size_t n, const T val T())
当 T 为 int 类型时会出现类型匹配的问题如下图因此对于 int 类型需要专门实现的一个函数重载。 vector(size_t n, const T value T()){reserve(n);while (n--){push_back(value);}}vector(int n, const T value T()){reserve(n);while (n--){push_back(value);}} ps.默认构造函数 vector(){} 附
完整代码链接My_vector/My_vector/My_vector.h · fantansy-13-07/Cpp - 码云 - 开源中国 (gitee.com) END
