目录1、vector介绍2、vector的使用2.1、vector的定义2.2、vector的遍历operator[ ]迭代器范围for2.3、vector的空间增长问题size和capacitymax_sizereserveresize2.4、vector的增删查改push_back和pop_backinsert和erasefindsort1、vector介绍vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小。为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deques, lists and forward_lists vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起lists和forward_lists统一的迭代器和引用更好。2、vector的使用2.1、vector的定义constructor构造函数声明接口说明1、vector()重点无参构造2、vectorsize_type n, const value_type val value_type()构造并初始化n个val3、vector (const vector x);重点拷贝构造4、vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造5、vector (initializer_listvalue_type il, const allocator_type alloc allocator_type());使用初始化器列表构造函数C11示例1、vector() 无参构造int main() { vectorint v1;//存储int类型数据 v1.push_back(1); vectordouble v2;//存储double类型数据 v2.push_back(1.1); vectorstring v3;//存储string类型数据 v3.push_back(hello,world); return 0; }2、vectorsize_type n, const value_type val value_type()构造并初始化n个valvectorint v1(10, 5);//用10个5来初始化v13、vector (const vector x); 拷贝构造vectorint v1(10, 5);//用10个5来初始化v1 vectorint v2(v1);//用v1去拷贝构造v24、vector (InputIterator first, InputIterator last); 使用迭代器进行初始化构造vectorint v1(10, 5);//用10个5来初始化v1 vectorint v3(v1.begin(), v1.end());//使用迭代器拷贝构造v2的数据还可以通过迭代器初始化来获得string的字符串string s hello world; vectorchar v(s.begin(), s.end());5、vector (initializer_listvalue_type il, const allocator_type alloc allocator_type()); 使用初始化列表构造函数int main() { vectorint v1 { 10, 20, 30, 40, 50 }; for (auto e : v1) cout e ; // 10 20 30 40 50 return 0; }2.2、vector的遍历接口名称使用说明1、operator[ ]下标 [ ]2、迭代器begin end 或 rbrgin rend3、范围for底层还是借用迭代器实现operator[ ]operator[ ]就是对[ ]的重载是我们可以像C语言那样使用下标 [ ]去访问元素。void test() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (size_t i 0; i v.size(); i) { v[i] 1; cout v[i] ; // 2 3 4 5 } }迭代器vector的迭代器和string的迭代器近乎一致规则也都类似。iterator的使用接口说明1、begin endbegin获取第一个数据位置的iterator/const_iteratorend获取最后一个数据的下一个位置的iterator/const_iterator2、rbegin rendrbegin获取最后一个数据位置的reverse_iteratorrend获取第一个数据前一个位置的reverse_iterator正向迭代器正向迭代器void test2() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //2、迭代器 vectorint::iterator it v.begin(); while (it ! v.end()) { *it - 2; cout *it ; // -1 0 1 2 it; } }反向迭代器void test() { vectorint v(10, 5); vectorint::reverse_iterator rit v.rbegin(); while (rit ! v.rend()) { cout *rit ; rit; } }范围for范围for的底层就是替换了迭代器先前string类已经实现过。​3、范围for void test() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //3、范围for for (auto e : v) { cout e ; //1 2 3 4 } }2.3、vector的空间增长问题容量空间接口说明1、size获取数据个数2、capacity获取容量大小3、max_size判断是否为空4、resize改变vector中的size5、reserve改变vector的capacitysize和capacityvector的size是用来获取有效数据个数而capacity就是获取容量大小void test() { vectorint v(7, 5); cout v.size() endl;//7 cout v.capacity() endl;//5 }max_sizemax_size的作用是返回vector容器可以容纳的最大元素数用类型的最大值除以sizeof(类型即max_size。void test() { vectorint v1; cout v1.max_size() endl;//1073741823 vectorchar v2; cout v2.max_size() endl;//2147483647 }reservereserve的作用是请求更改容量capacity。如果n大于当前容量则该函数会导致容器重新分配其存储将其容量增加到n或更大。在所有其他情况下函数调用不会导致重新分配且容量不会受影响。void test() { vectorint v(10, 5); cout v.capacity() endl;//10 //如果n 当前容量大小更新容量至n v.reserve(100); cout v.capacity() endl;//100 //如果n 当前容量大小不做出任何改动 v.reserve(20); cout v.capacity() endl;//100 }补充void test() { size_t sz; std::vectorint foo; sz foo.capacity(); std::cout making foo grow:\n; for (int i 0; i 100; i) { foo.push_back(i); if (sz ! foo.capacity()) { sz foo.capacity(); std::cout capacity changed: sz \n; } } }测试结果如下capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。vs是PJ版本STLg是SGI版本STL。为什么一定要按照1.5倍或2倍增长呢答案合适单次增容越多插入N个值增容次数越少效率就越高但是浪费空间就越多。单次增容越少就会导致频繁增容效率低下。1.5倍或2倍是最平衡的做法。resizeresize在空间的同时也进行了初始化。如果 n 小于当前容器大小则内容将减少到其前 n 个元素删除超出并销毁的元素。如果 n 大于当前容器大小 则通过在末尾插入所需数量的元素以达到 n 的大小来扩展内容。如果指定了 val则新元素将初始化为 val 的副本否则它们将进行值初始化。void test() { vectorint v(10, 5); cout v.size() endl;//10 cout v.capacity() endl;//10 //如果n的大小 size和capacity更新到n。超出的部分用1初始化 v.resize(100, 1); cout v.size() endl;//100 cout v.capacity() endl;//100 //如果n的大小 size更新size到n容量capacity不变 v.resize(50); cout v.size() endl;//50 cout v.capacity() endl;//100 //如果n的大小 size且 capacity更新size到n容量capacity不变 v.resize(70); cout v.size() endl;//50 cout v.capacity() endl;//100 }2.4、vector的增删查改vector增删查改接口说明1、push_back尾插2、pop_back尾删3、insert在下标为pos的前面插入val4、erase删除下标为pos的值5、find查找。注意这个是算法模块实现不是vector的成员接口6、sort排序。注意这里也不是vector的函数接口只是用于排序push_back和pop_back这俩接口和string类以及数据结构的没啥区别这里简单给出测试用例void test() { vectorint v; v.push_back(1); v.push_back(10); v.pop_back(); v.pop_back(); }insert和eraseinsert就是在下标为pos的前面插入valerase就是删除下标为pos的值void test9() { vectorint v; v.push_back(1); v.push_back(10); //insert v.insert(v.begin(), 0); //在下标为0的位置插入0 v.insert(v.begin(), 2, -1);//在下标为0的位置往后插入两个-1 for (auto e : v) cout e ; //-1 -1 0 1 10 cout endl; v.insert(v.begin() 3, 2);//在下标为3的位置插入2 for (auto e : v) cout e ; //-1 -1 0 2 1 10 cout endl; //erase v.erase(v.begin()); //头删 for (auto e : v) cout e ; //-1 0 2 1 10 cout endl; v.erase(v.begin() 3); //删除下标为3的值 for (auto e : v) cout e ; //-1 0 2 10 cout endl; //删除在该迭代器区间内的元素左闭右开 v.erase(v.begin(), v.begin() 3);//删除下标[0, 3)左闭右开的值 for (auto e : v) cout e ;//10 }find这里的find并不是vector的成员函数这个是算法模块实现。其本质就是在一段左闭右开的迭代器区间去寻找一个值。找到了就返回它的迭代器找不到就返回它的开区间那个迭代器。void test() { 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); auto pos find(v.begin(), v.end(), 3);//调用find在左闭右开的区间内寻找val if (pos ! v.end()) { cout 找到了 endl; v.erase(pos);//找到后把该值删掉 } else { cout 没有找到 endl; } for (auto e : v) cout e ; //1 2 4 }sortsort函数也不是vector的成员函数这里只是为了对vector创建的数据进行排序。void test() { vectorint v; v.push_back(1); v.push_back(-23); v.push_back(30); v.push_back(9); v.push_back(0); v.push_back(-90); //默认sort是升序 sort(v.begin(), v.end()); for (auto e : v) cout e ; //-90 -23 0 1 9 30 cout endl; //要排降序就要用到仿函数,具体是啥后续详谈 sort(v.begin(), v.end(), greaterint()); for (auto e : v) cout e ; //30 9 1 0 -23 -90 }