青海省住房建设厅网站,申请域名备案,成都品牌设计,昆山建设银行网站###vector底层相当于是数组#xff0c;查看源码可以发现#xff0c;这个类的私有成员变量是三个迭代器#xff1b;在实现时迭代器就可以当作是vector里面的元素的指针类型#xff1b;
###vector是一个类模板#xff0c;实现时也应当按照这样的写法用一个模板去实现#…###vector底层相当于是数组查看源码可以发现这个类的私有成员变量是三个迭代器在实现时迭代器就可以当作是vector里面的元素的指针类型
###vector是一个类模板实现时也应当按照这样的写法用一个模板去实现类模板vector中数据类型是T private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;
_start指向vector的开始地址_finish指向vector的有效元素的结束地址_end_of_storage指向vector最大存储数据的地址
一、迭代器
typedef T* iterator;
typedef const T* const_iterator;//迭代器
iterator begin()
{return _start;
}
const_iterator begin()const
{return _start;
}
iterator end()
{return _finish;
}
const_iterator end()const
{return _finish;
}
二、容量 size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage - _start;}bool empty()const{return size() 0;}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;}}void resize(size_t n, const T val T())//匿名对象作为缺省值{if (n capacity()){_finish _start n;}else{reserve(n);for (iterator i _finish ; i _start n; i){Insert(i,val);}}}
1、reserve
基本思路开辟一个临时的数组存放T类型的数据让这个数组的大小为指定的n将vector对象中的数据全部放到这个临时数组中再清空vector中的数据最后让vector对象存放数据的地址就是这个临时数组的地址
两个关键点
old_size若是不先记录下size的话后面给_finish重新赋值时使用到size()size函数中_size不再是原来的_size,而是tmp此时用_size去减_finish会出错;深、浅拷贝问题若是使用memcpy就是浅拷贝对于vector中是内置类型的数据可以但是若是vector对象中涉及到自定义类型例如string为数据的情况浅拷贝拷贝的是地址那么tmp中的数据的地址就是vector对象中的数据地址之后再delete掉_start就相当于把要存放数据的tmp中的数据给释放了这样会让数据丢失所以一个一个赋值对于内置类型无影响对于自定义类型例如string的类型就是赋值重载string实现时是深拷贝这样就解决了。
2、resize
基本思路若是比原来的size小那么就让_finish等于_startn这样就访问不到n之后的数据了若是比原来的size大没有给值就用匿名对象T()对于内置类型给初始值0、空指针、0.0一类对于自定义类型调用默认构造函数实现部分先扩容再插入数据。
三、元素获取 T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos)const{assert(pos size());return _start[pos];}
重载运算符[]在内部通过数组的方式返回对应下标的位置。
四、修改 void push_back(const T val){if (_end_of_storage _finish){reserve(size() 0 ? 4 : 2 * capacity());}*_finish val;_finish;}void pop_back(){assert(size() 0);_finish--;}iterator Insert(iterator pos, const T val){assert(pos _start);assert(pos _finish);if (_end_of_storage _finish){size_t len pos - _start;reserve(size() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *(end);end--;}*pos val;_finish;return pos;}iterator Erase(iterator pos){assert(pos _start pos _finish);iterator tmp pos 1;while (tmp _finish){*(tmp - 1) *tmp;tmp;}--_finish;return pos;}
1、insert和erase调用时迭代器失效的问题
insert实现时若是涉及到空间不够要扩容扩容时要先记录下pos和_start之间的距离扩容之后_start不是之前的了那么pos也要跟着更新;此时在调用insert时若是插入之后还要访问pos就要更新pos因为pos已经改变了若是不更新就使用原来的pos会找不到原来的数据
就算没有扩容空间够insert之后使用到pos还是要先更新因为此时的pos指向的是新插入进来的数据而不是我们想要访问的原来的数据。
eraseerase的迭代器失效举一个例子 vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);container_print(v);cout size: v.size() endl;cout capacity: v.capacity() endl;vectorint::iterator p v.begin();while(p v.end()){if (*p % 2 0){v.Erase(p);}p;}container_print(v); 运行结果似乎很正确那再看 vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4);v.push_back(5);container_print(v);cout size: v.size() endl;cout capacity: v.capacity() endl;vectorint::iterator p v.begin();while(p v.end()){if (*p % 2 0){v.Erase(p);}p;}container_print(v); 此时会发现有偶数没有删除完全这是因为迭代器失效了
原因erase的实现中删除了pos指向的数据之后返回pos此时的pos指向的是原来要删除的数据的下一个数据在这个删除偶数的例子中{12345}pos指向2.删除之后pos指向3再加加就是指向4刚好到了下一个偶数删除之后pos指向5再加加循环结束这里只是一个巧合数据是{123445}删除完2pos指向第一个4删除之后pos指向第二个4再加加那么pos指向是5了就跳过了这个4此时就是迭代器失效了
为了解决erase要使用到pos就要更新迭代器 while(p v.end()){if (*p % 2 0){pv.Erase(p);}else{p;}}
这样写每次删除完之后pos指向就是原来要删除数据的下一个数据若是这个数是偶数那就继续删是奇数就加加跳过这样就能够不错过数据了。
五、构造
1、强制的默认构造写法 vector() default;//强制的默认构造
2、拷贝构造 //拷贝构造vector(const vectorT v){reserve(v.capacity());for (auto it : v){push_back(it);}} 3、赋值重载 void clear(){_finish _start;}void swap(const vectorT tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}//赋值重载传统写法vectorT operator(const vectorT v){if (_start)//说明被赋值的对象不是空要先清除{clear();}reserve(v.capacity());for (auto it : v){push_back(it);}}//赋值重载现代写法vectorT operator(vectorT tmp){swap(tmp);return *this;}
a、传统写法
若是原vector不为空先置为空之后再扩容扩到和v一样的大小再使用拷贝构造那一套将v的数据一个一个尾插进入要被赋值的vector
b、现代写法
传参时用tmp接收赋值等式右边的vector进行拷贝构造之后再和赋值等式左边的vector进行交换现代写法一般要在拷贝构造写好的情况下进行
4、迭代器初始化 //迭代器初始化template class InputIterator//可以接收不同的迭代器但是迭代器里面的数据的类型要相同vector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}
这里使用到模板是为了接收各种类型的迭代器但是值得注意的是这些迭代器的各自的容器里面的数据类型应该和此时的待构造的vector里面的数据保持一致再不济也可以强制类型转换
5、n个val去初始化 //n个 val 去初始化vector(size_t n, const T val T())//不给值就用匿名对象,这个对象是 vector 里面的值{reserve(n);for (size_t i 0; i n; i){push_back(val);}}
6、析构 ~vector(){if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}}
六、容器打印函数模板中的注意事项 template class Tvoid vector_print(const vectorT v){//要写 typename,否则没有实例化的 vectorT 不知道const_iterator是类型还是静态成员变量typename vectorT:: const_iterator it v.begin();//auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;}
这个函数模板定义在我们自己实现的vector类外面用来打印vector使用到迭代器但是在写时注意这一行 typename vectorT:: const_iterator it v.begin(); 要加上typename否则编译器分不清这是类里面的静态成员变量还是类型当然若是写成静态成员变量去使用那就一定是静态成员变量但是这里不能直接写要在前面加上tyepname第二种方法可以直接用auto自动生成类型去使用。
