### 前言 ? 在前面的博文中剖析了STL的[數值算法](http://blog.csdn.net/chenhanzhun/article/details/39646237)、[基本算法](http://blog.csdn.net/chenhanzhun/article/details/39666289)和[set集合算法](http://blog.csdn.net/chenhanzhun/article/details/39669925)，本文剖析STL其他的算法，例如排序算法、合并算法、查找算法等等。在剖析的時候，會針對函數給出一些例子說明函數的使用。源碼出自SGI STL中的<stl_algo.h>文件。注：本文的源碼非常多，可能后續博文會對這些算法進行歸類分析。 ### STL算法剖析 ~~~ #ifndef __SGI_STL_INTERNAL_ALGO_H #define __SGI_STL_INTERNAL_ALGO_H #include <stl_heap.h>//這里包含堆的相關算法 //最大堆的相關算法已經介紹過了，有興趣詳見 //http://blog.csdn.net/chenhanzhun/article/details/39434491 // See concept_checks.h for the concept-checking macros // __STL_REQUIRES, __STL_CONVERTIBLE, etc. __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma set woff 1209 #endif // __median (an extension, not present in the C++ standard). //函數功能：取三個元素a，b，c的中間值 //版本一采用默認的operator<操作 template <class _Tp> inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { __STL_REQUIRES(_Tp, _LessThanComparable); if (__a < __b) if (__b < __c) return __b;//若a<b<c，則返回b else if (__a < __c) return __c;//若a<c<b，則返回c else return __a;//若c<a<b，則返回a else if (__a < __c) return __a;//若b<a<c，則返回a else if (__b < __c) return __c;//若b<c<a，則返回c else return __b;//否則返回b } //版本二采用仿函數comp比較 template <class _Tp, class _Compare> inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; else if (__comp(__a, __c)) return __c; else return __a; else if (__comp(__a, __c)) return __a; else if (__comp(__b, __c)) return __c; else return __b; } // for_each. Apply a function to every element of a range. //功能：Applies function fn to each of the elements in the range [first,last). //將仿函數f應用于[first,last)區間內的每一個元素上 //注：不能改變[first,last)內元素值 template <class _InputIter, class _Function> _Function for_each(_InputIter __first, _InputIter __last, _Function __f) { __STL_REQUIRES(_InputIter, _InputIterator); for ( ; __first != __last; ++__first) __f(*__first);//調用仿函數f return __f; } //for_each函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::for_each #include <vector> // std::vector void myfunction (int i) { // function: std::cout << ' ' << i; } struct myclass { // function object type: void operator() (int i) {std::cout << ' ' << i;} } myobject; int main () { std::vector<int> myvector; myvector.push_back(10); myvector.push_back(20); myvector.push_back(30); std::cout << "myvector contains:"; for_each (myvector.begin(), myvector.end(), myfunction); std::cout << '\n'; // or: std::cout << "myvector contains:"; for_each (myvector.begin(), myvector.end(), myobject); std::cout << '\n'; return 0; } Output: myvector contains: 10 20 30 myvector contains: 10 20 30 */ // 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 */ // count and count_if. There are two version of each, one whose return type // type is void and one (present only if we have partial specialization) // whose return type is iterator_traits<_InputIter>::difference_type. The // C++ standard only has the latter version, but the former, which was present // in the HP STL, is retained for backward compatibility. //計算指定元素的個數 //SGI STL中提供兩個版本，但是C++標準只提供一種版本 /*功能：Returns the number of elements in the range [first,last) that compare equal to val. C++標準只提供一種count原型： template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val); */ //SGI STL提供的版本一count，不是C++標準：默認使用operator== template <class _InputIter, class _Tp, class _Size> void count(_InputIter __first, _InputIter __last, const _Tp& __value, _Size& __n) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, _EqualityComparable); __STL_REQUIRES(_Tp, _EqualityComparable); //將區間[first,last)內的元素和指定值value比較 //若沒到達區間尾端，繼續查找 for ( ; __first != __last; ++__first) if (*__first == __value)//若存在相等的值 ++__n;//計數器累加1 } /*功能：Returns the number of elements in the range [first,last) for which pred is true. C++標準只提供一種count_if原型： template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, UnaryPredicate pred); */ //SGI STL提供的版本一count_if，不是C++標準：默認使用operator== template <class _InputIter, class _Predicate, class _Size> void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_InputIter>::value_type); //將區間[first,last)內的元素和指定值value比較 //若沒到達區間尾端，繼續查找 for ( ; __first != __last; ++__first) if (__pred(*__first))//存在符合規則的元素 ++__n;//計數器累加1 } #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION //SGI STL提供的版本二count，也C++標準提供的版本 template <class _InputIter, class _Tp> typename iterator_traits<_InputIter>::difference_type count(_InputIter __first, _InputIter __last, const _Tp& __value) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, _EqualityComparable); __STL_REQUIRES(_Tp, _EqualityComparable); typename iterator_traits<_InputIter>::difference_type __n = 0; //將區間[first,last)內的元素和指定值value比較 //若沒到達區間尾端，繼續查找 for ( ; __first != __last; ++__first) if (*__first == __value)//存在相等的元素 ++__n;//計數器累加1 return __n; } //SGI STL提供的版本二count_if，也C++標準提供的版本 template <class _InputIter, class _Predicate> typename iterator_traits<_InputIter>::difference_type count_if(_InputIter __first, _InputIter __last, _Predicate __pred) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_InputIter>::value_type); typename iterator_traits<_InputIter>::difference_type __n = 0; //將區間[first,last)內的元素和指定值value比較 //若沒到達區間尾端，繼續查找 for ( ; __first != __last; ++__first) if (__pred(*__first))//存在符合規則的元素 ++__n;//計數器累加1 return __n; } //下面針對count和count_if函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::count #include <vector> // std::vector bool IsOdd (int i) { return ((i%2)==1); } int main () { // counting elements in array: int myints[] = {10,20,31,30,21,10,11,20}; // 8 elements int mycount = std::count (myints, myints+8, 10); std::cout << "10 appears " << mycount << " times.\n"; // counting elements in container: std::vector<int> myvector (myints, myints+8); mycount = std::count (myvector.begin(), myvector.end(), 20); std::cout << "20 appears " << mycount << " times.\n"; mycount = count_if (myvector.begin(), myvector.end(), IsOdd); std::cout << "myvector contains " << mycount << " odd values.\n"; return 0; } Output: 10 appears 2 times. 20 appears 2 times. myvector contains 3 odd values. */ #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // 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 */ // swap_ranges //將區間[first1,last1)內的元素與“從first2開始，個數相同”的元素相互交換 //這兩個序列可位于同一容器，或不同容器 //如果第二序列小于第一序列長度，或者兩序列在同一容器且重疊，則結果未可預期 //Exchanges the values of each of the elements in the range [first1,last1) //with those of their respective elements in the range beginning at first2. template <class _ForwardIter1, class _ForwardIter2> _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) { __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator); __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator); __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type, typename iterator_traits<_ForwardIter2>::value_type); __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type, typename iterator_traits<_ForwardIter1>::value_type); for ( ; __first1 != __last1; ++__first1, ++__first2)//遍歷第一個序列 iter_swap(__first1, __first2);//交換迭代器所指的元素 return __first2; } //swap_ranges函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::swap_ranges #include <vector> // std::vector int main () { std::vector<int> foo (5,10); // foo: 10 10 10 10 10 std::vector<int> bar (5,33); // bar: 33 33 33 33 33 std::swap_ranges(foo.begin()+1, foo.end()-1, bar.begin()); // print out results of swap: std::cout << "foo contains:"; for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; std::cout << "bar contains:"; for (std::vector<int>::iterator it=bar.begin(); it!=bar.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: foo contains: 10 33 33 33 10 bar contains: 10 10 10 33 33 */ // transform //兩個版本 /* 函數原型： unary operation(1)：版本一 template <class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op); binary operation(2)：版本二 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op); 函數功能： (1) unary operation Applies op to each of the elements in the range [first1,last1) and stores the value returned by each operation in the range that begins at result. (2) binary operation Calls binary_op using each of the elements in the range [first1,last1) as first argument, and the respective argument in the range that begins at first2 as second argument. The value returned by each call is stored in the range that begins at result. */ //第一個版本：以仿函數opr作用于[first,last)中的每一個元素，并以其結果產生出一個新的序列 template <class _InputIter, class _OutputIter, class _UnaryOperation> _OutputIter transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); for ( ; __first != __last; ++__first, ++__result) *__result = __opr(*__first); return __result; } //第二個版本：以仿函數binary_op作用于一雙元素上（其中一個元素來自[first1,last1)，另一個元素來自“從first2開始的序列”） //并以其結果產生出一個新的序列 template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation> _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _OutputIter __result, _BinaryOperation __binary_op) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) *__result = __binary_op(*__first1, *__first2); return __result; } //transform函數舉例： /* #include <vector> // std::vector #include <functional> // std::plus int op_increase (int i) { return ++i; } int main () { std::vector<int> foo; std::vector<int> bar; // set some values: for (int i=1; i<6; i++) foo.push_back (i*10); // foo: 10 20 30 40 50 bar.resize(foo.size()); // allocate space std::transform (foo.begin(), foo.end(), bar.begin(), op_increase); // bar: 11 21 31 41 51 std::cout << "bar contains:"; for (std::vector<int>::iterator it=bar.begin(); it!=bar.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; // std::plus adds together its two arguments: std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>()); // foo: 21 41 61 81 101 std::cout << "foo contains:"; for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: bar contains: 11 21 31 41 51 foo contains: 21 41 61 81 101 */ // replace, replace_if, replace_copy, replace_copy_if //將區間[first,last)內的所有old_value都以new_value替代. template <class _ForwardIter, class _Tp> void replace(_ForwardIter __first, _ForwardIter __last, const _Tp& __old_value, const _Tp& __new_value) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_ForwardIter>::value_type, _Tp); __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); for ( ; __first != __last; ++__first) //將區間內所有old_value都以new_value替代. if (*__first == __old_value) *__first = __new_value; } //將區間[first,last)內的所有被pred判斷為true的元素都以new_value替代. template <class _ForwardIter, class _Predicate, class _Tp> void replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_ForwardIter>::value_type); for ( ; __first != __last; ++__first) if (__pred(*__first))//pred判斷為true *__first = __new_value;//修改其值 } //將區間[first,last)內的所有old_value都以new_value替代.將新序列復制到result所指的容器中 //原始容器的內容并不會改變 template <class _InputIter, class _OutputIter, class _Tp> _OutputIter replace_copy(_InputIter __first, _InputIter __last, _OutputIter __result, const _Tp& __old_value, const _Tp& __new_value) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_InputIter>::value_type, _Tp); for ( ; __first != __last; ++__first, ++__result) *__result = *__first == __old_value ? __new_value : *__first; return __result; } //將區間[first,last)內的所有被pred判斷為true的元素都以new_value替代.將新序列復制到result所指的容器中 //原始容器的內容并不會改變 template <class _InputIter, class _OutputIter, class _Predicate, class _Tp> _OutputIter replace_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred, const _Tp& __new_value) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_InputIter>::value_type); for ( ; __first != __last; ++__first, ++__result) *__result = __pred(*__first) ? __new_value : *__first; return __result; } // generate and generate_n //將仿函數gen的處理結果填充在[first, last)區間內所有元素上，所謂填寫 //就是用迭代器所指元素的assignment操作 //注意：對于用戶自定義類型要提供operator =() template <class _ForwardIter, class _Generator> void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_GENERATOR_CHECK(_Generator, typename iterator_traits<_ForwardIter>::value_type); for ( ; __first != __last; ++__first)//遍歷整個序列 *__first = __gen(); } //將仿函數gen的處理結果填充在first開始的n個元素上，所謂填寫 //就是用迭代器所指元素的assignment操作 template <class _OutputIter, class _Size, class _Generator> _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { __STL_REQUIRES(_OutputIter, _OutputIterator); for ( ; __n > 0; --__n, ++__first)//只限于n個元素 *__first = __gen(); return __first; } //generate和generate_n函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::generate_n int current = 0; int UniqueNumber () { return ++current; } int main () { int myarray[9]; std::generate_n (myarray, 9, UniqueNumber); std::cout << "myarray contains:"; for (int i=0; i<9; ++i) std::cout << ' ' << myarray[i]; std::cout << '\n'; std::cout <<"the value of current: "<<current; std::cout << '\n'; std::vector<int> myvector (6); std::generate (myvector.begin(), myvector.end(), UniqueNumber); std::cout << "myvector contains:"; for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: myarray contains: 1 2 3 4 5 6 7 8 9 the value of current: 9 myvector contains: 10 11 12 13 14 15 */ // remove, remove_if, remove_copy, remove_copy_if //移除[first,last)區間內所有與value值相等的元素，并不是真正的從容器中刪除這些元素(原容器的內容不會改變) //而是將結果復制到一個以result為起始位置的容器中。新容器可以與原容器重疊 template <class _InputIter, class _OutputIter, class _Tp> _OutputIter remove_copy(_InputIter __first, _InputIter __last, _OutputIter __result, const _Tp& __value) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_InputIter>::value_type, _Tp); for ( ; __first != __last; ++__first)//遍歷容器 if (!(*__first == __value)) {//如果不相等 *__result = *__first;//賦值給新容器 ++__result;//新容器前進一個位置 } return __result; } //移除[first,last)區間內被仿函數pred判斷為true的元素,并不是真正的從容器中刪除這些元素(原容器的內容不會改變) //而是將結果復制到一個以result為起始位置的容器中。新容器可以與原容器重疊 template <class _InputIter, class _OutputIter, class _Predicate> _OutputIter remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_InputIter>::value_type); for ( ; __first != __last; ++__first)//遍歷容器 if (!__pred(*__first)) {//若pred判斷為false *__result = *__first;//賦值給新容器 ++__result;//新容器前進一個位置 } return __result; } //移除[first,last)區間內所有與value值相等的元素,該操作不會改變容器大小，只是容器中元素值改變 //即移除之后，重新整理容器的內容 template <class _ForwardIter, class _Tp> _ForwardIter remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_ForwardIter>::value_type, _Tp); __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __first = find(__first, __last, __value);//利用順序查找找出第一個與value相等的元素 _ForwardIter __i = __first; //下面調用remove_copy return __first == __last ? __first : remove_copy(++__i, __last, __first, __value); } //移除[first,last)區間內所有被pred判斷為true的元素,該操作不會改變容器大小，只是容器中元素值改變 //即移除之后，重新整理容器的內容 template <class _ForwardIter, class _Predicate> _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_ForwardIter>::value_type); __first = find_if(__first, __last, __pred);//利用順序查找找出第一個與value相等的元素 _ForwardIter __i = __first; //下面調用remove_copy_if return __first == __last ? __first : remove_copy_if(++__i, __last, __first, __pred); } //上面四個移除函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::remove bool IsOdd (int i) { return ((i%2)==1); } int main () { int myints[] = {10,20,31,30,20,11,10,20}; // 10 20 31 30 20 11 10 20 std::vector<int> myvector (8); std::remove_copy (myints,myints+8,myvector.begin(),20); // 10 31 30 11 10 0 0 0 std::cout << "myvector contains:"; for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; // bounds of range: int* pbegin = myints; // ^ int* pend = myints+sizeof(myints)/sizeof(int); // ^ ^ pend = std::remove (pbegin, pend, 20); // 10 31 30 11 10 ? ? ? // ^ ^ std::cout << "range contains:"; for (int* p=pbegin; p!=pend; ++p) std::cout << ' ' << *p; std::cout << '\n'; std::vector<int> myvector2 (7); std::remove_copy_if (myints,myints+7,myvector2.begin(),IsOdd); std::cout << "myvector2 contains:"; for (std::vector<int>::iterator it=myvector2.begin(); it!=myvector2.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; pend = std::remove_if (pbegin, pend, IsOdd); // 10 30 10 ? ? ? ? ? // ^ ^ std::cout << "the range contains:"; for (int* p=pbegin; p!=pend; ++p) std::cout << ' ' << *p; std::cout << '\n'; return 0; } Output: myvector contains: 10 31 30 11 10 0 0 0 range contains: 10 31 30 11 10 myvector2 contains: 10 30 10 10 0 0 0 the range contains: 10 30 10 */ // unique and unique_copy template <class _InputIter, class _OutputIter, class _Tp> _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _Tp*) { _Tp __value = *__first; *__result = __value; while (++__first != __last) if (!(__value == *__first)) { __value = *__first; *++__result = __value; } return ++__result; } //若result類型為output_iterator_tag，則調用該函數 template <class _InputIter, class _OutputIter> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, output_iterator_tag) { //判斷first的value_type類型，根據不同類型調用不同函數 return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first)); } //若result類型為forward_iterator_tag，則調用該函數 template <class _InputIter, class _ForwardIter> _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, forward_iterator_tag) { *__result = *__first;//記錄第一個元素 while (++__first != __last)//遍歷區間 //若不存在相鄰重復元素，則繼續記錄到目標區result if (!(*__result == *__first)) *++__result = *__first;//記錄元素到目標區 return ++__result; } ////unique_copy將區間[first,last)內元素復制到以result開頭的區間上，但是如果存在相鄰重復元素時，只復制其中第一個元素 //和unique一樣，這里也有兩個版本 /* 函數原型： equality (1) template <class InputIterator, class OutputIterator> OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result); predicate (2) template <class InputIterator, class OutputIterator, class BinaryPredicate> OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); */ //版本一 template <class _InputIter, class _OutputIter> inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, _EqualityComparable); if (__first == __last) return __result; //根據result迭代器的類型，調用不同的函數 return __unique_copy(__first, __last, __result, __ITERATOR_CATEGORY(__result)); } template <class _InputIter, class _OutputIter, class _BinaryPredicate, class _Tp> _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred, _Tp*) { __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, _Tp, _Tp); _Tp __value = *__first; *__result = __value; while (++__first != __last) if (!__binary_pred(__value, *__first)) { __value = *__first; *++__result = __value; } return ++__result; } template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred, output_iterator_tag) { return __unique_copy(__first, __last, __result, __binary_pred, __VALUE_TYPE(__first)); } template <class _InputIter, class _ForwardIter, class _BinaryPredicate> _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _BinaryPredicate __binary_pred, forward_iterator_tag) { __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_InputIter>::value_type); *__result = *__first; while (++__first != __last) if (!__binary_pred(*__result, *__first)) *++__result = *__first; return ++__result; } //版本二 template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); if (__first == __last) return __result; //根據result迭代器的類型，調用不同的函數 return __unique_copy(__first, __last, __result, __binary_pred, __ITERATOR_CATEGORY(__result)); } //移除區間[first,last)相鄰連續重復的元素 //unique有兩個版本 //功能：Removes all but the first element from every consecutive group of equivalent elements in the range [first,last). /* 函數原型： equality (1)：版本一采用operator== template <class ForwardIterator> ForwardIterator unique (ForwardIterator first, ForwardIterator last); predicate (2)：版本二采用pred操作 template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate pred); */ //版本一 template <class _ForwardIter> _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _EqualityComparable); __first = adjacent_find(__first, __last);//找出第一個相鄰元素的起始位置 return unique_copy(__first, __last, __first);//調用unique_copy完成操作 } //版本二 template <class _ForwardIter, class _BinaryPredicate> _ForwardIter unique(_ForwardIter __first, _ForwardIter __last, _BinaryPredicate __binary_pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); __first = adjacent_find(__first, __last, __binary_pred);//找出第一個相鄰元素的起始位置 return unique_copy(__first, __last, __first, __binary_pred);//調用unique_copy完成操作 } // reverse and reverse_copy, and their auxiliary functions //若迭代器類型為bidirectional_iterator_tag，則調用此函數 template <class _BidirectionalIter> void __reverse(_BidirectionalIter __first, _BidirectionalIter __last, bidirectional_iterator_tag) { while (true) if (__first == __last || __first == --__last)//這里需注意，每次判斷last迭代器都會后退一位 return; else iter_swap(__first++, __last);//單向交換迭代器所指的元素 } //若迭代器類型為random_access_iterator_tag，則調用此函數 template <class _RandomAccessIter> void __reverse(_RandomAccessIter __first, _RandomAccessIter __last, random_access_iterator_tag) { while (__first < __last)//遍歷容器 iter_swap(__first++, --__last);//交換兩端迭代器所指的元素 } //將序列[first,last)的所有元素在原容器中顛倒重排 template <class _BidirectionalIter> inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); //首先萃取出迭代器的類型 __reverse(__first, __last, __ITERATOR_CATEGORY(__first)); } //行為類似reverse，但產生的新序列會被置于以result指出的容器中 template <class _BidirectionalIter, class _OutputIter> _OutputIter reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last, _OutputIter __result) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); while (__first != __last) {//遍歷容器 --__last;//尾端前移一個位置 *__result = *__last;//result容器的起始位置元素值為原始容器尾端元素值 ++__result;//更新result，使其前進一個位置 } return __result; } // rotate and rotate_copy, and their auxiliary functions template <class _EuclideanRingElement> _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) { while (__n != 0) { _EuclideanRingElement __t = __m % __n; __m = __n; __n = __t; } return __m; } //迭代器類型為forward_iterator_tag，調用此函數 template <class _ForwardIter, class _Distance> _ForwardIter __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last, _Distance*, forward_iterator_tag) { if (__first == __middle) return __last; if (__last == __middle) return __first; _ForwardIter __first2 = __middle; do { swap(*__first++, *__first2++); if (__first == __middle) __middle = __first2; } while (__first2 != __last); _ForwardIter __new_middle = __first; __first2 = __middle; while (__first2 != __last) { swap (*__first++, *__first2++); if (__first == __middle) __middle = __first2; else if (__first2 == __last) __first2 = __middle; } return __new_middle; } //迭代器類型為bidirectional_iterator_tag，調用此函數 template <class _BidirectionalIter, class _Distance> _BidirectionalIter __rotate(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance*, bidirectional_iterator_tag) { __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); if (__first == __middle) return __last; if (__last == __middle) return __first; __reverse(__first, __middle, bidirectional_iterator_tag()); __reverse(__middle, __last, bidirectional_iterator_tag()); while (__first != __middle && __middle != __last) swap (*__first++, *--__last); if (__first == __middle) { __reverse(__middle, __last, bidirectional_iterator_tag()); return __last; } else { __reverse(__first, __middle, bidirectional_iterator_tag()); return __first; } } //迭代器類型為Random_iterator_tag，調用此函數 template <class _RandomAccessIter, class _Distance, class _Tp> _RandomAccessIter __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Distance *, _Tp *) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); _Distance __n = __last - __first; _Distance __k = __middle - __first; _Distance __l = __n - __k; _RandomAccessIter __result = __first + (__last - __middle); if (__k == 0) return __last; else if (__k == __l) { swap_ranges(__first, __middle, __middle); return __result; } _Distance __d = __gcd(__n, __k); for (_Distance __i = 0; __i < __d; __i++) { _Tp __tmp = *__first; _RandomAccessIter __p = __first; if (__k < __l) { for (_Distance __j = 0; __j < __l/__d; __j++) { if (__p > __first + __l) { *__p = *(__p - __l); __p -= __l; } *__p = *(__p + __k); __p += __k; } } else { for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { if (__p < __last - __k) { *__p = *(__p + __k); __p += __k; } *__p = * (__p - __l); __p -= __l; } } *__p = __tmp; ++__first; } return __result; } //將區間[first,middle)內的元素和[middle,last)內的元素互換。minddle所指的元素會成為容器的第一個元素 //例如對序列{1,2,3,4,5,6,7}，對元素3進行旋轉操作,則結果為{3,4,5,6,7,1,2} template <class _ForwardIter> inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); //萃取出迭代器的類型，根據迭代器的類型調用不同的函數 return __rotate(__first, __middle, __last, __DISTANCE_TYPE(__first), __ITERATOR_CATEGORY(__first)); } //將區間[first,middle)內的元素和[middle,last)內的元素互換。minddle所指的元素會成為新容器result的第一個元素 template <class _ForwardIter, class _OutputIter> _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last, _OutputIter __result) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); //這里直接采用復制操作，先把[middle,last)復制到result容器中， //再把[first,middle)內容復制到result容器中 return copy(__first, __middle, copy(__middle, __last, __result)); } // Return a random number in the range [0, __n). This function encapsulates // whether we're using rand (part of the standard C library) or lrand48 // (not standard, but a much better choice whenever it's available). template <class _Distance> inline _Distance __random_number(_Distance __n) { #ifdef __STL_NO_DRAND48 return rand() % __n; #else return lrand48() % __n; #endif } // random_shuffle //將區間[first,last)內的元素隨機重排 //兩個版本的不同是隨機數的取得 //版本一是使用內部隨機數產生器 //版本二是使用一個會產生隨機數的仿函數 /* 函數功能：Rearranges the elements in the range [first,last) randomly. 函數原型： generator by default (1) template <class RandomAccessIterator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last); specific generator (2) template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& gen); */ //版本一 template <class _RandomAccessIter> inline void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __random_number((__i - __first) + 1)); } //版本二 template <class _RandomAccessIter, class _RandomNumberGenerator> void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, _RandomNumberGenerator& __rand) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __rand((__i - __first) + 1)); } // random_sample and random_sample_n (extensions, not part of the standard). template <class _ForwardIter, class _OutputIter, class _Distance> _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); while (__m > 0) { if (__random_number(__remaining) < __m) { *__out = *__first; ++__out; --__m; } --__remaining; ++__first; } return __out; } template <class _ForwardIter, class _OutputIter, class _Distance, class _RandomNumberGenerator> _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n, _RandomNumberGenerator& __rand) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); while (__m > 0) { if (__rand(__remaining) < __m) { *__out = *__first; ++__out; --__m; } --__remaining; ++__first; } return __out; } template <class _InputIter, class _RandomAccessIter, class _Distance> _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out, const _Distance __n) { _Distance __m = 0; _Distance __t = __n; for ( ; __first != __last && __m < __n; ++__m, ++__first) __out[__m] = *__first; while (__first != __last) { ++__t; _Distance __M = __random_number(__t); if (__M < __n) __out[__M] = *__first; ++__first; } return __out + __m; } template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator, class _Distance> _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out, _RandomNumberGenerator& __rand, const _Distance __n) { __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); _Distance __m = 0; _Distance __t = __n; for ( ; __first != __last && __m < __n; ++__m, ++__first) __out[__m] = *__first; while (__first != __last) { ++__t; _Distance __M = __rand(__t); if (__M < __n) __out[__M] = *__first; ++__first; } return __out + __m; } template <class _InputIter, class _RandomAccessIter> inline _RandomAccessIter random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); return __random_sample(__first, __last, __out_first, __out_last - __out_first); } template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator> inline _RandomAccessIter random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last, _RandomNumberGenerator& __rand) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); return __random_sample(__first, __last, __out_first, __rand, __out_last - __out_first); } // partition, stable_partition, and their auxiliary functions //若迭代器的類型為forward_iterator_tag，則調用此函數 template <class _ForwardIter, class _Predicate> _ForwardIter __partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, forward_iterator_tag) { if (__first == __last) return __first;//若為空，直接退出 while (__pred(*__first))//若pred出first的值為true if (++__first == __last) return __first;//先移動迭代器first，在判斷是否到達尾端last _ForwardIter __next = __first;//繼續判斷 while (++__next != __last)//若下一個位置依然不是尾端 if (__pred(*__next)) {//繼續pred出next的值，若為true swap(*__first, *__next);//交換值 ++__first;//繼續下一位置 } return __first; } //若迭代器的類型為bidirectional_iterator_tag，則調用此函數 template <class _BidirectionalIter, class _Predicate> _BidirectionalIter __partition(_BidirectionalIter __first, _BidirectionalIter __last, _Predicate __pred, bidirectional_iterator_tag) { while (true) { while (true) if (__first == __last)//若為空 return __first;//直接退出 else if (__pred(*__first))//first的值符合不移動條件，則不移動該值 ++__first;//只移動迭代器 else//若頭指針符合移動 break;//跳出循環 --__last;//尾指針回溯 while (true) if (__first == __last)//頭指針等于尾指針 return __first;//操作結束 else if (!__pred(*__last))//尾指針的元素符合不移動操作 --__last;//至移動迭代器，并不移動具體元素 else//尾指針的元素符合移動操作 break;//跳出循環 iter_swap(__first, __last);//頭尾指針交換元素 ++__first;//準備下一次循環 } } //將區間[first,last)的元素進行排序，被pred判斷為true的放在區間的前段，判定為false的放在區間后段 //該算算可能會使元素的元素位置放生改變. /* 算法功能：Rearranges the elements from the range [first,last), in such a way that all the elements for which pred returns true precede all those for which it returns false. The iterator returned points to the first element of the second group. 算法原型： template <class BidirectionalIterator, class UnaryPredicate> BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred); */ template <class _ForwardIter, class _Predicate> inline _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_ForwardIter>::value_type); //首先萃取出迭代器first的類型，根據迭代器的類型調用不同的函數 return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); } //partition函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::partition #include <vector> // std::vector bool IsOdd (int i) { return (i%2)==1; } int main () { std::vector<int> myvector; // set some values: for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9 std::vector<int>::iterator bound; bound = std::partition (myvector.begin(), myvector.end(), IsOdd); // print out content: std::cout << "odd elements:"; for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it) std::cout << ' ' << *it; std::cout << '\n'; std::cout << "even elements:"; for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: odd elements: 1 9 3 7 5 even elements: 6 4 8 2 */ template <class _ForwardIter, class _Predicate, class _Distance> _ForwardIter __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Distance __len) { if (__len == 1) return __pred(*__first) ? __last : __first; _ForwardIter __middle = __first; advance(__middle, __len / 2); return rotate(__inplace_stable_partition(__first, __middle, __pred, __len / 2), __middle, __inplace_stable_partition(__middle, __last, __pred, __len - __len / 2)); } template <class _ForwardIter, class _Pointer, class _Predicate, class _Distance> _ForwardIter __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size) { if (__len <= __buffer_size) { _ForwardIter __result1 = __first; _Pointer __result2 = __buffer; for ( ; __first != __last ; ++__first) if (__pred(*__first)) { *__result1 = *__first; ++__result1; } else { *__result2 = *__first; ++__result2; } copy(__buffer, __result2, __result1); return __result1; } else { _ForwardIter __middle = __first; advance(__middle, __len / 2); return rotate(__stable_partition_adaptive( __first, __middle, __pred, __len / 2, __buffer, __buffer_size), __middle, __stable_partition_adaptive( __middle, __last, __pred, __len - __len / 2, __buffer, __buffer_size)); } } template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> inline _ForwardIter __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Tp*, _Distance*) { _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); if (__buf.size() > 0) return __stable_partition_adaptive(__first, __last, __pred, _Distance(__buf.requested_size()), __buf.begin(), __buf.size()); else return __inplace_stable_partition(__first, __last, __pred, _Distance(__buf.requested_size())); } template <class _ForwardIter, class _Predicate> inline _ForwardIter stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; else return __stable_partition_aux(__first, __last, __pred, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } //找出快速排序的樞紐位置 //版本一采用operator< template <class _RandomAccessIter, class _Tp> _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot) { //找出樞紐軸的位置 //令頭端迭代器向尾端方向移動，尾端迭代器向頭端移動。 //當*first不小于樞紐值時，就停下來，當*last不大于樞紐值時也停下來，然后檢測兩個迭代器是否交錯 //如果first仍然在左側而last仍然在右側，就交換兩個元素，然后各自調整位置，向中央逼近，再繼續執行相同的行為. //直到first和last兩個迭代器交錯，此時表示已找到樞紐軸位置即first所在的位置 while (true) { while (*__first < __pivot) ++__first;//first向尾端移動，直到遇到不小于樞紐值時，停止 --__last; while (__pivot < *__last) --__last;//last向頭端移動，直到遇到不大于樞紐值時，停止 if (!(__first < __last))//檢測兩個迭代器是否交錯 return __first;//交錯，則此時已找到，即為first迭代器所指位置 iter_swap(__first, __last);//否則交換迭代器所指的元素 ++__first;//繼續執行相同行為 } } //版本一采用__comp template <class _RandomAccessIter, class _Tp, class _Compare> _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot, _Compare __comp) { while (true) { while (__comp(*__first, __pivot)) ++__first; --__last; while (__comp(__pivot, *__last)) --__last; if (!(__first < __last)) return __first; iter_swap(__first, __last); ++__first; } } const int __stl_threshold = 16; // sort() and its auxiliary functions. //__insertion_sort版本一的輔助函數 template <class _RandomAccessIter, class _Tp> void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { _RandomAccessIter __next = __last; --__next; //__insertion_sort的內循環 //注意：一旦不再出現逆轉對，循環就結束 while (__val < *__next) {//存在逆轉對 *__last = *__next;//調整元素 __last = __next;//調整迭代器 --__next;//左移一個位置 } *__last = __val;//value的正確插入位置 } //__insertion_sort版本二的輔助函數 template <class _RandomAccessIter, class _Tp, class _Compare> void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) { _RandomAccessIter __next = __last; --__next; while (__comp(__val, *__next)) { *__last = *__next; __last = __next; --__next; } *__last = __val; } //__insertion_sort版本一的輔助函數 template <class _RandomAccessIter, class _Tp> inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) { _Tp __val = *__last;//記錄尾元素 if (__val < *__first) {//尾元素比頭元素還小 //將整個區間向右移一個位置 copy_backward(__first, __last, __last + 1); *__first = __val;//令頭元素等于原先的尾元素 //以上兩行命令的功能相等于交換兩個元素 } else//尾元素不小于頭元素 __unguarded_linear_insert(__last, __val); } //__insertion_sort版本二的輔助函數 template <class _RandomAccessIter, class _Tp, class _Compare> inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Compare __comp) { _Tp __val = *__last; if (__comp(__val, *__first)) { copy_backward(__first, __last, __last + 1); *__first = __val; } else __unguarded_linear_insert(__last, __val, __comp); } //__insertion_sort以雙層循環形式進行。外循環遍歷整個序列，每次迭代決定出一個子區間； //內循環遍歷子區間，將子區間內的每一個“逆轉對”倒轉過來，如果一旦不存在“逆轉對”，表示排序完畢。 //“逆轉對”概念：指任何兩個迭代器i和j，i<j,而*i>*j. //版本一 template <class _RandomAccessIter> void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first == __last) return; //若區間為空，則退出 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)//外循環，遍歷整個區間 //[first,i)形成的子空間 __linear_insert(__first, __i, __VALUE_TYPE(__first)); } //版本二 template <class _RandomAccessIter, class _Compare> void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp); } template <class _RandomAccessIter, class _Tp> void __unguarded_insertion_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) { for (_RandomAccessIter __i = __first; __i != __last; ++__i) __unguarded_linear_insert(__i, _Tp(*__i)); } //sort版本一的輔助函數 template <class _RandomAccessIter> inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __unguarded_insertion_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Compare __comp) { for (_RandomAccessIter __i = __first; __i != __last; ++__i) __unguarded_linear_insert(__i, _Tp(*__i), __comp); } template <class _RandomAccessIter, class _Compare> inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first), __comp); } //sort版本一的輔助函數 template <class _RandomAccessIter> void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first > __stl_threshold) {//判斷元素個數是否大于16 //則把區間分割成兩段，一端長度為16，另一端為剩余的長度 __insertion_sort(__first, __first + __stl_threshold); __unguarded_insertion_sort(__first + __stl_threshold, __last); } else//若不大于16，直接調用插入排序 __insertion_sort(__first, __last); } template <class _RandomAccessIter, class _Compare> void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first > __stl_threshold) { __insertion_sort(__first, __first + __stl_threshold, __comp); __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); } else __insertion_sort(__first, __last, __comp); } //_lg()函數是用來控制分割惡化的情況 //該函數找出2^k <= n 的最大值k; //例如：n=7,得k=2; n=20,得k=4; n=8,得k=3; template <class _Size> inline _Size __lg(_Size __n) { _Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k; } //sort版本一的輔助函數 //參數__depth_limit表示最大的分割層數 template <class _RandomAccessIter, class _Tp, class _Size> void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit) { //__stl_threshold為全局常量，其值為16 while (__last - __first > __stl_threshold) {//若區間長度大于16 if (__depth_limit == 0) {//表示分割惡化 partial_sort(__first, __last, __last);//轉而調用堆排序heap_sort() return; } --__depth_limit; //計算分割點cut，樞紐值是采用首、尾、中央三個的中間值 _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1)))); //對右半部分遞歸地進行排序 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit); __last = __cut;//接下來對左半部分遞歸地進行排序 } } template <class _RandomAccessIter, class _Tp, class _Size, class _Compare> void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit, _Compare __comp) { while (__last - __first > __stl_threshold) { if (__depth_limit == 0) { partial_sort(__first, __last, __last, __comp); return; } --__depth_limit; _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1), __comp)), __comp); __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); __last = __cut; } } //SGI STL的排序算法，迭代器參數的類型必須是隨機訪問迭代器_RandomAccessIter /* 函數功能：Sorts the elements in the range [first,last) into ascending order. 函數原型： default (1) ：版本一采用默認的operator< template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); custom (2) ：版本二采用仿函數comp template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); */ //版本一 template <class _RandomAccessIter> inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); //_lg()函數是用來控制分割惡化的情況 if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2); //進行插入排序 __final_insertion_sort(__first, __last); } } //版本二 template <class _RandomAccessIter, class _Compare> inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2, __comp); __final_insertion_sort(__first, __last, __comp); } } // stable_sort() and its auxiliary functions. template <class _RandomAccessIter> void __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first < 15) { __insertion_sort(__first, __last); return; } _RandomAccessIter __middle = __first + (__last - __first) / 2; __inplace_stable_sort(__first, __middle); __inplace_stable_sort(__middle, __last); __merge_without_buffer(__first, __middle, __last, __middle - __first, __last - __middle); } template <class _RandomAccessIter, class _Compare> void __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first < 15) { __insertion_sort(__first, __last, __comp); return; } _RandomAccessIter __middle = __first + (__last - __first) / 2; __inplace_stable_sort(__first, __middle, __comp); __inplace_stable_sort(__middle, __last, __comp); __merge_without_buffer(__first, __middle, __last, __middle - __first, __last - __middle, __comp); } template <class _RandomAccessIter1, class _RandomAccessIter2, class _Distance> void __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size) { _Distance __two_step = 2 * __step_size; while (__last - __first >= __two_step) { __result = merge(__first, __first + __step_size, __first + __step_size, __first + __two_step, __result); __first += __two_step; } __step_size = min(_Distance(__last - __first), __step_size); merge(__first, __first + __step_size, __first + __step_size, __last, __result); } template <class _RandomAccessIter1, class _RandomAccessIter2, class _Distance, class _Compare> void __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size, _Compare __comp) { _Distance __two_step = 2 * __step_size; while (__last - __first >= __two_step) { __result = merge(__first, __first + __step_size, __first + __step_size, __first + __two_step, __result, __comp); __first += __two_step; } __step_size = min(_Distance(__last - __first), __step_size); merge(__first, __first + __step_size, __first + __step_size, __last, __result, __comp); } const int __stl_chunk_size = 7; template <class _RandomAccessIter, class _Distance> void __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Distance __chunk_size) { while (__last - __first >= __chunk_size) { __insertion_sort(__first, __first + __chunk_size); __first += __chunk_size; } __insertion_sort(__first, __last); } template <class _RandomAccessIter, class _Distance, class _Compare> void __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Distance __chunk_size, _Compare __comp) { while (__last - __first >= __chunk_size) { __insertion_sort(__first, __first + __chunk_size, __comp); __first += __chunk_size; } __insertion_sort(__first, __last, __comp); } template <class _RandomAccessIter, class _Pointer, class _Distance> void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance*) { _Distance __len = __last - __first; _Pointer __buffer_last = __buffer + __len; _Distance __step_size = __stl_chunk_size; __chunk_insertion_sort(__first, __last, __step_size); while (__step_size < __len) { __merge_sort_loop(__first, __last, __buffer, __step_size); __step_size *= 2; __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); __step_size *= 2; } } template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance*, _Compare __comp) { _Distance __len = __last - __first; _Pointer __buffer_last = __buffer + __len; _Distance __step_size = __stl_chunk_size; __chunk_insertion_sort(__first, __last, __step_size, __comp); while (__step_size < __len) { __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); __step_size *= 2; __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); __step_size *= 2; } } template <class _RandomAccessIter, class _Pointer, class _Distance> void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance __buffer_size) { _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); } else { __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0); __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0); } __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), _Distance(__last - __middle), __buffer, __buffer_size); } template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance __buffer_size, _Compare __comp) { _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, __comp); __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, __comp); } else { __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0, __comp); __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, __comp); } __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), _Distance(__last - __middle), __buffer, __buffer_size, __comp); } template <class _RandomAccessIter, class _Tp, class _Distance> inline void __stable_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Distance*) { _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); if (buf.begin() == 0) __inplace_stable_sort(__first, __last); else __stable_sort_adaptive(__first, __last, buf.begin(), _Distance(buf.size())); } template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> inline void __stable_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Distance*, _Compare __comp) { _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); if (buf.begin() == 0) __inplace_stable_sort(__first, __last, __comp); else __stable_sort_adaptive(__first, __last, buf.begin(), _Distance(buf.size()), __comp); } template <class _RandomAccessIter> inline void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __stable_sort_aux(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIter, class _Compare> inline void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __stable_sort_aux(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), __comp); } // partial_sort, partial_sort_copy, and auxiliary functions. //重新安排序列[first,last)，使序列前半部分middle-first個最小元素以遞增順序排序，并將其置于[first,middle) //其余last-middle個元素不指定任何排序，并將其置于[middle,last) //注意：迭代器middle是在[first,last)范圍之內 /* 函數功能：Rearranges the elements in the range [first,last), in such a way that the elements before middle are the smallest elements in the entire range and are sorted in ascending order, while the remaining elements are left without any specific order. 函數原型： default (1) 版本一 operator< template <class RandomAccessIterator> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); custom (2) 版本二 comp template <class RandomAccessIterator, class Compare> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); */ template <class _RandomAccessIter, class _Tp> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*) { //利用heap的知識，在SGI STL中，是采用最大堆 //將[first,middle)區間的元素創建成最大堆 //再根據最大堆的性質，一個一個彈出堆，并將其保存，即堆排序 make_heap(__first, __middle);//創建最大堆，定義與<stl_heap.h>文件 //以下是在區間中[first,last)找出middle-first個最小元素 //這里的是將后半部分[middle,last)的元素依次與最大堆的根節點元素(即堆的最大元素)比較 //若小于堆的最大元素，則與堆的最大元素交換，并調整堆，使其依次成為最大堆 //若不小于堆的最大元素，則不作任何操作 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) __pop_heap(__first, __middle, __i, _Tp(*__i), __DISTANCE_TYPE(__first)); sort_heap(__first, __middle);//對最大堆進行堆排序 } //版本一 template <class _RandomAccessIter> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*, _Compare __comp) { make_heap(__first, __middle, __comp); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (__comp(*__i, *__first)) __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, __DISTANCE_TYPE(__first)); sort_heap(__first, __middle, __comp); } //版本二 template <class _RandomAccessIter, class _Compare> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); } //partial_sort_copy與partial_sort的實現機制是相同，只是partial_sort_copy將元素排序后放在以result起始的容器中 template <class _InputIter, class _RandomAccessIter, class _Distance, class _Tp> _RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { *__result_real_last = *__first; ++__result_real_last; ++__first; } make_heap(__result_first, __result_real_last); while (__first != __last) { if (*__first < *__result_first) __adjust_heap(__result_first, _Distance(0), _Distance(__result_real_last - __result_first), _Tp(*__first)); ++__first; } sort_heap(__result_first, __result_real_last); return __result_real_last; } template <class _InputIter, class _RandomAccessIter> inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, _LessThanComparable); return __partial_sort_copy(__first, __last, __result_first, __result_last, __DISTANCE_TYPE(__result_first), __VALUE_TYPE(__first)); } template <class _InputIter, class _RandomAccessIter, class _Compare, class _Distance, class _Tp> _RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp, _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { *__result_real_last = *__first; ++__result_real_last; ++__first; } make_heap(__result_first, __result_real_last, __comp); while (__first != __last) { if (__comp(*__first, *__result_first)) __adjust_heap(__result_first, _Distance(0), _Distance(__result_real_last - __result_first), _Tp(*__first), __comp); ++__first; } sort_heap(__result_first, __result_real_last, __comp); return __result_real_last; } template <class _InputIter, class _RandomAccessIter, class _Compare> inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); return __partial_sort_copy(__first, __last, __result_first, __result_last, __comp, __DISTANCE_TYPE(__result_first), __VALUE_TYPE(__first)); } // nth_element() and its auxiliary functions. //nth_element版本一輔助函數 template <class _RandomAccessIter, class _Tp> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp*) { while (__last - __first > 3) {//區間長度大于3 //獲取分割點cut _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1)))); if (__cut <= __nth)//若分割點小于指定位置，則nth位置在右半段 __first = __cut;//再對右半段進行分割 else //否則，對左半段進行分割 __last = __cut; } __insertion_sort(__first, __last); } //重新排序序列[first,last)，使迭代器nth所指的元素，與“整個[first,last)序列完整排序后，同一位置的元素”同值. //此外，必須保證[nth,last)內的所有元素不小于[first,nth)內的元素，但是對于序列[first,nth)和序列[nth,last)內的元素的排序順序不能確定. /* 函數功能：Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. 函數原型： default (1) template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); custom (2) template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); */ //nth_element版本一 template <class _RandomAccessIter> inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __nth_element(__first, __nth, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp*, _Compare __comp) { while (__last - __first > 3) { _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1), __comp)), __comp); if (__cut <= __nth) __first = __cut; else __last = __cut; } __insertion_sort(__first, __last, __comp); } template <class _RandomAccessIter, class _Compare> inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp); } // 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); } // merge, with and without an explicitly supplied comparison function. //將兩個已排序的區間[first1,last1)和區間[first2,last2)合并 /* 函數功能：Combines the elements in the sorted ranges [first1,last1) and [first2,last2), into a new range beginning at result with all its elements sorted. 函數原型： default (1) ：版本一 template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); custom (2) ：版本二 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); */ //版本一： template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); //兩個序列都尚未到達尾端，則執行while循環 /* 情況1：若序列二元素較小,則記錄到目標區，且移動序列二的迭代器，但是序列一的迭代器不變. 情況2：若序列一元素較小或相等,則記錄到目標區，且移動序列一的迭代器，但是序列二的迭代器不變. 最后：把剩余元素的序列復制到目標區 */ while (__first1 != __last1 && __first2 != __last2) { //情況1 if (*__first2 < *__first1) {//若序列二元素較小 *__result = *__first2;//將元素記錄到目標區 ++__first2;//移動迭代器 } //情況2 else {//若序列一元素較小或相等 *__result = *__first1;//將元素記錄到目標區 ++__first1;//移動迭代器 } ++__result;//更新目標區位置，以便下次記錄數據 } //若有序列到達尾端，則把沒到達尾端的序列剩余元素復制到目標區 //此時，區間[first1,last1)和區間[first2,last2)至少一個必定為空 return copy(__first2, __last2, copy(__first1, __last1, __result)); } //版本二 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter1>::value_type); while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__first2; } else { *__result = *__first1; ++__first1; } ++__result; } return copy(__first2, __last2, copy(__first1, __last1, __result)); } //merge函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::merge, std::sort #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); std::sort (first,first+5); std::sort (second,second+5); std::merge (first,first+5,second,second+5,v.begin()); std::cout << "The resulting vector contains:"; for (std::vector<int>::iterator it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: The resulting vector contains: 5 10 10 15 20 20 25 30 40 50 */ // inplace_merge and its auxiliary functions. //版本一的輔助函數，無緩沖區的操作 template <class _BidirectionalIter, class _Distance> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2) { if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { if (*__middle < *__first) iter_swap(__first, __middle); return; } _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) { __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut); distance(__middle, __second_cut, __len22); } else { __len22 = __len2 / 2; advance(__second_cut, __len22); __first_cut = upper_bound(__first, __middle, *__second_cut); distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = rotate(__first_cut, __middle, __second_cut); __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22); __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22); } template <class _BidirectionalIter, class _Distance, class _Compare> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Compare __comp) { if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { if (__comp(*__middle, *__first)) iter_swap(__first, __middle); return; } _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) { __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); distance(__middle, __second_cut, __len22); } else { __len22 = __len2 / 2; advance(__second_cut, __len22); __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = rotate(__first_cut, __middle, __second_cut); __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22, __comp); __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22, __comp); } //版本一的輔助函數，有緩沖區的操作 template <class _BidirectionalIter1, class _BidirectionalIter2, class _Distance> _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, _BidirectionalIter1 __middle, _BidirectionalIter1 __last, _Distance __len1, _Distance __len2, _BidirectionalIter2 __buffer, _Distance __buffer_size) { _BidirectionalIter2 __buffer_end; if (__len1 > __len2 && __len2 <= __buffer_size) {//緩沖區足夠放置序列二 __buffer_end = copy(__middle, __last, __buffer); copy_backward(__first, __middle, __last); return copy(__buffer, __buffer_end, __first); } else if (__len1 <= __buffer_size) {//緩沖區足夠放置序列一 __buffer_end = copy(__first, __middle, __buffer); copy(__middle, __last, __first); return copy_backward(__buffer, __buffer_end, __last); } else//若緩沖區仍然不夠，則調用STL算法rotate，不使用緩沖區 return rotate(__first, __middle, __last); } template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result) { if (__first1 == __last1) return copy_backward(__first2, __last2, __result); if (__first2 == __last2) return copy_backward(__first1, __last1, __result); --__last1; --__last2; while (true) { if (*__last2 < *__last1) { *--__result = *__last1; if (__first1 == __last1) return copy_backward(__first2, ++__last2, __result); --__last1; } else { *--__result = *__last2; if (__first2 == __last2) return copy_backward(__first1, ++__last1, __result); --__last2; } } } template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3, class _Compare> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result, _Compare __comp) { if (__first1 == __last1) return copy_backward(__first2, __last2, __result); if (__first2 == __last2) return copy_backward(__first1, __last1, __result); --__last1; --__last2; while (true) { if (__comp(*__last2, *__last1)) { *--__result = *__last1; if (__first1 == __last1) return copy_backward(__first2, ++__last2, __result); --__last1; } else { *--__result = *__last2; if (__first2 == __last2) return copy_backward(__first1, ++__last1, __result); --__last2; } } } //版本一的輔助函數，有緩沖區的操作 template <class _BidirectionalIter, class _Distance, class _Pointer> void __merge_adaptive(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size) { if (__len1 <= __len2 && __len1 <= __buffer_size) { //case1：把序列一放在緩沖區 _Pointer __buffer_end = copy(__first, __middle, __buffer); //直接調用歸并函數merge merge(__buffer, __buffer_end, __middle, __last, __first); } else if (__len2 <= __buffer_size) { //case2：把序列二放在緩沖區 _Pointer __buffer_end = copy(__middle, __last, __buffer); __merge_backward(__first, __middle, __buffer, __buffer_end, __last); } else {//case3：緩沖區不足放置任何一個序列 _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) {//若序列一比較長 __len11 = __len1 / 2;//計算序列一的一半 advance(__first_cut, __len11);//讓first_cut指向序列一的中間位置 //找出*__first_cut在[middle,last)區間中的第一個不小于*__first_cut的元素位置 __second_cut = lower_bound(__middle, __last, *__first_cut); //計算middle到__second_cut之間的距離，保存在__len22 distance(__middle, __second_cut, __len22); } else {//若序列二比較長 __len22 = __len2 / 2;//計算序列二的一半 advance(__second_cut, __len22);//讓__second_cut指向序列二的中間位置 //找出*__second_cut在[first,middle)區間中的第一個大于*__second_cut的元素位置 __first_cut = upper_bound(__first, __middle, *__second_cut); //計算__first到__first_cut之間的距離，保存在__len11 distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, __len22, __buffer, __buffer_size); //對左半段遞歸調用 __merge_adaptive(__first, __first_cut, __new_middle, __len11, __len22, __buffer, __buffer_size); //對右半段遞歸調用 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22, __buffer, __buffer_size); } } template <class _BidirectionalIter, class _Distance, class _Pointer, class _Compare> void __merge_adaptive(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp) { if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = copy(__first, __middle, __buffer); merge(__buffer, __buffer_end, __middle, __last, __first, __comp); } else if (__len2 <= __buffer_size) { _Pointer __buffer_end = copy(__middle, __last, __buffer); __merge_backward(__first, __middle, __buffer, __buffer_end, __last, __comp); } else { _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) { __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); distance(__middle, __second_cut, __len22); } else { __len22 = __len2 / 2; advance(__second_cut, __len22); __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, __len22, __buffer, __buffer_size); __merge_adaptive(__first, __first_cut, __new_middle, __len11, __len22, __buffer, __buffer_size, __comp); __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22, __buffer, __buffer_size, __comp); } } //版本一的輔助函數 template <class _BidirectionalIter, class _Tp, class _Distance> inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Tp*, _Distance*) { _Distance __len1 = 0; distance(__first, __middle, __len1);//計算序列一的長度 _Distance __len2 = 0; distance(__middle, __last, __len2);//計算序列二的長度 //使用暫時緩沖區 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); if (__buf.begin() == 0)//若緩沖區配置失敗 //則調用不使用緩沖區的合并操作 __merge_without_buffer(__first, __middle, __last, __len1, __len2); else//若分配成功 //則調用具有緩沖區的合并操作 __merge_adaptive(__first, __middle, __last, __len1, __len2, __buf.begin(), _Distance(__buf.size())); } template <class _BidirectionalIter, class _Tp, class _Distance, class _Compare> inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Tp*, _Distance*, _Compare __comp) { _Distance __len1 = 0; distance(__first, __middle, __len1); _Distance __len2 = 0; distance(__middle, __last, __len2); _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); if (__buf.begin() == 0) __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); else __merge_adaptive(__first, __middle, __last, __len1, __len2, __buf.begin(), _Distance(__buf.size()), __comp); } //將兩個已排序的序列[first,middle)和[middle,last)合并成單一有序序列. //若原來是增序，現在也是遞增排序，若原來是遞減排序，現在也是遞減排序 /* 函數功能：Merges two consecutive sorted ranges: [first,middle) and [middle,last), putting the result into the combined sorted range [first,last). 函數原型： default (1) ：版本一 template <class BidirectionalIterator> void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); custom (2) ：版本二 template <class BidirectionalIterator, class Compare> void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); */ //版本一 template <class _BidirectionalIter> inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, _LessThanComparable); if (__first == __middle || __middle == __last)//若有空序列，則之間返回 return; __inplace_merge_aux(__first, __middle, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } //版本二 template <class _BidirectionalIter, class _Compare> inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Compare __comp) { __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_BidirectionalIter>::value_type, typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __middle || __middle == __last) return; __inplace_merge_aux(__first, __middle, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), __comp); } //inplace_merge函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::inplace_merge, std::sort, std::copy #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); std::vector<int>::iterator it; std::sort (first,first+5); std::sort (second,second+5); it=std::copy (first, first+5, v.begin()); std::copy (second,second+5,it); std::inplace_merge (v.begin(),v.begin()+5,v.end()); std::cout << "The resulting vector contains:"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output： The resulting vector contains: 5 10 10 15 20 20 25 30 40 50 */ // Set algorithms: includes, set_union, set_intersection, set_difference, // set_symmetric_difference. All of these algorithms have the precondition // that their input ranges are sorted and the postcondition that their output // ranges are sorted. /* 下面是計算set集合的相關算法，分別是并集set_union，差集set_difference，交集set_intersection 和對稱差集set_symmetric_difference，這是個函數都提供了兩個版本的函數原型 第一個版本是采用默認的排序比較方式 operator< 第二個版本是用戶通過comp自行指定排序方式 注意：這四個算法接受的輸入區間都是有序的，輸出也是有序的 */ // Set algorithms: includes, set_union, set_intersection, set_difference, // set_symmetric_difference. All of these algorithms have the precondition // that their input ranges are sorted and the postcondition that their output // ranges are sorted. // 判斷[first1, last1)是否包含[first2, last2), // 注意: 兩個區間要保證有序,默認排序方式是operator<，若要自行定義排序方式，則調用第二版本; template <class _InputIter1, class _InputIter2> bool includes(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); while (__first1 != __last1 && __first2 != __last2)//遍歷兩個區間 if (*__first2 < *__first1)//first2小于first1表示不包含 return false;//返回FALSE else if(*__first1 < *__first2)//若first1小于first2 ++__first1;//尋找第一個區間下一個位置 else ++__first1, ++__first2;//若first2等于first1,遍歷兩區間的下一位置 return __first2 == __last2;//若第二個區間先到達尾端，則返回TRUE } //版本二：用戶通過comp自行指定排序方式 template <class _InputIter1, class _InputIter2, class _Compare> bool includes(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) return false; else if(__comp(*__first1, *__first2)) ++__first1; else ++__first1, ++__first2; return __first2 == __last2; } //兩個集合區間的并集，同樣也有兩個版本 //求存在于[first1, last1)或存在于[first2, last2)內的所有元素 //注意：輸入區間必須是已排序 /* default (1) :默認是operator<操作的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); custom (2) :用戶指定的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); */ //版本一：默認是operator<操作的排序方式 template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); //兩個區間都尚未到達區間尾端，執行以下操作 while (__first1 != __last1 && __first2 != __last2) { /* 在兩區間內分別移動迭代器，首先將元素較小者(假設為A區)記錄在目標區result 移動A區迭代器使其前進；同時另一個區的迭代器不變。然后進行一次新的比較， 記錄較小值，移動迭代器...直到兩區間中有一個到達尾端。若兩區間存在元素相等， 默認記錄第一區間的元素到目標區result. */ if (*__first1 < *__first2) {//first1小于first2 *__result = *__first1;//則result初始值為first1 ++__first1;//繼續第一個區間的下一個元素位置 } else if (*__first2 < *__first1) {//first2小于first1 *__result = *__first2;//第二區間元素值記錄到目標區 ++__first2;//移動第二區間的迭代器 } else {//若兩區間存在相等的元素，把第一區間元素記錄到目標區 //同時移動兩個區間的迭代器 *__result = *__first1; ++__first1; ++__first2; } ++__result;//更新目標區位置，以備進入下一次記錄操作操作 } /* 只要兩區間之中有一個區間到達尾端，就結束上面的while循環 以下將尚未到達尾端的區間剩余的元素拷貝到目標區 此刻，[first1, last1)和[first2, last2)至少有一個是空區間 */ return copy(__first2, __last2, copy(__first1, __last1, __result)); } //版本二：用戶根據仿函數comp指定排序規則 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first1, *__first2)) { *__result = *__first1; ++__first1; } else if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__first2; } else { *__result = *__first1; ++__first1; ++__first2; } ++__result; } return copy(__first2, __last2, copy(__first1, __last1, __result)); } /*例子: #include <iostream> // std::cout #include <algorithm> // std::set_union, std::sort #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0 std::vector<int>::iterator it; std::sort (first,first+5); // 5 10 15 20 25 std::sort (second,second+5); // 10 20 30 40 50 it=std::set_union (first, first+5, second, second+5, v.begin()); // 5 10 15 20 25 30 40 50 0 0 v.resize(it-v.begin()); // 5 10 15 20 25 30 40 50 std::cout << "The union has " << (v.size()) << " elements:\n"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: The union has 8 elements: 5 10 15 20 25 30 40 50 */ //兩個集合區間的交集，同樣也有兩個版本 //求存在于[first1, last1)且存在于[first2, last2)內的所有元素 //注意：輸入區間必須是已排序，輸出區間的每個元素的相對排序和第一個區間相對排序相同 /* default (1) :默認是operator<操作的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); custom (2) :用戶指定的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); */ //版本一：默認是operator<操作的排序方式 template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); //若兩個區間都尚未到達尾端，則執行以下操作 while (__first1 != __last1 && __first2 != __last2) //在兩個區間分別移動迭代器，直到遇到相等元素，記錄到目標區 //繼續移動迭代器...直到兩區間之中有到達尾端 if (*__first1 < *__first2) //第一個區間元素小于第二區間元素 ++__first1;//移動第一區間的迭代器，此時第二區間的迭代器不變 else if (*__first2 < *__first1) //第二區間的元素小于第一區間元素 ++__first2;//移動第二區間元素，此時第一區間的迭代器不變 else {//若第一區間元素等于第二區間元素 *__result = *__first1;//按第一區間的相對排序記錄到目標區 //分別移動兩區間的迭代器 ++__first1; ++__first2; //更新目標區迭代器，以便繼續記錄元素 ++__result; } //若有區間到達尾部，則停止while循環 //此時，返回目標區 return __result; } //版本二：用戶根據仿函數comp指定排序規則 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) ++__first1; else if (__comp(*__first2, *__first1)) ++__first2; else { *__result = *__first1; ++__first1; ++__first2; ++__result; } return __result; } /*例子： #include <iostream> // std::cout #include <algorithm> // std::set_intersection, std::sort #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0 std::vector<int>::iterator it; std::sort (first,first+5); // 5 10 15 20 25 std::sort (second,second+5); // 10 20 30 40 50 it=std::set_intersection (first, first+5, second, second+5, v.begin()); // 10 20 0 0 0 0 0 0 0 0 v.resize(it-v.begin()); // 10 20 std::cout << "The intersection has " << (v.size()) << " elements:\n"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: The intersection has 2 elements: 10 20 */ //兩個集合區間的差集，同樣也有兩個版本 //求存在于[first1, last1)但不存在于[first2, last2)內的所有元素 //注意：輸入區間必須是已排序，輸出區間的每個元素的相對排序和第一個區間相對排序相同 /* default (1) :默認是operator<操作的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); custom (2) :用戶指定的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); */ //版本一：默認是operator<操作的排序方式 template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); //若兩個區間都尚未到達尾端，則執行以下操作 while (__first1 != __last1 && __first2 != __last2) /* 在兩個區間分別移動迭代器，當第一區間元素等于第二區間元素時，表示兩區間共同存在該元素 則同時移動迭代器； 當第一區間元素大于第二區間元素時，就讓第二區間迭代器前進； 第一區間元素小于第二區間元素時，把第一區間元素記錄到目標區 繼續移動迭代器...直到兩區間之中有到達尾端 */ if (*__first1 < *__first2) {//第一區間元素小于第二區間元素 *__result = *__first1;//把第一區間元素記錄到目標區 ++__first1;//移動第一區間迭代器 ++__result;//跟新目標區，以便繼續記錄數據 } else if (*__first2 < *__first1)//當第一區間的元素大于第二區間的元素 ++__first2;//移動第二區間迭代器,注意：這里不記錄任何元素 else {//若兩區間的元素相等時,同時移動兩區間的迭代器 ++__first1; ++__first2; } //若第二區間先到達尾端，則把第一區間剩余的元素復制到目標區 return copy(__first1, __last1, __result); } //版本二：用戶根據仿函數comp指定排序規則 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { *__result = *__first1; ++__first1; ++__result; } else if (__comp(*__first2, *__first1)) ++__first2; else { ++__first1; ++__first2; } return copy(__first1, __last1, __result); } /*例子： #include <iostream> // std::cout #include <algorithm> // std::set_difference, std::sort #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0 std::vector<int>::iterator it; std::sort (first,first+5); // 5 10 15 20 25 std::sort (second,second+5); // 10 20 30 40 50 it=std::set_difference (first, first+5, second, second+5, v.begin()); // 5 15 25 0 0 0 0 0 0 0 v.resize(it-v.begin()); // 5 15 25 std::cout << "The difference has " << (v.size()) << " elements:\n"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output： The difference has 3 elements: 5 15 25 */ //兩個集合區間的對稱差集，同樣也有兩個版本 //求存在于[first1, last1)但不存在于[first2, last2)內的所有元素以及出現在[first2, last2)但不出現在[first1, last1) //注意：輸入區間必須是已排序 /* default (1) :默認是operator<操作的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); custom (2) :用戶指定的排序方式 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); */ //版本一：默認是operator<操作的排序方式 template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); //若兩個區間都尚未到達尾端，則執行下面的操作 while (__first1 != __last1 && __first2 != __last2) /* 情況1：若兩區間元素相等，則同時移動兩區間的迭代器. 情況2：若第一區間的元素小于第二區間元素，則把第一區間元素記錄到目標區，且移動第一區間迭代器. 情況3：若第一區間的元素大于第二區間元素，則把第二區間元素記錄到目標區，且移動第二區間迭代器. */ if (*__first1 < *__first2) {//屬于情況2 *__result = *__first1;//把第一區間元素記錄到目標區 ++__first1;//移動第一區間迭代器.此時第二區間迭代器不變 ++__result; } else if (*__first2 < *__first1) {//屬于情況3 *__result = *__first2;//把第二區間元素記錄到目標區 ++__first2;//移動第二區間迭代器.此時第一區間迭代器不變 ++__result; } else {//屬于情況1 //同時移動兩區間的迭代器 ++__first1; ++__first2; } /* 只要兩區間之中有一個區間到達尾端，就結束上面的while循環 以下將尚未到達尾端的區間剩余的元素拷貝到目標區 此刻，[first1, last1)和[first2, last2)至少有一個是空區間 */ return copy(__first2, __last2, copy(__first1, __last1, __result)); } //版本二：用戶根據仿函數comp指定排序規則 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { *__result = *__first1; ++__first1; ++__result; } else if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__first2; ++__result; } else { ++__first1; ++__first2; } return copy(__first2, __last2, copy(__first1, __last1, __result)); } /*例子： #include <iostream> // std::cout #include <algorithm> // std::set_symmetric_difference, std::sort #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0 std::vector<int>::iterator it; std::sort (first,first+5); // 5 10 15 20 25 std::sort (second,second+5); // 10 20 30 40 50 it=std::set_symmetric_difference (first, first+5, second, second+5, v.begin()); // 5 15 25 30 40 50 0 0 0 0 v.resize(it-v.begin()); // 5 15 25 30 40 50 std::cout << "The symmetric difference has " << (v.size()) << " elements:\n"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output： The symmetric difference has 6 elements: 5 15 25 30 40 50 */ // min_element and max_element, with and without an explicitly supplied // comparison function. //返回序列[first,last)中最大元素的位置 /* default (1):版本一 template <class ForwardIterator> ForwardIterator max_element (ForwardIterator first, ForwardIterator last); custom (2):版本二 template <class ForwardIterator, class Compare> ForwardIterator max_element (ForwardIterator first, ForwardIterator last, Compare comp); */ //版本一： template <class _ForwardIter> _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _LessThanComparable); if (__first == __last) return __first;//若為空，直接返回 _ForwardIter __result = __first;//若不為空，從第一個元素開始，即把第一個元素暫時保存為最大值 while (++__first != __last) //按順序查找最大值 if (*__result < *__first)//若有更大的值 __result = __first;//則更新最大值位置 return __result;//返回最大值位置 } //版本二 template <class _ForwardIter, class _Compare> _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, _Compare __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) if (__comp(*__result, *__first)) __result = __first; return __result; } //返回序列[first,last)中最小元素的位置 /* default (1):版本一 template <class ForwardIterator> ForwardIterator min_element (ForwardIterator first, ForwardIterator last); custom (2):版本二 template <class ForwardIterator, class Compare> ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp); */ //版本一： template <class _ForwardIter> _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _LessThanComparable); if (__first == __last) return __first;//若為空，直接返回 _ForwardIter __result = __first;//若不為空，從第一個元素開始，即把第一個元素暫時保存為最小值 while (++__first != __last) //按順序查找最小值 if (*__first < *__result)//若存在更小的值 __result = __first;//則更新最小值位置 return __result;//返回最小值位置 } //版本二 template <class _ForwardIter, class _Compare> _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, _Compare __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) if (__comp(*__first, *__result)) __result = __first; return __result; } //max_element和min_element函數舉例 /* #include <iostream> // std::cout #include <algorithm> // std::min_element, std::max_element bool myfn(int i, int j) { return i<j; } struct myclass { bool operator() (int i,int j) { return i<j; } } myobj; int main () { int myints[] = {3,7,2,5,6,4,9}; // using default comparison: std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n'; std::cout << "The largest element is " << *std::max_element(myints,myints+7) << '\n'; // using function myfn as comp: std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myfn) << '\n'; std::cout << "The largest element is " << *std::max_element(myints,myints+7,myfn) << '\n'; // using object myobj as comp: std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myobj) << '\n'; std::cout << "The largest element is " << *std::max_element(myints,myints+7,myobj) << '\n'; return 0; } Output: The smallest element is 2 The largest element is 9 The smallest element is 2 The largest element is 9 The smallest element is 2 The largest element is 9 */ // next_permutation and prev_permutation, with and without an explicitly // supplied comparison function. //next_permutation獲取[first,last)區間所標示序列的下一個排列組合，若果沒有下一個排序組合，則返回false;否則返回true; /* 函數功能：Rearranges the elements in the range [first,last) into the next lexicographically greater permutation. 函數原型： default (1) ：版本一采用less-than操作符 template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); custom (2) ：版本二采用仿函數comp決定 template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); */ //版本一 template <class _BidirectionalIter> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, _LessThanComparable); if (__first == __last) return false;//若為空，則返回false _BidirectionalIter __i = __first; ++__i; if (__i == __last)//區間只有一個元素 return false; //若區間元素個數不小于兩個 __i = __last;//i指向尾端 --__i;//不斷后移 for(;;) { //下面兩行是讓ii和i成為相鄰的元素 //其中i為第一個元素，ii為第二個元素 _BidirectionalIter __ii = __i;// --__i; //以下在相鄰元素判斷 if (*__i < *__ii) {//若前一個元素小于后一個元素， //則再從最尾端開始往前檢查，找出第一個大于*i的元素，令該元素為*j，將*i和*j交換 //再將ii之后的所有元素顛倒排序 _BidirectionalIter __j = __last;//令j指向最尾端 while (!(*__i < *--__j))//由尾端往前檢查，直到遇到比*i大的元素 {} iter_swap(__i, __j);//交換迭代器i和迭代器j所指的元素 reverse(__ii, __last);//將ii之后的元素全部逆向重排 return true; } if (__i == __first) {//進行到最前面 reverse(__first, __last);//整個區間全部逆向重排 return false; } } } //版本二 template <class _BidirectionalIter, class _Compare> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_BidirectionalIter>::value_type, typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __last) return false; _BidirectionalIter __i = __first; ++__i; if (__i == __last) return false; __i = __last; --__i; for(;;) { _BidirectionalIter __ii = __i; --__i; if (__comp(*__i, *__ii)) { _BidirectionalIter __j = __last; while (!__comp(*__i, *--__j)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; } if (__i == __first) { reverse(__first, __last); return false; } } } //next_permutation函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort int main () { int myints[] = {1,2,3,4}; std::sort (myints,myints+4); std::cout << "The 3! possible permutations with 3 elements:\n"; do { std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] <<' ' << myints[3]<< '\n'; } while ( std::next_permutation(myints,myints+4) ); //std::next_permutation(myints,myints+4); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << ' ' << myints[3]<<'\n'; return 0; } Output: The 3! possible permutations with 3 elements: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 After loop: 1 2 3 4 */ //prev_permutation獲取[first,last)區間所標示序列的上一個排列組合，若果沒有上一個排序組合，則返回false;否則返回true; /* 函數功能：Rearranges the elements in the range [first,last) into the previous lexicographically-ordered permutation. 函數原型： default (1) ：版本一采用less-than操作符 template <class BidirectionalIterator> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last ); custom (2) ：版本二采用仿函數comp template <class BidirectionalIterator, class Compare> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); */ //版本一 template <class _BidirectionalIter> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, _LessThanComparable); if (__first == __last) return false;//若區間為空，返回false _BidirectionalIter __i = __first; ++__i; if (__i == __last)//區間只有一個元素 return false;//返回false //若區間元素個數不小于兩個 __i = __last; --__i; for(;;) { //下面兩行是讓ii和i成為相鄰的元素 //其中i為第一個元素，ii為第二個元素 _BidirectionalIter __ii = __i; --__i; //以下在相鄰元素判斷 if (*__ii < *__i) {//若前一個元素大于后一個元素， //則再從最尾端開始往前檢查，找出第一個小于*i的元素，令該元素為*j，將*i和*j交換 //再將ii之后的所有元素顛倒排序 _BidirectionalIter __j = __last;//令j指向最尾端 while (!(*--__j < *__i))//由尾端往前檢查，直到遇到比*i小的元素 {} iter_swap(__i, __j); //交換迭代器i和迭代器j所指的元素 reverse(__ii, __last);//將ii之后的元素全部逆向重排 return true; } if (__i == __first) {//進行到最前面 reverse(__first, __last);//把區間所有元素逆向重排 return false; } } } //版本二 template <class _BidirectionalIter, class _Compare> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_BidirectionalIter>::value_type, typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __last) return false; _BidirectionalIter __i = __first; ++__i; if (__i == __last) return false; __i = __last; --__i; for(;;) { _BidirectionalIter __ii = __i; --__i; if (__comp(*__ii, *__i)) { _BidirectionalIter __j = __last; while (!__comp(*--__j, *__i)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; } if (__i == __first) { reverse(__first, __last); return false; } } } //prev_permutation函數舉例 /* #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort, std::reverse int main () { int myints[] = {1,2,3}; std::sort (myints,myints+3); std::reverse (myints,myints+3); std::cout << "The 3! possible permutations with 3 elements:\n"; do { std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; } while ( std::prev_permutation(myints,myints+3) ); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; return 0; } Output: The 3! possible permutations with 3 elements: 3 2 1 3 1 2 2 3 1 2 1 3 1 3 2 1 2 3 After loop: 3 2 1 */ // 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 */ // is_heap, a predicate testing whether or not a range is // a heap. This function is an extension, not part of the C++ // standard. template <class _RandomAccessIter, class _Distance> bool __is_heap(_RandomAccessIter __first, _Distance __n) { _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { if (__first[__parent] < __first[__child]) return false; if ((__child & 1) == 0) ++__parent; } return true; } template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering> bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, _Distance __n) { _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { if (__comp(__first[__parent], __first[__child])) return false; if ((__child & 1) == 0) ++__parent; } return true; } template <class _RandomAccessIter> inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); return __is_heap(__first, __last - __first); } template <class _RandomAccessIter, class _StrictWeakOrdering> inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, _StrictWeakOrdering __comp) { __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); return __is_heap(__first, __comp, __last - __first); } // is_sorted, a predicated testing whether a range is sorted in // nondescending order. This is an extension, not part of the C++ // standard. template <class _ForwardIter> bool is_sorted(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _LessThanComparable); if (__first == __last) return true; _ForwardIter __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { if (*__next < *__first) return false; } return true; } template <class _ForwardIter, class _StrictWeakOrdering> bool is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return true; _ForwardIter __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { if (__comp(*__next, *__first)) return false; } return true; } #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1209 #endif __STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_ALGO_H */ // Local Variables: // mode:C++ // End: ~~~ 參考資料： 《STL源碼剖析》侯捷