6.7.1 单纯的数据处理

1、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,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 
 
*/  

2、count和count_if

//count：计算指定元素的个数  
//count_if：计算满足仿函数pred的条件的元素的个数
//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++标准，计数n由参数提供：默认使用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,UnaryPredicate pred); 
*/  
//SGI STL提供的版本一count_if，不是C++标准：默认使用operator==  
template <class _InputIter,class _Predicate,class _Size>  
void count_if(_InputIter __first,_Predicate __pred,_InputIterator);  
  __STL_UNARY_FUNCTION_CHECK(_Predicate,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,const _Tp& __value) {  
  __STL_REQUIRES(_InputIter,_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,_Predicate __pred) {  
  __STL_REQUIRES(_InputIter,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,31,21,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(),20); 
      std::cout << "20 appears " << mycount  << " times.n"; 
   
      mycount = count_if (myvector.begin(),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. 
*/  

3、?find?和?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,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,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,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,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,const T& val); 
*/  
//find函数对外接口  
template <class _InputIter,const _Tp& __val)  
{  
  __STL_REQUIRES(_InputIter,_InputIterator);  
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL,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,UnaryPredicate pred); 
*/  
//find_if 函数对外接口  
template <class _InputIter,typename iterator_traits<_InputIter>::value_type);  
  //首先萃取出first迭代器的类型，根据迭代器的类型调用不同的函数  
  return find_if(__first,__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(),IsOdd); 
      std::cout << "The first odd value is " << *it << 'n'; 
 
      // using std::find with vector and iterator: 
      it = find (myvector.begin(),40); 
      if (it != myvector.end()) 
        std::cout << "Element found in myvector: " << *it << 'n'; 
      else 
        std::cout << "Element not found in myintsn"; 
 
      return 0; 
    } 
    Output: 
    The first odd value is 25 
    Element found in myvector: 40 
  
*/  

4、find_end

//在序列[first1,last1)中查找序列[first2,last2)最后一次出现的位置
// find_end for forward iterators.   
//若萃取出来的迭代器类型为正向迭代器forward_iterator_tag，则调用此函数  
template <class _ForwardIter1,class _ForwardIter2>  
_ForwardIter1 __find_end(_ForwardIter1 __first1,_ForwardIter1 __last1,_ForwardIter2 __first2,_ForwardIter2 __last2,forward_iterator_tag,forward_iterator_tag)  
{  
  if (__first2 == __last2)//若第二个区间为空  
    return __last1;//则直接返回第一个区间的尾端  
  else {  
    _ForwardIter1 __result = __last1;  
    while (1) {  
        //以下利用search函数查找出某个子序列的首次出现点；若找不到直接返回last1  
      _ForwardIter1 __new_result  
  
        = search(__first1,__last1,__first2,__last2);  
      if (__new_result == __last1)//若返回的位置为尾端，则表示没找到  
        return __result;//返回last1  
      else {//若在[first1,last1)中找到[first2,last2)首次出现的位置，继续准备下一次查找  
            
        __result = __new_result;//更新返回的位置  
        __first1 = __new_result;//更新查找的起始位置  
        ++__first1;//确定正确查找起始位置  
      }  
    }  
  }  
}  
//版本二：指定规则  
template <class _ForwardIter1,class _ForwardIter2,class _BinaryPredicate>  
_ForwardIter1 __find_end(_ForwardIter1 __first1,_BinaryPredicate __comp)  
{  
  if (__first2 == __last2)  
    return __last1;  
  else {  
    _ForwardIter1 __result = __last1;  
    while (1) {  
      _ForwardIter1 __new_result  
        = search(__first1,__last2,__comp);  
      if (__new_result == __last1)  
        return __result;  
      else {  
        __result = __new_result;  
        __first1 = __new_result;  
        ++__first1;  
      }  
    }  
  }  
}  
  
