前言
在前面的博文中剖析了STL的数值算法、基本算法和set集合算法，本文剖析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 << "
";
// or:
std::cout << "myvector contains:";
for_each (myvector.begin(), myvector.end(), myobject);
std::cout << "
";
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 << "
";
// 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 << "
";
else
std::cout << "Element not found in myints
";
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 << "
";
//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 << "
";
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.
";
// 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.
";
mycount = count_if (myvector.begin(), myvector.end(), IsOdd);
std::cout << "myvector contains " << mycount << " odd values.
";
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()) << "
";
else
std::cout << "match not found
";
// 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()) << "
";
else
std::cout << "match not found
";
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()) << "
";
else
std::cout << "needle1 not found
";
// 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()) << "
";
else
std::cout << "needle2 not found
";
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 << "
";
std::cout << "bar contains:";
for (std::vector<int>::iterator it=bar.begin(); it!=bar.end(); ++it)
std::cout << " " << *it;
std::cout << "
";
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 << "
";
// 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 << "
";
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 << "
";
std::cout <<"the value of current: "<<current;
std::cout << "
";
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 << "
";
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 << "
";
// 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 << "
";
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 << "
";
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 << "
";
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的放在区间的前段，判
- 上一篇：STL算法之set集合算法
- 下一篇：STL算法之sort排序算法
- 文章导航