无投入网站推广,北京学习网站建设,网站的配色技巧,怎么用织梦做购物网站#x1f47b;内容专栏#xff1a; C/C编程 #x1f428;本文概括#xff1a;vector的介绍与使用、深度剖析及模拟实现。 #x1f43c;本文作者#xff1a; 阿四啊 #x1f438;发布时间#xff1a;2023.10.8 一、vector的介绍与使用
1. vector的介绍
像string的学习… 内容专栏 C/C编程 本文概括vector的介绍与使用、深度剖析及模拟实现。 本文作者 阿四啊 发布时间2023.10.8 一、vector的介绍与使用
1. vector的介绍
像string的学习一样我们依旧得学会在cplusplus网站中学会查看文档。
关于vector的文档介绍
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自 动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小 为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是 一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大 小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是 对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增 长。与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list 统一的迭代器和引用更好。 使用STL的三个境界能用明理能扩展 那么下面学习vector我们也是按照这个方法去学习
2. vector的使用
vector在实际中非常的重要在实际中我们熟悉常见的接口就可以。我们一一介绍学习常见的vector接口。
2.1 vector的定义
constructor构造函数声明接口说明vector()重点无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x);重点拷贝构造vector (InputIterator first, InputIterator last)使用迭代器进行初始化构造
//vector的构造
void test_vector1()
{vectorint v1; // 无参初始化vectorint v2(10, 1); //带参初始化//利用迭代区间进行初始化vectorint v3(v1.begin(), v1.end());vectorint v4(v2); //拷贝构造//也利用string的迭代区间也可以进行初始化string s1(hello world);vectorint v5(s1.begin(), s1.end());vectorint::iterator it v5.begin();while (it ! v5.end()){//打印字符所对应的ascii码值cout *it ;it;}
}2.2 vector 迭代器的使用
iterator的使用接口说明begin/cbegin end/cend获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置的iterator/const_iteratorrbegin rend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的reverse_iterator void PrintVector(const vectorint v)
{// const对象使用const迭代器进行遍历打印vectorint::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}void test_vector2()
{vectorint vec(10,0);vectorint::iterator it vec.begin();while (it ! vec.end()){cout *it ;it;}cout endl;//使用迭代器进行修改it vec.begin();int i 1;while (it ! vec.end()){*it i;it;i;}//反向迭代器auto rit vec.rbegin();while (rit ! vec.rend()){cout *rit ;rit;}cout endl;//迭代器遍历打印vecPrintVector(vec);
}2.3 空间增长问题
容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize改变vector的sizereserve改变vector的capacity
capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果预知需要用多少空间reserve可以缓解vector频繁增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。
// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vectorint v;sz v.capacity();cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}
vs运行结果vs下使用的STL基本是按照1.5倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141g运行结果linux下使用的STL基本是按照2倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128// 如果已经确定vector中要存储元素大概个数可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{vectorint v;size_t sz v.capacity();v.reserve(100); // 提前将容量设置好可以避免一遍插入一遍扩容cout making bar grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}2.4 vector的增删查改
vector的增删查改接口说明push_back尾插pop_back尾删insert在position位置之前插入val值erase删除position位置的元素swap交换两个vector的数据空间operator[ ]像数组一样访问clear删除容器的所有元素将size置为0但并不改变capacity的大小
// 尾插和尾删push_back/pop_back
void test_vector3()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;v.pop_back();v.pop_back();it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;
}// 任意位置插入insert和erase以及查找find
// 注意find不是vector自身提供的方法是STL提供的算法
void test_vector4()
{// 使用列表方式初始化C11新语法vectorint v{ 1, 2, 3, 4 };// 在指定位置前插入值为val的元素比如3之前插入30,如果没有则不插入// 1. 先使用find查找3所在位置// 注意vector没有提供find方法如果要查找只能使用STL提供的全局findauto pos find(v.begin(), v.end(), 3);if (pos ! v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vectorint::iterator it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;pos find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;v.clear();//调用clear后vector的size将变成0但是它的容量capacity并未发生改变
}二、vector的底层实现
1.说明和准备工作
创建一个vector的源文件写一个vector的类模板放入一个自己的MyVector的命名空间里面以免与库里面的vector发生冲突。 在模拟vector时我们并没有和string一样使用动态分配的指针_Ptr、_size、_capacity在类中我们使用了三个iterator贴近stl库里面的实现方式其实本质就是原生指针。
_start: _start指向动态数组或容器的第一个元素的位置。它用于表示容器的起始位置。
_finish: _finish 也是一个指针指向容器中当前元素的下一个位置。它表示容器中元素的结束位置。通常_finish 处于有效元素的末尾但它之后的内存可能已经分配但未被使用。
_end_of_storage: _end_of_storage 指向容器内存分配的末尾位置。这个位置之后的内存是容器为将来添加更多元素而预留的。当容器的大小接近容量时它可能需要重新分配内存并将新的_end_of_storage更新为新的内存末尾。
namespace MyVector
{templateclass Tclass vector{public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
};2.push_back操作
首选我们提前需要写好构造函数与析构函数构造函数在初始化列表将三个iterator置为nullptr即可析构函数进行释放资源与指针置空操作。 size()接口函数表示vector的有效数据个数即_finish - _start capacity()接口函数表示vector的容量大小即_end_of_storage - _start
在push_back尾插之前我们还需要进行判断是否要进行扩容扩容机制我们在数据结构学习了很多不作细致讲解下面直接放代码
namespace MyVector
{templateclass Tclass vector{public:typedef T* iterator;vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}size_t capacity(){return _end_of_storage - _start;}size_t size(){return _finish - _start;}void push_back(const T val){//扩容if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;T* tmp new T[newcapacity];if (_start){memcpy(tmp, _start, sizeof(T)* size());delete[] _start;}_start tmp;_finish _start size();_end_of_storage _start newcapacity;}*_finish val;_finish;}//通过[]进行访问vectorT operator[] (size_t n){assert(n size());return *(_start n);}~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test_vector1(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;}
};在main函数中我们调用MyVector::test_vector1()将程序运行起来之后程序就出问题了
报错说_finish是nullptr什么原因呢
我们将程序调试起来观察发现vector发生了扩容其_start与_end_of_storage均发生了改变我们讲他俩相减等于16字节1个int占4个字节说明确实刚开始扩容了4个元素但是我们细心观察发现_finish的值还是为空指针原因其实就在于_finish _start size()这里更新了_start而size()里面的_finish还是指向原来的空间也就是0x00000000属于迭代器失效问题解决办法就是在扩容之前提前用sz变量记录好偏移量。 解决方案
void push_back(const T val)
{if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;size_t sz size();T* tmp new T[newcapacity];if (_start){memcpy(tmp, _start, sizeof(T)* sz);delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start newcapacity;}*_finish val;_finish;
}3.vector的访问与遍历
第一种[]下标访问遍历 第二种将迭代器_start与_finish用begin与end方法进行封装为成员函数利用iterator进行遍历。 第三种一旦有了迭代器就可以支持范围for语句因为其底层就是迭代器。
namespace MyVector
{templateclass Tclass vector{public:typedef T* iterator;vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}iterator begin(){return _start;}iterator end(){return _finish;}size_t capacity(){return _end_of_storage - _start;}size_t size(){return _finish - _start;}void push_back(const T val){if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;size_t sz size();T* tmp new T[newcapacity];if (_start){memcpy(tmp, _start, sizeof(T)* sz);delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start newcapacity;}*_finish val;_finish;}T operator[] (size_t n){assert(n size());return *(_start n);}~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test_vector1(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;vectorint v2;v2.push_back(10);v2.push_back(20);v2.push_back(30);v2.push_back(40);v2.push_back(50);vectorint::iterator it v2.begin();while (it ! v2.end()){cout *it ;it;}cout endl;for(auto e:v2){cout e ;}cout endl;}
};
4.resize与reserve
resize接口函数改变vector的size可以增加或减少容器中的元素数量。 当使用 resize 减少size大小时多余的元素会被移除当使用 resize 增加size大小时会发生扩容。 reserve接口函数改变vector的容量大小它能够预留足够的空间使用 reserve 可以减少因为频繁扩容而带来的性能开销。 psreserve本身有检查扩容机制的意思我们直接使用push_back写的扩容机制代码然后用push_back复用reserve.
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);delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}
}//为什么这里的val要给匿名对象初始化而不是0
//因为这里写的是vector类模板
//传进来的参数类型可能是intdouble,也可能是vectorstring,vectorint……
//C泛型编程对内置类型也支持构造函数匿名对象)不然C模板很难用
//添加const说明匿名对象具有常属性添加可以延长匿名对象的生命周期
void resize(size_t n, const T val T())
{//分为三种情况//小于等于size 缩容(多余元素被移除)// 大于size 小于capacity//大小capacity 扩容if (n size()){_finish _start n;}else{reserve(n);while (_finish _start n){*_finish val;_finish;}}
}
void push_back(const T val)
{if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish val;_finish;
}测试
void test_vector2()
{vectorint* v1;v1.resize(5);vectorstring v2;v2.resize(10,xxx);for (auto e: v1){cout e ;}cout endl;for (auto e : v2){cout e ;}cout endl;
}5.insert和erase
5.1 insert插入操作
void insert(iterator pos,const T val)
{assert(pos _start);assert(pos _finish);//判断是否需要扩容if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}//挪动数据iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;
}测试
void test_vector3()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;//第一次在下标为2的位置插入一个元素30v1.insert(v1.begin() 2, 30);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;//第二次头插一个元素8此时会发生扩容导致pos失效v1.insert(v1.begin(), 8);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;
}第一次我们在下标为2的位置插入一个元素30程序能够正确运行结果也是对的。 但是我们再次利用insert头插一个元素此时正好是添加新的元素需要进行扩容最后程序发生了崩溃。 为何呢是因为扩容的原因导致的吗接下来我们探究一下 在扩容之前我们调试观察看到pos接收的地址的确和_start的地址一模一样都是0x0122da28 一旦经过reseve扩容我们发生三个iterator地址都发生了变化唯独pos却纹丝不动还是原来的地址空间此时的问题貌似很眼熟没错就是在前面部分我们提到的_finish如出一辙也属于迭代器失效问题本质就是因为pos使用的是释放之前的空间空间发生了扩容pos在对以前已经释放的空间进行操作时就会引起代码运行崩溃。 解决方案在扩容之前保存pos位置的偏移量在扩容后更新pos位置。
void insert(iterator pos,const T val)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;
}5.2 erase删除操作
void erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}_finish--;
}测试
void test_vector4()
{vectorint 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);v1.push_back(7);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;auto it v1.begin();v1.erase(it);for (auto e:v1){cout e ;}cout endl;v1.erase(it 2);for (auto e : v1){cout e ;}cout endl;}以上我们对头部和下标为2的元素进行了删除操作代码的结果也能顺畅地跑出来结果也是正确的但是这里的it迭代器不会失效吗答案并非如此我们来看下面的场景
我们给出三组样例数据分别计算给出的样例中用erase删除偶数元素。
第一组测试数据1 2 3 4 5 6 7
//第一种情况
void test_vector5()
{vectorint 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);v1.push_back(7);cout begin:;for (auto e : v1){cout e ;}cout endl;auto it v1.begin();while (it ! v1.end()){if (*it % 2 0){v1.erase(it);}it;}cout after:;for (auto e : v1){cout e ;}cout endl;
}运行结果结果正确
begin:1 2 3 4 5 6 7
after:1 3 5 7第二种测试数据1 2 3 4 5 6 7 8
//第二种情况
void test_vector6()
{vectorint 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);v1.push_back(7);v1.push_back(8);cout begin:;for (auto e : v1){cout e ;}cout endl;auto it v1.begin();while (it ! v1.end()){if (*it % 2 0){v1.erase(it);}it;}cout after:;for (auto e : v1){cout e ;}cout endl;
}运行结果程序崩溃
begin:1 2 3 4 5 6 7 8
error运行崩溃(触发断言)第三种测试数据2 2 3 4 5 6 7
//第三种情况
void test_vector7()
{vectorint v1;v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);cout begin:;for (auto e : v1){cout e ;}cout endl;auto it v1.begin();while (it ! v1.end()){if (*it % 2 0){v1.erase(it);}it;}cout after:;for (auto e : v1){cout e ;}cout endl;
}打印结果结果错误
begin:2 2 3 4 5 6 7
after:2 3 5 7分析 注⚠️ 以上也是Linux下g的编译器对迭代器的检测并不严格处理没有vs编译器果断极端。 以上代码在vs下程序会出现崩溃vs一些编译器会进行强制检查认为erase之后it就失效了访问就会报错。但是在Linux下虽然可能可以运行但是输出的结果是不对的。
那么对于以上it等迭代器失效问题该如何解决呢 其实erase有具体的返回值返回的是一个iterator指向被删除元素的下一个元素的位置。 修正erase的代码
iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}_finish--;return pos;
} //迭代器失效的解决方案
//在使用前对迭代器进行重新赋值
void test_vector8()
{vectorint v1;v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);cout begin:;for (auto e : v1){cout e ;}cout endl;auto it v1.begin();while (it ! v1.end()){if (*it % 2 0){//在下次操作it之前对迭代器进行重新赋值it v1.erase(it); }else{//不删除即可it;}}cout after:;for (auto e : v1){cout e ;}cout endl;
}
结论在使用了 insert 和 erase 之后迭代器失效了不能再访问需要谨慎处理。
6.关于具体迭代器失效问题的分析
关于剖析迭代器失效问题 博客关于迭代器失效问题
7.memcpy浅拷贝问题
使用memcpy拷贝的是内置类型那么通常是高效又安全的但是如果对于自定义类型涉及动态资源管理会导致浅拷贝问题造成内存泄露等不可预知的结果
//测试对于自定义类型扩容时使用memcpy会导致浅拷贝问题
void test_vector9()
{vectorstring v1;v1.push_back(11111111111);v1.push_back(11111111111);v1.push_back(11111111111);v1.push_back(11111111111);v1.push_back(11111111111);for (auto e : v1){cout e ;}cout endl;}解决方案 很简单使用一个for循环对每个字节进行赋值操作对于内置类型是赋值对于自定义类型就会调用自身的赋值重载函数
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;_end_of_storage _start n;}
}8.vector的拷贝构造与赋值重载
//拷贝构造
//v2(v1)
vector(const vectorT x): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//开辟和x一样大的空间reserve(x.capacity());for (size_t i 0; i x.size(); i){push_back(x[i]);}
}void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v.finish);std::swap(_end_of_storage, v._end_of_storage);
}//赋值重载
//v2 v1
vectorT operator(vectorT tmp)
{swap(tmp);return *this;
}测试赋值重载
//测试赋值重载void test_vector10(){vectorint v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);vectorint v2;v2 v1;for (auto e : v2){cout e ;}cout endl;}9.迭代区间初始化与n个val初始化
类模板里面可以嵌套函数模板可以传入任意类型的迭代区间初始化在形参部分用InputIterator进行接收具体细节可下面的测试用例。 对于n个val初始化不能直接写成vector(size_t n, const T val T())在编译器认为会优先去调用最匹配的就会调用迭代区间的初始化此时编译就会出错那么我们就需要写一个更匹配的vector(int n, const T val T())此时就能正确编译并执行了。
//利用迭代器区间进行初始化
//函数模板
template class InputIterator
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{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 (int i 0; i n; i){push_back(val);}
}测试迭代器区间初始化与n个val初始化
//测试迭代器区间初始化与n个val初始化
void test_vector11()
{//n个val初始化vectorint v1(10, 0);//利用迭代器区间初始化string str(hello world);vectorint v2(str.begin(), str.end());for (auto e : v2){cout e ;}cout endl;
}10.vector模拟实现源代码
vector的深度剖析及模拟实现
