STL---vector详解(从使用到底层)

前言在我的C专栏里有一篇讲解string的文章里边的各种接口讲解的比较详细大家对使用有疑惑的可以去我的专栏里看重复的接口相似的使用我就不再过多介绍了本文主要讲vector的底层。vector简介vector就是一个会自动扩容的顺序表。在cplusplus里边它是一个模板类。template class T, class Alloc allocatorT class vector; // generic templatevector的使用构造函数关于第一个构造函数的解释explicit vector (const allocator_type alloc allocator_type());//声明也许会有人有疑惑明明已经有第二个模板参数了就算不想用它默认的那个空间配置器类型即allocatorT那模板显示实例化的时候显示传第二个模板参数就行了为什么构造函数里还要给参数答(首先要知道allocator_type()是typedef过的而且模板参数是类型函数参数是对象不是一个概念模板决定的是类型但决定不了模板里函数用这个类型的哪个对象。)模板第二个参数Alloc决定了「允许使用的分配器类型」构造函数参数只能传「该类型的对象」不能传其他类型不传构造函数参数时默认用「模板参数类型的默认对象」传构造函数参数时用的是「该类型下你指定的具体对象」但类型必须和模板参数一致vectorint v1;//第一个构造函数当它是无参构造就行vectorint v2(10, 1);vectorint v2(v2.begin(), v2.end());遍历for (size_t i 0; i 10; i) { cout v1[i] ; } cout endl; for (auto e : v1) { cout e ; } cout endl; vectorint::iterator it1 v1.begin(); while (it1 ! v1.end()) { cout (*it1) ; it1; } cout endl;Capacity模块这里唯一需要注意的一个点就是在vs底层是1.5倍扩容构造的空vector的容量就是0不像string有一个_Buf数组。Modifiers模块vector里并没有去实现头插头删原因就是由于效率太低但可以使用insert去实现头插的效果。void test_03() { vectorint v1(5, 2);// 2 2 2 2 2 //在某个位置前插入 v1.insert(v1.begin(), 5);// 5 2 2 2 2 2 v1.insert(v1.begin() 3, 6);// 5 2 2 6 2 2 2 //在某个值前插入---vector里边没有find函数因为算法库里的find就够使用了 //在v1的6这个值前边插入一个7 auto it1 find(v1.begin(), v1.end(), 6); v1.insert(it1, 7); for (auto e : v1) { cout e ; } cout endl; v1.erase(v1.begin()); v1.erase(v1.begin() 1, v1.begin() 3);//删除的区间是左闭右开的 for (auto e : v1) { cout e ; } cout endl; }vector的一些特殊使用string s;vectorchar v1;这两个的区别在哪?从底层的角度来说都是一个字符数组但是vectorchar仅仅只是说数组里边存着char没有\0的标识并且没有string里边针对字符串的各种处理接口。////void push_back (const value_type val);vectorstring v2;v2.push_back(xxc);上边的代码走的是隐式类型转换xxc作为const char*的字符串会先去构造一个string类型的临时对象而val引用这个临时对象将这个临时对象拷贝构造给vector内部此时的value_type就是string。关于范围for便利自定义类型的小注意点void test_01() { vectorstring v1; v1.push_back(xxc); v1.push_back(lqm); /* * 范围for的底层会转化成*iterator*iterator的结果是一个string类型的对象 * 不加引用就是调用的赋值运算符重载是深拷贝效率不高了 * 所以建议如果是自定义类型就加上引用去便利如果不需修改一同加上const * 对于内置类型由于引用底层也是转化成指针去开空间的所以加不加引用效果都不大 */ for (const auto e : v1) { cout e ; } }initializer_listinitializer_list是C11出的新语法它是一个模板类底层其实是一个数组并且有两个指针一个指向头一个指向尾通俗理解就是两个迭代器。vector支持initializer_list去构造。vector (initializer_listvalue_type il, const allocator_type alloc allocator_type());//initializer_List auto il1 { 1,2,3 };//相当于是initializer_listint il auto il2 { 1,2,3,4,5,6,7 }; /* * v1v2是直接调用vector的拷贝构造 * {12345}会直接被编译器识别为initializer_listint类型传参传给拷贝构造的第一个参数 * 构造函数底层用相当于用范围for将数据一个个push_back()到vector里边 * * v3v4相当于是隐式类型转换 * 先用initializer_list去构造一个vector临时对象再将这个临时对象拷贝构造给v3, v4 * 但是编译器底层会优化成直接构造 */ vectorint v1({1,2,3,4,5}); vectorint v2({1,2,3,4,5,6,7,8,9,10}); //vectorint v3{1,2,3,4,5};//另一种写法效果是跟下边的v3一样的 vectorint v3 { 1,2,3,4,5 }; vectorint v4 { 1,2,3,4,5,6,7,8,9,10 };vector底层实现vector.h#pragma once #includeassert.h #includeiostream #includeinitializer_list using namespace std; namespace xxc { templateclass 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; } //这个默认构造无法省略不写虽然它什么都没干但是由于写了拷贝构造编译器不会再自动生成构造函数 //这就导致我们要vectorint v;就无构造可用 //也可以vector() default;强制编译器生成默认构造不管有没有显示写构造 vector() {} //注意这里都是在声明的地方给缺省值的不给的话由于C标准没有规定给不给成员变量初始化 //不同平台对于初不初始化成员变量都是不确定的所以给缺省值比较安全 //不初始化如果成员变量里边是随机值那么reserve的时候就会有问题 vector(const vectorT v) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } //initializer_list是支持迭代器的 vector(initializer_listT il) { reserve(il.size()); for (auto e : il) { push_back(e); } } //注下边两个函数在调用的时候会产生问题因为函数调用会去匹配最合适的 //xxc::vectorint v7(10, 1);此时会匹配到迭代器区间构造因为10和1都是int类型匹配到模板最合适 //n个val构造的参数一个是size_t一个是T参数不如迭代器区间构造匹配 //但迭代器区间构造里涉及到解引用就运行出错了 //解决方法就是再写一个最匹配的实例函数 //迭代器区间构造---为什么要用函数模板是因为可能要用到其他容器的迭代器区间来构造vector template class InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } } vector(int n, T val T()) { resize(n, val); } vector(size_t n, T val T()) { resize(n, val); } //如果vector为空再析构 ~vector() { if (_start) { delete[] _start; _start _finish _end_of_shorage nullptr; } } void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_shorage, v._end_of_shorage); } //现代写法---v1 v7v7先拷贝构造给vv跟v1再交换一下数据相当于就v7赋值给了v1最后函数结束v出作用域销毁 vectorT operator(vectorT v) { swap(v); return *this; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_shorage - _start; } void reserve(size_t n) { /* * 下边的_finish _start size();有问题 * 因为size()是去调用size()函数此时的_start已经不是原来的0了指向了新空间 * 但_finish还是原来的0两个相减计算出来的size()就不对了应该加上原来的size()才对 * 所以要先保存原来的size() */ //if (n capacity()) //{ // //异地扩容 // T* tmp new T[n]; // if (_start)//如果_start不为nullptr就拷贝旧数据过来 // { // memcpy(tmp, _start, size()); // } // _start tmp; // _finish _start size(); // _end_of_shorage _start n; //} if (n capacity()) { //异地扩容 T* tmp new T[n]; size_t old_size size(); if (_start)//如果_start不为nullptr就拷贝旧数据过来 { //memcpy不是深拷贝 //memcpy(tmp, _start, sizeof(T) * old_size); for (size_t i 0; i old_size; i) { tmp[i] _start[i];//内置类型浅拷贝自定义类型调用赋值运算符重载(深拷贝) } delete[] _start; } _start tmp; _finish _start old_size; _end_of_shorage _start n; } } T operator[](size_t i) { assert(i size()); return _start[i]; } const T operator[](size_t i) const { assert(i size()); return _start[i]; } iterator insert(iterator pos, const T x) { assert(pos _finish pos _start); //扩容 if (_finish _end_of_shorage) { //这里如果不更新pos迭代器扩容后会存在一个迭代器失效的问题 size_t len pos - _start; reserve(capacity() 0 ? 4 : 2 * capacity()); pos _start len; } //这里的挪动数据没有string的那么麻烦要去考虑头插的无限循环问题 //因为pos是迭代器往后再怎么减都不可能是0的循环的条件也不可能恒成立 iterator end _finish - 1; while (end pos) { *(end 1) *end; end--; } *pos x; _finish; return pos; } iterator erase(iterator pos) { assert(pos _start); assert(pos _finish); iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it;//尽量用前置因为后置在底层是会有拷贝的Date类里边就有 } _finish--; return pos; } void push_back(const T x) { //扩容 if (_finish _end_of_shorage) { reserve(capacity() 0 ? 4 : 2 * capacity()); } *_finish x; _finish; } void pop_back() { //assert(_finish _start); assert(!empty()); _finish--; } bool empty() const { return _start _finish; } void clear() { _finish _start; } //T()是匿名对象也叫临时对象 void resize(size_t n, T val T()) { if (n size()) { reserve(n); while (_finish ! _start n) { *(_finish) val; _finish; } } else { _finish _start n; } } private: iterator _start nullptr; iterator _finish nullptr; iterator _end_of_shorage nullptr; }; }vector的一些小细节迭代器失效//迭代器失效 void test_03() { xxc::vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); //v1.push_back(5); v1.insert(v1.begin(), 0); v1.insert(v1.begin() 2, 0); Print(v1); int x; cin x; auto it find(v1.begin(), v1.end(), x); v1.insert(it, 100); *it 1000;//这里的it也是迭代器失效 /* * 扩容会让it失效 * 由于不知道什么时候扩容所以insert过后就认为其失效 * * 明明insert函数内部有对迭代器失效进行了处理为什么it还是失效了 * 因为insert函数的iterator是传值传值是拷贝改变不会影响it本身 * * 能不能改成传引用 * 不能因为像v1.insert(v1.begin(), 0);这种场景的v1.begin()是传值返回 * 返回的是临时对象具有常性那begin()传引用返回呢不行因为无法应对 * v1.insert(v1.begin() 2, 0);这种场景v1.begin() 2计算结果也是临时对象具有常性 * * 那insert函数参数的iterator如果改成const引用呢 * 不行加上constinsert函数内部的pos迭代器无法修改了 * * 综上失效的迭代器无法使用 * * 同理使用erase函数依旧认为是迭代器失效了vs下对迭代器会有严格的检查 * * 为了解决迭代器失效库里边的inserterase....会有一个返回值使用迭代器之后更新一下就可以使用了 */ //erase中迭代器失效的简单场景 // 要求删除所有偶数 auto it v1.begin(); while (it ! v1.end()) { if (*it % 2 0) { // erase也会迭代器失效失效的迭代器就不能再使用了 // 要重新赋值更新这个迭代器才能使用 it v1.erase(it); } else { it; } } }insert函数里的迭代器失效关于T()C里边对于内置类型也有构造函数目的就是为了在给像resize这种函数的缺省值的时候能用模板给缺省值。void test_04() { int a int();//0 int b(1);//1 int c int(10);//10 //其他类型也一样不给他初始化默认就初始化为00.0ASCII码为0的值即\0 }由浅拷贝引发的问题以下这是reserve没修改前的代码void reserve(size_t n) { if (n capacity()) { //异地扩容 T* tmp new T[n]; size_t old_size size(); if (_start)//如果_start不为nullptr就拷贝旧数据过来 { //memcpy不是深拷贝 memcpy(tmp, _start, sizeof(T) * old_size); delete[] _start; } _start tmp; _finish _start old_size; _end_of_shorage _start n; } }问题拷贝构造自定义类型譬如string的时候会有深拷贝的问题因为string内部也会指向空间由于拷贝构造是复用真正的问题出在reservememcpy没有深拷贝导致拷贝给tmp的数据不包括string内部指向的资源使得tmp和_start指向同一块资源在delete[] _start的时候不仅释放掉了vector内部的string并且string也会调用自己的析构函数去释放掉自己额外开辟的空间这样一来tmp指向的数据就变成随机值了紧接着_start tmp后续打印出来的就变成随机值了使用函数模板打印不同vector我们自己写的vector在xxc这个命名空间里边而库里边的vector在std这个命名空间里边如果我们在既想打印库里边的又想打印自己手动实现的vector同一个Print就无法实现功能此时要设计成模板。templateclass Container void Print(const Container v) { for (auto e : v) { cout e ; } cout endl; }