【C++】——vector深度剖析模拟实现

低头赶路，敬事如仪

---

目录

1、模拟vector

1.1底层结构

1.2构造析构

1.3尾插扩容

1.4迭代器

1.5增删查改

1.6模拟中的注意事项

2、vector模拟补充

2.1迭代器区间构造问题

2.2memcpy深浅拷贝问题

2.3动态二维数组的模拟及遍历

---

1、模拟vector

想要模拟实现自己的vector，得知其所以然！

分析一下STL源码里的vector底层成员变量

可以看到是三个迭代器类型成员变量，迭代器类型是什么呢？

经过typedef的底层指针，而T类型是模版类的参数。

大致框架如图：

1.1底层结构

根据我们刚才所查看的源码，我们要使用三个迭代器，要使用迭代器，我们可以使用指针进行模拟。

namespace xc
{//设置成模板 兼容各种参数 但是不能分离编译否则链接错误template<class T>class vector{public:typedef T* iterator;private:iterator _start = nullptr;//指向容器开始iterator _finish = nullptr;//指向有效数据下一个位置iterator _end_of_storage = nullptr;//指向空间容量的下一个位置};
}

写出三个迭代器（指针）后，我们可以接着实现构造函数：需要初始化三个迭代器，所以我们给予初始值nullptr。然后进行开辟空间。

1.2构造析构

实现常用的构造析构以及赋值重载

/*	vector(){}*///C++11 强制生成默认构造vector() = default;//优先匹配构造函数，防止非法的间接寻址问题vector(size_t n, const T& val = T()){reserve(n);for (size_t i=0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i=0; i < n; i++){push_back(val);}}vector(long long n, const T&val = T()){reserve(n);for (long long i=0; i < n; i++){push_back(val);}}//类模板的成员函数还可以继续是函数模板template<class InputIterator>  //写成模板是为了兼容所有容器vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}// v1(v)vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}void clear(){_finish = _start;}v1=v//vector<T>& operator=(const vector<T>&v)//{//	if (this != &v)//	{//		clear();//		reserve(v.size());//		for (auto& e : v)//		{//			push_back(e);//		}//	}//	return *this;//}void swap(vector<T>&v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//现代写法 V1=vvector<T>& operator=(const vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[]_start;_start = _finish = _end_of_storage = nullptr;}}

1.3尾插扩容

想要实现尾插的操作，根据之前的经验，可以知道需要复用一些常用的简单接口（size() capacity() reserve() 等）

size_t size()const { return _finish - _start; }size_t capacity()const { return _end_of_storage - _start; }bool empty()const { _start == _finish; }//void reserve(size_t n)
//{
//	if (n > capacity())
//	{
//		T* tmp = new T[n];
//		memcpy(tmp, _start, sizeof(T));
//		delete[]_start;//		_start = tmp;
//		_finish = _start + size();//这是错误的  _start 已经是扩容后的 start了 而size调用的是 finish - start
//									//解决方法 可以先更新 finish 或者记录一下 size的值
//		_end_of_storage = _start + n;
//	}
//}void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size()*sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}void reseize(size_t n, T val = T())//内置类型也具有的构造析构等函数行为 但是并没有概念
{if (n < size()){_finih = _start + n;}else{reserve(n);while (_finsh < _start+n){*_finish++ = val;}}
}void push_back(const T& x)
{//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish++ = x;
}

注意：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

1.4迭代器

所需要实现的迭代器其实很简单，对指针 typedef 即可

typedef T* iterator;
typedef const T* const_iterator;iterator begin() { return _start; }iterator end() { return _finish; }const_iterator begin()const { return _start; }const_iterator end()const { return _finish; }

实现了简单的迭代器，我们可以测试一下 迭代器遍历和范围for遍历

void test_vector1()
{vector<int> v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << ' ';++it;}cout << endl;for (auto e : v){cout << e << ' ';}cout << endl;
}

这里我们为了后续方便封装一个打印函数

template<class T>
void print_vector(const vector<T>& v)
{vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << ' ';++it;}cout << endl;
}

可是这居然报错

为什么呢？没有实例化的类模板里面取东西，编译器是分不清 const_iterator 是静态成员变量还是类型的，在前面加一个 typename 显示告诉编译器是类型即可

template<class T>
void print_vector(const vector<T>& v)
{typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << ' ';++it;}cout << endl;
}

1.5增删查改

void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;
}

看起来没什么问题，但是存在着迭代器失效的风险

pos仍指向原来的空间！记录相对位置，修正一下pos即可

void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){size_t len = pos - _start;//记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;
}

值得注意的是STL里的 insert有返回值！

这是为什么呢？还是防止迭代器失效的一种措施。

