C++系列-STL中搜索相关算法

---

纳兰性德《减字木兰花·相逢不语》
相逢不语，一朵芙蓉著秋雨。小晕红潮，斜溜鬟心只凤翘。
待将低唤，直为凝情恐人见。欲诉幽怀，转过回阑叩玉钗。

---

💢search相关算法

算法	描述
search(beg1, end1, beg2, end2)	在[beg1, end1) 范围内查找[beg2, end2)首次出现，查找成功，返回[beg1, end1)内第一次出现[beg2, end2)的位置，查找失败返回end1
search(beg1, end1, beg2, end2, pred)	使用pred代替==操作符执行search()
search_n(beg, end, n, val)	在[beg, end)范围内查找val出现n次的字序列
search_n(beg, end, n, val, pred)	使用pred代替==操作符执行search_n()
binary_search(beg, end, val)	使用二分法在[beg, end)范围内查找val，速度非常快。要求序列是有序的，否则结果未知，查找到后返回true，否则false
binary_search(beg, end, val, pred)	使用pred代替==操作符执行binary_search()
lower_bound(beg, end, val)	在[beg1, end1) 范围内查找第一个不小于val(>=val)的元素的迭代器，查找到后返回该元素的迭代器，否则返回序列的end()，因为内部是二分法实现的，需要保证是有序序列
lower_bound(beg, end, val，pred)	查找第一个不满足pred的元素对应的迭代器
upper_bound(beg, end, val)	在[beg1, end1) 范围内查找第一个大于val的元素的迭代器，查找到后返回该元素的迭代器，否则返回序列的end()，，因为内部是二分法实现的，需要保证是有序序列

💢💢search算法举例

👉 👉 👉
在下面的代码中，search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end())，当在vec1{1, 33, 44, 2, 5, 55, 25, 44, 2, 7}中找到vec2{44, 2}时返回，在vec1中，有两处44,2子序列，只返回vec1中第一个44对应的迭代器。
search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), [](int val1, int val2) -> bool {return val2 > val1;}，在vec1{1, 33, 23, 2, 5, 55, 25, 44, 2, 7}中，寻找连续的子序列，对应的元素分别小于vec2{44, 5}中的44,5，vec1中的23,2分别小于44,5，故返回vec1中23所对应的迭代器。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;template<typename T>
void print_vector(const vector<T>& vec)
{for (auto i_vec : vec){cout << i_vec << " ";}cout << endl;
}void test01()
{vector<int> vec1 {1, 33, 44, 2, 5, 55, 25, 44, 2, 7};vector<int> vec2 {44, 2};vector<int>::iterator it = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());if (it != vec1.end()){vector<int> vec3;vec3.assign(it, vec1.end());print_vector(vec3);}else{cout << "没找到" << endl;}
}void test02()
{vector<int> vec1 {1, 33, 23, 2, 5, 55, 25, 44, 2, 7};vector<int> vec2 {44, 5};// vec2中是一个整体，vec1从头开始搜索，当发现连续的元素满足和vec2的关系时，停止搜索vector<int>::iterator it = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), [](int val1, int val2) -> bool {return val2 > val1;});if (it != vec1.end()){vector<int> vec3;vec3.assign(it, vec1.end());print_vector(vec3);}else{cout << "没找到" << endl;}
}
void main()
{test01();test02();system("pause");
}result:
44 2 5 55 25 44 2 7
23 2 5 55 25 44 2 7

---

💢💢search_n算法举例

👉 👉 👉
在下面的代码中，search_n(vec1.begin(), vec1.end(), 2, 5)，在vec1 {1, 33, 44, 2, 5, 5, 25, 44, 2, 7}中搜索连续的2个5，返回第一个5对应的迭代器。
search_n(vec1.begin(), vec1.end(), 3, 5, [](int val1, int val2) -> bool {return val1 > val2;})，在谓词中，第1个参数val1是vec1中的元素，第2个参数val2是5。
在vec1{1, 33, 23, 2, 18, 55, 25, 44, 2, 7}中搜索，连续3个元素满足分别大于5，18, 55, 25满足条件，则返回第一个元素18对应的迭代器。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;template<typename T>
void print_vector(const vector<T>& vec)
{for (auto i_vec : vec){cout << i_vec << " ";}cout << endl;
}void test01()
{vector<int> vec1 {1, 33, 44, 2, 5, 5, 25, 44, 2, 7};vector<int>::iterator it = search_n(vec1.begin(), vec1.end(), 2, 5);if (it != vec1.end()){vector<int> vec3;vec3.assign(it, vec1.end());print_vector(vec3);}else{cout << "没找到" << endl;}
}void test02()
{vector<int> vec1 {1, 33, 23, 2, 18, 55, 25, 44, 2, 7};vector<int>::iterator it = search_n(vec1.begin(), vec1.end(), 3, 5, [](int val1, int val2) -> bool {return val1 > val2;});if (it != vec1.end()){vector<int> vec3;vec3.assign(it, vec1.end());print_vector(vec3);}else{cout << "没找到" << endl;}
}
void main()
{test01();test02();system("pause");
}result:
5 5 25 44 2 7
18 55 25 44 2 7

