首页 > 代码库 > STL源码剖析——STL算法stl_algo.h
STL源码剖析——STL算法stl_algo.h
前言
在前面的博文中剖析了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 << '\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 = http://www.mamicode.com/*__first;>参考资料：《STL源码剖析》侯捷
STL源码剖析——STL算法stl_algo.h
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。