个人主页 ： zxctscl
如有转载请先通知
文章目录
1. 前言2. vector源码3. 构造、赋值和析构3.1 无参构造3.2 拷贝构造3.3 迭代器区间构造3.4 赋值3.5 析构 4. Capacity4.1 size4.2 capacity4.3 empty4.4 resize4.5 reserve 5. 下标访问和迭代器6. 输出7. Modifiers7.1 push_back7.2 pop_back7.3 insert7.4 erase7.5 swap 8. 迭代器失效8.1 insert导致迭代器失效8.2 erase导致迭代器失效 9. 附代码
1. 前言
在之前已经介绍了vector【C++】vector介绍，这次来看看它的模拟实现。
2. vector源码
来看一下vector源码：这里的成员变量都是iterator，而iterator是value_type*，看源码中value_type*又是T。
再来看一下构造，为了方便知道它最开始的初始化。
来看一下push_back：
3. 构造、赋值和析构
3.1 无参构造
像源码里面的一样，成员变量直接给缺省值，这样在构造的时候就走初始化列表。
namespace{template<class T>class vector{public:typedef T* iterator;vector() {}private:iterator _start=nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};}3.2 拷贝构造
这里是一个深拷贝，先开空间reserve(v.capacity())，再把数据插入进去。
// v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}3.3 迭代器区间构造
类模板里面的成员函数可以是函数模板。
可以是其他容器的迭代器也可以用。
就是遍历这个迭代区间，然后把数据放进去就行。
template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}
还可以用string类，支持隐式类型转换，就转换为对应的ASCII码：
void test_vector4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(4);print_vector(v1);vector<int> v2(v1.begin()+1, v1.end()-1);print_vector(v2);string str("abcd");vector<int> v3(str.begin() , str.end() );print_vector(v3);}
size_type就是size_t:
value_type是T:
这里缺省值不能给0，T类型可能会string，也可能是int,所以这里就用一个T类型的匿名对象。
直接开n个空间，然后插入这n个数据push_back(val)。
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);}}
在c++11里面支持花括号：
其实就是两个指针：
单参数的构造函数，隐式类型转换：
还可以直接push_back一个常量字符串
想要模拟实现支持花括号的构造，就得用到initializer_list
initializer_list里面就包了迭代器：
所以模拟实现出来就是：
vector(initializer_list<T> il){reserve(il.size());for(auto& e:il){push_back(e);}}结果测试没有问题：
3.4 赋值
如果把v3赋值给v1，传值传参，v就是v3的拷贝，然后和this交换，返回*this.
vector<T>& operator=(vector<T> v){swap(v);return *this;}
3.5 析构
~vector(){delete[] _start;_start = _finish = _endofstorage=nullptr;}4. Capacity
4.1 size
size_t size() const{return _finish - _start;}4.2 capacity
size_t capacity() const{return _endofstorage - _start;}4.3 empty
bool empty(){return _start == _finish;}4.4 resize
resize这里要给一个缺省值，这个缺省值不能给0。这里可能会是string也可能是vector，所以这里用一个无参匿名对象const T& val = T()。
内置类型没有初始化，但是C++出现模板之后，被迫给内置类型也有构造和析构。
来看个例子：
如果空间不够就先扩容reserve(n);，然后再插入。
删除就只保留n个数据，直接把_finish = _start + n;
void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);// 插入while (_finish < _start + n){*_finish = val;++_finish;}}else{// 删除_finish = _start + n;}}来个代码测试一下：
void test_vector2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(4);print_vector(v1);v1.resize(10);print_vector(v1);v1.resize(3);print_vector(v1);}
4.5 reserve
先判断给的空间是不是大于n，如果大于就开新空间，再把原来的数据拷贝到新开的空间，然后删除就空间，更新_start、_finish和_endofstorage。空间够了，就插入数据，最后++_finish。
void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}}
但是用string类型插入，就挂了:
调试发现这里发生权限：
问题就在reserve里面的memcpy,vector深拷贝了，但是这里的string是浅拷贝，就是说memcpy导致string是浅拷贝：
要解决这里问题就需要string深拷贝，释放上面的空间，对下面的没有影响。
解决方式就是：直接赋值
void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();//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;_endofstorage = tmp + n;}}这样就没有问题了：
5. 下标访问和迭代器
下标访问，const对象和非const对象都写：
T& operator[](size_t pos){assert(pos < size()); return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}都和之前的string的底层相同。
迭代器先得有开始和结尾,就先记录一下，const对象和非const对象都写：
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;}来个例子测试一下：
void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}
6. 输出
想要实现不同类型的vector打印输出，就直接定义一个类模板template<class T>然后再写打印函数输出的时候把T代入：
void print_vector(const vector<T>& v){for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;}来个代码测试一下：
vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(4);print_vector(v1);vector<double> v2;v2.push_back(1.1);v2.push_back(2.2);v2.push_back(3.1);print_vector(v2);这样不同类型的vector就都可以实现输出：
7. Modifiers
7.1 push_back
先检查是否想要扩容，如果没有开空间，就先给4，不然就扩容2倍：size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;，再把原来的数据拷贝到新开的空间，然后删除就空间，更新_start、_finish和_endofstorage。空间够了，就插入数据，最后++_finish。
void push_back(const T& val){if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;T* tmp = new T[newcapacity];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + size();_endofstorage = tmp + newcapacity;}*_finish = val;++_finish;}用代码测试的时候发现出错：
这个是因为在计算新开辟空间的_finish时候用的size是新空间的，而原来空间的已经丢失了。
为了避免这样，先记录一下原来的size大小size_t old_size = size();,再将原来的代码修改为：
void push_back(const T& val){if (_finish == _endofstorage){size_t old_size = size();size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;T* tmp = new T[newcapacity];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + newcapacity;}*_finish = val;++_finish;}加上测试代码看看结果：
void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;}发现可以了：
7.2 pop_back
先判断一下里面是不是有数据，就先判断一下，在执行尾删。
尾删就直接--_finish;
void pop_back(){assert(!empty());--_finish;}来看看测试：
void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);print_vector(v1);v1.pop_back();v1.pop_back();print_vector(v1); }
7.3 insert
在pos位置插入一个数据，这个pos位置得先判断一下，必须在_start和_finish之间。
再判断一下是不是想要扩容，如果扩容了要更新pos。
为什么要更新pos？
开了新的空间pos位置已经释放了，已经成了野指针。
所以得计算相对位置size_t len = pos - _start;，更新到新的空间里面才好找到pos：pos = _start + len;。
然后挪动数据到pos位置，再把val插入pos位置，再更新一下_finish。
void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = val;++_finish;}
7.4 erase
删除每个位置的数据，同样得先判断一下pos的位置在_start和_finish之间，然后挪动数据覆盖，再--_finish。
void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;}来测试一下：
vector<double> v2;v2.push_back(1.1);v2.push_back(2.2);v2.push_back(3.3);v2.push_back(4.4);print_vector(v2);v2.insert(v2.begin(), 11.11);print_vector(v2);v2.erase(v2.begin());print_vector(v2);v2.erase(v2.begin() + 2);print_vector(v2);
7.5 swap
这里直接调用库里面的swap：
void swap(vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}8. 迭代器失效
8.1 insert导致迭代器失效
这里插入数据之后，发现对应出来了随机值
这里是因为it指向旧空间扩容了，被释放了：
怎么解决，如果加引用的话，那么就不能像下面图中这样传了：
而库里面是怎么解决的呢？
库里面就直接不使用这个失效的迭代器，所以这里也是，如果要找的话，就重新更新一下
8.2 erase导致迭代器失效
先来看一个代码：删除所有偶数，有三种情况
第一种：这个是成功的：
第二种：有连续两个4时候，有个4没有删除：
第三种：最后一个是4，,这样就挂了：
第一种：删除4之后，5就覆盖了4的位置，然后再加加。
第二种：删除4之后，后面一个4就覆盖了4的位置，然后再加加，这里就跳过了后面这个4。
第三种：删除4之后，后面一个5就覆盖了4的位置，然后再加加，这里会出现删除最后这个4之后，it往后再加加，就会和end错开，循环判断条件成立，还好继续，就会越界
那么怎么解决这些问题呢？
迭代器失效后，不要直接使用，如果要使用就按规则重新更新后使用。
然后把erase实现里面把返回的位置更新一下就行：
iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}这样就可以使用了：
9. 附代码
#pragma once#include<iostream>#include<assert.h>#include<vector>using namespace std;namespace bit{template<class T>class vector{public: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;}vector(){}// v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}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(initializer_list<T> il){reserve(il.size());for(auto& e:il){push_back(e);}}void swap(vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//v3=v1vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}size_t size() const{return _finish - _start;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();//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;_endofstorage = tmp + n;}}void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);// 插入while (_finish < _start + n){*_finish = val;++_finish;}}else{// 删除_finish = _start + n;}}void push_back(const T& val){/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;++_finish;*/insert(end(), val);}void pop_back(){assert(!empty());--_finish;/*erase(--end());*/}bool empty(){return _start == _finish;}void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = val;++_finish;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};template<class T>void print_vector(const vector<T>& v){for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;}void test_vector1(){/*vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_vector(v1);v1.insert(v1.begin()+2, 30);print_vector(v1);*/vector<double> v2;v2.push_back(1.1);v2.push_back(2.2);v2.push_back(3.3);v2.push_back(4.4);print_vector(v2);v2.insert(v2.begin(), 11.11);print_vector(v2);v2.erase(v2.begin());print_vector(v2);v2.erase(v2.begin() + 2);print_vector(v2);/*for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;*/}void test_vector2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(4);print_vector(v1);v1.resize(10);print_vector(v1);v1.resize(3);print_vector(v1);}void test_vector3(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(4);print_vector(v1);vector<int> v2=v1;print_vector(v2);}void test_vector4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(4);print_vector(v1);/*vector<int> v2(v1.begin()+1, v1.end()-1);print_vector(v2);string str("abcd");vector<int> v3(str.begin() , str.end() );*//*print_vector(v3);*/}void test_vector5(){vector<int> v1(10,1);print_vector(v1);/*vector<char> v3(10, 'a');print_vector(v3);*/}void test_vector6(){//auto x= { 1,2,3,4,5,6,7,8,9,10};//cout << typeid(x).name()<< endl;//vector<int> v1 = { 1,2,3,4,5,6,7,8 }; 单参数的构造函数，隐式类型转换//string str = "11111"; // 构造 + 拷贝构造 -> 优化 直接构造//const string& str1 = "11111"; // 构造临时对象，引用的是临时对象//vector<string> v;//v.push_back(str);//v.push_back(string("22222"));//v.push_back("33333");vector<int> v1 = { 1,2,3,4,5,6,7,8 };for (auto e : v1){cout << e << " ";}cout << endl;}void test_vector7(){vector<string> v;v.push_back("11111");v.push_back("22222");v.push_back("33333");v.push_back("44444");v.push_back("55555");for (auto e : v){cout << e << " ";}cout << endl;}void test_vector8(){vector<int> 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(7);v1.push_back(8);print_vector(v1);vector<int>::iterator it = v1.begin() + 3;v1.insert(it, 40);print_vector(v1);it= v1.begin() + 3;cout << *it << endl;}void test_vector9(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(5);v1.push_back(4);print_vector(v1);// 删除偶数 -- 迭代器失效以后，不要直接使用，如果要使用按规则重新更新后使用vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);}else{++it;}}//print_vector(v1);for (auto e : v1){cout << e << " ";}cout << endl;}}有问题请指出，大家一起进步！！！