---

💢💢binary_search算法举例

👉 👉 👉
binary_search是用二分法进行搜索的，序列应该是经过排序的，否则可能出现错误。
binary_search(vec1.begin(), vec1.end(), 2), 在vec1中搜索2，找到后返回true，否则为false。
binary_search(vec1.begin(), vec1.end(), 55, [](int val1, int val2)-> bool { return val1 > val2; });, 首先在vec1中搜索55，找到后，取vec1.begin()到55对应的迭代器区间中所有元素，与55进行pred中的规则判断，若区间中含有满足对比规则的元素，则返回 true ，反之返回 false。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;template<typename T>
void print_vector(const vector<T>& vec)
{for (auto i_vec : vec){cout << i_vec << " ";}cout << endl;
}void test01()
{vector<int> vec1 {1, 33, 44, 2, 5, 25, 7};cout << "vec1排序前:" << endl;print_vector(vec1);cout << "vec1排序后:" << endl;sort(vec1.begin(), vec1.end());print_vector(vec1);bool result = binary_search(vec1.begin(), vec1.end(), 2);if (result){cout << "找到了" << endl << endl;}else{cout << "没找到" << endl << endl;}
}void test02()
{vector<int> vec1 {1, 33, 23, 18, 55, 25, 44, 23, 7};cout << "vec1排序前:" << endl;print_vector(vec1);cout << "vec1排序后:" << endl;sort(vec1.begin(), vec1.end(),greater<int>());print_vector(vec1);// bool std::binary_search(_FwdIt _First, _FwdIt _Last, const _Ty & _Val, _Pr _Pred);// _Pred 为 bool (*)(const _Ty & _Ele, const _Ty & _Val)// 在bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)的基础上，取_First至_Val迭代器区间的所有元素，// 与Val进行自定义规则的对比，若区间中含有满足对比规则的元素，则返回 true ，反之返回 false。bool result = binary_search(vec1.begin(), vec1.end(), 55, [](int val1, int val2)-> bool { return val1 > val2; });if (result){cout << "找到了" << endl;}else{cout << "没找到" << endl;}
}void main()
{test01();test02();system("pause");
}result:
vec1排序前:
1 33 44 2 5 25 7
vec1排序后:
1 2 5 7 25 33 44
找到了vec1排序前:
1 33 23 18 55 25 44 23 7
vec1排序后:
55 44 33 25 23 23 18 7 1
找到了

---

💢 lower_bound

• 🔥找到第一个可以插入 __val 的位置，并且不改变原有排序。
• 🔥找到的是大于等于目标数的位置。

👉 👉 👉
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);前两个分别为起始和结束迭代器，val是要进行对比的数值。
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); comp是自定义的比较规则。
前提是有序的情况下，lower_bound 返回指向第一个值不小于 val 的位置，也就是返回第一个大于等于val值的位置（通过二分查找）。
lower_bound(vec1.begin(), vec1.end(), 3); // – 排序后: 1 2 5 7 25 33 44, 第1个>=3的元素是5，返回其迭代器。
cout << "distance(vec1.begin(), iter1): " << distance(vec1.begin(), iter1) << endl; // distance用于计算两个迭代器之间的距离，从vec1.begin()到5对应的迭代器,距离是2。
lower_bound(vec1.begin(), vec1.end(), 6, [](int val1, int val2)-> bool { return val1 < val2; })，寻找序列中第一个不满足<6的元素。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;template<typename T>
void print_vector(const vector<T>& vec)
{for (auto i_vec : vec){cout << i_vec << " ";}cout << endl;
}void test01()
{vector<int> vec1 {1, 33, 44, 2, 5, 25, 7};cout << "vec1排序前:" << endl;print_vector(vec1);cout << "vec1排序后:" << endl;sort(vec1.begin(), vec1.end());print_vector(vec1);vector<int>::iterator iter1;vector<int>::iterator iter2;// 在动态数组中寻找 >=3 出现的第一个数 并以迭代器的形式返回iter1 = lower_bound(vec1.begin(), vec1.end(), 3);  // -- 排序后: 1 2 5 7 25 33 44, 第1个>=3的元素是5，返回其迭代器// 在动态数组中寻找 >=7 出现的第一个数 并以迭代器的形式返回iter2 = lower_bound(vec1.begin(), vec1.end(), 30);  // -- 排序后: 1 2 5 7 25 33 44, 第1个>=30的元素是33，返回其迭代器// distance用于计算两个迭代器之间的距离，从vec1.begin()到5对应的迭代器,距离是2cout << "distance(vec1.begin(), iter1): " << distance(vec1.begin(), iter1) << endl;// distance用于计算两个迭代器之间的距离，从vec1.begin()到33对应的迭代器,距离是5 cout << "distance(vec1.begin(), iter2): " << distance(vec1.begin(), iter2) << endl; 
}void test02()
{vector<int> vec1 {2, 7, 18, 23, 25, 33, 44, 55};sort(vec1.begin(), vec1.end());cout << "\nvec1:" << endl;print_vector(vec1);vector<int>::iterator iter1;vector<int>::iterator iter2;// vec1的元素是2, 7, 18, 23, 25, 33, 44, 55// iter1, pred的条件是val1<val2, vec1中的元素小于val2,lower_bound返回的是不满足pred设定的条件第1个元素，// 那么应该找到第一个不满足小于6的元素,是7，则返回7对应的迭代器。iter1 = lower_bound(vec1.begin(), vec1.end(), 6, [](int val1, int val2)-> bool { return val1 < val2; });// 应该找到第一个不满足小于30的元素,是7，则返回33对应的迭代器。iter2 = lower_bound(vec1.begin(), vec1.end(), 30, [](int val1, int val2)-> bool { return val1 < val2; });if (iter1 == vec1.end()){cout << "没找到" << endl;}else{cout << *iter1 << endl;}if (iter2 == vec1.end()){cout << "没找到" << endl;}else{cout << *iter2 << endl;}
}
void main()
{test01();test02();system("pause");
}result:
vec1排序前:
1 33 44 2 5 25 7
vec1排序后:
1 2 5 7 25 33 44
distance(vec1.begin(), iter1): 2
distance(vec1.begin(), iter2): 5vec1:
2 7 18 23 25 33 44 55
7
33

