STL算法之find查找算法 · STL源碼剖析

### 前言 ? 由于在前文的《[STL算法剖析](http://blog.csdn.net/chenhanzhun/article/details/39698523)》中，源碼剖析非常多，不方便學習，也不方便以后復習，這里把這些算法進行歸類，對他們單獨的源碼剖析進行講解。本文介紹的STL算法中的find、search查找算法。在STL源碼中有關算法的函數大部分在本文介紹，包含findand find_if、adjacent_find、search、search_n、lower_bound、upper_bound、equal_range、binary_search、find_first_of、find_end相關算法，下面對這些算法的源碼進行了詳細的剖析，并且適當給出應用例子，增加我們對其理解，方便我們使用這些算法。具體詳見下面源碼剖析。 ### 查找算法源碼剖析 ~~~ // find and find_if. //查找區間[first,last)內元素第一個與value值相等的元素，并返回其位置 //其中find函數是采用默認的equality操作operator== //find_if是采用用戶自行指定的操作pred //若find函數萃取出來的迭代器類型為輸入迭代器input_iterator_tag，則調用此函數 template <class _InputIter, class _Tp> inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val, input_iterator_tag) {//若尚未到達區間的尾端，且未找到匹配的值，則繼續查找 while (__first != __last && !(*__first == __val)) ++__first; //若找到匹配的值，則返回該位置 //若找不到，即到達區間尾端，此時first=last，則返回first return __first; } //若find_if函數萃取出來的迭代器類型為輸入迭代器input_iterator_tag，則調用此函數 template <class _InputIter, class _Predicate> inline _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred, input_iterator_tag) {//若尚未到達區間的尾端，且未找到匹配的值，則繼續查找 while (__first != __last && !__pred(*__first)) ++__first; //若找到匹配的值，則返回該位置 //若找不到，即到達區間尾端，此時first=last，則返回first return __first; } #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION //若find函數萃取出來的迭代器類型為隨機訪問迭代器random_access_iterator_tag，則調用此函數 template <class _RandomAccessIter, class _Tp> _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last, const _Tp& __val, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2; for ( ; __trip_count > 0 ; --__trip_count) { if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; } switch(__last - __first) { case 3: if (*__first == __val) return __first; ++__first; case 2: if (*__first == __val) return __first; ++__first; case 1: if (*__first == __val) return __first; ++__first; case 0: default: return __last; } } //若find_if函數萃取出來的迭代器類型為隨機訪問迭代器random_access_iterator_tag，則調用此函數 template <class _RandomAccessIter, class _Predicate> _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last, _Predicate __pred, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2; for ( ; __trip_count > 0 ; --__trip_count) { if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; } switch(__last - __first) { case 3: if (__pred(*__first)) return __first; ++__first; case 2: if (__pred(*__first)) return __first; ++__first; case 1: if (__pred(*__first)) return __first; ++__first; case 0: default: return __last; } } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ /*find函數功能：Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last. find函數原型： template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val); */ //find函數對外接口 template <class _InputIter, class _Tp> inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_InputIter>::value_type, _Tp); //首先萃取出first迭代器的類型，根據迭代器的類型調用不同的函數 return find(__first, __last, __val, __ITERATOR_CATEGORY(__first)); } /*find_if函數功能：Returns an iterator to the first element in the range [first,last) for which pred returns true. If no such element is found, the function returns last. find_if函數原型： template <class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred); */ //find_if 函數對外接口 template <class _InputIter, class _Predicate> inline _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_InputIter>::value_type); //首先萃取出first迭代器的類型，根據迭代器的類型調用不同的函數 return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); } //find和find_if函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::find_if #include <vector> // std::vector bool IsOdd (int i) { return ((i%2)==1); } int main () { std::vector<int> myvector; myvector.push_back(10); myvector.push_back(25); myvector.push_back(40); myvector.push_back(55); std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd); std::cout << "The first odd value is " << *it << '\n'; // using std::find with vector and iterator: it = find (myvector.begin(), myvector.end(), 40); if (it != myvector.end()) std::cout << "Element found in myvector: " << *it << '\n'; else std::cout << "Element not found in myints\n"; return 0; } Output: The first odd value is 25 Element found in myvector: 40 */ // adjacent_find. //查找區間[first,last)內第一次重復的相鄰元素 //若存在返回相鄰元素的第一個元素位置 //若不存在返回last位置 /*該函數有兩個版本：第一版本是默認操作operator==；第二版本是用戶指定的二元操作pred 函數對外接口的原型： equality (1)：默認操作是operator== template <class ForwardIterator> ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last); predicate (2)：用戶指定的二元操作pred template <class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate pred); */ //版本一：默認操作是operator== template <class _ForwardIter> _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _EqualityComparable); /* 情況1：若輸入區間為空，則直接返回尾端last；情況2：若輸入區間不為空，且存在相鄰重復元素，則返回相鄰元素的第一個元素的位置；情況3：若輸入區間不為空，但是不存在相鄰重復元素，則直接返回尾端last； */ //情況1： if (__first == __last)//若輸入區間為空 return __last;//直接返回last //情況2： _ForwardIter __next = __first;//定義當前位置的下一個位置(即當前元素的相鄰元素) while(++__next != __last) {//若還沒到達尾端，執行while循環 if (*__first == *__next)//相鄰元素值相等，則找到相鄰重復元素 return __first;//返回第一個元素的位置 __first = __next;//若暫時找不到，則繼續找，直到到達區間尾端 } //情況3： return __last;//直接返回尾端last } //版本二：用戶指定的二元操作pred //實現過程和版本一一樣，只是判斷規則不同 template <class _ForwardIter, class _BinaryPredicate> _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, _BinaryPredicate __binary_pred) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __last; _ForwardIter __next = __first; while(++__next != __last) { //如果找到相鄰元素符合用戶指定條件，就返回第一元素位置 if (__binary_pred(*__first, *__next)) return __first; __first = __next; } return __last; } //adjacent_find函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::adjacent_find #include <vector> // std::vector bool myfunction (int i, int j) { return (i==j); } int main () { int myints[] = {5,20,5,30,30,20,10,10,20}; std::vector<int> myvector (myints,myints+8); std::vector<int>::iterator it; // using default comparison: it = std::adjacent_find (myvector.begin(), myvector.end()); if (it!=myvector.end()) std::cout << "the first pair of repeated elements are: " << *it << '\n'; //using predicate comparison: it = std::adjacent_find (++it, myvector.end(), myfunction); if (it!=myvector.end()) std::cout << "the second pair of repeated elements are: " << *it << '\n'; return 0; } Output: the first pair of repeated elements are: 30 the second pair of repeated elements are: 10 */ // search. //在序列一[first1,last1)所涵蓋的區間中，查找序列二[first2,last2)的首次出現點 //該查找函數有兩個版本： //版本一：使用默認的equality操作operator== //版本二：用戶根據需要自行指定操作規則 /*search函數功能：Searches the range [first1,last1) for the first occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found. search函數的原型： equality (1)：版本一 template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); predicate (2)：版本二 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); */ //版本一：使用默認的equality操作operator== template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { __STL_REQUIRES(_ForwardIter1, _ForwardIterator); __STL_REQUIRES(_ForwardIter2, _ForwardIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_ForwardIter1>::value_type, typename iterator_traits<_ForwardIter2>::value_type); // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; // Test for a pattern of length 1. _ForwardIter2 __tmp(__first2); ++__tmp; if (__tmp == __last2) return find(__first1, __last1, *__first2); // General case. _ForwardIter2 __p1, __p; __p1 = __first2; ++__p1; _ForwardIter1 __current = __first1; while (__first1 != __last1) {//若還沒到達區間尾端 __first1 = find(__first1, __last1, *__first2);//查找*first2在區間[first1,last1)首次出現的位置 if (__first1 == __last1)//若在[first1,last1)中不存在*first2，即在[first1,last1)不存在子序列[first2,last2) return __last1;//則直接返回區間尾端 __p = __p1; __current = __first1; if (++__current == __last1)//若[first1,last1)只有一個元素，即序列[first1,last1)小于序列[first2,last2) return __last1;//不可能成為其子序列，返回last1 while (*__current == *__p) {//若兩個序列相對應的值相同 if (++__p == __last2)//若序列[first2,last2)只有兩個元素，且與序列一匹配 return __first1;//則返回匹配的首次位置 if (++__current == __last1)//若第一個序列小于第二個序列 return __last1;//返回last1 } ++__first1; } return __first1; } //版本二：用戶根據需要自行指定操作規則 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __predicate) { __STL_REQUIRES(_ForwardIter1, _ForwardIterator); __STL_REQUIRES(_ForwardIter2, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, typename iterator_traits<_ForwardIter1>::value_type, typename iterator_traits<_ForwardIter2>::value_type); // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; // Test for a pattern of length 1. _ForwardIter2 __tmp(__first2); ++__tmp; if (__tmp == __last2) { while (__first1 != __last1 && !__predicate(*__first1, *__first2)) ++__first1; return __first1; } // General case. _ForwardIter2 __p1, __p; __p1 = __first2; ++__p1; _ForwardIter1 __current = __first1; while (__first1 != __last1) { while (__first1 != __last1) { if (__predicate(*__first1, *__first2)) break; ++__first1; } while (__first1 != __last1 && !__predicate(*__first1, *__first2)) ++__first1; if (__first1 == __last1) return __last1; __p = __p1; __current = __first1; if (++__current == __last1) return __last1; while (__predicate(*__current, *__p)) { if (++__p == __last2) return __first1; if (++__current == __last1) return __last1; } ++__first1; } return __first1; } // search_n. Search for __count consecutive copies of __val. //在序列[first,last)查找連續count個符合條件值value元素的位置 //該查找函數有兩個版本： //版本一：使用默認的equality操作operator== //版本二：用戶根據需要自行指定操作規則 /*search_n函數功能：Searches the range [first,last) for a sequence of count elements, each comparing equal to val (or for which pred returns true). search_n函數的原型： equality (1)：版本一 template <class ForwardIterator, class Size, class T> ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& val); predicate (2)：版本二 template <class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator search_n ( ForwardIterator first, ForwardIterator last, Size count, const T& val, BinaryPredicate pred ); */ //版本一：使用默認的equality操作operator== template <class _ForwardIter, class _Integer, class _Tp> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _EqualityComparable); __STL_REQUIRES(_Tp, _EqualityComparable); if (__count <= 0) return __first; else {//首先查找value第一次出現的位置 __first = find(__first, __last, __val); while (__first != __last) {//若出現的位置不是區間尾端 _Integer __n = __count - 1;//更新個數，下面只需查找n=count-1個連續相同value即可 _ForwardIter __i = __first; ++__i;//從當前位置的下一個位置開始查找 //若沒有到達區間尾端，且個數n大于0，且區間元素與value值相等 while (__i != __last && __n != 0 && *__i == __val) { ++__i;//繼續查找 --__n;//減少查找的次數，因為已經找到value再次出現 } if (__n == 0)//若區間尚未到達尾端，但是count個value已經查找到 return __first;//則輸出查找到的首次出現value的位置 else __first = find(__i, __last, __val);//若尚未找到連續count個value值的位置，則找出value下次出現的位置，并準備下一次while循環 } return __last; } } //版本二：用戶根據需要自行指定操作規則 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val, _BinaryPred __binary_pred) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, typename iterator_traits<_ForwardIter>::value_type, _Tp); if (__count <= 0) return __first; else { while (__first != __last) { if (__binary_pred(*__first, __val)) break; ++__first; } while (__first != __last) { _Integer __n = __count - 1; _ForwardIter __i = __first; ++__i; while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { ++__i; --__n; } if (__n == 0) return __first; else { while (__i != __last) { if (__binary_pred(*__i, __val)) break; ++__i; } __first = __i; } } return __last; } } //search和search_n函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::search_n #include <vector> // std::vector bool mypredicate (int i, int j) { return (i==j); } int main () { int myints[]={10,20,30,30,20,10,10,20}; std::vector<int> myvector (myints,myints+8); std::vector<int>::iterator it; // using default comparison: it = std::search_n (myvector.begin(), myvector.end(), 2, 30); if (it!=myvector.end()) std::cout << "two 30s found at position " << (it-myvector.begin()) << '\n'; else std::cout << "match not found\n"; // using predicate comparison: it = std::search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate); if (it!=myvector.end()) std::cout << "two 10s found at position " << int(it-myvector.begin()) << '\n'; else std::cout << "match not found\n"; int needle1[] = {10,20}; // using default comparison: it = std::search (myvector.begin(), myvector.end(), needle1, needle1+2); if (it!=myvector.end()) std::cout << "needle1 found at position " << (it-myvector.begin()) << '\n'; else std::cout << "needle1 not found\n"; // using predicate comparison: int needle2[] = {30,20,10}; it = std::search (myvector.begin(), myvector.end(), needle2, needle2+3, mypredicate); if (it!=myvector.end()) std::cout << "needle2 found at position " << (it-myvector.begin()) << '\n'; else std::cout << "needle2 not found\n"; return 0; } Output: two 30s found at position 2 two 10s found at position 5 needle1 found at position 0 needle2 found at position 3 */ // Binary search (lower_bound, upper_bound, equal_range, binary_search). template <class _ForwardIter, class _Tp, class _Distance> _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*) { _Distance __len = 0; distance(__first, __last, __len);//求取整個區間的長度len _Distance __half; _ForwardIter __middle;//定義區間的中間迭代器 while (__len > 0) {//若區間不為空，則在區間[first,last)開始查找value值 __half = __len >> 1;//向右移一位，相當于除以2，即取區間的中間值 __middle = __first;//middle初始化為區間的起始位置 advance(__middle, __half);//middle向后移half位，此時middle為區間的中間值 if (*__middle < __val) {//將value值與中間值比較，即是二分查找,若中間值小于value，則繼續查找右半部分 //下面兩行令first指向middle的下一個位置 __first = __middle; ++__first; __len = __len - __half - 1;//調整查找區間的長度 } else __len = __half;//否則查找左半部分 } return __first; } //在已排序區間[first,last)查找value值 //若該區間存在與value相等的元素，則返回指向第一個與value相等的迭代器 //若該區間不存在與value相等的元素，則返回指向第一個不小于value值的迭代器 //若該區間的任何元素都比value值小，則返回last /* 函數功能：Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val. 函數原型： default (1) ：版本一采用operator<比較 template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); custom (2) ：版本二采用仿函數comp比較規則 template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); */ //版本一 template <class _ForwardIter, class _Tp> inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_REQUIRES(_Tp, _LessThanComparable); return __lower_bound(__first, __last, __val, __DISTANCE_TYPE(__first)); } template <class _ForwardIter, class _Tp, class _Compare, class _Distance> _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp, _Distance*) { _Distance __len = 0; distance(__first, __last, __len);//求取整個區間的長度len _Distance __half; _ForwardIter __middle;//定義區間的中間迭代器 while (__len > 0) {//若區間不為空，則在區間[first,last)開始查找value值 __half = __len >> 1;//向右移一位，相當于除以2，即取區間的中間值 __middle = __first;//middle初始化為區間的起始位置 advance(__middle, __half);//middle向后移half位，此時middle為區間的中間值 if (__comp(*__middle, __val)) {//若comp判斷為true，則繼續在右半部分查找 //下面兩行令first指向middle的下一個位置 __first = __middle; ++__first; __len = __len - __half - 1;//調整查找區間的長度 } else __len = __half;//否則查找左半部分 } return __first; } //版本二： template <class _ForwardIter, class _Tp, class _Compare> inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); return __lower_bound(__first, __last, __val, __comp, __DISTANCE_TYPE(__first)); } template <class _ForwardIter, class _Tp, class _Distance> _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*) { _Distance __len = 0; distance(__first, __last, __len);//求取整個區間的長度len _Distance __half; _ForwardIter __middle;//定義區間的中間迭代器 while (__len > 0) {//若區間不為空，則在區間[first,last)開始查找value值 __half = __len >> 1;//向右移一位，相當于除以2，即取區間的中間值 __middle = __first;//middle初始化為區間的起始位置 advance(__middle, __half);//middle向后移half位，此時middle為區間的中間值 if (__val < *__middle)//若value小于中間元素值 __len = __half;//查找左半部分 else { //下面兩行令first指向middle的下一個位置 __first = __middle; ++__first; __len = __len - __half - 1;//更新len的值 } } return __first; } //在已排序區間[first,last)查找value值 //返回大于value值的第一個元素的迭代器 /* 函數功能：Returns an iterator pointing to the first element in the range [first,last) which compares greater than val. 函數原型： default (1) ：版本一采用operator<比較 template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val); custom (2) ：版本二采用仿函數comp比較規則 template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); */ //版本一 template <class _ForwardIter, class _Tp> inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_REQUIRES(_Tp, _LessThanComparable); return __upper_bound(__first, __last, __val, __DISTANCE_TYPE(__first)); } template <class _ForwardIter, class _Tp, class _Compare, class _Distance> _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp, _Distance*) { _Distance __len = 0; distance(__first, __last, __len); _Distance __half; _ForwardIter __middle; while (__len > 0) { __half = __len >> 1; __middle = __first; advance(__middle, __half); if (__comp(__val, *__middle)) __len = __half; else { __first = __middle; ++__first; __len = __len - __half - 1; } } return __first; } //版本二 template <class _ForwardIter, class _Tp, class _Compare> inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); return __upper_bound(__first, __last, __val, __comp, __DISTANCE_TYPE(__first)); } //函數舉例 /* #include <iostream> // std::cout #include <algorithm> // std::lower_bound, std::upper_bound, std::sort #include <vector> // std::vector int main () { int myints[] = {10,20,30,30,20,10,10,20}; std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 std::vector<int>::iterator low,up; low=std::lower_bound (v.begin(), v.end(), 20); // ^ up= std::upper_bound (v.begin(), v.end(), 20); // ^ std::cout << "lower_bound at position " << (low- v.begin()) << '\n'; std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; return 0; } Output: lower_bound at position 3 upper_bound at position 6 */ template <class _ForwardIter, class _Tp, class _Distance> pair<_ForwardIter, _ForwardIter> __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*) { _Distance __len = 0; distance(__first, __last, __len);//計算區間的長度len _Distance __half; _ForwardIter __middle, __left, __right; while (__len > 0) {//若區間非空 __half = __len >> 1;//len右移一位，相等于除以2，即half為區間的長度的一半 __middle = __first;//初始化middle的值 advance(__middle, __half);//前進middle位置，使其指向區間中間位置 if (*__middle < __val) {//若指定元素value大于中間元素值，則在右半部分繼續查找 //下面兩行使first指向middle的下一個位置，即右半區間的起始位置 __first = __middle; ++__first; __len = __len - __half - 1;//更新待查找區間的長度 } else if (__val < *__middle)//若指定元素value小于中間元素值，則在左半部分繼續查找 __len = __half;//更新待查找區間的長度 else {//若指定元素value等于中間元素值 //在前半部分找lower_bound位置 __left = lower_bound(__first, __middle, __val); advance(__first, __len); //在后半部分找upper_bound __right = upper_bound(++__middle, __first, __val); return pair<_ForwardIter, _ForwardIter>(__left, __right);//返回pair對象，第一個迭代器為left，第二個迭代器為right } } return pair<_ForwardIter, _ForwardIter>(__first, __first); } //查找區間與value相等的相鄰重復元素的起始位置和結束位置 //注意：[first,last)是已排序，思想還是采用二分查找法 //同樣也有兩個版本 /* 函數功能：Returns the bounds of the subrange that includes all the elements of the range [first,last) with values equivalent to val. 函數原型： default (1) ：版本一默認operator< template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val); custom (2) ：版本二采用仿函數comp template <class ForwardIterator, class T, class Compare> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); */ //版本一 template <class _ForwardIter, class _Tp> inline pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_REQUIRES(_Tp, _LessThanComparable); return __equal_range(__first, __last, __val, __DISTANCE_TYPE(__first)); } template <class _ForwardIter, class _Tp, class _Compare, class _Distance> pair<_ForwardIter, _ForwardIter> __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp, _Distance*) { _Distance __len = 0; distance(__first, __last, __len); _Distance __half; _ForwardIter __middle, __left, __right; while (__len > 0) { __half = __len >> 1; __middle = __first; advance(__middle, __half); if (__comp(*__middle, __val)) { __first = __middle; ++__first; __len = __len - __half - 1; } else if (__comp(__val, *__middle)) __len = __half; else { __left = lower_bound(__first, __middle, __val, __comp); advance(__first, __len); __right = upper_bound(++__middle, __first, __val, __comp); return pair<_ForwardIter, _ForwardIter>(__left, __right); } } return pair<_ForwardIter, _ForwardIter>(__first, __first); } //版本二 template <class _ForwardIter, class _Tp, class _Compare> inline pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); return __equal_range(__first, __last, __val, __comp, __DISTANCE_TYPE(__first)); } //equal_range函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::equal_range, std::sort #include <vector> // std::vector bool mygreater (int i,int j) { return (i>j); } int main () { int myints[] = {10,20,30,30,20,10,10,20}; std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds; // using default comparison: std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 bounds=std::equal_range (v.begin(), v.end(), 20); // ^ ^ std::cout << "bounds at positions " << (bounds.first - v.begin()); std::cout << " and " << (bounds.second - v.begin()) << '\n'; // using "mygreater" as comp: std::sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10 bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); // ^ ^ std::cout << "bounds at positions " << (bounds.first - v.begin()); std::cout << " and " << (bounds.second - v.begin()) << '\n'; return 0; } Output： bounds at positions 3 and 6 bounds at positions 2 and 5 */ //二分查找法 //注意：[first,last)是已排序 //同樣也有兩個版本 /* 函數功能：Returns true if any element in the range [first,last) is equivalent to val, and false otherwise. 函數原型： default (1) ：版本一默認operator< template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val); custom (2) ：版本二采用仿函數comp template <class ForwardIterator, class T, class Compare> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); */ template <class _ForwardIter, class _Tp> bool binary_search(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_REQUIRES(_Tp, _LessThanComparable); _ForwardIter __i = lower_bound(__first, __last, __val);//調用二分查找函數，并返回不小于value值的第一個迭代器位置i return __i != __last && !(__val < *__i); } template <class _ForwardIter, class _Tp, class _Compare> bool binary_search(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_SAME_TYPE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); _ForwardIter __i = lower_bound(__first, __last, __val, __comp);//調用二分查找函數，并返回不小于value值的第一個迭代器位置i return __i != __last && !__comp(__val, *__i); } // find_first_of, with and without an explicitly supplied comparison function. //以[first2,last2)區間內的某些元素為查找目標，尋找他們在[first1,last1)區間首次出現的位置 //find_first_of函數有兩個版本： //版本一：提供默認的equality操作operator== //版本二：提供用戶自行指定的操作規則comp /* 函數功能：Returns an iterator to the first element in the range [first1,last1) that matches any of the elements in [first2,last2). If no such element is found, the function returns last1. 函數原型： equality (1)：版本一 template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); predicate (2)：版本二 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); */ //版本一：提供默認的equality操作operator== template <class _InputIter, class _ForwardIter> _InputIter find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_InputIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); for ( ; __first1 != __last1; ++__first1) //若序列一不為空，則遍歷序列一，每次指定一個元素 //以下，根據序列二的每個元素 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) if (*__first1 == *__iter)//若序列一的元素等于序列二的元素，則表示找到 return __first1;//返回找到的位置 return __last1;//否則沒找到 } //版本二：提供用戶自行指定的操作規則comp template <class _InputIter, class _ForwardIter, class _BinaryPredicate> _InputIter find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_InputIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); for ( ; __first1 != __last1; ++__first1) for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) if (__comp(*__first1, *__iter)) return __first1; return __last1; } //find_first_of函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::find_first_of #include <vector> // std::vector #include <cctype> // std::tolower bool comp_case_insensitive (char c1, char c2) { return (std::tolower(c1)==std::tolower(c2)); } int main () { int mychars[] = {'a','b','c','A','B','C'}; std::vector<char> haystack (mychars,mychars+6); std::vector<char>::iterator it; int needle[] = {'A','B','C'}; // using default comparison: it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3); if (it!=haystack.end()) std::cout << "The first match is: " << *it << '\n'; // using predicate comparison: it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3, comp_case_insensitive); if (it!=haystack.end()) std::cout << "The first match is: " << *it << '\n'; return 0; } Output: The first match is: A The first match is: a */ // find_end, with and without an explicitly supplied comparison function. // Search [first2, last2) as a subsequence in [first1, last1), and return // the *last* possible match. Note that find_end for bidirectional iterators // is much faster than for forward iterators. // find_end for forward iterators. //若萃取出來的迭代器類型為正向迭代器forward_iterator_tag，則調用此函數 template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, forward_iterator_tag, forward_iterator_tag) { if (__first2 == __last2)//若第二個區間為空 return __last1;//則直接返回第一個區間的尾端 else { _ForwardIter1 __result = __last1; while (1) { //以下利用search函數查找出某個子序列的首次出現點；若找不到直接返回last1 _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2); if (__new_result == __last1)//若返回的位置為尾端，則表示沒找到 return __result;//返回last1 else {//若在[first1,last1)中找到[first2,last2)首次出現的位置，繼續準備下一次查找 __result = __new_result;//更新返回的位置 __first1 = __new_result;//更新查找的起始位置 ++__first1;//確定正確查找起始位置 } } } } //版本二：指定規則 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPredicate> _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, forward_iterator_tag, forward_iterator_tag, _BinaryPredicate __comp) { if (__first2 == __last2) return __last1; else { _ForwardIter1 __result = __last1; while (1) { _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp); if (__new_result == __last1) return __result; else { __result = __new_result; __first1 = __new_result; ++__first1; } } } } // find_end for bidirectional iterators. Requires partial specialization. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION //若萃取出來的迭代器類型為雙向迭代器bidirectional_iterator_tag，則調用此函數 template <class _BidirectionalIter1, class _BidirectionalIter2> _BidirectionalIter1 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag) { __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator); __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator); //利用反向迭代器很快就可以找到 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; _RevIter1 __rlast1(__first1); _RevIter2 __rlast2(__first2); //查找時將序列一和序列二逆方向 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, _RevIter2(__last2), __rlast2); if (__rresult == __rlast1)//表示沒找到 return __last1; else {//找到了 _BidirectionalIter1 __result = __rresult.base();//轉會正常迭代器 advance(__result, -distance(__first2, __last2));//調整回到子序列的起始位置 return __result; } } //版本二：指定規則comp template <class _BidirectionalIter1, class _BidirectionalIter2, class _BinaryPredicate> _BidirectionalIter1 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag, _BinaryPredicate __comp) { __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator); __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator); typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; _RevIter1 __rlast1(__first1); _RevIter2 __rlast2(__first2); _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, _RevIter2(__last2), __rlast2, __comp); if (__rresult == __rlast1) return __last1; else { _BidirectionalIter1 __result = __rresult.base(); advance(__result, -distance(__first2, __last2)); return __result; } } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // Dispatching functions for find_end. //find_end函數有兩個版本： //版本一：提供默認的equality操作operator== //版本二：提供用戶自行指定的操作規則comp //注意：這里也有偏特化的知識 /*函數功能：Searches the range [first1,last1) for the last occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found. 函數原型： equality (1)：版本一 template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); predicate (2)：版本二 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); */ //對外接口的版本一 template <class _ForwardIter1, class _ForwardIter2> inline _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { __STL_REQUIRES(_ForwardIter1, _ForwardIterator); __STL_REQUIRES(_ForwardIter2, _ForwardIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_ForwardIter1>::value_type, typename iterator_traits<_ForwardIter2>::value_type); //首先通過iterator_traits萃取出first1和first2的迭代器類型 //根據不同的迭代器類型調用不同的函數 return __find_end(__first1, __last1, __first2, __last2, __ITERATOR_CATEGORY(__first1), __ITERATOR_CATEGORY(__first2)); } //對外接口的版本一 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPredicate> inline _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPredicate __comp) { __STL_REQUIRES(_ForwardIter1, _ForwardIterator); __STL_REQUIRES(_ForwardIter2, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_ForwardIter1>::value_type, typename iterator_traits<_ForwardIter2>::value_type); //首先通過iterator_traits萃取出first1和first2的迭代器類型 //根據不同的迭代器類型調用不同的函數 return __find_end(__first1, __last1, __first2, __last2, __ITERATOR_CATEGORY(__first1), __ITERATOR_CATEGORY(__first2), __comp); } //find_end函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::find_end #include <vector> // std::vector bool myfunction (int i, int j) { return (i==j); } int main () { int myints[] = {1,2,3,4,5,1,2,3,4,5}; std::vector<int> haystack (myints,myints+10); int needle1[] = {1,2,3}; // using default comparison: std::vector<int>::iterator it; it = std::find_end (haystack.begin(), haystack.end(), needle1, needle1+3); if (it!=haystack.end()) std::cout << "needle1 last found at position " << (it-haystack.begin()) << '\n'; int needle2[] = {4,5,1}; // using predicate comparison: it = std::find_end (haystack.begin(), haystack.end(), needle2, needle2+3, myfunction); if (it!=haystack.end()) std::cout << "needle2 last found at position " << (it-haystack.begin()) << '\n'; return 0; } Output: needle1 found at position 5 needle2 found at position 3 */ ~~~ 參考資料：《STL源碼剖析》侯捷