// find_end for bidirectional iterators.  Requires partial specialization.  
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION  
//若萃取出来的迭代器类型为双向迭代器bidirectional_iterator_tag，则调用此函数  
template <class _BidirectionalIter1,class _BidirectionalIter2>  
_BidirectionalIter1  
__find_end(_BidirectionalIter1 __first1,_BidirectionalIter1 __last1,_BidirectionalIter2 __first2,_BidirectionalIter2 __last2,bidirectional_iterator_tag,bidirectional_iterator_tag)  
{  
  __STL_REQUIRES(_BidirectionalIter1,_BidirectionalIterator);  
  __STL_REQUIRES(_BidirectionalIter2,_BidirectionalIterator);  
  //利用反向迭代器很快就可以找到  
  typedef reverse_iterator<_BidirectionalIter1> _RevIter1;  
  typedef reverse_iterator<_BidirectionalIter2> _RevIter2;  
  
  _RevIter1 __rlast1(__first1);  
  _RevIter2 __rlast2(__first2);  
  //查找时将序列一和序列二逆方向  
  _RevIter1 __rresult = search(_RevIter1(__last1),__rlast1,_RevIter2(__last2),__rlast2);  
  
  if (__rresult == __rlast1)//表示没找到  
    return __last1;  
  else {//找到了  
    _BidirectionalIter1 __result = __rresult.base();//转会正常迭代器  
    advance(__result,-distance(__first2,__last2));//调整回到子序列的起始位置  
    return __result;  
  }  
}  
//版本二：指定规则comp  
template <class _BidirectionalIter1,class _BidirectionalIter2,class _BinaryPredicate>  
_BidirectionalIter1  
__find_end(_BidirectionalIter1 __first1,_BinaryPredicate __comp)  
{  
  __STL_REQUIRES(_BidirectionalIter1,_BidirectionalIterator);  
  typedef reverse_iterator<_BidirectionalIter1> _RevIter1;  
  typedef reverse_iterator<_BidirectionalIter2> _RevIter2;  
  
  _RevIter1 __rlast1(__first1);  
  _RevIter2 __rlast2(__first2);  
  _RevIter1 __rresult = search(_RevIter1(__last1),__rlast2,__comp);  
  
  if (__rresult == __rlast1)  
    return __last1;  
  else {  
    _BidirectionalIter1 __result = __rresult.base();  
    advance(__result,__last2));  
    return __result;  
  }  
}  
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */  
  
// Dispatching functions for find_end.  
//find_end函数有两个版本：  
//版本一：提供默认的equality操作operator==  
//版本二：提供用户自行指定的操作规则comp  
//注意：这里也有偏特化的知识  
/*函数功能：Searches the range [first1,last1) for the last occurrence of the sequence defined by [first2,last2),and returns an iterator to its first element,or last1 if no occurrences are found. 
函数原型： 
equality (1)：版本一     
    template <class ForwardIterator1,class ForwardIterator2> 
    ForwardIterator1 find_end (ForwardIterator1 first1,ForwardIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2); 
predicate (2)：版本二 
    template <class ForwardIterator1,class ForwardIterator2,class BinaryPredicate> 
    ForwardIterator1 find_end (ForwardIterator1 first1,ForwardIterator2 last2,BinaryPredicate pred); 
*/  
//对外接口的版本一  
template <class _ForwardIter1,class _ForwardIter2>  
inline _ForwardIter1   
find_end(_ForwardIter1 __first1,_ForwardIter2 __last2)  
{  
  __STL_REQUIRES(_ForwardIter1,_ForwardIterator);  
  __STL_REQUIRES(_ForwardIter2,_ForwardIterator);  
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL,typename iterator_traits<_ForwardIter1>::value_type,typename iterator_traits<_ForwardIter2>::value_type);  
  //首先通过iterator_traits萃取出first1和first2的迭代器类型  
  //根据不同的迭代器类型调用不同的函数  
  return __find_end(__first1,__ITERATOR_CATEGORY(__first1),__ITERATOR_CATEGORY(__first2));  
}  
//对外接口的版本一  
template <class _ForwardIter1,class _BinaryPredicate>  
inline _ForwardIter1   
find_end(_ForwardIter1 __first1,_BinaryPredicate __comp)  
{  
  __STL_REQUIRES(_ForwardIter1,__ITERATOR_CATEGORY(__first2),__comp);  
}  
//find_end函数举例：  
/* 
    #include <iostream>     // std::cout 
    #include <algorithm>    // std::find_end 
    #include <vector>       // std::vector 
 
    bool myfunction (int i,int j) { 
      return (i==j); 
    } 
 
    int main () { 
      int myints[] = {1,2,3,4,1,5}; 
      std::vector<int> haystack (myints,myints+10); 
 
      int needle1[] = {1,3}; 
 
      // using default comparison: 
      std::vector<int>::iterator it; 
      it = std::find_end (haystack.begin(),haystack.end(),needle1,needle1+3); 
 
      if (it!=haystack.end()) 
        std::cout << "needle1 last found at position " << (it-haystack.begin()) << 'n'; 
 
      int needle2[] = {4,1}; 
 
      // using predicate comparison: 
      it = std::find_end (haystack.begin(),needle2,needle2+3,myfunction); 
 
      if (it!=haystack.end()) 
        std::cout << "needle2 last found at position " << (it-haystack.begin()) << 'n'; 
 
      return 0; 
    } 
    Output: 
    needle1 found at position 5 
    needle2 found at position 3 
*/  
 

