一.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 : 用于查找相等或滿足條件的鄰近元素對