建设众筹网站,建设项目竣工环保验收网站,网页系统设计,做网站，好苦逼文章目录 前言一、vector的介绍二、vector的使用2.1 vector求容量的用法2.2 vector的增删查改用法2.2.1 尾插2.2.2 尾删2.2.3 头插2.2.4 任意位置删除 2.3 vector的iterator是什么以及失效问题 三、vector的模拟实现3.1 成员变量3.2 成员函数3.2.1 构造函数3.2.2 拷贝构造3.2.3… 文章目录 前言一、vector的介绍二、vector的使用2.1 vector求容量的用法2.2 vector的增删查改用法2.2.1 尾插2.2.2 尾删2.2.3 头插2.2.4 任意位置删除 2.3 vector的iterator是什么以及失效问题 三、vector的模拟实现3.1 成员变量3.2 成员函数3.2.1 构造函数3.2.2 拷贝构造3.2.3 析构函数3.2.4 operator3.2.5 size3.2.6 capacity3.2.7 迭代器相关3.2.8 reserve3.2.9 resize3.2.10 operator[ ]3.2.11 insert3.2.12 erase3.2.13 pop_back 总结 前言
哈喽大家好这里是夏目学长的C学习笔记本次主要讲解一下C的STL当中的vector 如果大家正在学习vector或者需要对STL更加精进的同学那么本篇博客非常适合你的学习因为这里夏目将会不仅仅会写vector的各种功能和还会手搓vector的各种基本功能帮助大家的学习。 一、vector的介绍
首先如果要学习STL的话肯定要去下面这个网站去读取第一手文档的这是我们之后学习很重要的手段。
点击这里前去网站C学习网站 这里就需要我们去翻译文本来进行学习这里节约大家的时间我就直接归纳总结了。
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问和数组一样高效。 但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自 动处理。本质讲vector使用 动态分配数组来存储它的元素。 当新元素插入时候这个数组需要被重新分配大小 为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是 一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大 小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存 储空间更大。 不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是 对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增 长。与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list 统一的迭代器和引用更好.
这里我要给大家挖一个坑因为动态增长这里Linux环境和VS环境的增长倍数是不一样的。这个比较细节曾经出过面试题。
二、vector的使用
我相信你读取了上边六条vector的介绍肯定对于vector的了解肯定还是不是很深入所以我打算从上层应用的角度讲起然后先学会使用vector然后再去讲解vector的底层也就是手挫vector的各种功能写成代码的形式。
所以下面一起聊聊vector的使用讲到vector其实可以近似理解它就是强化版本的数组但是数组是静态的而vector是动态的vector可以动态增长增长的倍数在Linux下是标准的2倍在VS环境下是1.5倍后面专门验证数组和vector都可以通过下标的方法进行索引访问并且他们分配的物理或者逻辑空间是连续的。
capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。 这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义 的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问 题。resize在开空间的同时还会进行初始化影响size。
说了这么多的vector和数组的对比那既然学习vector了那么vector肯定要比数组要厉害所以厉害在哪里所以就引出了vector的功能增删查改。
这里举出vector 类型的例子帮助大家去理解。
2.1 vector求容量的用法 这些都是vector的求容量的用法这里给出代码看到代码基本就会使用我也会添加注释讲解。
#includeiostream
#includevectorusing namespace std;
int main()
{
// test_vector1();vectorint v;cout v.size() endl;cout v.max_size() endl;cout v.capacity() endl; return 0;
}size顾名思义就是求vector的已经添加了多少个元素了capacity就是求vector的总容量是多少max_size()说白了就是纯纯没用的库函数所以不学也罢。
2.2 vector的增删查改用法
2.2.1 尾插
vector的尾插查阅文档就是std::vector::push_back(const T x); 顾名思义就是在vector容器里面的末尾插入一个数据。 代码例子
#includeiostream
#includevectorusing namespace std;void test_vector1()
{vectorint v;v.push_back(1);v.push_back(2);for(int i 0 ; i 2 ; i)cout v[i] ;cout endl;
}
int main()
{test_vector1();return 0;
}例子结果 声明 后面的代码我自动只写类似于test_vectorx();的代码了这样更加方便不会冗余。
2.2.2 尾删
vector的尾删查阅文档就是std::vector::pop_back();
代码例子
void test_vector2()
{vectorint v;v.push_back(1);v.push_back(2);v.pop_back();for(int i 0 ; i v.size() ; i)cout v[i] ;cout endl;
}例子结果
2.2.3 头插
vector的头插查阅文档就是iterator insert(iterator pos, const T x T()); 或者就是 void insert(iteraotr pos, size_t n, const T x) 再或者就是需要用到迭代器了这个我会专门在下面讲。 代码例子
void test_vector3()
{vectorint v;v.push_back(1);v.push_back(2);v.insert(v.begin(),0);//第一种写法v.insert(v.begin(),2);v.insert(v.begin(),10,1);//第二种写法for(int i 0 ; i v.size() ; i)cout v[i] ;cout endl;
}测试结果是1 1 1 1 1 1 1 1 1 1 2 0 1 2
2.2.4 任意位置删除
vector的头插查阅文档就是iterator erase(iterator pos); 或者就是 iterator erase(iterator first,iterator last); 代码例子
void test_vector4()
{vectorint v;v.push_back(1);v.push_back(2);v.insert(v.begin(),0);v.insert(v.begin(),1);v.insert(v.begin(),2);v.insert(v.begin(),3);for(int i 0 ; i v.size() ; i)cout v[i] ;cout endl;v.erase(v.begin());v.erase(v.begin() 2);for(int i 0 ; i v.size() ; i)cout v[i] ;cout endl;
}测试结果是
删除前3 2 1 0 1 2 删除后2 1 1 2
2.3 vector的iterator是什么以及失效问题 查阅了给出网站的文档我知道了iterator其实就是vector的迭代器我是这样理解的迭代器其实就是类似指针的东西但是他不是指针我们在以后的学习还是会继续学习他的所以这里就来讲解一下iterator的用法。
顾名思义begin其实就是元素首地址end就是元素的末地址的下一个地址rbegin其实就是endrend就是begin目前来说这些都是最长用的也是最有用的剩下的自己去读取文档学习。
然后再讲解一个很重要的知识点就是迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了 封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的 空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器 程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有
会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、 push_back等。指定位置元素的删除操作–erase注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。与vector类似string在插入扩容操作erase之后迭代器也会失效
对于迭代器失效的第一条 我认为其实就是it这个指针原本指向老空间没错但是经过增加元素导致了vector的扩容就会使得vector开辟新的一段空间并且把老的空间的内容拷贝进去而我们的it迭代器还指向旧空间因此就会导致it的失效。 迭代器失效解决办法在使用前对迭代器重新赋值即可
对于迭代器失效的第二条
void test_vector5()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::iterator pos find(v.begin(),v.end(),3);v.erase(pos);cout *pos endl;
}erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代 器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是 没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效 了。 所以迭代器失效的最重要的方法就是: 迭代器失效解决办法在使用前对迭代器重新赋值即可 迭代器失效解决办法在使用前对迭代器重新赋值即可 迭代器失效解决办法在使用前对迭代器重新赋值即可 重要的事情说三遍。
三、vector的模拟实现
3.1 成员变量
namespace Vct
{templateclass Tclass vector{public:typedef T* iterator;typedef T* const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;}
}3.2 成员函数
3.2.1 构造函数
vector():_start(NULL),_finish(NULL),_endofstorage(NULL)
{}vector(size_t n, const T x T()):_start(NULL),_finish(NULL),_endofstorage(NULL)
{resize(n,x);
}vector(int n, const T x T()):_start(NULL),_finish(NULL),_endofstorage(NULL)
{resize(n,x);
}
//迭代器区间初始化 [first,last)
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}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);}
}
3.2.3 析构函数
~vector()
{if(_start){delete[] _start;_start _finish _endofstorage NULL;}
}3.2.4 operator
void swap(vectorT v)
{std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _endofstorage);
}vectorT operator(vectorT v)//调用拷贝构造函数
{swap(v);return *this;
}
3.2.5 size
size_t size() const
{return _finish - _start;
}
3.2.6 capacity
size_t capacity() const
{return _endofstorage - _start;
}3.2.7 迭代器相关
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}3.2.8 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_endofstorage _start new_capacity;}
}3.2.9 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.10 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.11 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 new_capacity capacity();reserve(new_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;
}
3.2.12 erase
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator cur pos 1;while (cur ! _finish){*(cur - 1) *cur;cur;}_finish--;return pos;
}3.2.13 pop_back
//直接复用
void pop_back()
{erase(--end());
}总结
写了一个晚自习终于把C的vector的博客给写完了写了很多东西如果觉得写的不错的可以给夏目一个三连支持一下谢谢。
