黑龙江省和城乡建设厅网站,免费微信网站源码,网站建设及维护费,网站页面设计文章目录 一、STL1.1 什么是STL?1.2 STL的版本1.3 STL的六大组件 二、vector的介绍及使用2.1 vector的介绍2.2 vector的使用2.2.1 vector的定义2.2.2 vector iterator2.2.3 vector空间增长问题2.2.4 vector增删查改 2.3 vector\char\ 可以替代 string 嘛#xff1f; … 文章目录 一、STL1.1 什么是STL?1.2 STL的版本1.3 STL的六大组件 二、vector的介绍及使用2.1 vector的介绍2.2 vector的使用2.2.1 vector的定义2.2.2 vector iterator2.2.3 vector空间增长问题2.2.4 vector增删查改 2.3 vector\char\ 可以替代 string 嘛 三、vector模拟实现3.1 成员变量3.2 成员函数3.2.1 构造函数3.2.2 拷贝构造3.2.3 operator3.2.4 size3.2.5 capacity3.3.6 迭代器相关3.2.7 reserve深拷贝问题3.2.8 resize3.2.9 operator[ ]3.2.10 insert迭代器失效问题3.2.11 erase迭代器失效问题3.2.12 pop_back 四、结语 一、STL
1.1 什么是STL?
STL(standard template libaray-标准模板库)是C标准库的一部分不仅是一个可复用的组件库而且是一个包罗数据结构与算法的软件框架。 1.2 STL的版本 原始版本Alexander Stepanov、Meng Lee在惠普实验室完成的版本本着开源精神它们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码无需付费。唯一的条件就是也需要像原始版本一样做开源使用。HP版本是所有STL的祖先。 P.J版本由P. J. Plauger开发继承自HP版本被微软Windows Visual C采用不能公开或修改缺陷可读性比较低符号命名比较怪异。 RW版本由Rouge Wage公司开发继承自HP版本。被CBuilder采用不能公开或修改可读性一般。 SGI版本由Silicon Graphics Computer SystemsInc公司开发继承自HP版本。被GCCLinux采用可移植性好可公开、修改甚至贩卖从命名风格和编程风格上看阅读性非常高。建议大家在学习STL的过程中可以参考这个版本的源代码。
1.3 STL的六大组件 二、vector的介绍及使用
2.1 vector的介绍 vector 是表示可变大小数组序列容器。 就像数组一样vector 也采用连续的存储空间来存储元素。也就意味着可以采用小标对 vector 的元素进行访问和数组处理一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 本质讲vector 使用动态分配数组来存储它的元素。当新元素插入时为了增加存储空间这个数组需要被重新分配大小。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价较高的任务因为每当一个新的元素加入到容器的时候vector 并不会每次都重新分配大小。 vector 分配空间策略vector 会分配一些额外的空间以适应可能的增长因此存储空间容量比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候实在常数时间复杂度完成的。 因此vector 占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 与其它的动态序列容器相比如deque、list、forward_listvector 在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率会比较低。
2.2 vector的使用
vector 学习时一定要学会查看文档vector的文档介绍vector 在实际中非常重要在实际中我们熟悉常用的接口就可以下面列出了需要我们重点掌握的接口。
2.2.1 vector的定义
构造函数声明接口说明vector()无参构造vector(size_type n, const value_type val value_type())构造并初始化 n 个 valvector(const vector x)拷贝构造vector(Inputlterator first, Inputiterator last)使用迭代器区间进行初始化构造
小Tipssize_type 表示一个无符号整数类型value_type 是第一个模板参数也就是要存储的数据类型。使用迭代器区间的构造函数是函数模板只要是满足 Input 类型的迭代器都可以使用该构造函数。
int TestVector1()
{vectorint first; vectorint second(4, 100); vectorint third(second.begin(), second.end()); vectorint fourth(third); int myints[] { 16,2,77,29 };vectorint fifth(myints, myints sizeof(myints) / sizeof(int));cout The contents of fifth are:;for (vectorint::iterator it fifth.begin(); it ! fifth.end(); it)cout *it;cout \n;return 0;
}2.2.2 vector iterator
iterator的使用接口说明begin end获取第一个数据位置的 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;
}2.2.3 vector空间增长问题
容量空间接口说明size()获取数据个数capacity()获取容量大小empty()判断是否为空resize(size_type n); resize (size_type n, const value_type val)改变 vector 的 sizereserve(size_type n)改变 vector 的 capacity vs 和 g 的扩容机制有所不同vs 下 capacity 是按照 1.5 倍增长的g 是按照 2 倍增长的。vs 是 PJ 版本 STLg 是 SGI 版本 STL。 reserve 只负责开辟空间如果确定知道需要多少空间reserve 可以缓解 vector 增容的代价缺陷问题。 resize 在开空间的同时还会进行初始化影响 成员变量 _size。
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 下的结果 Linux 下的结果 小Tips如果已经确定 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.2.4 vector增删查改
vector 增删查改接口说明push_back尾插pop_back尾删find查找这个是算法模块实现不是 vector 的成员接口insert在 position 之前插入 valerase删除 position 位置的数据swap交换两个 vector 的数据空间operator[ ]像数组一样访问通过断言来检查而 at 是通过抛异常
//经典的错误
void Testerro()
{vectorint v1;v1.reserve(10);for (size_t i 0; i 10; i){v1[i] i;}
}注意上面的代码虽然给 v1 提前开了 10 个空间但是 v1 中的有效元素个数还是 0即 v1.size() 的返回值是0这样一来我们就不能直接通过下标去访问 vector 对象中的每一个元素因为 operator[ ] 实现中的第一步就是检查下标的合理性防止越界访问执行 assert(pos _size)而此时 _size 是 0就会出错。上面的代码只需要把 reserve 改成 resize 就可以正常运行因为 resize 会改变 _size 的大小。如果硬要使用 reserve 提前开空间那么接下来要使用 push_back 来插入数据。
2.3 vectorchar 可以替代 string 嘛
答案是不可以虽然他们俩的底层本质上都是动态增长的数组但是 string 字符串的结尾默认有 \0可以更好的兼容 C 接口而 vectorchar 的结尾默认是没有 \0 的需要我们自己插入。
三、vector模拟实现 3.1 成员变量
public:typedef T* iterator;typedef const T* const_iterator;
private:iterator _start;iterator _finish;iterator _end_of_storage;3.2 成员函数
3.2.1 构造函数
vector():_start(nullptr), _finish(nullptr),_end_of_storage(nullptr)
{}vector(size_t n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{resize(n, val);
}vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{resize(n, val);
}//迭代器区间初始化
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}小Tips迭代器区间初始化采用的是函数模板因为它可能使用不同类型的迭代器。其次需要单独提供一个 vector(int n, const T val T())因为迭代器区间初始化采用的是函数模板如果不单独提供这种构造函数的话vectorint v1(10, 1) 这种情况会去走最匹配的即和迭代器区间初始化函数匹配而我们希望它走 vector(size_t n, const T val T()) 构造函数但是 10 会被当做 int 型和 size_t 匹配不上因此就会去和迭代器区间初始化函数进行匹配InputIterator 就会被实例化成 int 型函数中会对 int 型解引用就会报错其次逻辑也不符。因此需要针对 int 单独提供一个构造函数。
3.2.2 拷贝构造
//方案一
vector(const vectorT V):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{iterator tmp new T[V.capacity()];//memcpy(tmp, V._start, sizeof(T) * V.size());for (size_t i 0; i V.size(); i){tmp[i] V._start[i];}_start tmp;_finish _start V.size();_end_of_storage _start V.capacity();
}//方案二
vector(const vectorT V):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(V.capacity());for (auto e : V){push_back(e);}
}小Tips这里设计深拷贝问题在下文的 reserve 中会提到。
3.2.3 operator
void swap(vectorT v)
{std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);
}vectorT operator(vectorT v)//调用拷贝构造函数
{swap(v);return *this;
}3.2.4 size
size_t size() const
{return _finish - _start;
}3.2.5 capacity
size_t capacity() const
{return _end_of_storage - _start;
}3.3.6 迭代器相关
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}3.2.7 reserve深拷贝问题
void reserve(size_t new_capacity)
{if (new_capacity capacity()){iterator tmp new T[new_capacity];if (_start)//如果原来的_start申请过空间要先将源空间中的内容拷贝过来{memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}size_t vsize size();_start tmp;_finish tmp vsize;//记得更新_finish_end_of_storage _start new_capacity;}
}注意这里需要更新 _finish 和 _end_ofstorage因为他俩表示的是位置。要更新 _finish首先要将 size() 保存一下因为更新 _start 后_start 指向新空间的开头而 _finish 指向旧空间的结尾此时去调用 size()计算出来的个数是有问题的因此需要再更新 _start 之前就将原来的元素个数即 size() 保存一份。
小Tips上面这种扩容逻辑当 T 是内置类或者是无需进行深拷贝的自定义类型来说是完全满足的。但是当 T 是需要进行深拷贝的内置类型时上面这种扩容方式就会出现大问题。以 vectorstring 为例即当 T 是 string 的时候。 如上图所示如果简单的用 memcpy 将旧空间的数据拷贝到新空间那么新旧空间中存储的 string 对象指向同一个堆区上的字符串接着在执行 delete[] _start; 销毁旧空间的时候由于该 _start 是一个 string* 的指针所以会先调用 string 的析构函数将对象中申请的空间释放即释放 _str 指向的空间接着再去调用 operator delete 函数释放 string 对象的空间。这样一来新空间中存储的 string 对象就有问题了它们的成员变量 _str 指向的空间已经被释放了。这里的问题就出在 memcpy 执行的是浅拷贝。我们可以对上述代码稍作修改即可
void reserve(size_t new_capacity)
{if (new_capacity capacity()){iterator tmp new T[new_capacity];if (_start)//如果原来的_start申请过空间要先将源空间中的内容拷贝过来{//memcpy(tmp, _start, sizeof(T)*size());for (size_t i 0; i size(); i){tmp[i] _start[i];}delete[] _start;}size_t vsize size();_start tmp;_finish tmp vsize;//记得更新_finish_end_of_storage _start new_capacity;}
}修改后执行tmp[i] _start[i]; 会去调用 string 对象的赋值运算重载进行深拷贝。
3.2.8 resize
void resize(size_t n, const T val T())//缺省参数给的是一个匿名对象
{if (n size()){//检查容量扩容if (n capacity()){reserve(n);}//开始填数iterator it end();while (it _start n){*it val;it;}}_finish _start n;
}3.2.9 operator[ ]
T operator[](size_t pos)//读写版本
{assert(pos size());return _start[pos];
}const T operator[](size_t pos) const//只读版本
{assert(pos size());return _start[pos];
}3.2.10 insert迭代器失效问题
iterator insert(iterator pos, const T val)
{assert(pos _start pos _finish);size_t rpos pos - _start;//保存一下pos的相对位置//检查容量if (_finish 1 _end_of_storage){size_t old_capacity capacity();reserve(old_capacity 0 ? 4 : old_capacity * 2);}pos _start rpos;//更新pos//插入数据iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;
}注意在进行 insert 的时候会引发一个著名的问题——迭代器失效。我们希望在 pos 位置插入一个数据pos 是一个迭代器。在插入数据之前要先检查容量进行扩容如果执行了扩容逻辑_start、_finish、_end_of_storage 都指向了新空间旧空间已经被释放了而 pos 指向的还是原来空间中的某个位置此时 pos 就变成了野指针再去 pos 指向的位置填入数据就会造成非法访问。为了避免这个问题我们可以先保存一下 pos 的相对位置扩完容之后再去更新 pos。 小Tips保存相对位置更新 pos是 insert 函数内部的解决方式由于是传值传参形参的 pos 更新并不会改变实参的 pos因此为了解决外部的迭代器失效问题这里采用返回值的方式将更新后的 pos 返回。可能会有小伙伴觉得直接把形参的 pos 变成引用不香嘛这样对形参的更新就相当于是对实参的更新。想法很好但是不现实因为实参很有可能具有常性例如实参如果用 begin()、end()他俩都是传值返回会产生一个临时变量该临时变量具有常性如果形参 pos 用引用的话就需要加 const 进行修饰但是但是如果用 const 进行修饰那在函数内部就不能对 pos 进行更新。因此形参 pos 不能用引用。
总结会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、 push_back等。
3.2.11 erase迭代器失效问题
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator cur pos 1;while (cur ! _finish){*(cur - 1) *cur;cur;}_finish--;return pos;
}注意erase 删除 pos 位置元素后pos 位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果 pos 刚好是最后一个元素删完之后 pos 刚好是 _finish 的位置而 _finish 位置是没有元素的那么 pos 就失效了。因此删除 vector 中任意位置上的元素时VS 就认为该迭代器失效了VS 是通过自己重写的 iterator 进行强制检查。Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。为了解决外部的迭代器失效问题这里还是采用返回值的方式返回 pos 下一个位置元素的迭代器。
3.2.12 pop_back
//直接复用即可
void pop_back()
{erase(--end());
}四、结语
今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下春人的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是春人前进的动力
