长春网站免费制作,柳州seo公司,凡科免费建站怎么样,个人怎么进行网络广告营销文章目录 vector的介绍及使用vector的介绍vector的使用 vector的模拟实现 vector的介绍及使用
vector的介绍 1、vector是表示可变大小数组的序列容器。 2、就像数组一样#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数… 文章目录 vector的介绍及使用vector的介绍vector的使用 vector的模拟实现 vector的介绍及使用
vector的介绍 1、vector是表示可变大小数组的序列容器。 2、就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3、本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4、vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5、因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6、与其他动态序列容器相比vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。 vector的使用
需要重点掌握的接口 vector的构造函数 // vector的构造int TestVector1()
{// constructors used in the same order as described above:vectorint first; //空vectorint second(4, 100); //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;
} 迭代器的使用这里是左闭右开的区间 void PrintVector(const vectorint v)
{// const对象使用const迭代器进行遍历打印vectorint::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}void TestVector2()
{// 使用push_back插入4个数据vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器进行遍历打印vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;// 使用迭代器进行修改it v.begin();while (it ! v.end()){*it * 2;it;}// 使用反向迭代器进行遍历再打印// vectorint::reverse_iterator rit v.rbegin();auto rit v.rbegin();while (rit ! v.rend()){cout *rit ;rit;}cout endl;PrintVector(v);
}
vector的扩容 capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。 // reisze(size_t n, const T data T())
// 将有效元素个数设置为n个如果时增多时增多的元素使用data进行填充
// 注意resize在增多元素个数时可能会扩容
void TestVector3()
{vectorint v;// set some initial content:for (int i 1; i 10; i)v.push_back(i);v.resize(5);v.resize(8, 100);v.resize(12);cout v contains:;for (size_t i 0; i v.size(); i)cout v[i];cout \n;
}// 测试vector的默认扩容机制
// vs按照1.5倍方式扩容
// linux按照2倍方式扩容
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;}}
}// 往vecotr中插入元素时如果大概已经知道要存放多少个元素
// 可以通过reserve方法提前将容量设置好避免边插入边扩容效率低
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;}}
}vector的增删查改
// 尾插和尾删push_back/pop_back
void TestVector4()
{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 TestVector5()
{// 使用列表方式初始化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;
}// operator[]index 和 C11中vector的新式forauto的遍历
// vector使用这两种遍历方式是比较便捷的。
void TestVector6()
{vectorint v{ 1, 2, 3, 4 };// 通过[]读写第0个位置。v[0] 10;cout v[0] endl;// 1. 使用for[]小标方式遍历for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;vectorint swapv;swapv.swap(v);cout v data:;for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;// 2. 使用迭代器遍历cout swapv data:;auto it swapv.begin();while (it ! swapv.end()){cout *it ;it;}// 3. 使用范围for遍历for (auto x : v)cout x ;cout endl;
}
vector迭代器失效问题 迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 迭代器失效的情况扩容后迭代器失效删除时迭代器失效。 解决方法 迭代器失效解决办法在使用前对迭代器重新赋值即可。 vector的模拟实现
#pragma once
#include iostream
#include assert.h
namespace vec
{templateclass Tclass vector{typedef T* iterator;typedef const T* const_iterator;public:vector(){}//内置类型也可以有构造函数我们下一次再说vector(size_t n, const T it T()){resize(n, it);}vector(int n, const T val T()){resize(n, val);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void reserve(size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];//拷贝原有的数据if (_start){for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endofstorage _start n;}}void push_back(const T x){//考虑增容的情况if (_finish _endofstorage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}//*_finish x;//_finish;insert(end(), x);}iterator erase(iterator pos){//考虑pos位置的合法性assert(pos _start pos _finish);//移动数据iterator p pos 1;while (p ! _finish){*(p - 1) *p;p;}_finish--;return pos;}void resize(size_t n, const T x T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish x;_finish;}}}iterator insert(iterator pos, const T x){//判断pos位置的合法性assert(pos _start pos _finish);//考虑扩容if (_finish _endofstorage){//解决迭代器失效问题size_t len _finish - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);pos _start len;}//开始插入数据//移动数据iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}//插入数据*pos x;_finish;return pos;}void pop_back(){erase(--end());}T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}//拷贝构造vector(const vectorT v){//深度拷贝_start new T[v.capacity()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_endofstorage _start v.capacity();}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//赋值运算符重载vectorT operator(vectorT v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start _finish _endofstorage nullptr;}}void print(const vectorT v){for (auto e : v){std::cout e ;}std::cout std::endl;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}好的我们下一篇再见
