C++容器——vector的基本实现(下)

在上一篇博客中已经讲述了vector的基本使用方法。为了更好的理解其底层原理和提高一定的代码能力本篇博客将针对vector进行一个简单的基础实现。一.vector的基础实现由于vector是模板类所以类内函数的定义和声明不能分开编写否则会出现编译错误。vector是顺序表本质应该类似于在C语言阶段实现过的顺序表但其成员变量有着一些不同的改动。1.1成员变量的声明templateclass T class vector { private: T* _start nullptr; T* _end nullptr; T* _end_of_store nullptr; };std数据库中的vector由3个指针封装而成不再是之前的一个数组指针一个指示数据多少的size_t类型的size 和一个指示空间容量多少的size_t 类型的capacity。三个指针用来指示整个数据_start指向了整个数组的开始位置该指针也起到了申请新的空间大小的功能。_end指向最后一个数据的下一个位置。_end_of_store指向整个数组可存放空间的最后一个位置的下一个位置。用这三个指针变量就可以实现基础的vector的成员结构以及各项参数的表示。例如size的大小就是_end - _startcapacity的大小就是_end_of_store - _start。1.2 基础构造函数 和析构函数vector() :_start(nullptr) , _end(nullptr) , _end_of_store(nullptr) { } ~vector() { if (_start) { delete[] _start; _start _end _end_of_store nullptr; } }首先基础构造函数的实现较为简单实现了一个无参数的默认构造函数将三个指针变量都赋值为nullptr。同样该构造函数也可写作下面这种形式vector() default表示利用系统自动生成的默认构造。因为这里是将三个指针都赋值为nullptr和系统中默认生成的起到相同的效果。析构函数如果_start函数不是空指针需要释放空间。1.3 迭代器相关typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _end; } const_iterator begin() const { return _start; } const_iterator end() const { return _end; }vector本质是数组的结构所以在这里的迭代器自然可以继续利用原生指针类型。直接typedef T* 为iterator同时再次强调const_iterator是其指向的内容不能修改而非其本身不能修改。begin和end分别返回开始位置的迭代器和数据末尾的迭代器。同时也要实现const版本用来针对const对象的使用。1.4 容量大小和 [ ]运算符重载T operator[](size_t pos) { return _start[pos]; } const T operator[](size_t pos) const { return _start[pos]; } size_t size() const { return _end - _start; } size_t capacity() const { return _end_of_store - _start; }[ ]运算符重载需要重载两份同样是针对普通对象和const对象版本。直接返回_start的第pos位置的值即可。同样可以写作*(_start pos)。size和capacity均实现为const成员函数可同时实现针对普通对象和const对象的调用。size的实现直接用指向数据最后一个位置的指针减去开始位置的指针即可。capacity就用指向数组可利用空间最后一个位置的指针减去开始位置的指针即可。1.5 reserve 开辟空间函数void reserve(size_t target_capacity) { size_t old_capacity this-capacity(); size_t old_size this-size(); if (target_capacity old_capacity) { T* tmp new T[target_capacity]; memcpy(tmp, _start, sizeof(T)*old_size); delete[] _start; _start tmp; _end _start old_size; _end_of_store _start target_capacity; } else { return; } }reserve函数用来提前进行空间的开辟或者提供给后续针对数据增加函数的调用。该函数只能实现扩容而非缩容所以利用if进行判断如果要开辟的目标空间大于原空间再进行空间的开辟和数据的挪动否则直接返回即可。空间开辟部分利用new创建一个目标空间大小的 T类型的数组并进行数据拷贝。之后将_start赋值为tmp。_end 和 _end_of_store分别在_start的基础上加size和capacity即可。在这里需要重点注意的是size()函数和capacity()函数虽然能实现计算size和capacity的大小但其实现的方式为两个指针相减。而在扩容函数中_start已经指向了一块新的数组空间_end和_end_of_store仍然指向原来的那块且已经被销毁了的空间。所以直接调用size()和capacity()函数会出问题。在这里的解决方法是在_start指向新空间之前利用两个变量old_size和old_capacity来承接size和capacity的大小之后在_start的基础上直接加上old_size和old_capacity即可。1.6 push_back和pop_backvoid push_back(const T val) { if (_end _end_of_store) { //扩容 size_t new_capacity this-capacity() 0 ? 4 : (this-capacity()) * 2; reserve(new_capacity); } *_end val; _end; } void pop_back() { assert(_start ! _end); _end--; }在有了reserve函数之后push_back函数的实现就变得非常简单。首先判断扩容 仍然采用二倍的扩容机制。直接在end的位置添加数据end向后自增即可。pop_back则相反让_end向前走一步即可。同时要进行断言如果在这个顺序表为空表时仍然向前走就会出现很大的问题。可能会导致后续判断始终无法做到_start _end从而导致死循环等。再实现一个打印函数用来方便输出vector内部的数据templateclass Container void print(const Container val) { for (size_t i 0; i val.size(); i) { cout val[i] ; } cout endl; }该打印函数同样利用模板来实现这样方便其输出各种参数的vector。遍历整个vector输出每一项值即可。将vector实现到这一步就可以进行一些基础测试了vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); print(v1); v1.pop_back(); print(v1); v1.pop_back(); v1.pop_back(); v1.pop_back(); v1.pop_back(); print(v1); v1.pop_back(); print(v1);首先创建一个空的vectorint的对象v1尾插5个数据之后再尾删6次这样会触发断言报错。第一个print顺利输出了1-5这5个数据。在尾删了一个数据之后只输出了1-4。把剩下的数据删完后只输出了一个空行。最后再进行删除出现了断言报错。截至到这里的函数实现方式没有大的问题。1.7insert函数void insert(iterator pos, const T val) { assert(pos _start); assert(pos _end); if (_end _end_of_store) { size_t position pos - _start; //扩容 size_t new_capacity this-capacity() 0 ? 4 : (this-capacity()) * 2; reserve(new_capacity); //因为这里的pos是一个迭代器而非下标 //所以扩容后这个pos仍然指向了原来那个数组的某个位置成为了类似与野指针的东西 //这叫做迭代器失效 //失效后的迭代器一定不要使用 pos _start position; } iterator it _end; while (it ! pos) { *it *(it - 1); it--; } _end; *pos val; }insert函数的参数需要传递一个迭代器位置并在这个位置插入数据。整体思路实现为将pos位置的数据依次往后挪动一个位置之后在pos位置插入数据即可。首先assert检查pos的合法性pos需要在_start和_end之间才能插入数据。之后判断空间是否足够不够则扩容。扩容时就会产生问题在string的实现中insert函数传递的参数是一个size_t 类型的pos数据而在这里传递的是一个迭代器位置本质就是一个指针指向了需要修改数据的位置。而这个位置是原数组的位置在reserve开辟新的空间之后三个指针成员变量会指向一个新的数组。所以指向原数组pos位置的迭代器就不再能用。管着叫做——迭代器失效。失效后的迭代器就不能在继续使用了。而解决方法也很简答只需要提前记录好pos和_start的相对位置在变换新数组后_start 相对位置即可得到针对当前这个新数组的pos位置的迭代器了。之后依次挪动数据并在pos位置赋值即可。最后记得_end要自增指向下一个位置。简单测试如下vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.insert(v1.begin(), 0); print(v1); vectorint::iterator target find(v1.begin(),v1.end(), 3); if (target ! v1.end()) { v1.insert(target, 11); } print(v1); //此时的*target 虽然没有失效 *target 1000; print(v1);首先创建了一个空的vector对象尾插1-4这4个数据。之后在v1开始位置插入了一个0。其次利用find函数在这个顺序表中查找3这个数据如果找到了返回3的迭代器位置。如果这个迭代器位置有效则在该迭代器位置插入一个11。最后将该迭代器位置的值改为1000。可看到正确的在第一个位置插入了一个0以及在3之前插入了一个11最后将11改为了1000。此时的该迭代器虽然没有失效且能正确的将顺序表中的11改成了1000。但这是没有发生扩容的情况。在所有情况下我们都应该认为顺序表会随时发生扩容都认为该迭代器已经失效后续不可继续使用否则会很危险。1.8 erase函数iterator erase(iterator pos) { assert(pos _start); assert(pos _end); //erase就不用考虑扩容导致迭代器失效的问题但也有其他考虑 iterator it pos; while (it ! _end -1) { *it *(it 1); it; } --_end; return pos; }erase函数的实现首先要判断pos位置是否合理。之后数据依次向前移动即可。erase函数虽然不会因为扩容导致迭代器失效但仍然要认为其迭代器发生了失效。而为了解决该问题erase返回值为一个迭代器该迭代器指向了顺序表中下一个位置的数据而又由于已经删除了一个数据所有数据向前移动了一个位置所以还是直接返回pos即可。一个测试案例如下vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(6); v1.push_back(6); v1.push_back(6); v1.push_back(6); print(v1); vectorint::iterator it v1.begin(); while (it ! v1.end()) { if (*it % 2 0) { it v1.erase(it); } else { it; } } print(v1);空对象v1尾插1 2 3 4 5 6 6 6 6 下面实现如果当前迭代器位置的数据是偶数则删除否则跳过。可看到该程序正常删除了偶数连续偶数和最后一个位置是偶数的情况也顺利的解决。1.9 resize函数void resize(size_t n, T val T()) { if (n size()) { _end _start n; return; } else { if (n capacity()) { reserve(n); } size_t num n - size(); for (size_t i 0; i num; i) { push_back(val); } } }在有了之前函数的基础上resize函数的实现就较为便捷。首先resize分三种请况1.如果目标长度小于原长度直接缩小_end的指向这样做会导致一部分数据丢失。第二三种情况本质都是要改变的目标长度大于原长度这时候开辟出的空间需要在之后补充数据这是resize的第二个参数。第二个参数给了缺省参数的默认构造而在C中为了解决模板是内置类型如int、double、char等的默认构造问题这些内置类型也支持该方式进行默认构造int会自动给0char会给‘\0’如果T是一个自定义类型则会调用默认构造。之后依次将不足的数据添加到顺序表末尾即可。至此vector的基础实现部分完成。下面部分实现一些需要借助这些函数来实现的构造、拷贝构造等。1.10 reserve函数的不足与改进void reserve(size_t target_capacity) { size_t old_capacity this-capacity(); size_t old_size this-size(); if (target_capacity old_capacity) { T* tmp new T[target_capacity]; //memcpy(tmp, _start, sizeof(T)*old_size); for (size_t i 0; i old_size; i) { tmp[i] _start[i]; } delete[] _start; _start tmp; _end _start old_size; _end_of_store _start target_capacity; } else { return; } }在1.5部分实现的reserve函数中数据拷贝用的是memcpy。这是将原始数组中存放的数据拷贝到新的数组中针对内置类型和没有额外资源的自定义类型该方法没有问题。但如果vector存放的是string这样存放有额外资源的类型就会出现浅拷贝的问题。string中存放有一个指向数组的_str指针一个_size和一个_capacity。这三个成员变量存放在vector中而利用memcpy仅仅会将这三个变量的空间拷贝到新的数组中但仍然指向原字符串数组的空间。之后delete [ ]会调用string的析构函数释放掉字符串数组空间那就导致了存放在vector顺序表中的string中的指针变为了野指针。针对这个问题本质还是浅拷贝的问题需要深拷贝将string中的资源一并拷贝。所以直接遍历每个元素位置进行赋值即可。这会调用自定义类型的赋值运算符重载进行深拷贝。1.11 拷贝构造和赋值运算符重载void swap(vectorT v) { std::swap(_start, v._start); std::swap(_end, v._end); std::swap(_end_of_store, v._end_of_store); } vector(const vectorT v) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } vector operator(vectorT v) { swap(v); return *this; }拷贝构造和赋值运算符重载分别用了传统写法和现代写法。拷贝构造首先开辟目标对象大小的空间之后遍历目标对象依次尾插即可。赋值运算符重载传递一个形参对象注意一定不能用引用类型之后直接调用swap即可。1.12 其它类型的拷贝构造vector(initializer_listT il) { reserve(il.size()); for (auto e : il) { push_back(e); } } vector(iterator first, iterator last) { reserve(last - first); iterator pos first; while (pos ! last) { push_back(*pos); pos; } } vector(size_t n, T val) { reserve(n); resize(n,val); } vector(int n, T val) { reserve(n); resize(n,val); } vector(long n, T val) { reserve(n); resize(n,val); }在这里实现了三种构造。1.initializer_list构造需要用到initializer_list.h这个头文件开辟空间范围for遍历initializer_list对象尾插即可。2.迭代器区间构造开辟空间遍历这个迭代器区间每个数据依次尾插即可。3.n个T类型数值的构造开辟空间resizen,val即可。重载版本多主要是n的类型不同 防止调用到迭代器区间构造。至此vector的底层基础结构大致实现。