C++零基础到工程实战（4.3.4）：vector数组搜索、删除、插入与排序

目录一、前言二、vector搜索find 的使用2.1 find函数的作用2.2 使用find要包含哪个头文件2.3 find的参数怎么理解1开始位置2结束位置3目标值2.4 find返回的是什么2.5 *f 是什么意思2.6 f - datas.begin() 为什么能得到位置2.7 find默认只找第一个匹配项三、vector删除erase 的使用3.1 erase删除单个元素3.2 erase删除后为什么后面元素会前移3.3 删除后为什么位置会变化3.4 为什么删除多个元素常常从后往前删3.5 从前往后删为什么容易出问题3.6 从后往前删为什么更安全3.7 删除多个指定值的完整逻辑1先定义要找的值2准备一个数组存位置3从后往前找所有位置4输出这些位置5按记录的位置逐个删除3.8 erase后原迭代器要小心四、vector插入insert 的使用4.1 insert的基本作用4.2 在指定元素前插入数据4.3 datas.begin() 2 是什么意思4.4 插入后为什么后面的元素会后移4.5 insert和erase的共同特点五、vector排序sort 的使用5.1 排序为什么也要用algorithm头文件5.2 正序排序5.3 倒序排序5.4 greater () 是什么意思5.5 关于 greater () 再补充一点六、完整代码实战分析七、本节重点总结7.1 find的核心要点7.2 erase的核心要点7.3 insert的核心要点7.4 sort的核心要点一、前言在上一篇4.3.3中我们已经把vector的基础部分讲清楚了包括vector的定义与初始化push_back()增加元素size()获取大小下标访问三种遍历方式迭代器iteratorbegin()和end()的含义如果说上一节解决的是“vector 怎么创建、怎么访问、怎么遍历”那么这一节解决的就是“vector 里面的数据怎么查、怎么删、怎么插、怎么排”这几个操作在实际开发中非常常见。例如在一组数据中查找某个值删除某个元素在指定位置插入新数据对数据进行升序或降序排序而vector作为连续空间容器在做这些操作时有一个很重要的特点一旦发生删除或插入后面的元素位置可能整体发生变化。所以这一节除了讲函数怎么用更重要的是讲清楚它背后的逻辑。二、vector搜索find 的使用2.1 find函数的作用在vector中如果我们想查找某个元素可以使用标准库算法find。例如auto f find(datas.begin(), datas.end(), 7);它的意思是在datas这个vector中从开头到结尾顺序查找值为7的元素。这里的查找方式不是二分不是哈希而是最基础的从前往后一个一个比。所以find可以理解成顺序查找。2.2 使用find要包含哪个头文件find和sort一样都属于标准算法库中的内容所以要包含头文件#include algorithm如果没有这个头文件find和sort都无法正常使用。2.3 find的参数怎么理解find的基本格式是find(开始位置, 结束位置, 要查找的值)例如find(datas.begin(), datas.end(), 7);这里三个参数分别表示1开始位置datas.begin()表示从vector的第一个元素开始查找。2结束位置datas.end()表示查找到尾后位置为止。注意end()不是最后一个元素而是最后一个元素后面的位置。3目标值7表示要找的内容是值为7的元素。所以整句意思就是在 datas 的全部范围内查找值为 7 的元素。2.4 find返回的是什么这一点非常重要。find返回的不是下标不是布尔值而是迭代器。也就是说找到了就返回指向该元素的迭代器没找到就返回datas.end()2.5*f是什么意思因为f是迭代器它表示一个位置。而*f表示取出这个位置上的元素值。例如如果f指向的是元素7那么*f结果就是7所以f是位置*f是位置上的值这一点和指针很像。2.6f - datas.begin()为什么能得到位置代码f - datas.begin()这里表示当前找到的位置和起始位置之间相差了多少个元素。由于vector是连续空间迭代器支持随机访问所以可以直接相减。例如datas.begin()指向第 0 个元素f指向第 3 个元素那么f - datas.begin()结果就是3这也就相当于该元素的下标位置。所以这句代码cout find *f in f - datas.begin() endl;可以理解为找到了这个值它在第几个位置。2.7 find默认只找第一个匹配项这个也要特别说明。例如vectorint datas{7,2,3,6,5,6,7,8}; auto f find(datas.begin(), datas.end(), 7);这里虽然有两个7但find只会返回第一个 7 的位置。也就是说它找到第一个匹配项后就停止了不会继续帮你找后面的所有结果。如果要找所有匹配位置就需要自己写循环。三、vector删除erase 的使用3.1 erase删除单个元素代码datas.erase(f);这里表示删除迭代器f所指向的那个元素。例如auto f find(datas.begin(), datas.end(), 7); if (f ! datas.end()) { datas.erase(f); }意思就是先找到第一个7然后把这个7删掉。3.2 erase删除后为什么后面元素会前移这一点是vector很核心的特性。因为vector底层本质上是连续空间。例如原来数据是7 2 3 6 5如果删掉第一个元素7为了保证仍然连续后面的元素就要整体往前移动2 3 6 5所以你可以理解成删除vector中某个位置的元素时后面的数据会自动“补位”。这也正因为如此删除操作相比单纯访问会有额外开销。3.3 删除后为什么位置会变化因为元素前移了。举个例子原数组0 1 2 3 4 5如果删掉下标为 2 的元素那么原来下标 3、4、5 的元素删除后都会变成 2、3、4。也就是说删除会改变后续元素的位置。所以一旦在循环中一边遍历一边删除就要格外小心。3.4 为什么删除多个元素常常从后往前删这是非常重要的工程经验。int fdata 6; vectorint datapos; for (int i datas.size() - 1; i 0; i--) { if (datas[i] fdata) { datapos.push_back(i); } }这里是从后往前找所有值为6的位置。为什么这么做因为如果你从前往后删前面删掉一个元素后后面的下标全部变化可能会导致漏删下标错位删除错误元素而从后往前删就不会影响前面还没处理的位置。3.5 从前往后删为什么容易出问题例如数据是1 6 6 8如果你从前往后删先删第一个6原来后面的那个6下标已经变了删完后变成1 6 8如果循环变量继续正常往后加就容易跳过它。所以删除多个元素时从前往后直接删风险很大。3.6 从后往前删为什么更安全如果先删后面的元素前面的元素位置不受影响。这就是你代码里这一段的意义vectorint datas{7,2,3,6,5,6,7,8}; int fdata 6; vectorint datapos; for (int i datas.size() - 1; i 0; i--) { if (datas[i] fdata) { datapos.push_back(i); } }先把所有目标位置按“从后往前”的顺序记录下来。然后再删除for (auto p : datapos) { datas.erase(datas.begin() p); }因为删的是后面的元素所以前面的下标不会被破坏。3.7 删除多个指定值的完整逻辑你这段代码完整逻辑是1先定义要找的值int fdata 6;表示我们要处理所有值为6的元素。2准备一个数组存位置vectorint datapos;用来保存所有找到的下标。3从后往前找所有位置for (int i datas.size() - 1; i 0; i--) { if (datas[i] fdata) { datapos.push_back(i); } }如果某个位置的值等于6就把这个位置保存下来。4输出这些位置for (auto p : datapos) cout p ;方便观察哪些位置将要被删除。5按记录的位置逐个删除for (auto p : datapos) { datas.erase(datas.begin() p); }这就是一种很典型的先找位置再从后往前删。3.8 erase后原迭代器要小心这里再补一个工程中很重要的点。vector删除元素后后续元素会移动所以某些原来的迭代器可能失效。也就是说erase之后不要随便继续使用原来已经保存的迭代器。你当前这份代码里因为删除时重新用的是datas.begin() p所以逻辑是安全的。但如果你把一个老迭代器留着删除后还继续乱用就容易出问题。四、vector插入insert 的使用4.1 insert的基本作用insert用来在指定位置插入元素。例如datas.insert(f, 3311);表示在迭代器f指向的位置前面插入一个新元素3311。注意是插入到 f 的前面。4.2 在指定元素前插入数据代码f find(datas.begin(), datas.end(), 3312); datas.insert(f, 3311);这段逻辑是先找到值为3312的位置在这个位置前面插入3311假设原来是12 3312 334插入后就变成12 3311 3312 334所以这里本质上是在做按目标值定位再在该位置前插入。4.3datas.begin() 2是什么意思代码datas.insert(datas.begin() 2, 99);这里的datas.begin() 2表示从起始位置往后移动 2 个位置。也就是begin() 0第 1 个元素位置begin() 1第 2 个元素位置begin() 2第 3 个元素位置所以这句代码的意思是在第 3 个位置前插入元素 99。4.4 插入后为什么后面的元素会后移和删除一样因为vector是连续空间。如果你在中间插入一个元素那么后面的元素必须整体向后移动一个位置为新元素腾出空间。例如原来10 20 30 40在位置 2 插入99后10 20 99 30 40可以看到原来的30和40都往后移动了。4.5 insert和erase的共同特点无论是insert还是erase本质上都会影响后续元素位置。所以你可以把这两个操作统一理解为erase删除当前位置后面元素前移insert在当前位置前插入后面元素后移这也是为什么它们虽然好用但做得多时开销会比单纯访问更大。五、vector排序sort 的使用5.1 排序为什么也要用algorithm头文件sort和 find同样来自标准算法库所以也要#include algorithm它不是vector自己的成员函数而是通用算法。这也是 STL 的一个很重要思想容器负责存数据算法负责处理数据。5.2 正序排序代码std::sort(datas.begin(), datas.end());这表示对datas中的元素进行排序默认是从小到大。5.3 倒序排序代码std::sort(datas.begin(), datas.end(), greaterint());这表示按从大到小进行排序。5.4greaterint()是什么意思greaterint()可以理解为“按大的在前小的在后” 的比较规则。默认sort没写第三个参数时使用的是升序规则。加上greaterint()之后就变成降序规则。5.5 关于greaterint()再补充一点更规范一点的话可以额外包含#include functional因为greaterint属于函数对象相关内容。有些环境可能不写也能过但从工程习惯看写上更严谨。六、完整代码实战分析下面把你这一段代码完整整理一下并做适度规范化。#include iostream #include vector #include algorithm #include functional using namespace std; int main() { std::vectorint datas{ 7,2,3,6,5,6,7,8,0,10, 5,12,3312,334,11 }; // 1. 查找元素7 auto f find(datas.begin(), datas.end(), 7); if (f ! datas.end()) { cout find *f in f - datas.begin() endl; datas.erase(f); // 删除找到的第一个7 } // 2. 在3312前插入3311 f find(datas.begin(), datas.end(), 3312); if (f ! datas.end()) { datas.insert(f, 3311); } // 3. 在第三个位置插入99 datas.insert(datas.begin() 2, 99); // 4. 查找所有值为6的位置 int fdata 6; vectorint datapos; for (int i datas.size() - 1; i 0; i--) { if (datas[i] fdata) { datapos.push_back(i); } } // 输出所有找到的位置 for (auto p : datapos) cout p ; cout \n; // 5. 删除所有值为6的元素 for (auto p : datapos) { datas.erase(datas.begin() p); } // 输出删除后的结果 for (auto d : datas) { cout d -; } cout endl; // 6. 正序排序 std::sort(datas.begin(), datas.end()); for (auto d : datas) cout d -; cout endl; // 7. 倒序排序 std::sort(datas.begin(), datas.end(), greaterint()); for (auto d : datas) cout d -; cout endl; return 0; }七、本节重点总结7.1 find的核心要点1find需要#include algorithm2格式是find(开始, 结束, 目标值)3返回值是迭代器不是下标4找到则返回目标位置找不到返回end()5*f表示取出找到的值6f - begin()可以求出位置7.2 erase的核心要点1erase可以删除指定位置元素2删除后后续元素会前移3删除会导致后面元素位置变化4删除多个元素时通常从后往前更安全5删除后原有迭代器可能失效要小心7.3 insert的核心要点1insert用于在指定位置前插入元素2可以配合find先定位再插入3可以用begin() 偏移量指定位置4插入后后面元素会整体后移7.4 sort的核心要点1sort也需要#include algorithm2默认从小到大排序3加greaterint()可以从大到小排序4sort操作的是一个区间不局限于vector