STL算法 | 查找函数 find()、二分查找binary_search/upper_bound、子序列查找search
一、find系列函数（单个元素顺序查找）
该算法提供范围内查找对象的算法，在<algorithm>头文件中定义。
指向首个满足条件的迭代器，或若找不到这种元素则为 last 。
参考自：《https://zh.cppreference.com/w/cpp/algorithm/find》
1. find 搜索等于 value 的元素。
// 在范围 [first, last) 中满足特定判别标准的首个元素
template< class InputIt, class T >
constexpr InputIt find( InputIt first, InputIt last, const T& value );
template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, const T& value );
2. find_if 搜索谓词 p 对其返回 true 的元素
参数说明：p - 若为要求的元素则返回 true 的一元谓词。
template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if( InputIt first, InputIt last,
UnaryPredicate p );
// 指定执行策略
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate p );
3. find_if_not 搜索谓词 q 对其返回 false 的元素。
参数说明：q - 若为要求的元素则返回 false 的一元谓词。
template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if_not( InputIt first, InputIt last,
UnaryPredicate q );
// 指定执行策略
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if_not( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate q );
测试用例
int main()
{
vector<int>vec{ 3,6,10,8,7,9,1,5,2,4 }; // vector_int
int val = 7;
test1:// find
auto ret1 = find(vec.begin(), vec.end(), val); // 查找
if (ret1 != vec.end()) // 如果找到，输出
{
cout << " vec[" << distance(vec.begin(), ret1) << "] == " << val << endl;
}
// 输出: vec[4] == 7
test2:// find_if
auto ret2 = find_if(vec.begin(), vec.end(),
[val](int v) {return v == val; }); // 查找 等于val的元素
if (ret2 != vec.end())
{
cout << " vec[" << distance(vec.begin(), ret2) << "] == " << val << endl;
}
// 输出: vec[4] == 7
test3:// find_if_not
auto ret3 = find_if_not(vec.begin(), vec.end(),
[val](int v) {return v != val; }); // 查找，不满足 (v != val) 的数
// 即，v==val
if (ret3 != vec.end())
{
cout << " vec[" << distance(vec.begin(), ret3) << "] == " << val << endl;
}
// 输出: vec[4] == 7
return 0;
}
一、二分查找系列函数（单个元素二分查找）
注：二分查找的基础是给定范围是有序排列的。
1. lower_bound 二分查找大于等于
返回指向范围 [first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素则返回 last 。
// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
2. upper_bound 二分查找大于
返回指向范围 [first, last) 中首个大于 value 的元素的迭代器，或若找不到这种元素则返回 last 。采用二分实现，所以调用前必须保证有序。
// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
3. equal_range 二分查找等价区间
返回范围 [first, last) 中含有所有等价于 value 的元素的范围。
含有定义所需范围的一对迭代器的 std::pair ，第一迭代器指向首个不小于 value 的元素，而第二迭代器指向首个大于 value 的元素。
若无元素小于 value ，则 last 作为第一元素返回。类似地，若无元素大于 value ，则 last 作为第二元素返回。
// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt,ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value );
// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt,ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value, Compare comp );
4. binary_search 二分查找是否存在元素value
检查等价于 value 的元素是否出现于范围 [first, last) 中。
若找到等于 value 的元素则为 true ，否则为 false 。
// 用 operator< 比较元素
template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );
// 用给定的比较函数 comp
template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
测试用例
int main()
{
vector<int>vec{ 3,6,10,8,7,9,1,5,2,4 }; // vector_int
sort(vec.begin(), vec.end(), less<int>()); // 排序 ｛1,...10｝
int val = 7;
test1:// lower_bound 大于等于
auto ret1 = lower_bound(vec.begin(), vec.end(), val); // 查找，大于等于
if (ret1 != vec.end()) // 如果找到，输出
{
cout << "( vec[" << distance(vec.begin(), ret1) << "] == " << *ret1
<< " ) >= " << val << endl;
}
// 输出: ( vec[6] == 7 ) >= 7
test2:// upper_bound 大于
auto ret2 = upper_bound(vec.begin(), vec.end(), val); // 查找，大于
if (ret2 != vec.end())
{
cout << "( vec[" << distance(vec.begin(), ret2) << "] == " << *ret2
<< " ) > " << val << endl;
}
// 输出: ( vec[7] == 8 ) > 7
test3:// equal_range
vector<int> vecs{ 1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7 };
int vals = 4;
auto ret3 = equal_range(vecs.begin(), vecs.end(), vals); // 查找，等价区间
for(auto i = ret3.first; i != ret3.second; i++)
{
cout << " vec[" << distance(vec.begin(), ret2) << "] == " << *i << "\n";
}
/* 输出:
vec[7] == 4
vec[7] == 4
vec[7] == 4
*/
return 0;
}
三、子序列查找 search
搜索范围 [first, last - (s_last - s_first)) 中元素子序列 [s_first, s_last) 的首次出现。
指向范围中 [first, last - (s_last - s_first)) ，首个子序列 [s_first, s_last) 起始的迭代器。若找不到这种子序列，则返回 last
参考自《https://zh.cppreference.com/w/cpp/algorithm/search》
1. 使用operator== 比较
// 元素用 operator== 比较
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// 指定执行策略
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
2. 用给定的二元谓词 p 比较
// 元素用给定的二元谓词 p 比较
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// 指定执行策略
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
3. 在序列 [first, last) 中搜索 searcher 构造函数中指定的模式
注： 此函数返回searcher.operator() 的结果，即指向找到的子串位置的迭代器，或若找不到则为 last
// 在序列 [first, last) 中搜索 searcher 构造函数中指定的模式。等效地执行
// return searcher(first, last).first;
template<class ForwardIt, class Searcher>
constexpr ForwardIt search( ForwardIt first, ForwardIt last,
const Searcher& searcher );
测试用例
int main()
{
string str = { "It was Christmas Eve, a cold dark evening."
"There was coming a little poor girl."
"She was so cold and hungry."
"But she had to stay on the street."
"She had to sell the matches." }; // string
// search
string sub = "a little poor girl";
auto res = search(str.begin(), str.end(), sub.begin(),sub.end()); // 查找
if (res != str.end()) // 输出该句及其之后的内容
{
int start = distance(str.begin(), res);
int end = distance(res, str.end());
cout << str.substr(start, end) << endl;
}
return 0;
}