vector(二)vector模拟实现
vector成员变量是三个迭代器 vector的迭代器底层与string相同是使用 指针实现的 使用的是类模版T*指针
template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;这里使用的是模版类 同时三个私有成员都是由指针的迭代器创建的
其中 _start是指向容器第一个元素位置 _finish是指向容器有效元素的最后一个位置的下一位
_end_of_storage 是指向容器整个空间的最后一个位置
vector<int>v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);在没写构造函数时会自动生成默认的构造函数
void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}push_back尾插 首先是判断是否扩容 之后将要插入的参数放在_finish的位置 之后++_finish 完成尾插 这里的扩容需要reserve函数
void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * oldsize);//对任意类型进行的都是浅拷贝for (size_t i = 0; i < oldsize; i++)tmp[i] = _start[i];//这里的赋值使用的是string的赋值//std::swap(tmp[i], start[i]);delete[] _start;}_start = tmp;_finish = tmp + oldsize;_end_of_storage = _start + n;}}这里的size使用来查看容器中有效数据长度的
size_t capacity()
{return _end_of_storage - _start;
}size_t size()
{return _finish - _start;
}首先必须先拿到size有效长度 并且赋值给一个变量 这样就可以防止后面size()出错
如果直接使用size()函数进行查找 那么在后面当_start重新指向新空间时 这是_finish 和_end_of_storage 还是指向旧的空间 这是通过size和capacity函数进行访问时 就会发生错误
所以要使用变量对size进行赋值存储 防止之后出错
对于vector容器进行遍历需要用到 []重载 以及迭代器begin和end
iterator begin()
{return _start;
}iterator end()
{return _finish;
}
_start和_finish所指向的位置与begin和end相同所以直接返回这两个指针就好
T& operator[](size_t i)
{assert(i < size());return _start[i];
}[]返回的是对应下标的值 这里的访问不仅可以查看 还可以修改当前位置的值
在写好迭代器和[]重载后即可利用三种方式对vector容器进行遍历
void test1()
{vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i = 0; i < v1.size(); i++)//.h文件在运行时不会被编译而是在预处理阶段就会被展开(规则一){//规则二 编译器只会向上查找cout << v1[i] << " ";}cout << endl;vector<int>::iterator it = v1.begin();//这是使用int*作为类型也是可以通过的 因为这里的本质就是int* 但是这里最好是写成标准形式 方便调用其他命名空间和库时可以直接使用while (it != v1.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;
}接下来模拟对容器插入和删除元素 insert和erase
iterator insert(iterator pos, const T& x)//出现随机值问题 扩容会导致pos迭代器失效（野指针）
{//扩容后续重新计算assert(pos >= _start);assert(pos < _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}这里首先通过assert对pos进行检查是否合法 之后就要检查空间是否足够 空间不够则会先进行扩容 之后就是挪动数据 为插入的元素腾出空间 之后在pos位置插入对应元素 完成插入
这里在测试时可能会出现随机值问题 这是因为出现的pos迭代器失效的情况 原理是pos迭代器指向原本的空间 但是如果发生扩容 就会深拷贝 导致pos迭代器还是指向已经消失的空间 没有指向对应的新空间的对应位置上 解决方法 就是使用len记录pos在空间上距离_start的距离 之后在扩容结束后 使用新的_start对pos迭代器进行更新 这样就能 保证迭代器在函数体内正常使用
由于我们的参数是传值的 也就是说我们函数体外面的调用的这个pos迭代器也会失效 正常情况下是不能使用 如果非要使用 可以更改insert的返回类型 返回更新后的pos迭代器 对外面的pos进行一次更新 保证其可以使用
iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}--_finish;return pos;}
erase是删除pos位置的元素并且重新分配空间 首先通过assert来对pos迭代器进行是否合法检查 之后便是挪动数据 更新_finish完成删除 这里的pos也是有可能会发生失效的 如果刚好删除的是最后一个队尾元素 那么在删除完成后迭代器会处于失效 而在一些比遍历情况下 删除即使处于队中的迭代器也会发生失效
void test2(){bit::vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;v1.insert(v1.begin(), 0);for (auto e : v1){cout << e << " ";}cout << endl;v1.erase(v1.begin());for (auto e : v1){cout << e << " ";}cout << endl;v1.insert(v1.begin() + 2, 50);for (auto e : v1){cout << e << " ";}cout << endl;//只有string提供了find 而vector list等都是没有直接提供find 但是他们可以使用算法algorithm库中的find函数（复用）}
void test3()
{bit::vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int x;cin >> x;//如果可以找到x 那么就在x的位置前面插入 如果找不到 那就不插入bit::vector<int>::iterator pos = find(v1.begin(), v1.end(), x);//insert以后这个实参会不会失效if (pos != v1.end())//也是会发生失效的 即使函数内部已经预防进行调整 但是形参改变 不会影响实参 依旧是扩容就会失效{//因为不知道什么时候扩容什么时候失效 所以迭代器的建议是 不要使用可能会失效的迭代器 也不能在参数上加引用 因为begin返回的是传值返回 会产生拷贝后临时变量 具有常性 此时引用会导致权限的放大pos = v1.insert(pos, 1000);//通过函数返回值 来更新一下pos迭代器防止失效 也就是建议失效迭代器不要访问 除非更新一下它}for (auto e : v1){cout << e << " ";}cout << endl;}
void test4()
{vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);int x;cin >> x;vector<int>::iterator pos = find(v1.begin(), v1.end(), x);if (pos != v1.end()){pos = v1.erase(pos);//可能是由删除后缩容引起的迭代器失效//也有可能在删除最后一个成员会导致非法访问if (pos != v1.end())//这里为了访问到队尾的最后一个元素cout << *pos << endl;//这里erase也是通过返回值来更新迭代器从而保证迭代器不会失效}cout << typeid(pos).name() << endl;//不论是在函数执行中形参失效 还是函数执行完成后实参都会失效 这里的vs做的比较绝 在执行完成后会统一将迭代器的类型做出修改 一旦访问这个类型的迭代器就会报错警告for (auto e : v1){cout << e << " ";}cout << endl;
}
void test5()
{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);//如果最后一个是偶数 需要删除的也是可以的 在删除后 pos指向了_finish while循环检查之后就会直接结束了vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);//每次删除后都会导致当前迭代器的失效 需要进行手动更新}else{it++;//不要存侥幸 如果偶尔在一个编译器上能跑 你要考虑这串代码是否在其他编译器上都能跑}}for (auto e : v1){cout << e << " ";}cout << endl;
}
vector() = default;//这里可以强制生成默认构造;vector(const vector<T>& v)
{for (auto e : v){push_back(e);}
}这里是拷贝构造 通过遍历方式依次将内容拷贝给this指向的容器
在写完拷贝构造后 由于拷贝构造也是构造的一种 所以会被当做默认构造 所以通过default强行生成默认构造
void test6(){vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2(v1);//如果不写 生成的是默认的浅拷贝 值拷贝就会导致这里析构两次的问题for (auto e : v2)//没有写 会自动构造 使用的是缺省值 但是没有写构造 写了拷贝构造 构造的规则是 拷贝构造也算构造 这时我们需要自己去写构造了{cout << e << " ";}cout << endl;vector<int>v3;v3.push_back(10);v3.push_back(20);v3.push_back(30);vector<int>v4;v4 = v3;for (auto e : v4){cout << e << " ";}cout << endl;}
//迭代器区间初始化
template <class InputIterator>//一个类模版的成员函数还可以写成函数模版
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}通过这个构造可以直接通过迭代器选择范围进行拷贝
void test7(){vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2(v1.begin(),v1.end());//这是在没写迭代器区间初始化也能做到的for (auto e : v2){cout << e << " ";}cout << endl;vector<int> v3(v1.begin()+2, v1.end());//这是只有迭代器区间初始化后才能做到的for (auto e : v3){cout << e << " ";}cout << endl;string s1("hello");vector<int> v4(s1.begin() +1, s1.end());//char类型转换成整型后使用的是ascll码值for (auto e : v4)//这里因为是模版 谁的迭代器都可以使用{cout << e << " ";}cout << endl;}
vector(size_t n, const T& val = T())//这个地方由于是T模版 所以不能用0去初始化 这里是匿名对象
{//内置类型没有默认构造 这里是默认c++进行了升级reserve(n);for (size_t i = 0;i <n;i++){push_back(val);}
}vector(int n, const T& val = T())//这个地方由于是T模版 所以不能用0去初始化 这里是匿名对象
{//内置类型没有默认构造 这里是默认c++进行了升级reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}void test8()
{int i = 0;int j(1);int k = int();int x = int(2);string s("hello");vector<string> v1(10);//不给第二个参数 走的是缺省值vector<string> v2(10, "xxx");//这里是隐式类型转换vector<string>v3(10,s);for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}cout << endl;for (auto e : v3){cout << e << " ";}cout << endl;vector<int>v4(10, 1);//这里会调用错误的迭代器区间函数 编译器会认为那个编译器更加匹配for (auto e : v4)//也就是上述两个构造同时存在导致的{//解决问题 在输入是手动改为uint//第二就是写一个重载的版本cout << e << " ";}cout << endl;}
vector(initializer_list<int> e2)
{reserve(e2.size());for (auto e : e2){push_back(e);}}void test9()
{vector<int>v2 ({ 1,2,3,4,5,6,7,8,9 });//这里参数数量不固定 即便是上面的也只能写一个或者两个 不能多个，直接构造for (auto e : v2){cout << e << " ";}cout << endl;vector<int>v1 = {1,2,3,4,5,6,7,8,9};//隐式类型转换for (auto e : v1){cout << e << " ";}cout << endl;auto e = { 1,2,3 };initializer_list<int> e2 = {1,2,3,5,7,8,9};//这两者是等价的
}在c++11中添加一些关于隐式类型转化的新形式
在之前的隐式类型转换中最多只有2个进行隐式类型转换 在使用上述的构造后可以进行多个数据进行隐式类型转换
void test10()
{vector<string>v1;v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");for (auto e : v1){cout << e << " ";}cout << endl;
}这里连续超过四个尾插会造成崩溃 原因是第五个插入是会进行扩容 而扩容使进行拷贝时如果使用的memcpy 由于memcpy对任何都是浅拷贝 之后删除_start会导致tmp指向的同一片空间被删除 这样就会导致崩溃 所以时候用swap或者赋值对内容进行拷贝