C++ STL算法系列2---find ,find_first_of , find_if , adjacent_find的使用

一.find运算

假设有一个int型的vector对象,名为vec,我们想知道其中是否包含某个特定值

解决这个问题最简单的方法时使用标准库提供的find运算:

 1 // value we'll look for
 2 int search_value = 42;
 3 
 4 //call find to see if that value is present
 5 vector<int>::const_iterator result = find(vec.begin() , vec.end() , search_value);
 6 
 7 //report the result
 8 cout<<"The value "<<search_value
 9 <<(result == vec.end() ? " is not present" : "is present")
10 <<endl;

具体实现代码:

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8 // value we'll look for
 9    int search_value = 42;
10    int ival;
11    vector<int> vec;
12 
13    while(cin>>ival)
14       vec.push_back(ival);
15    
16    cin.clear();
17 
18 //call find to see if that value is present
19    vector<int>::const_iterator result = find(vec.begin() , vec.end() , search_value);
20 
21 //report the result
22   cout<<"The value "<<search_value
23       <<(result == vec.end() ? " is not present" : "is present")
24       <<endl;
25 
26   return 0;
27 }

 接下来再举一个例子:

 1 #include <algorithm>  
 2 #include <list>  
 3 #include <iostream>  
 4   
 5 using namespace std;  
 6   
 7 int main()  
 8 {  
 9     list<int> ilist;  
10     for (size_t i = 0; i < 10; ++i)  
11     {  
12         ilist.push_back(i+1);  
13     }  
14   
15     ilist.push_back(10);  
16   
17     list<int>::iterator iLocation = find(ilist.begin(), ilist.end(), 10);   //find操作查找等于10的元素,并返回指向该元素的迭代器,如果没有找到,返回指向集合最后一个元素的迭代器
18   
19     if (iLocation != ilist.end())  
20     {  
21         cout << "找到元素 10" << endl;  
22     }  
23   
24     cout << "前一个元素为:" << *(--iLocation) << endl;  
25   
26     return 0;  
27 }  

类似地,由于指针的行为与作用在内置数组上的迭代器一样,因此也可以使用find来搜索数组:

1 int ia[6] = {27 , 210 , 12 , 47 , 109 , 83};
2 int search_value = 83;
3 int *result = find(ia , ia + 6 , search_value);
4 cout<<"The value "<<search_value
5     <<(result == ia + 6 ? " is not present" : "is present")
6     <<endl;

如果需要传递一个子区间,则传递指向这个子区间的第一个元素以及最后一个元素的下一位置的迭代器(或指针)。

例如,在下面对find函数的调用中,只搜索了ia[1]和ia[2]:

//only search elements ia[1] and ia[2]
int *result = find(ia + 1 , ia + 3 , search_value);

二.find_first_of的使用

除了find之外,标准库还定义了其他一些更复杂的查找算法。当中的一部分类似string类的find操作,其中一个是find_first_of函数。

这个算法带有两对迭代器参数来标记两端元素范围:第一段范围内查找与第二段范围中任意元素匹配的元素,然后返回一个迭代器,指向第一个匹配的元素。如果找不到匹配元素,则返回第一个范围的end迭代器。

假设roster1和roster2是两个存放名字的list对象,可使用find_first_of统计有多少个名字同时出现在这两个列表中

 1 size_t cnt = 0;
 2 list<string>::iterator it = roster1.begin();
 3 
 4 // look in roster1 for any name also in roster2
 5 while((it = find_first_of(it , roster1.end() , roster2.begin() , roster2.end())) != roster1.end())
 6 {
 7     ++cnt;
 8     // we got a match , increment it to look in the rest of roster1
 9     ++it;
10 }
11 cout<<"Found "<<cnt
12     <<"  names on both rosters "<<endl;

调 用find_first_of查找roster2中的每个元素是否与第一个范围内的元素匹配,也就是在it到roster1.end()范围内查找一个元 素。该函数返回此范围内第一个同时存在于第二个范围中的元素。在while的第一次循环中,遍历整个roster1范围。第二次以及后续的循环迭代则只考 虑roster1中尚未匹配的部分。

循环条件检查find_first_of的返回值,判断是否找到匹配的名字。如果找到一个匹配,则使计 数器加1,同时给it加1,使它指向roster1中的下一个元素。很明显可知,当不再有任何匹配时,find_first_of返回 roster1.end(),完成统计。

find_first_of,带有两对迭代器参数。每对迭代器中,两个参数的类型必须精确匹配,但不要求两对之间的类型匹配。特别是,元素可存储在不同类型的序列中,只要这两个序列的元素可以比较即可。

在 上述程序中,roster1和roster2的类型不必精确匹配:roster1可以使list对象,而roster2则可以使vector对象、 deque对象或者是其他后面要学到的序列。只要这两个序列的的元素可使用相等(==)操作符进行比较即可。如果roster1是list< string>对象,则roster2可以使vector<char*>对象,因为string标准库为string对象与char* 对象定义了相等(==)操作符。

三.find_if的使用

find_if算法 是find的一个谓词判断版本,它利用返回布尔值的谓词判断pred,检查迭代器区间[first, last)上的每一个元素,如果迭代器iter满足pred(*iter) == true,表示找到元素并返回迭代器值iter;未找到元素,则返回last。

find_if :在序列中找符合某谓词的第一个元素。

函数原型为:

1     template<class InputIterator, class Predicate>  
2        InputIterator find_if(  
3           InputIterator _First,   
4           InputIterator _Last,   
5           Predicate _Pred  
6        );  

