佛山建设工程交易中心网站,wordpress 蜘蛛,网站开发人员职责,邢台市属于哪个省vector是表示可变大小数组的序列容器。就像数组一样#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问#xff0c;和数组一样高效。但是又不像数组#xff0c;它的大小是可以动态改变的#xff0c;而且它的大小会被容器自… vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3.本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4.vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5.因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6.与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。 一.常用接口介绍
官方文档
1.resize和reserve
区别
1.resize开空间并且初始化reserve只负责开空间。意味着reserve后不能通过下标访问元素因为它只开了容量空间而resize后改变了容器大小并初始化了容器对象可以通过下标访问元素。 2.reserve只接受一个参数表示预留空间的大小resize接受两个参数一个是空间大小第二个是填充空间的对象类型如果没有就调用对象的默认构造函数。 3.如果resize的大小比当前capacity大那么vector中存储元素的地址会发生改变(vector对象的地址不变)会引起内存中指针引用的重新分配。因此用resize扩容前可以用reserve预留足够的空间再初始化。
模拟实现
void reserve(size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}}void resize(size_t n, const T val T()){if (n capacity()){reserve(n);}if (n size()){while (_finish _start n){*finish val;finish;}}else{_finish _start n;}}2.oprerator【】和at
前者会用断言检查越界 后者则会抛异常。
二.知识点总结
1.构造函数 vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}vector(const vectorT v){_start new T[v.capacity()];//v.size()也可以memcpy(_start, v._start, sizeof(T) * v.size());_finish _start v.size();_end_of_storage _start v.capacity();}vector(size_t n, const T value T()):_start(new T(n)), _finish(_start n), _end_of_storage(_finish){for (int i 0; i n; i){_start[i] value;}}vector(int n, const T value T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);while (n--){push_back(value);}}templateclass InputIterator//写成模板可以用其他类型的迭代区间构造vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first ! last){push_back(*first);first;}}2.赋值运算符重载 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值v1v2,适用于所有的类深拷贝vectorT operator(const vectorT v){swap(v);return *this;}3.迭代器失效问题 迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T*。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 vector中会引起底层空间改变的操作都会使迭代器失效resizepush_back,insert,erase #includevector
#includeiostreamusing namespace std;int main()
{vectorint v { 1,2,3,5,7 };vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 1)v.erase(it);it;}return 0;}在进行删除时由于把当前位置数据删了后面的数据要分别向前移动一个位置因此删除该位置后的迭代器全部失效。
解决方案
#includeiostreamusing namespace std;int main()
{vectorint v { 1,2,3,5,7 };vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 1)it v.erase(it);elseit;}return 0;}erase后返回删除位置下一个位置迭代器用it再去接收即可。
同理解决插入问题 如果每次插入之后不更新迭代器那么insert时如果发生扩容那么迭代器指针就会指向新开的空间而此时的it仍指向旧空间向后访问就会出现野指针的问题了。 因此仍然需要每次插入过后更新it迭代器
4.简述迭代器按功能分类问题 单向迭代器 egforward_list,unordered_map 双向迭代器 -- eg:list 随机迭代器–- eg:vector