💢 upper_bound

• 🍐找到最后一个可以插入 val 而不改变原来有序数组的排序位置。
• 🍐前提是有序的情况下，upper_bound 返回第一个大于–val值的位置（通过二分查找）。
• 🍐 用lower_bound类似。只是把lower_bound的 大于等于换成大于, pred是相同的用法。

👉 👉 👉
upper_bound(vec1.begin(), vec1.end(), 4)即找到序列中第一个大于4的位置。
upper_bound(vec1.begin(), vec1.end(), 4, [](int val, int serial)-> bool { return val < serial; }); _Pred(_Val, *_UMid)中的第1个参数是upper_bound中的第3个参数，本例中_Pred要求4<序列中的值，找到第一个满足的位置，应该为8。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void test01()
{vector<int> vec1 = { 1, 4, 8, 18, 22, 34, 55 };vector<int>::iterator iter1;vector<int>::iterator iter2;// 在vec1中寻找>4的第一个数 返回其迭代器iter1 = upper_bound(vec1.begin(), vec1.end(), 4);  // 大于4，则指向8// 在动态数组中寻找 >7 出现的第一个数 并以迭代器的形式返回iter2 = upper_bound(vec1.begin(), vec1.end(), 15); // 大于17，则指向18if (iter1 == vec1.end())cout << "未找到满足条件的元素" << endl;else{cout << "*iter1: " << * iter1 << endl;  }if (iter2 == vec1.end())cout << "未找到满足条件的元素" << endl;else{cout << "*iter2: " << * iter2 << endl; }
}void test02()
{vector<int> vec1 = { 1, 4, 8, 18, 22, 34, 55 };vector<int>::iterator iter1;vector<int>::iterator iter2;// _Pred(_Val, *_UMid)中的第1个参数是upper_bound中的第3个参数，本例中_Pred要求4<序列中的值，找到第一个满足的位置，应该为8iter1 = upper_bound(vec1.begin(), vec1.end(), 4, [](int val, int serial)-> bool { return val < serial; }); if (iter1 == vec1.end())cout << "未找到满足条件的元素" << endl;else{cout << "*iter1: " << *iter1 << endl; }
}void main()
{test01();test02();system("pause");
}result:
*iter1: 8
*iter2: 18
*iter1: 8

💢 lower_bound和upper_bound

• 🥝 在没有pred参数的情况下，lower_bound是寻找第一个大于等于参数val的元素的位置，upper_bound是寻找第一个大于参数val的元素的位置。
• 🥝 有pred的情况下，lower_bound中pred的默认参数为_Pred(*_UMid, _Val)，第1个是序列中的元素，第2个是lower_bound中的val参数。upper_bound中pred的默认参数为_Pred(_Val, *_UMid)，第2个是upper_bound中的val参数，第2个是序列中的元素。

💢equal_range

• 🍋 返回pair类型，两个迭代器，第1个是lower_bound，第2个是upper_bound。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;template<typename T>
void print_vector(const vector<T>& vec)
{for (auto i_vec : vec){cout << i_vec << " ";}cout << endl;
}void test01()
{vector<int> vec1 {1, 2, 5, 7, 25, 33, 44};print_vector(vec1);pair<vector<int>::iterator, vector<int>::iterator> p1;// equal_range,返回一对迭代器，第1个是lower_bound(>=33)，第2个是upper_bound(>33)p1 = equal_range(vec1.begin(), vec1.end(), 33); if (p1.first != vec1.end()){cout << *p1.first << endl;}else{cout << "lower_bound not found!" << endl;}if (p1.second != vec1.end()){cout << *p1.second << endl;}else{cout << "upper_bound not found!" << endl;}
}void main()
{test01();system("pause");
}result:
1 2 5 7 25 33 44
33
44