void test_vector2()
{vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_vector(v);/*	v.insert(v.begin() + 1, 10);print_vector(v);*/int x;cin >> x;// x==2auto pos = find(v.begin(), v.end(), x);//没找到返回 last 左闭右开区间if (pos != v.end()){v.insert(pos, 40);//pos 可以理解为下标位置 也可以理解为原来位置数据前面插入一个数据print_vector(v);(*pos) *= 10;//期望将x乘以10 但是是插入的40*10  并没有指向原来的数据//归为迭代器失效一类}print_vector(v);}

如果这里还发生了扩容呢？？就是将push的5给删掉

这是什么鬼？我们不是已经修正了pos的位置吗？显然这里的p已经失效了！形参是无法改变实参的，我们修正了pos，但是影响不了p

传const 引用过去影响实参。但不是常量引用的话 ，下面代码会报错！

因为函数调用返回的参数是临时变量，且临时变量具有常性。

而事实上加了const引用里面的pos就无法修正了！我们的思路错了，STL的操作是加一个返回值 （返回的是新插入数据的下标）

iterator insert(iterator  pos, const T& x)
{assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage){size_t len = pos - _start;//记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;
}

所以 insert后不能再访问find 的 p 想要访问得更新！

增删查改：

iterator insert(iterator  pos, const T& x)
{assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage){size_t len = pos - _start;//记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;
}iterator erase(iterator pos)
{assert(pos < _finish && pos >= _start);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;
}size_t find(T val = T())
{for (auto it = _start; it < _finish; it++){if (*it == val){return it - _start;}}return -1;
}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 pop_back()
{assert(!empty());--_finish;
}

1.6模拟中的注意事项

• 规定：类模板在没有实例化时，迭代器无法读取！编译器不能区分这里const_iterator是类型还是静态成员变量。要想解决：第一可以在前面加上typename用来证明这里是类型；第二用auto，让编译器判断为类型
• 
• 内置类型是没有构造函数的概念，但为了兼容模板（T val = T( ) ），可以被视为具有默认构造函数的行为

void reseize(size_t n, T val = T())//内置类型具有的构造析构等函数行为，并没有对应概念
{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start+n){*_finish++ = val;}}
}

•  c++11中有强制生成默认构造的操作，即使类中已有其他构造函数，也能强制生成。eg：vector( ) = default

• 类里面可以用类名替代类型（特殊化），类外面规定：类名不能代表类型

//类里面可以用类名替代类型（特殊化）
//vector & operator=(vector v)
vector<T>& operator= (vector<T> v)
{swap(v);return *this;
}

• 类模板的成员函数，还可继续是函数模板

//类模板的成员函数还可以继续是函数模板
template<class InputIterator>  //写成模板是为了兼容所有容器
vector(InputIterator first, InputIterator last)
{while(first != last){push_back(*first);++first;}
}

2、vector模拟补充

2.1迭代器区间构造问题

//C++11 强制生成默认构造
vector() = default;vector(size_t n, const T& val = T())
{reserve(n);for (size_t i; i < n; i++){push_back(val);}
}//类模板的成员函数还可以继续是函数模板
template<class InputIterator>  //写成模板是为了兼容所有容器
vector(InputIterator first, InputIterator last)
{while(first != last){push_back(*first);++first;}
}

这个是对迭代器区间进行的构造函数，思路很简单，把迭代器区间的数据依次尾插就可以了（这里之所以另外使用一个新的模版，而不是使用vector类的模版，是为了兼容其他容器类型）。这样就可以通过一个现有的类型来构造容器。
但是出乎意料的是出现了一个问题： C2100 非法的间接寻址 （编译层面的问题） 。非法的间接寻址的造成原因有很多：

1. 空指针引用：当一个指针没有被初始化或者为NULL时，对它进行间接寻址操作会导致非法访问。
2. 野指针引用：当一个指针超出了它所指向的内存范围，或者已经被释放但仍然被引用时，进行间接寻址操作也会导致非法访问。
3. 类型不匹配：如果试图将指针转换为不兼容的类型进行间接寻址，也会导致非法访问。

为什么报错在迭代器构造呢？因为编译器会寻找最合适的函数，但是这里与我们期望所违背！！

为了解决编译器选择的问题，可以多枚举几个构造函数：

vector(size_t n, const T& val = T())
{reserve(n);for (size_t i=0; i < n; i++){push_back(val);}
}vector(int n, const T& val = T())
{reserve(n);for (int i=0; i < n; i++){push_back(val);}
}
vector(long long n, const T&val = T())
{reserve(n);for (long long i=0; i < n; i++){push_back(val);}
}

这样可以做到优先匹配vector(int n,T val = T());，我们的问题也就解决了。 

2.2memcpy深浅拷贝问题

我们测试一下自定义类型的vector（这里以string为例）：

void vector_test6() {vector<string> v1;v1.push_back("11111");v1.push_back("22222");v1.push_back("33333");v1.push_back("44444");//再次插入扩容v1.push_back("55555");print_vector(v1);
}

程序崩溃了

分析：
<1> memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
<2> 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃

解决方法：

void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, size()*sizeof(T));//浅拷贝for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];//自定义类型的话 也是会调用自定义类型的赋值重载}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

2.3动态二维数组的模拟及遍历

结构框架图：

//二维数组
vector<int>v(3, 1);
vector<vector<int>>vv(5, v);vv[2][1] = 2;
//与上述等价  vv.operator[](2).operator[](1) = 2;
for (size_t i = 0; i < vv.size(); i++)
{for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << ' ';}cout << endl;
}
cout << endl;for (auto it = vv.begin(); it != vv.end(); it++)
{for (auto jt = (*it).begin(); jt != (*it).end(); jt++){cout << *jt << ' ';}cout << endl;
}
cout << endl;auto it1 = vv.begin();
/*auto it2 = (*it1).begin();*/
while (it1 != vv.end())
{auto it2 = (*it1).begin();//更新it2 指针在堆上分配，所以可以看见内存不是连续分配的while (it2 != (*it1).end()){cout << *it2 << ' ';it2++;}cout << endl;it1++;
}
cout << endl;for (auto row : vv)
{for (auto column : row){cout << column << ' ';}cout << endl;
}
cout << endl;

应用：杨辉三角

// 以杨慧三角的前n行为例：假设n为5
void test2vector(size_t n)
{// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>vector<vector<int>> vv(n);// 将二维数组每一行中的vecotr<int>中的元素全部设置为1for (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];}}
}

构造一个vv动态二维数组，vv中总共有n个元素，每个元素 都是vector类型的，每行没有包含任何元素，n为5时如下所示：