STL算法 | 查找函数 find()、二分查找binary_search/upper_bound、子序列查找search

亦凉 2022-10-30 12:26 188阅读 0赞

### 文章目录 ###

*  一、find系列函数（单个元素顺序查找）
 *   *   *  1. find 搜索等于 value 的元素。
         *  2. find\_if 搜索谓词 p 对其返回 true 的元素
         *  3. find\_if\_not 搜索谓词 q 对其返回 false 的元素。
         *  测试用例
 *  一、二分查找系列函数（单个元素二分查找）
 *   *   *  1. lower\_bound 二分查找大于等于
         *  2. upper\_bound 二分查找大于
         *  3. equal\_range 二分查找等价区间
         *  4. binary\_search 二分查找是否存在元素value
         *  测试用例
 *  三、子序列查找 search
 *   *   *  1. 使用operator== 比较
         *  2. 用给定的二元谓词 p 比较
         *  3. 在序列 \[first, last) 中搜索 searcher 构造函数中指定的模式
         *  测试用例

参考：[执行策略：cppreference.com  
][cppreference.com]

--------------------

# 一、find系列函数（单个元素顺序查找） #

该算法提供范围内查找对象的算法，在<algorithm>头文件中定义。

指向首个满足条件的迭代器，或若找不到这种元素则为 last 。

参考自：《[https://zh.cppreference.com/w/cpp/algorithm/find][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][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;
    }

[cppreference.com]: https://zh.cppreference.com/w/cpp/algorithm/execution_policy_tag_t
[https_zh.cppreference.com_w_cpp_algorithm_find]: https://zh.cppreference.com/w/cpp/algorithm/find
[https_zh.cppreference.com_w_cpp_algorithm_search]: https://zh.cppreference.com/w/cpp/algorithm/search