![头像](http://zhangshiyu.com/zb_users/upload/2024/09/20240906160502172560990255405.png)
目录
?1、vector的主要函数接口?2、vector的模拟实现?2.1 构造和析构?2.2 vector属性相关函数?2.3 运算符重载?2.3.1 赋值重载?2.3.2 [ ] 重载 ?2.4 vector的打印?2.5 扩容?2.5.1 深拷贝中的浅拷贝问题 ?2.6 迭代器失效的问题?2.6.1 插入和删除?扩容形成野指针?挪动数据位置意义改变 ?2.7 调整大小 ?3、vector模拟实现完整代码
?1、vector的主要函数接口
namespace yjz{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认构造vector(){}//拷贝构造vector(const vector<T>& v){}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){}//指定n个值构造vector(size_t n, const T& val = T()){}vector(int n, const T& val = T()){}//析构~vector(){}//交换数据void swap(vector<T>& tmp){}//清理数据void clear(){}传统写法//vector<T>& operator=(const vector<T>& v)//{}//现代写法vector<T>& operator=(vector<T> tmp){}size_t size() const{}size_t capacity() const{}//迭代器iterator begin(){}iterator end(){}const_iterator begin() const{}const_iterator end() const{}//【】重载T& operator[](size_t i){}const T& operator[](size_t i) const{}//判空bool empty(){}//尾删void pop_back(){}//扩容void reserve(size_t n){}//尾插void push_back(const T& n)//可能插入类等{}//插入iterator insert(iterator pos, const T& n){}//删除iterator erase(iterator pos){}//调整大小void resize(size_t n, T val = T()){}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};template<class T>void print_vector(const vector<T>& v){}}
?2、vector的模拟实现
?2.1 构造和析构
虽然vector
使用编译器生成的默认构造就行,但是我们还需要写拷贝构造,有了构造函数编译器就不会生成默认构造了,所以可以在形式上写个默认构造类模版的成员函数,还可以继续是函数模版 //默认构造vector(){}//拷贝构造vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//指定n个值构造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 (size_t i = 0; i < n; i++){push_back(val);}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
?2.2 vector属性相关函数
size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}
?2.3 运算符重载
?2.3.1 赋值重载
赋值重载可以借助swap
函数,需要注意的是形参必须传值 void swap(vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}//现代写法vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}
?2.3.2 [ ] 重载
T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}
vs系列编译器,debug模式下at()
和 operator[]
都是根据下标获取任意位置元素的,在debug模式下两者都会去做边界检查。当发生越界行为时,at 是抛异常,operator[]
内部的assert
会触发 ?2.4 vector的打印
为了方便打印vector
中不同类型的数据,可以将迭代器遍历和范围for遍历封装成一个模版函数,有几点需要注意:
const
引用传参,避免拷贝,迭代器也要保持一致使用const_iterator
没有实例化的类模版里面取东西,编译器不能区分这里的const_iterator
是类型还是静态成员变量,从属名称的使用必须以typename
为前缀当然最省事的还是auto
template<class T>void print_vector(const vector<T>& v){//typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}
?2.5 扩容
?2.5.1 深拷贝中的浅拷贝问题
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;//_finish = _start + size();_finish = _start + old_size;//_finish也要更新_end_of_storage = _start + n;}}
上面是以前扩容的常规操作,但是在这里有些潜在的问题:
void test_vector7(){vector<string> v1;v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");print_vector(v1);}
当我们在不扩容的情况下在vector
中插入string
类,不会出现什么问题,但如果扩容的话,就会出现问题:
这里的问题在扩容的过程中memcpy
是按字节拷贝的(浅拷贝),而string
类中还有_str
指向一块空间,memcpy
将string
类中的所有数据都浅拷贝到tmp
指向的空间中,tmp
中的_str
指向的还是原来的空间,释放旧空间时其中的string
类会自动调用析构函数,释放掉_str
指向的空间,最后tmp
空间中的_str
指向的就是非法空间。
要想解决这个问题也简单,用深拷贝来代替memcpy
的浅拷贝,可以考虑赋值重载,因为 string
类的赋值重载是深拷贝:
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;//_finish = _start + size();_finish = _start + old_size;//_finish也要更新_end_of_storage = _start + n;}}
?2.6 迭代器失效的问题
?2.6.1 插入和删除
?扩容形成野指针
在指定位置插入一个数据,首先要判断vector
是否满了,如果满了调用reserve
扩容。插入前还需要挪动指定位置之后的数据,最后插入数据,++_finish
。
void insert(iterator pos, const T& n){ assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;}
这是常规的插入方法,和string
类插入一个字符一样。
但是当我们插入一个数据需要扩容时,编译运行就会陷入死循环。
原因是虽然扩容后_start
、_finish
、_end_of_storage
都更新了,但是pos
指向的还是原来的位置。
所以我们需要在扩容后将pos
的指向也更新一下:
void insert(iterator pos, const T& n){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;}
?挪动数据位置意义改变
假如我们想在某个数据前面插入但是不知道具体位置,则需要先查找到这个数据的地址:
int n;cin >> n;auto pos = find(v.begin(), v.end(), n);if (pos != v.end()){v.insert(pos, 40);*pos += 100;}print_vector(v);
如果没有扩容,pos
原本指向的数据是我们要查找的3,但是在我们往3的前面插入一个40后,pos
指向的数据就变了,这也被认为是迭代器失效;如果扩容,则就是上面讲的pos
变成野指针。
vector
类似,string
在插入+扩容操作+erase
后,迭代器也会失效所以不管扩不扩容, insert
后pos
就失效,不要直接访问,要访问就要更新迭代器的值。 可以在insert
函数最后返回pos
的值:
iterator insert(iterator pos, const T& n){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;return pos;}
int n;cin >> n;auto pos = find(v.begin(), v.end(), n);if (pos != v.end()){ pos = v.insert(pos, 40);*(p + 1) += 100;}print_vector(v);
同样的删除也会使迭代器失效:
iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}
删除vector
中任意位置的数据,VS都认为该位置迭代器失效 ?2.7 调整大小
为了兼容类类型给缺省值的情况,内置类型也有了构造函数的概念。
void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);//大了才扩容while (_finish < _start + n){*_finish = val;++_finish;}}}
?3、vector模拟实现完整代码
vector.h:
#pragma once#include <iostream>#include <assert.h>#include <string>using namespace std;namespace yjz{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认构造vector(){}//拷贝构造vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//指定n个值构造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 (size_t i = 0; i < n; i++){push_back(val);}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void swap(vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}void clear(){_finish = _start;}传统写法//vector<T>& operator=(const vector<T>& v)//{//if (this != &v)//{//clear();//reserve(v.size());//for (auto e : v)//{//push_back(e);//}//}//}//现代写法vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}bool empty() const{return _start == _finish;}void pop_back(){assert(!empty());_finish--;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;//_finish = _start + size();_finish = _start + old_size;//_finish也要更新_end_of_storage = _start + n;}}void push_back(const T& n)//可能插入类等{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = n;++_finish;}iterator insert(iterator pos, const T& n){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;return 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;}void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};template<class T>void print_vector(const vector<T>& v){//typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;//for (auto e : v)//{//cout << e << " ";//}//cout << endl;}}
拷贝构造最后不需要再更新_finish
和_end_of_storage
,因为reserve
中更新了_end_of_storage
和_start
指向的空间reserve
中不能使用memcpy
拷贝原始数据,memcpy
是浅拷贝,而vector
中也可以存类类型;可以考虑赋值重载reserve
中更新_finish
的时候不能用_finish = _start + size()
,因为size()
是通过_finish - _start
得到的,而扩容过后_start
和_finish
指向的已经不是同一空间了,所以size()
是错误的,应该在扩容前保存下旧的size
的值,扩容后再用这个值更新_finish
在insert
中同样也有类似的问题,当空间不够时就要扩容,而pos
是指向原来空间的迭代器,所以在扩容前也要提前保存下pos
相较于_start
的位置,在扩容后及时地更新pos
的指向还需要特别注意的是insert
和erase
中迭代器失效的问题 test.cpp:
#define _CRT_SECURE_NO_WARNINGS#include "vector.h"namespace yjz{void test_vector1(){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);}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() + 2, 10);print_vector(v);}void test_vector3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);int n;cin >> n;auto pos = find(v.begin(), v.end(), n);if (pos != v.end()){pos = v.insert(pos, 40);*(pos + 1) += 100;}print_vector(v);}void test_vector4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4);print_vector(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}print_vector(v);}void test_vector5(){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.resize(3);print_vector(v);v.resize(8, 1);print_vector(v);}void test_vector6(){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(10, 1);print_vector(v2);vector<int> v3(v2.begin() + 1, v2.begin() + 5);print_vector(v3);}void test_vector7(){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");v1.push_back("11111111111111");v1.push_back("11111111111111");print_vector(v1);}}int main(){//yjz::test_vector1();//yjz::test_vector2();//yjz::test_vector3();//yjz::test_vector4();//yjz::test_vector5();//yjz::test_vector6();yjz::test_vector7();return 0;}