集翔网大网站建设,房地产 网站 案例,张雪峰说软件工程,做队徽的网站vector
vector的说明文档
vector是表示可变大小数组的序列容器(动态顺序表)。就像数组一样#xff0c;vector也采用连续的存储空间来储存元素。这就意味着可以用下标对vector的元素进行访问#xff0c;和数组一样高效。与数组不同的是#xff0c;它的大小可以动态改变——…vector
vector的说明文档
vector是表示可变大小数组的序列容器(动态顺序表)。就像数组一样vector也采用连续的存储空间来储存元素。这就意味着可以用下标对vector的元素进行访问和数组一样高效。与数组不同的是它的大小可以动态改变——由容器自动处理。底层而言vector使用动态分配的数组来存储元素。当新元素插入时这个数组可能需要被重新分配大小(扩容)。其做法为分配一个新的数组然后将所有元素移到这个新数组。就时间成本而言这是一个代价较高的行为因此不会在每次向容器添加元素时都重新分配大小。vector会分配一些额外的空间以应对可能需要的扩容因此容器的实际容量大小可能大于容纳其元素所必须的存储空间的大小。不同的库采用不同的策略来权衡空间的使用(usage)与重新分配(reallocation)。但在任何情况下重新分配都应该只发生在对数增长的大小间隔上以使得尾插一个元素的时间复杂度为常数。因此相较于数组vector占用了更多的存储空间以获得管理存储空间的能力并以一种高效率的方式动态增长。与其它动态序列容器相比deque(双端队列),lists(双链表),forward_lists(单链表) vector在访问其元素时非常高效(就像数组一样)而且从其末端添加或删除元素时也相对高效。对于在末端以外的位置插入或删除元素的操作它的效率较低。而且与list和forward_lists相比它的迭代器与引用不太一致。
string是负责管理字符类型的数组而vector是负责管理任意类型的数组 。 string相比vector有太多冗余的接口vector的设计相对更合理些。
vector构造函数
vector构造函数接口说明vector()重点无参构造vector (const vector x); 重点拷贝构造vectorsize_type n, const value_type val value_type())构造并初始化n个valvector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
vector容量管理
接口接口说明resize重点改变vector的sizereserve 重点改变vector的capacitysize获取数据个数capacity获取容量大小empty判断是否为空
capacity的代码在vs和g下分别运行可以发现vs下capacity是按1.5倍增长的g是按2倍增长的。vector每次增容增多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间。如果明确知道需要用多少空间可使用reserve来缓解vector增容代价较高的问题。resize在开空间的同时还会进行初始化影响size。
vector增删查改
接口接口说明push_back重点 尾插pop_back重点 尾删operator[]重点 像数组一样访问find查找。注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间
vector迭代器
接口接口说明begin end重点获取第一个元素位置的iterator/const_iterator 获取最后一个元素的下一位的iterator/const_iteratorrbegin rend获取最后一个元素位置的reverse_iterator获取第一个元素前一位的reverse_iteratorvector 迭代器失效问题(重点)
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际上就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。而迭代器失效实际上就是迭代器底层所对应的指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果便是程序崩溃(即若继续使用已经失效的迭代器程序可能会崩溃)。 对于vector可能会导致其迭代器失效的操作有 1.会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。
2.指定位置元素的删除操作–erase
3.注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。
-SGI STL中迭代器失效后代码不一定会崩溃但运行结果肯定不 对。若it不在begin和end范围内肯定会崩溃。
4.与vector类似string在插入扩容操作erase之后迭代器也会失效
迭代器失效解决办法在使用前对迭代器重新赋值即可。
模拟实现vector
#pragma once
#include iostream
#include vector
#include string
#include algorithm
#include assert.h
using namespace std;namespace my_vector {templateclass Tclass vector {public:typedef T* iterator;typedef const T* const_iterator;vector(){}vector(size_t n, const T val T()) /*由于要兼容所有类型缺省值不能为0而是调默认构造函数构造匿名对象*/{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);}}//复用实现深拷贝/*vector(const vectorT v){reserve(v.capacity());for (auto e : v){push_back(e);}}*///原生方式实现深拷贝vector(const vectorT v){_start new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());//memcpy是浅拷贝不适用于自定义类型for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();}templateclass InputIterator//允许类的成员函数本身是函数模板vector(InputIterator first, InputIterator last)/*迭代器区间 [first,last)*/{while (first ! last) {//这里不能比较大小有的结构如链表前后节点的地址大小关系并不确定push_back(*first);first;}}~vector() {delete[] _start;_start _finish _end_of_storage nullptr;}iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const {return _start;}const_iterator end() const {return _finish;}void resize(size_t n, T val T()) {//由于要兼容所有类型缺省值不能为0而是调默认构造函数构造匿名对象 if (n size()) {_finish _start n;//等效于删除数据}else {if (n capacity()) {reserve(n);while (_finish ! _start n) {*_finish val;_finish;}}}}void reserve(size_t n) {if (n capacity()) {size_t sz size();//提前记录sizeT* tmp new T[n];if (_start) {//memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝不适用于自定义类型for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;//size()返回的是_finish - _start ,这里用size()的话会变成_finish_start_finish-_start ,_finish会变成0 ,只能用提前记录的sz_end_of_storage _start n;}}size_t capacity() const {return _end_of_storage - _start;}size_t size() const {return _finish - _start;}bool empty() {return _start _finish;}T operator[](size_t pos) {assert(pos size());return _start[pos];}const T operator[](size_t pos) const {assert(pos size());return _start[pos];}void push_back(const T x) {if (_finish _end_of_storage) {//容量检查reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}void pop_back() {assert(!empty());//确保非空--_finish;}iterator insert(iterator pos, const T val) {assert(pos _start);assert(pos _finish);if (_finish _end_of_storage) {//容量检查size_t len pos - _start;//为防迭代器失效需要在扩容前记录pos到_start的相对距离以便在扩容后更新pos位置。reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;//扩容后用记录的相对距离更新pos位置避免pos位置错误导致的迭代器失效(野指针型)}iterator end _finish - 1;while (end pos) {*(end 1) *end;--end;}*pos val;_finish;return pos;}iterator erase(iterator pos) {assert(pos _start);assert(pos _finish);//pos不能等于_finishiterator start pos 1;while (start ! _finish) {//挨个往前挪*(start - 1) *start;start;}--_finish;return pos;}private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};//类分隔线void func(const vectorint v) {cout endl;for (size_t i 0; i v.size(); i) {cout v[i] ;}cout endl;vectorint::const_iterator it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;cout endl;}void test_vector1() {vectorint v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);func(v1);for (size_t i 0; i v1.size(); i) {cout v1[i] ;}cout endl;v1.pop_back();v1.pop_back();vectorint::iterator it v1.begin();while (it ! v1.end()) {cout *it ;it;}cout endl;for (auto e : v1) {cout e ;}cout endl;}templateclass Tvoid f() {T x T();cout x endl;}void test_vector2() {//虽然内置类型理论上没有构造函数但为兼容模板一般支持像自定义类型一样用构造函数//int i int();//会初始化为0//int j int(1);//会初始化为1fint();fint*();fdouble();}void test_vector3() {vectorint v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);cout v1.size() endl;cout v1.capacity() endl;v1.resize(10);cout v1.size() endl;cout v1.capacity() endl;func(v1);v1.resize(3);func(v1);}void test_vector4() {vectorint v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);//v1.push_back(4);//*v1.insert(v1.begin(), 9);auto pos find(v1.begin(), v1.end(), 2);if (pos ! v1.end()) {//pos v1.insert(pos, 50);v1.insert(pos, 50);}//insert后的pos默认看作已失效(野指针)不能再使用因为位置关系变了for (auto e : v1) {cout e ;}cout endl;}void test_vector5() {vectorint v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1) {cout e ;}cout endl;auto pos find(v1.begin(), v1.end(), 3);if (pos ! v1.end()) {v1.erase(pos);}//类似于insert后erase后pos也视作失效(野指针),因为位置关系也变了//(比如pos指向最后一个元素erase这个元素后pos就指向了_finish不再指向合法位置)//(*pos);//vs下会被检查到然后报错linux下g不检查但还是可能会出问题(行为结果未定义与具体编译器实现有关)//string也会有迭代器失效的情况但string的erase和insert更常用下标而不是迭代器故问题不算明显。for (auto e : v1) {cout e ;}cout endl;}void test_vector6() {vectorint v1;v1.push_back(0);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1) {cout e ;}cout endl;//删除所有偶数:迭代器适合删除vectorint::iterator it v1.begin();while (it!v1.end()){if (*it % 2 0) {it v1.erase(it);//迭代器erase后失效接收返回值以更新pos}else {it;//迭代器未失效正常}}for (auto e : v1) {cout e ;}cout endl;}void test_vector7() {//vectorint v1(10u, 5);//u表示无符号vectorint v1(10, 5);for (auto e : v1) {cout e ;}cout endl;vectorint v2(v1.begin() 1, v1.end() - 1);for (auto e : v2){cout e ;}cout endl;std::string s1(hell word);vectorint v3(s1.begin(), s1.end());for (auto e : v3){cout e ;}cout endl;int arr[] {1,2,60,3,4,5};vectorint v4(arr, arr 4);for (auto e : v4){cout e ;}cout endl;v1.insert(v1.begin(), 8);for (auto e : v1){cout e ;}cout endl;sort(v1.begin(), v1.end());for (auto e : v1){cout e ;}cout endl;for (auto e : arr){cout e ;}cout endl;sort(arr, arr sizeof(arr) / sizeof(int), greaterint());//sort默认升序。除了能对迭代器的区间排序还可以对数组排序。for (auto e : arr){cout e ;}cout endl;}void test_vector8(){vectorint v1(10, 5);for (auto e : v1){cout e ;}cout endl;vectorint v2(v1);for (auto e : v2){cout e ;}cout endl;vectorstd::string v3(3, 123456789123456789);for (auto e : v3){cout e ;}cout endl;vectorstd::string v4(v3);for (auto e : v4){cout e ;}cout endl;v4.push_back(1111111111);v4.push_back(2222222222);v4.push_back(3333333333);for (auto e : v4){cout e ;}cout endl;}}
