二、vector的深度剖析及模拟实现
💦 std::vector的核心框架接口的模拟实现
注意我们模拟实现不是把源码中的内容都搬下来，搞一个一模一样的东西，也不是造一个更好的轮子。模拟实现的目的是为了学习源码中的一些细节及核心框架。
💨 vector.h
#pragma once namespace bit { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } const_iterator begin() const { return _start; } iterator end() { return _finish; } const_iterator end() const { return _finish; } vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} //类模板的成员函数还可以再定义模板参数,这样写的好处是first/last可以是list等其它容器的迭代器,只要它解引用后的类型与T匹配 template<class InputIterator> vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { //reserve(?)这个构造函数里传的是一段迭代器区间,只有对象才知道你有多少个容量 while(first != last) { push_back(*first); ++first; } } //v2(v1) //1、传统写法 /*vector(const vector<T>& v) { _start = new T[v.capacity()]; memcpy(_start, v._start, sizeof(T) * v.size()); _finish = _start + v.size(); _endofstorage = _start + v.capacity(); }*/ //2、传统写法————复用当前的一些接口,本质还是自己开空间,这里相对于现代写法更推荐第二种传统写法,因为它这里提前把空间开好了,并利用 /*vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity());//一次性开好空间 for(const auto& e : v)//引用的作用是为了防止T是string等 { push_back(e); } }*/ //3、现代写法,sring那我们是取_str来构造一个临时对象再交换,但是这里怎么取所有的数据来构造并交换呢,没有法子 //这里有个法子：vector的构造函数里还提供了一个显示的迭代器(它可以传其它容器或原生指针做迭代器,但是原生指针必须要求指向的空间是连续的) //所以这里还需要构造一个函数,这里的现代写法对比上面的传统写法并没有讨到便宜() vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { //现代写法里提前开空间没有意义,因为现代写法的空间是tmp去搞的,tmp没办法自己开,因为它不知道有多少个数据,那有人说用last－first,不敢减,因为比如list是不支持减的,它不是一段连续的空间 vector<T> tmp(v.begin(), v.end()); swap(tmp); } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } //v1 = v4; //1、传统写法————不推荐(如果你能掌握现代写法,任何容器的深拷贝都推荐现代写法,尤其是赋值操作) /*vector<T>& operator=(const vector<T>& v) { if(this != &v) { delete[]_start; _start = _finish = _endofstorage = nullptr; reserve(v.capacity()); for(const auto& e : v) { push_back(e); } } return *this; }*/ //2、现代写法,v就是去深拷贝的v4 vector<T>& operator=(vector<T> v) { //v是v1想要的,所以v1和v交换 swap(v); return *this; } ~vector() { delete[] _start; _start = _finish = _endofstorage = nullptr; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstorage - _start; } T& operator[](size_t i) { assert(i < size()); return _start[i]; } const T& operator[](size_t i) const { assert(i < size()); return _start[i]; } void reserve(size_t n) { if(n > capacity()) { //备份一份 size_t sz = size(); T* tmp = new T[n]; if(_start) { //对于string,memcpy会引发更深层次的浅拷贝问题,具体如下说明 //memcpy(tmp, _start, sizeof(T) * size()); for(size_t i = 0; i < size(); ++i) { //如果T是string,它会调用string的operator=完成深拷贝 tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; //_finish = _start + size();err,size去计算时,_finish还是旧空间的_finish,而_start却是新空间的_start了,所以_finish-_start就是一个负值,再加_start就是0 _endofstorage = _start + n; } } //如果没有给值,就用默认值,如果T是int,那就是int的匿名对象。T是string,那就是stirng的匿名对象。它会调用对应的默认构造函数————int是0,double是0.0,指针就是空指针 //所以一般写一个类型,一定要提供一个不用参数就可以调的函数 void resize(size_t n, const T& val = T()) { if(n <= size()) { _finish = _start + n; } else { if(n > capacity()) { reserve(n); } while(_finish < _start + n) { *_finish = val; ++_finish; } } } void push_back(const T& x) { /*if(_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } //这里不用像源码中一样使用定位new,因为使用定位new的原因是finish指向的空间没有初始化,所以使用定位new把对象构造上去。但是我们这里的对象是new出来的,所以这里直接赋值即可 *_finish = x; ++_finish;*/ insert(end(), x); } void pop_back() { /* //一般情况下--finish就行了,但是特殊情况vector为空时就不好 //所以一般需要assert assert(!empty()); --_finish;*/ erase(--end()); } iterator insert(iterator pos, const T& x) { //可以=_finish,因为它相当于尾插 assert(pos >= _start && pos <= _finish); if(_finish == _endofstorage) { size_t len = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; //reserve里会更新那三个成员变量,insert返回新插入的那个元素的地址,所以这里的pos需要先备份一下旧空间里与_start之间的长度,然后再在新空间里重新赋值 reserve(newcapacity); pos = _start + len; } iterator end = _finish - 1; while(end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator it = pos + 1; while(it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; } private: iterator _start; iterator _finish; iterator _endofstorage; }; void print(const vector<int>& v)//const版本的迭代器和operator[] { vector<int>::const_iterator it = v.begin(); while(it != v.end()) { cout << *it << " "; ++it; } cout << endl; for(auto e : v) { cout << e << " "; } cout << endl; for(size_t i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << endl; } void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin(); while(it != v.end()) { cout << *it << " "; ++it; } cout << endl; for(auto e : v) { cout << e << " "; } cout << endl; for(size_t i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << endl; print(v); } void test_vector2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for(auto e : v) { cout << e << " "; } cout << endl; v.resize(2); for(auto e : v) { cout << e << " "; } cout << endl; v.resize(4); for(auto e : v) { cout << e << " "; } cout << endl; v.resize(10, 5); for(auto e : v) { cout << e << " "; } cout << endl; } void test_vector3() { //放string vector<string> v; string s("hello"); v.push_back(s); v.push_back(string("hello")); v.push_back("hello"); v.push_back("hello"); v.push_back("hello"); v.push_back("hello"); for(auto e : v) { cout << e << " "; } cout << endl; } void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator pos = find(v.begin(), v.end(), 2); if(pos != v.end()) { pos = v.insert(pos, 20); } cout << *pos << endl; *pos = 100; ++pos; for(auto e : v) { cout << e << " "; } cout << endl; } void test_vector5() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator pos = find(v.begin(), v.end(), 2); if(pos != v.end()) { v.erase(pos); } //在VS下这段代码是会崩溃的,但是我们很难做到的,但是在Linux下没有崩,所以这块我们就按Linux下实现 cout << *pos << endl; *pos = 100; } void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //删除v中所有偶数 vector<int>::iterator it = v.begin(); while(it != v.end()) { if(*it % 2 == 0) { it = v.erase(it); } else { ++it; } } for(auto e : v) { cout << e << " "; } cout << endl; } void test_vector7() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int> v2(v1); for(auto e : v2) { cout << e << " "; } cout << endl; //为什么现代写法里的构造函数的实现还需要再定义模板,而不使用T*或iterator //因为如果是T*的话就写死了,你是其它容器的迭代器就不行了 string s("abcde"); vector<int> v3(v1.begin(), v1.end()); vector<int> v4(s.begin(), s.end()); //赋值 v1 = v4; for(auto e : v1) { cout << e << " "; } cout << endl; } }
💨 vector.cpp
//库里的string是一个typedef的类模板,当时在模拟的时候简化了 //这里的vector我们就实现成类模板了,在模板初阶里我们提过函数/类模板不支持把声明写到.h,定义写到.cpp的方式，会报链接错误,所以这里我们就不写vector.cpp了
💨 test.cpp
#include<memory.h> #include<assert.h> #include<algorithm> #include<string> #include<iostream> using namespace std; #include "vector.h"//编译器不会去编译头文件vector.h,所以vector.h里所需要的头文件都在此行之前展开就行 //以下是比较常见的错误,编译器编译的原理是头文件展开,展开后,又有一个原则,我用一个东西只会向上去查找,也就是说vector.h里用了cout,它会向上去查找定义,cout是一个全局的对象ostream,唉!那没问题呀,这就是我们之前说的编译器找的时候它只会在全局域里去找,它不会到类域、命名空间里去找,而库里的东西都在std这个域里,而此时我的std是在vector.h之后展开的,所以找不到。 //解决方法就是顺序问题————参照上面写的,或是直接指定类域 //#include<iostream> //#include "vector.h" //using namespace std; int main() { bit::test_vector1(); cout << "-----------------------cut-----------------------" << endl; bit::test_vector2(); cout << "-----------------------cut-----------------------" << endl; bit::test_vector3(); cout << "-----------------------cut-----------------------" << endl; bit::test_vector4(); cout << "-----------------------cut-----------------------" << endl; bit::test_vector5(); cout << "-----------------------cut-----------------------" << endl; bit::test_vector6(); cout << "-----------------------cut-----------------------" << endl; bit::test_vector7(); return 0; }
📝补充
所有的容器我们都不推荐使用传统写法，尤其是后面要学的知识，现在的结构还比较简单，是数组(开好空间，memcpy就都过去了)。后面学到 list、map、树形结构等，就深拷贝时，要把数据拷贝就不是这么简单了。
💦 使用memcpy拷贝问题
假设模拟实现的 vector 中的 reserve 接口中，使用 memcpy 进行的拷贝，以下代码会发生什么问题 ❓
vector<string> v; string s("hello"); //第一次push,开了4块空间 v.push_back(s); v.push_back(string("hello")); v.push_back("hello"); v.push_back("hello"); //再次增容 v.push_back("hello"); v.push_back("hello");
在模拟实现 vector 时，还有一个深层次的浅拷贝问题：如果是 int 是不会出现问题的，问题出在 string 上，详细见下图：
注意我们以前写的拷贝构造的传统写法，包括之前的 string 也面临这种问题。
💦 对bit::vector核心接口的测试
同上 test.cpp 文件
💦 动态二维数组理解
//以杨慧三角的前n行为例:假设n为5 void test5(size_t n) { //使用vector定义二维数组vv,vv中的每个元素都是vector<int> bit::vector<bit::vector<int>> vv(n); //将二维数组每一行中的vecotr<int>中的元素全部设置为1 for (size_t i = 0; i < n; ++i) vv[i].resize(i + 1, 1); //给杨慧三角中第一列和对角线的所有元素赋值 for (int i = 2; i < n; ++i) { for (int j = 1; j < i; ++j) { vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1]; } } }
📝说明
bit::vector<bit::vector< int >> vv(n); 构造一个 vv 动态二维数组，vv 中总共有n 个元素，每个元素都是 vector 类型的，每行没有包含任何元素，如果 n 为 5 时如下所示：
vv 中元素填充完成之后，如下图所示：
使用标准库中 vector 构建动态二维数组时与上图实际是一致的。
