郑州网站seo优化公司,Wix网站开发 工作室,女朋友做网站,中信建设有限责任公司客户前言#xff1a;vector是表示可变大小数组的序列容器。就像数组一样#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问#xff0c;和数组一样高效。但是又不像数组#xff0c;它的大小是可以动态改变的#xff0c;而且它… 前言vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是 一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小下面我们就来介绍一下实现vector时可能会遇到的一些问题和接决策略最终奉上模拟实现代码。 还是老规矩我们给出实现类的初始代码以方便更好的阅读后续的代码,该部分的代码不再做过多赘述有兴趣的读者可以评论
#pragma once
#includeassert.hnamespace my_std
{templateclass T//vector存储的元素需要用模板来表示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()//声明中已给出缺省值可以省略不写{}~vector(){delete[] _start;//采用new/delete的形式存储_finish _endofstorage nullptr;}size_t capacity() const //空间容量{return _endofstorage - _start;}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];}private://初始化加上缺省值iterator _startnullptr;//开头iterator _finish nullptr;//结尾加1iterator _endofstorage nullptr;//空间容量};
}
目录
1.尾插元素和扩容函数
异地扩容导致原地址失效
2.匿名对象做缺省值的resize函数
3.memcpy-特殊类型的浅拷贝“隐藏杀手”
string类成员的浅拷贝
4.迭代器失效问题
insert函数带来的迭代器失效
erase函数带来的迭代器失效
5.拷贝构造和赋值问题
6.迭代器区间初始化构造
7.完整代码
vector.h
test.cpp 1.尾插元素和扩容函数
异地扩容导致原地址失效 我们的vector实际上是一个数组容器也是一个由头尾指针组成的一定长度的顺序表我们在实际操作时只能操作头指针或者尾指针中的一个来控制数组另一个指针是随着操作的指针变化而变化的我们只需要知道数组长度即可但是在当前空间不够用的情况下又采取异地扩容可能会导致头尾指针分离一段时间如果不能察觉就会导致数组出现错误 void reserve(size_t n)//扩容函数{if (n capacity()){T* tmp new T[n];size_t sz size();if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endofstorage _start n;}}
void push_back(const T x){//如果空间满了先扩容size_t n _finish - _start;//提前算出保存避免后序因异地扩容而导致原地址失效if (_finish _endofstorage){size_t len capacity() 0 ? 4 : capacity() * 2;T* temp new T[len];if (_start)//如果原来有内容{memcpy(temp, _start, sizeof(T)*n);delete[] _start;}_start temp;_finish _start n;_endofstorage _start len;//reserve(len);如果复用将从T* temp开始到_endofstorge_startlen注释即可}*_finish x;_finish;//insert(end(), x);}
2.匿名对象做缺省值的resize函数 如果我们调用resize函数其实就是重新给数组分配一定的空间那么这个空间内部的元素该如何初始化呢这一般都由输入者自定义的类型来这样一来我们就不能将缺省值特别规定为int或者别的类型而是使用模板按照代码编辑者需要的类型自动生成对应的缺省值类型即可并且在C中我们的内置类型intdouble等也有自己的构造函数同时我们可以将参数匿名对象设为const这样一来可以延长匿名对象的使用周期到其使用结束后销毁。
void resize(size_t n,const T valT())//匿名对象表示填入的缺省值其有可能是整形字符串甚至是vector等所以采用匿名对象来调用默认构造,而const可以延长匿名对象的生命周期到不用之后再销毁{if (n size())//不大于尾部不用变{_finish _start n;}else{reserve(n);//在reserve函数内部判断是否需要扩容并返回扩容后的空间_finish指针不会改变相对于_start的距离while (_finish _start n){*_finish val;_finish;}}}
3.memcpy-特殊类型的浅拷贝“隐藏杀手” memcpy函数的简介 1. memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中 2. 如果拷贝的是自定义类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且 自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。 string类成员的浅拷贝 我们知道string类对象的字符串并不是存放在对象本身的空间里而是存放在对象的数据成员所指向的堆中所以在使用memcpy时就会导致只是将string对象的数据成员原封不动的复制拷贝下来相当于其指向的string对象的成员的数据还是保存在原来的堆空间中并没有发生深拷贝出现了两个指针指向同一处的情况这就会在原拷贝对象在析构时产生重复析构的错误。 解决办法也比较简单那就是用我们的笨方法采用循环的方式将原对象一一拷贝到新的空间里来就行了当然这种错误的出现只会发生在需要扩容的情况下所以我们只需要调整扩容函数即可。
void reserve(size_t n)//扩容函数{if (n capacity()){T* tmp new T[n];size_t sz size();if (_start){//memcpy(tmp, _start, sizeof(T) * sz);//自定义对象造成异地扩容浅拷贝for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endofstorage _start n;}}
4.迭代器失效问题 迭代器失效的特征 1.如果迭代器失效了就不能再使用这个迭代器 2.如果使用了这个迭代器其结果将会是未定义的。 insert函数带来的迭代器失效 在vector中我们使用的一般都是迭代器的位置来表示元素的位置像在某个元素的位置后面插入一个元素的函数其定义一般为void insert(iterator pos, const T x)那么就可能会发生如下的场景 在这样的场景下插入元素势必就会导致出错所以其中一个方法就是我们记住pos与_start的相对偏移量在扩容后数组移动到新的空间之后再将pos也更新到新的位置即可。 void insert(iterator pos, const T x){assert(pos _start pos _finish);//等于_finish相当于尾插//首先检查是否空间满了满了就要先开空间if (_finish _endofstorage){size_t len1 pos - _start;cout 扩容前待插入位置相对于begin的偏移量为 len1 endl;reserve(capacity() 0 ? 4 : capacity() * 2);//注意扩容之后会导致迭代器发生变化也将会导致原来传入的参数失效size_t len2 pos - _start;cout 扩容后待插入位置相对于begin的偏移量为 len2 endl;pos _start len1;}iterator end _finish-1;_finish;while (end pos){*(end 1) *end;--end;}*pos x;}
上述的做法还有些许不妥之处如果我们有如下的需求 这样的话返回的迭代器还能使用吗 首先我们知道insert函数在内部修改了传入的迭代器但是这和实参并没有什么关系因为我们的insert函数是传值传参众所周知传值传参不影响实参所以一旦调用了insert函数迭代器就会出现诸多的可能性也就是迭代器失效了。 为何不建议传引用传参 针对上面的问题有的人可能会想到传引用传参但是我们得形参是实参的一份拷贝而实参又是一个常量形参作为临时变量而具有了常性所以不能被修改逻辑上也就不对了如果再将引用加上const那我们在insert函数内部就不能对参数迭代器再进行修改了所以对于insert函数来说正常的使用我们一般选择传值传参但是其使用会导致迭代器失效的问题这一点我们需要注意。 erase函数带来的迭代器失效 vector的删除函数比较好写我们传入迭代器参数因为不涉及扩容问题自然也就不存在上面的insert函数造成的迭代器失效的类型的问题我们直接在原来的空间上进行移动覆盖即可这里详细的也不再赘述
void erase(iterator pos){assert(pos _start pos _finish);//注意不能等于_finish因为_finish指向的是尾部元素的下一个元素该处本来没有元素所以也不能删除iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;}
那删除完之后的迭代器失效了吗 我们不妨来实测一下我们取三组样例分别对样例中的偶数元素进行删除分析并查看其结果 为什么会有这样的结果呢其实重点就在迭代器的位置我们知道当迭代器判断到一个元素符合条件时会执行删除指令这个指令也就是我们上面的erase函数其本质上是向前挪动数据覆盖达到删除效果而此时的迭代器在删除完元素后其实是指向了被删除元素的下一个元素下一步我们就需要判断该元素如果此时仍然让迭代器的话就会导致上一个被删除元素后面紧挨着的下一个数据被跳过了判断也就出现了错误问题。 解决办法其实也简单就是我们在判断符合条件时不执行迭代器操作只有当该元素不符合删除条件时才执行迭代器操作这样就可以保证每个元素都能够被判断到也就解决了错误。 那如果我想访问这个迭代器就真没办法了吗别急还真有我们来看官方文档对于迭代器失效问题的解决方案 官方的意思是让erase函数返回一个迭代器这个迭代器指向上一个已删除元素的下一个元素其实还是原来的那个迭代器的位置。
iterator erase(iterator pos){assert(pos _start pos _finish);//注意不能等于_finish因为_finish指向的是尾部元素的下一个元素该处本来没有元素所以也不能删除iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;return pos;//删除元素的下一个位置其实还是该迭代器的位置,因为向前挪动覆盖原来迭代器的位置上删除后存储的就是下一个元素}
void test_vector5(){// 1 2 3 4 5// 1 2 3 4 5 6// 2 2 3 4 5std::vectorint v;//调用库里的vector,默认原来的erase迭代器失效v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v.push_back(6);for (auto e : v){cout e ;}cout endl;auto it v.begin();while (it ! v.end()){if (*it % 2 0){itv.erase(it);//让迭代器重新赋值,再次有效}elseit;}
5.拷贝构造和赋值问题 对于自己写的vector如果不单独写拷贝构造函数那么将会使用默认的拷贝函数也就会造成浅拷贝的情况和赋值操作同理所以我们也是需要编写拷贝构造函数和赋值函数这部分在string的部分已经详细展开这里也不再赘述
//拷贝构造函数vector(const vectorT x):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(x.capacity());//修改空间为x的空间for (auto e : x){push_back(e);//赋值即可}}
//赋值操作// v1 v3void swap(vectorT v)//写成vector x也可以{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vectorT operator(vectorT tmp){swap(tmp);//交换后tmp为临时变量后续自动销毁return *this;}
6.迭代器区间初始化构造
在官方的vector文档中我们还可以看到vector构造函数的另外l两种初始化方案 在上面实现的功能的基础上想实现这两个构造函数并不能这里给出一种实现方案
template class InputIteratorvector(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);}
但是如果我们来整上一个测试样例vectorint v0(10, 0);显然我们的目的是想让编译器给我们初始化10个空间并且全都初始化为0但是编译器真的会乖乖的听我们的吗 很显然出错了编译器不听我们的因为编译器不知道该匹配哪个了因为这两个数据参数都可以看做同一个类型所以它也符合模板的迭代器初始化的函数的参数列表所以编译器就会调用最匹配的那一个函数来构造 这种情况下官方采用的是将 vector(size_t n, const T val T())再次重载使其更加符合我们类型比如重载为vector(int n, const T val T()),就可以解决我们上面的错误了但不过说实话这种方式的代码复用性比较差有点面向样例编程的滋味但是目前也没有好的解决办法了。
7.完整代码
vector.h
#pragma once
#includeassert.h
#include vectornamespace my_std
{templateclass Tclass 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()//声明中已给出缺省值可以省略不写{}//拷贝构造函数vector(const vectorT x):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(x.capacity());//修改空间为x的空间for (auto e : x){push_back(e);//赋值即可}}template class InputIteratorvector(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 (size_t i 0; i n; i)push_back(val);}//赋值操作// v1 v3void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vectorT operator(vectorT tmp){swap(tmp);//交换后tmp为临时变量后续自动销毁return *this;}~vector(){delete[] _start;//采用new/delete的形式存储_finish _endofstorage nullptr;}size_t capacity() const //空间容量{return _endofstorage - _start;}size_t size() const //数组长度{return _finish - _start;}void reserve(size_t n)//扩容函数{if (n capacity()){T* tmp new T[n];size_t sz size();if (_start){//memcpy(tmp, _start, sizeof(T) * sz);//自定义对象造成异地扩容浅拷贝for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endofstorage _start n;}}void resize(size_t n,const T valT())//匿名对象表示填入的缺省值其有可能是整形字符串甚至是vector等所以采用匿名对象来调用默认构造,而const可以延长匿名对象的生命周期到不用之后再销毁{if (n size())//不大于尾部不用变{_finish _start n;}else{reserve(n);//在reserve函数内部判断是否需要扩容并返回扩容后的空间_finish指针不会改变相对于_start的距离while (_finish _start n){*_finish val;_finish;}}}void push_back(const T x){//如果空间满了先扩容size_t n _finish - _start;//提前算出保存避免后序因异地扩容而导致原地址失效if (_finish _endofstorage){size_t len capacity() 0 ? 4 : capacity() * 2;//T* temp new T[len];//if (_start)//如果原来有内容//{// memcpy(temp, _start, sizeof(T)*n);// delete[] _start;//}//_start temp;//_finish _start n;//_endofstorage _start len;reserve(len);}*_finish x;_finish;//insert(end(), x);}void insert(iterator pos, const T x)//而且此处不能加引用{assert(pos _start pos _finish);//等于_finish相当于尾插//首先检查是否空间满了满了就要先开空间if (_finish _endofstorage){size_t len1 pos - _start;cout 扩容前待插入位置相对于begin的偏移量为 len1 endl;reserve(capacity() 0 ? 4 : capacity() * 2);//注意扩容之后会导致迭代器发生变化也将会导致原来传入的参数失效size_t len2 pos - _start;cout 扩容后待插入位置相对于begin的偏移量为 len2 endl;pos _start len1;}iterator end _finish-1;_finish;while (end pos){*(end 1) *end;--end;}*pos x;}iterator erase(iterator pos){assert(pos _start pos _finish);//注意不能等于_finish因为_finish指向的是尾部元素的下一个元素该处本来没有元素所以也不能删除iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;return pos;//删除元素的下一个位置其实还是该迭代器的位置,因为向前挪动覆盖原来迭代器的位置上删除后存储的就是下一个元素}T operator[](size_t pos)//可读可写{assert(pos size());return _start[pos];}const T operator[](size_t pos) const//只读{assert(pos size());return _start[pos];}private://初始化加上缺省值iterator _startnullptr;//开头iterator _finish nullptr;//结尾加1iterator _endofstorage nullptr;//空间容量};void test1(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;for (vectorint::iterator it v.begin(); it ! v.end(); it){*it * 10;cout *it ;}cout endl;for (auto e : v)cout e ;cout endl;}void test_vector2(){int i 0;int j(1);//可见内置类型在模板中是存在默认构造函数的int k int(2);vectorint* v1;v1.resize(10);vectorstring v2;//v2.resize(10, string(xxx));v2.resize(10, xxx);//单参数的构造函数支持隐式类型的转换for (auto e : v1){cout e ;}cout endl;for (auto e : v2){cout e ;}cout endl;}void test_vector3(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);for (auto e : v){cout e ;}cout endl;vectorint::iterator it v.begin() 2;v.insert(it, 30);for (auto e : v){cout e ;}cout endl;//v.insert(v.begin(), 30);v.insert(v.begin() 3, 30);for (auto e : v){cout e ;}cout endl;}void test_vector4(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);for (auto e : v){cout e ;}cout endl;auto pos v.begin();v.erase(pos);for (auto e : v){cout e ;}cout endl;v.erase(v.begin() 3);for (auto e : v){cout e ;}cout endl;}void test_vector5(){// 1 2 3 4 5// 1 2 3 4 5 6// 2 2 3 4 5std::vectorint v;//调用库里的vector,默认原来的erase迭代器失效v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v.push_back(6);for (auto e : v){cout e ;}cout endl;auto it v.begin();while (it ! v.end()){if (*it % 2 0){itv.erase(it);//让迭代器重新赋值,再次有效}elseit;}for (auto e : v){cout e ;}cout endl;}void test_vector6(){vectorstring v;v.push_back(111111111111111111111);v.push_back(111111111111111111111);v.push_back(111111111111111111111);v.push_back(111111111111111111111);v.push_back(111111111111111111111);for (auto e : v){cout e ;}cout endl;}void test_vector7(){vectorint v1;v1.push_back(1);v1.push_back(1);v1.push_back(1);v1.push_back(1);v1.push_back(1);vectorint v2(v1);for (auto e : v1){cout e ;}cout endl;for (auto e : v2){cout e ;}cout endl;vectorint v3;v3.push_back(10);v3.push_back(20);v3.push_back(30);v3.push_back(40);v1 v3;for (auto e : v1){cout e ;}cout endl;}void test_vector8(){vectorint v0(10, 0);vectorstring v1(10, xxxx);for (auto e : v1){cout e ;}cout endl;vectorint v2;v2.push_back(10);v2.push_back(20);v2.push_back(30);v2.push_back(40);vectorint v3(v2.begin(), v2.end());string str(hello world);vectorint v4(str.begin(), str.end());for (auto e : v3){cout e ;}cout endl;for (auto e : v4){cout e ;}cout endl;}
}
test.cpp
#includeiostream
using namespace std;
#include vector.h
int main()
{//my_std::test1();my_std::test_vector8();return 0;
} 每个人都有一段异常艰难的时光生活的压力工作的失意学业的压力爱的惶惶不可终日如果此刻不太顺利的话一定是有十倍百倍的运气在前方等着你不要怀疑自我大步往前走以后会很好很好的。