举个例子说明如下:

 1 #include <algorithm>  
 2 #include <vector>  
 3 #include <iostream>  
 4   
 5 using namespace std;  
 6   
 7 //谓词判断函数 divbyfive : 判断x是否能5整除  
 8 bool divbyfive(int x)  
 9 {  
10     return x % 5 ? 0 : 1;  
11 }  
12   
13 int main()  
14 {  
15   /*  
16     //初始vector : 方式一 
17     //使用下标方式来操作vector
18     //vector随机访问方便,但插入、删除操作效率非常低
19     vector<int> iVect(20);  
20 
21     for(size_t i = 0; i < iVect.size(); ++i)   //注意:size_t
22     {  
23         iVect[i] = (i+1) * (i+3);  
24     }  
25 
26 */
27     //初始vector :方式二
28     vector<int> iVect;
29     for(vector<int>::size_type i = 0 ; i != 20 ; ++i)
30         iVect.push_back((i+1) * (i + 3));
31      
32 
33     //输出vector里的元素
34     for(vector<int>::iterator iter = iVect.begin() ; iter != iVect.end() ; ++iter)
35         cout<<*iter<<" ";
36     cout<<endl;
37   
38   
39     vector<int>::iterator iLocation;  
40     iLocation = find_if(iVect.begin(), iVect.end(), divbyfive);  
41   
42     if (iLocation != iVect.end())  
43     {  
44         cout << "第一个能被5整除的元素为:"  
45              << *iLocation << endl                  //打印元素:15                 
46              << "元素的索引位置为:"  
47              << iLocation - iVect.begin() << endl;  //打印索引位置:2  
48     }  
49      
50     return 0;  
51 }  

四. adjacent_find算法

adjacent_find算法用于查找相等或满足条件的邻近元素对。其有两种函数原型:一种在迭代器区间[first , last)上查找两个连续的元素相等时,返回元素对中第一个元素的迭代器位置。另一种是使用二元谓词判断binary_pred,查找迭代器区间 [first , last)上满足binary_pred条件的邻近元素对,未找到则返回last。

原型:

 1 <strong>template<class ForwardIterator>  
 2    ForwardIterator adjacent_find(  
 3       ForwardIterator _First,   
 4       ForwardIterator _Last  
 5       );  
 6 template<class ForwardIterator , class BinaryPredicate>  
 7    ForwardIterator adjacent_find(  
 8       ForwardIterator _First,   
 9       ForwardIterator _Last,   
10             BinaryPredicate _Comp  
11    );  
12 </strong> 

举例如下:

 1 #include <algorithm>  
 2 #include <list>  
 3 #include <iostream>  
 4   
 5 using namespace std;  
 6   
 7 //判断X和y是否奇偶同性  
 8 bool parity_equal(int x, int y)  
 9 {  
10     return (x - y) % 2 == 0 ? 1 : 0;  
11 }  
12   
13 int main()  
14 {  
15     //初始化链表  
16     list<int> iList;  
17     iList.push_back(3);  
18     iList.push_back(6);  
19     iList.push_back(9);  
20     iList.push_back(11);  
21     iList.push_back(11);  
22     iList.push_back(18);  
23     iList.push_back(20);  
24     iList.push_back(20);  
25   
26     //输出链表  
27     list<int>::iterator iter;  
28     for(iter = iList.begin(); iter != iList.end(); ++iter)  
29     {  
30         cout << *iter << "  ";  
31     }  
32     cout << endl;  
33       
34     //查找邻接相等的元素  
35     list<int>::iterator iResult = adjacent_find(iList.begin(), iList.end());  
36     if (iResult != iList.end())  
37     {  
38         cout << "链表中第一对相等的邻近元素为:" << endl;  
39         cout << *iResult++ << endl;  
40         cout << *iResult << endl;  
41     }  
42   
43     //查找奇偶性相同的邻近元素  
44     iResult = adjacent_find(iList.begin(), iList.end(), parity_equal);  
45     if (iResult != iList.end())  
46     {  
47         cout << "链表中第一对奇偶相同的元素为:" << endl;  
48         cout << *iResult++ << endl;  
49         cout << *iResult << endl;  
50     }  
51     return 0;  
52 }  

总结:

find()            :  在序列中找某个值的第一个出现

find_if()         :    在序列中符合某谓词的第一个元素

find_first_if     :    在两个序列中找匹配元素

adjacent_find     :    用于查找相等或满足条件的邻近元素对

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人分享

Scala第一章学习笔记

  面向对象编程是一种自顶向下的程序设计方法。用面向对象方法构造软件时,我们将代码以名词(对象)做切割,每个对象有某种形式的表示服(self/this)、行为(...

12320
来自专栏desperate633

LintCode 比较字符串题目分析代码

比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母

6410
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

52250
来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

211100
来自专栏androidBlog

笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

22910
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

16100
来自专栏LeetCode

LeetCode 738. Monotone Increasing Digits

这是我开始选择的方法,非常直白,但是直白简单的方法往往不是最佳的解法,提交到LeetCode上,给我抛出一个超时,可见效率有多低。首先写一个函数,判断一个数是否...

16300
来自专栏老马说编程

(54) 剖析Collections - 设计模式 / 计算机程序的思维逻辑

上节我们提到,类Collections中大概有两类功能,第一类是对容器接口对象进行操作,第二类是返回一个容器接口对象,上节我们介绍了第一类,本节我们介绍第二类。...

26890
来自专栏xx_Cc的学习总结专栏

iOS-正则表达式的简单使用

49870
来自专栏大神带我来搬砖

程序员的职业素养真是完全靠不住的东西

这里面<T extends Comparable<? super T>>有什么用?

6010

扫码关注云+社区

领取腾讯云代金券