STL vector

I.vector 的介绍及使用0x00 vector 介绍 vector 文档介绍vector - C Reference1.vector是表示可变大小数组的序列容器我们说vector像是数组但又不像数组为啥像数组vector就像是数组一样它也是采用连续存储空间来存储元素的这也就意味着我们可以用下标访问vector元素和数组一样高效。为啥不像数组vector的大小是可以动态改变的而且它的大小会被容器自动处理2.本质上来说vector使用动态分配数组来存储它的元素。当新元素插入时为了增加存储空间这个数组就需要被重新分配大小。具体做法是分配一个新的数组然后将全部的元素转移到这个新的数组。就时间成本而言vector的消耗过高我们通常不会考虑每次插入新的元素就要重新分配一次数组空间。3.vector空间分配策略所以为了简化我们的操作vector在动态分配上往往会分配额外的存储空间以适应可能的增长因此容器的实际容量可能会大于严格容纳其元素所需的存储空间即其大小)。4.与其他动态序列容器双端队列、列表和前向列表相比向量在访问其元素方面非常高效与数组一样并且在从其末尾添加或删除元素方面相对高效。对于涉及在非末尾位置插入或删除元素的操作向量的性能比其他容器差并且与列表和前向列表相比其迭代器和引用的一致性较差。0x01 初始化vector1.无参构造vectorint v1; // 无参构造创建一个int类型的空的vector对象2.构造并初始化用 n 个 value 初始化vectorint v2(10, 3); // 10个33.迭代器区间初始化begin endvectorint v3(v2.begin(), v2.end());4.拷贝构造vectorint v4(v2);但是不乏有这种情况我不要拷贝对象的头尾数据呢即不要它的 begin 和 endvectorint v3(v2.begin(), --v2.end());综合vectorint arr1; //一个空数组 vectorint arr2 {1, 2, 3, 4, 5}; //包含1、2、3、4、5五个变量 vectorint arr3(4); //开辟4个空间值默认为0 vectorint arr4(5, 3); //5个值为3的数组 vectorint arr5(arr4); //将arr4的所有值复制进去和arr4一样 vectorint arr6(arr4.begin(), arr4.end()); //将arr4的值从头开始到尾复制 vectorint arr7(arr4.rbegin(), arr4.rend()); //将arr4的值从尾到头复制---------------------------------------------------------------------------------------------------------------------------------对于迭代器区间初始化它这里的 InputInerator 不一定是 vector Inerator。它是一个模板所以你传的是谁的迭代器它就可以实例化出谁的迭代器0x02 关于 vector 的析构、拷贝构造和赋值构造​ 至于析构函数一般情况下我们不需要管因为它会自动调用。拷贝构造和赋值构造vector 的拷贝构造和赋值其实就是深拷贝。这些我们放在 vector 模拟实现的章节里详细探讨。II.vector的遍历0x00 push_backvector 不能用爽到飞起地 operatorstring 能用 主要是 string 不仅可以尾插一个字符还可以追加一个字符串。但是 vector 就只支持一个一个数据的插入和删除push_back 和 pop_back。vector.push_back(内容);0x01 下标方括号遍历vector 是连续的空间又支持 operator[] 和 size() 所以可以用下标方括号遍历。void vector_Traversal_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) { cout v[i] ; } cout endl; }结果如下当然也支持修改void vector_Traversal_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; // 令每个元素1 cout v[i] ; } cout endl; }结果如下0x02 访问vector的at顺便再讲一下 at() 它和 operator[] 一样也是用来访问 vector 的但是 at() 会进行边界检查void test_vector4() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout v.at(0) endl; cout v.at(3) endl; }结果如下需要注意的是 operator会用断言assert检查是否越界而at会抛出异常void test_vector4() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout v.at(5) endl; // 故意越界看看 }结果如下0x03 迭代器遍历vector//迭代器vectorint::iterator for (vectorint::iterator it arr.begin(); it ! arr.end(); it) { cout *it endl; } //迭代器vectorint::reverse_iterator for (vectorint::reverse_iterator it arr.rbegin(); it ! arr.rend(); it) { cout *it endl; }0x04 范围forvector支持迭代器也就支持范围 for这个我们在模拟实现 string 的时候已经验证过了。范围 for 的本质就是编译器在编译时自动替换成迭代器这里也一样。void vector_Traversal_test() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 范围for for (auto e : v) { cout e ; } cout endl; for (auto e : v) { e 10; cout e ; } cout endl; }结果如下Ⅲ. vector 空间0x00 获取数据个数的 size()和string里的一样用来获取数据的元素个数void test_vector2() { vectorint v(6, 6); // 生成6个6 cout v.size() endl; }0x01 改变 vector 容量的 reserve()void test_vector3() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.reserve(100); }结果如下reserve 会扩容但是不会影响数据个数。[capacity] 4 → [capacity]1000x02 改变 vector 大小的 resize()void test_vector4() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.resize(100); }string 的 resize 如果不指定 填充值 默认给的是 \0而 vector 的 resize 如果不指定默认给的是其对应类型的缺省值作为 填充值这里是 int 就是 0如果是指针对应的缺省值就是空指针。注意注意如果开的数据比之前小还会删除数据void test_vector4() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.resize(2); }结果如下Ⅳ. vector 增删查改0x00 pop_back尾删void test_vector5() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); for (auto e : v) cout e ; cout endl; v.pop_back(); // 尾删3 for (auto e : v) cout e ; cout endl; v.pop_back(); // 尾删2 for (auto e : v) cout e ; cout endl; }结果如下0x01 assign() 赋值assign 可以把 vector 的内容覆盖掉。允许给一段区间覆盖也可以给个value去覆盖。void test_vector6() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.assign(10, 5); // 原来是1到4现在改成10个5 }结果如下0x02探讨为什么vector不提供find接口string、map、set 都有 find() 用凭什么 vector 和 list 没有其实我们应该考虑的是 —— 为什么 string、map、set 能有 find 操作。而 vector 之所以不提供 find 是因为如果去查找元素效率就会是……但其实我们也可以用算法库algorithm里就有同样的find操作。该find内部是从begin到end进行一次遍历复杂度为On值得一提的是在C中凡是使用迭代器区间都是左闭右开的——firstlast].再去思考 map、set 为什么有 find() 通过迭代器从头到尾遍历 map 与 set 时得到的结果是按 key 排序的结果而不是插入时的顺序所以这两个容器没有 push_back 操作。其实插入到 map 与 set 中的元素会被组织到一颗红黑树上红黑树是一颗平衡二叉树平衡二叉树是一颗二叉排序树对一颗二叉排序树的查找有点像二分查找复杂度是 由于 map 与 set 的数据结构能有更快的查找方法所以在容器内提供了 find 方法。0x03 insert () 插入void test_vector7() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vectorint::iterator ret find(v.begin(), v.end(), 3); if (ret ! v.end()) { cout 找到了 endl; v.insert(ret, 30); // 在ret位置前面插入一个30 } for (auto e : v) cout e ; cout endl; }结果如下用insert去头插void test_vector8() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) cout e ; cout endl; v.insert(v.begin(), -1); // 在起始位置插入一个-1 for (auto e : v) cout e ; cout endl; }结果如下0x04 erase删除使用erase的时候需要判断一下有没有要删除的元素void test_vector9() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) cout e ; cout endl; vectorint::iterator pos find(v.begin(), v.end(), 5); if (pos ! v.end()) { // 判断pos是否存在 v.erase(pos); // 删除pos } for (auto e : v) cout e ; cout endl; }结果如下怕的就是要删的目标不存在比如我要删个 5但是 vector 里只有 1234 。vectorint::iterator pos find(v.begin(), v.end(), 5); v.erase(pos);如果有了判断就不会翻车了如果待删目标不存在就不会去走 erase() 。因为pos如果找不到就会等于 end() 上的值我们利用这一点进行 if 判断vectorint::iterator pos find(v.begin(), v.end(), 5); if (pos ! v.end()) { // 检查 v.erase(pos); }0x05 clear清空数据void test_vector10() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); printf(清空前); for (auto e : v) cout e ; cout endl; v.clear(); printf(清空后); for (auto e : v) cout e ; cout endl; }结果如下