1、? for_each

将仿函数f施行于区间内的每一个元素上，但f不能改变元素的内容

// 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(),myobject); 
      std::cout << 'n'; 
 
      return 0; 
    } 
    Output: 
    myvector contains: 10 20 30 
    myvector contains: 10 20 30 
*/  

2、generate和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 
#include<vector>
 
    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(),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 
*/  

?

3、includes

判断区间[first1,?last1)是否包含区间[first2,?last2)（注：两区间都必须有序），主要用于求set的计算，详情参考上一节：http://www.voidcn.com/article/p-hjkddlmd-gw.html。

// 判断[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,_InputIter2 __last2,_Compare __comp) {  
  __STL_REQUIRES(_InputIter1,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;  
}  

?4、max_element和min_element

//返回序列[first,last)中最大元素（最小元素）的位置  
// 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,_Compare __comp) {  
  __STL_REQUIRES(_ForwardIter,_ForwardIterator);  
  __STL_BINARY_FUNCTION_CHECK(_Compare,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,class Compare> 
    ForwardIterator min_element (ForwardIterator first,Compare comp); 
*/  
//版本一：  
template <class _ForwardIter>  
_ForwardIter min_element(_ForwardIter __first,_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,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,myfn) << 'n'; 
 
      // using object myobj as comp: 
      std::cout << "The smallest element is " << *std::min_element(myints,myobj) << 'n'; 
      std::cout << "The largest element is "  << *std::max_element(myints,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 
*/  

5、merge

// merge,with and without an explicitly supplied comparison function.  
//将两个已排序的区间[first1,last1)和区间[first2,last2)合并  
/* 
函数功能：Combines the elements in the sorted ranges [first1,last1) and [first2,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 OutputIterator,class Compare> 
    OutputIterator merge (InputIterator1 first1,OutputIterator result,Compare comp); 
*/  
//版本一：  
template <class _InputIter1,class _OutputIter>  
_OutputIter merge(_InputIter1 __first1,_OutputIter __result) {  
  __STL_REQUIRES(_InputIter1,_InputIterator);  
  __STL_REQUIRES(_OutputIter,_OutputIterator);  
  __STL_REQUIRES_SAME_TYPE(  
          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,last2)至少一个必定为空  
  return copy(__first2,__last2,copy(__first1,__last1,__result));  
}  
//版本二  
template <class _InputIter1,class _OutputIter,class _Compare>  
_OutputIter merge(_InputIter1 __first1,_OutputIter __result,_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,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,__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,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 
*/  

6、?partition

//将区间[first,last)的元素进行排序，被pred判断为true的放在区间的前段，判定为false的
//放在区间后段 ，该算法会使元素的位置放生改变，而且会改变元素的原始相对位置
//若迭代器的类型为forward_iterator_tag，则调用此函数  
template <class _ForwardIter,class _Predicate>  
_ForwardIter __partition(_ForwardIter __first,_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,_Predicate   __pred) {  
  __STL_REQUIRES(_ForwardIter,_Mutable_ForwardIterator);  
  __STL_UNARY_FUNCTION_CHECK(_Predicate,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(),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 
  
*/  

7、remove_copy

移除[first,last)区间内所有与value值相等的元素，并不是真正的从容器中删除这些元素(原容器的内容不会改变)??，而是将结果复制到一个以result为起始位置的容器中。新容器可以与原容器重叠??。

template <class _InputIter,class _Tp>  
_OutputIter remove_copy(_InputIter __first,const _Tp& __value) {  
  __STL_REQUIRES(_InputIter,_OutputIterator);  
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL,typename iterator_traits<_InputIter>::value_type,_Tp);  
  for ( ; __first != __last; ++__first)//遍历容器  
    if (!(*__first == __value)) {//如果不相等  
      *__result = *__first;//赋值给新容器  
      ++__result;//新容器前进一个位置  
    }  
  return __result;  
}  

8、?remove

移除[first,last)区间内所有与value值相等的元素,该操作不会改变容器大小，只是容器中元素值改变。相当于重新整理容器的内容?，非value值都放在了容器前面。

如下图所示：

template <class _ForwardIter,class _Tp>  
_ForwardIter remove(_ForwardIter __first,const _Tp& __value) {  
  __STL_REQUIRES(_ForwardIter,_Mutable_ForwardIterator);  
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL,_Tp);  
  __STL_CONVERTIBLE(_Tp,typename iterator_traits<_ForwardIter>::value_type);  
  __first = find(__first,__value);//利用顺序查找找出第一个与value相等的元素  
  _ForwardIter __i = __first;  
  //下面调用remove_copy  
  return __first == __last ? __first   
                           : remove_copy(++__i,__first,__value);  
}  

9、remove_copy_if????

移除[first,last)区间内被仿函数pred判断为true的元素,并不是真正的从容器中删除这些元素(原容器的内容不会改变)??。而是将结果复制到一个以result为起始位置的容器中。新容器可以与原容器重叠??

template <class _InputIter,class _Predicate>  
_OutputIter remove_copy_if(_InputIter __first,_Predicate __pred) {  
  __STL_REQUIRES(_InputIter,_OutputIterator);  
  __STL_UNARY_FUNCTION_CHECK(_Predicate,typename iterator_traits<_InputIter>::value_type);  
  for ( ; __first != __last; ++__first)//遍历容器  
    if (!__pred(*__first)) {//若pred判断为false  
      *__result = *__first;//赋值给新容器  
      ++__result;//新容器前进一个位置  
    }  
  return __result;  
}  

10、remove_if

移除[first,last)区间内所有被pred判断为true的元素,该操作不会改变容器大小，只是容器中元素值改变??。即移除之后，重新整理容器的内容??

template <class _ForwardIter,class _Predicate>  
_ForwardIter remove_if(_ForwardIter __first,_Predicate __pred) {  
  __STL_REQUIRES(_ForwardIter,typename iterator_traits<_ForwardIter>::value_type);  
  __first = find_if(__first,__pred);//利用顺序查找找出第一个与value相等的元素  
  _ForwardIter __i = __first;  
  //下面调用remove_copy_if  
  return __first == __last ? __first   
                           : remove_copy_if(++__i,__pred);  
}  
//上面四个移除函数举例：  
/* 
    #include <iostream>     // std::cout 
    #include <algorithm>    // std::remove 
  #include<vector>
 
    bool IsOdd (int i) { return ((i%2)==1); } 
 
    int main () { 
      int myints[] = {10,31,11,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,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,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 
*/