5、?find_first_of

// find_first_of,with and without an explicitly supplied comparison function.  
//以[first2,last2)区间内的某些元素为查找目标，寻找他们在[first1,last1)区间首次出现的位置  
//find_first_of函数有两个版本：  
//版本一：提供默认的equality操作operator==  
//版本二：提供用户自行指定的操作规则comp  
/* 
函数功能：Returns an iterator to the first element in the range [first1,last1) that matches any of the elements in [first2,last2).  
If no such element is found,the function returns last1. 
函数原型： 
equality (1)：版本一     
    template <class ForwardIterator1,class ForwardIterator2> 
    ForwardIterator1 find_first_of (ForwardIterator1 first1,ForwardIterator2 last2); 
predicate (2)：版本二    
    template <class ForwardIterator1,class BinaryPredicate> 
    ForwardIterator1 find_first_of (ForwardIterator1 first1,BinaryPredicate pred); 
*/  
//版本一：提供默认的equality操作operator==  
template <class _InputIter,class _ForwardIter>  
_InputIter find_first_of(_InputIter __first1,_InputIter __last1,_ForwardIter __first2,_ForwardIter __last2)  
{  
  __STL_REQUIRES(_InputIter,_InputIterator);  
  __STL_REQUIRES(_ForwardIter,typename iterator_traits<_ForwardIter>::value_type);  
  
  for ( ; __first1 != __last1; ++__first1) //若序列一不为空，则遍历序列一，每次指定一个元素  
      //以下，根据序列二的每个元素  
    for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)  
      if (*__first1 == *__iter)//若序列一的元素等于序列二的元素，则表示找到  
        return __first1;//返回找到的位置  
  return __last1;//否则没找到  
}  
//版本二：提供用户自行指定的操作规则comp  
template <class _InputIter,class _ForwardIter,class _BinaryPredicate>  
_InputIter find_first_of(_InputIter __first1,_ForwardIter __last2,_BinaryPredicate __comp)  
{  
  __STL_REQUIRES(_InputIter,typename iterator_traits<_ForwardIter>::value_type);  
  
  for ( ; __first1 != __last1; ++__first1)   
    for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)  
      if (__comp(*__first1,*__iter))  
        return __first1;  
  return __last1;  
}  
//find_first_of函数举例：  
/* 
    #include <iostream>     // std::cout 
    #include <algorithm>    // std::find_first_of 
    #include <vector>       // std::vector 
    #include <cctype>       // std::tolower 
 
    bool comp_case_insensitive (char c1,char c2) { 
      return (std::tolower(c1)==std::tolower(c2)); 
    } 
 
    int main () { 
      int mychars[] = {'a','b','c','A','B','C'}; 
      std::vector<char> haystack (mychars,mychars+6); 
      std::vector<char>::iterator it; 
 
      int needle[] = {'A','C'}; 
 
      // using default comparison: 
      it = find_first_of (haystack.begin(),needle,needle+3); 
 
      if (it!=haystack.end()) 
        std::cout << "The first match is: " << *it << 'n'; 
 
      // using predicate comparison: 
      it = find_first_of (haystack.begin(),needle+3,comp_case_insensitive); 
 
      if (it!=haystack.end()) 
        std::cout << "The first match is: " << *it << 'n'; 
 
      return 0; 
    } 
    Output: 
    The first match is: A 
    The first match is: a