C++ 学习系列 -- 标准库常用得 algorithm function

一   前言

c++ 标准库中提供了许多操作数据结构：vector、list、deque、map、set 等函数，学习并了解这些常用函数对于我们理解 c++ 的一些设计模式有着重要的作用。

二  常用的 algorithm function 源码

源代码位置：

bits/stl_algo.h

1.  accumulate

/***  @brief  Accumulate values in a range.**  Accumulates the values in the range [first,last) using operator+().  The*  initial value is @a init.  The values are processed in order.**  @param  __first  Start of range.*  @param  __last  End of range.*  @param  __init  Starting value to add other values to.*  @return  The final sum.*/
template<typename _InputIterator, typename _Tp>inline _Tpaccumulate(_InputIterator __first, _InputIterator __last, _Tp __init){for (; __first != __last; ++__first)__init = __init + *__first;return __init;}/***  @brief  Accumulate values in a range with operation.**  Accumulates the values in the range [first,last) using the function*  object @p __binary_op.  The initial value is @p __init.  The values are*  processed in order.**  @param  __first  Start of range.*  @param  __last  End of range.*  @param  __init  Starting value to add other values to.*  @param  __binary_op  Function object to accumulate with.*  @return  The final sum.*/template<typename _InputIterator, typename _Tp, typename _BinaryOperation>inline _Tpaccumulate(_InputIterator __first, _InputIterator __last, _Tp __init,_BinaryOperation __binary_op){for (; __first != __last; ++__first)__init = __binary_op(__init, *__first);return __init;}

accumulate 函数又两个重载版本：

第一个函数的第三个参数是初始值，是单纯的将 数据累加到初始值 init 上；

第二个函数的第三个参数是 “累加”  的初始值，第四个参数是函数或者仿函数对象，是可以自定义 “累加” 的函数 binary_op ，该函数的作用是将迭代器中的每个元素都执行一遍 binar_op 后，将结果 “累加” 到 初始值 init 上

2. for_each

 /***  @brief Apply a function to every element of a sequence.*  @ingroup non_mutating_algorithms*  @param  __first  An input iterator.*  @param  __last   An input iterator.*  @param  __f      A unary function object.*  @return   @p __f**  Applies the function object @p __f to each element in the range*  @p [first,last).  @p __f must not modify the order of the sequence.*  If @p __f has a return value it is ignored.*/template<typename _InputIterator, typename _Function>_Functionfor_each(_InputIterator __first, _InputIterator __last, _Function __f){for (; __first != __last; ++__first)__f(*__first);return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.}

      for_each 函数第三个函数是函数或者仿函数对象，该函数作用是遍历迭代器，并对迭代器中的每个元素分别执行一次 _Function ，_Function 可以用户自定义

3. replace/replace_if

/***  @brief Replace each occurrence of one value in a sequence with another*         value.*  @ingroup mutating_algorithms*  @param  __first      A forward iterator.*  @param  __last       A forward iterator.*  @param  __old_value  The value to be replaced.*  @param  __new_value  The replacement value.*  @return   replace() returns no value.**  For each iterator @c i in the range @p [__first,__last) if @c *i ==*  @p __old_value then the assignment @c *i = @p __new_value is performed.*/template<typename _ForwardIterator, typename _Tp>voidreplace(_ForwardIterator __first, _ForwardIterator __last,const _Tp& __old_value, const _Tp& __new_value){for (; __first != __last; ++__first)if (*__first == __old_value)*__first = __new_value;}/***  @brief Replace each value in a sequence for which a predicate returns*         true with another value.*  @ingroup mutating_algorithms*  @param  __first      A forward iterator.*  @param  __last       A forward iterator.*  @param  __pred       A predicate.*  @param  __new_value  The replacement value.*  @return   replace_if() returns no value.**  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)*  is true then the assignment @c *i = @p __new_value is performed.*/template<typename _ForwardIterator, typename _Predicate, typename _Tp>voidreplace_if(_ForwardIterator __first, _ForwardIterator __last,_Predicate __pred, const _Tp& __new_value){for (; __first != __last; ++__first)if (__pred(*__first))*__first = __new_value;}

    3.1  replace 函数 第三个参数传入的是待被替换的旧值，第四个参数是 被替换后的新值，该函数执行后，会把迭代器中所有值等于旧值得元素都替换为新值

    3.2  replace_if 函数第三个参数是一个函数对象，第四个参数是替换后得新值。该函数得作用是将迭代器中所有符合传入函数规则得旧值替换为新值。

4. count/count_if

template<typename _InputIterator, typename _Predicate>typename iterator_traits<_InputIterator>::difference_type__count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred){typename iterator_traits<_InputIterator>::difference_type __n = 0;for (; __first != __last; ++__first)if (__pred(__first))++__n;return __n;}/***  @brief Count the number of copies of a value in a sequence.*  @ingroup non_mutating_algorithms*  @param  __first  An input iterator.*  @param  __last   An input iterator.*  @param  __value  The value to be counted.*  @return   The number of iterators @c i in the range @p [__first,__last)*  for which @c *i == @p __value*/template<typename _InputIterator, typename _Tp>inline typename iterator_traits<_InputIterator>::difference_typecount(_InputIterator __first, _InputIterator __last, const _Tp& __value){return std::__count_if(__first, __last,__gnu_cxx::__ops::__iter_equals_val(__value));}/***  @brief Count the elements of a sequence for which a predicate is true.*  @ingroup non_mutating_algorithms*  @param  __first  An input iterator.*  @param  __last   An input iterator.*  @param  __pred   A predicate.*  @return   The number of iterators @c i in the range @p [__first,__last)*  for which @p __pred(*i) is true.*/template<typename _InputIterator, typename _Predicate>inline typename iterator_traits<_InputIterator>::difference_typecount_if(_InputIterator __first, _InputIterator __last, _Predicate __pred){return std::__count_if(__first, __last,__gnu_cxx::__ops::__pred_iter(__pred));}

   1. __count_if 函数第三个传入参数是一个函数或者仿函数对象，该函数的作用是遍历迭代器，统计有符合传入函数的元素个数

  2. count 函数第三个参数是一个值，该函数作用是遍历迭代器，统计与传入值相等的元素个数

  3. count_if 直接调用了 __count_if ，作用与 1 中描述相同

5. find/find_if

 /// This is an overload used by find algos for the Input Iterator case.template<typename _InputIterator, typename _Predicate>inline _InputIterator__find_if(_InputIterator __first, _InputIterator __last,_Predicate __pred, input_iterator_tag){while (__first != __last && !__pred(__first))++__first;return __first;}/// This is an overload used by find algos for the RAI case.template<typename _RandomAccessIterator, typename _Predicate>_RandomAccessIterator__find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,_Predicate __pred, random_access_iterator_tag){typename iterator_traits<_RandomAccessIterator>::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;}}template<typename _Iterator, typename _Predicate>inline _Iterator__find_if(_Iterator __first, _Iterator __last, _Predicate __pred){return __find_if(__first, __last, __pred,std::__iterator_category(__first));}/***  @brief Find the first occurrence of a value in a sequence.*  @ingroup non_mutating_algorithms*  @param  __first  An input iterator.*  @param  __last   An input iterator.*  @param  __val    The value to find.*  @return   The first iterator @c i in the range @p [__first,__last)*  such that @c *i == @p __val, or @p __last if no such iterator exists.*/template<typename _InputIterator, typename _Tp>inline _InputIteratorfind(_InputIterator __first, _InputIterator __last,const _Tp& __val){return std::__find_if(__first, __last,__gnu_cxx::__ops::__iter_equals_val(__val));}/***  @brief Find the first element in a sequence for which a*         predicate is true.*  @ingroup non_mutating_algorithms*  @param  __first  An input iterator.*  @param  __last   An input iterator.*  @param  __pred   A predicate.*  @return   The first iterator @c i in the range @p [__first,__last)*  such that @p __pred(*i) is true, or @p __last if no such iterator exists.*/template<typename _InputIterator, typename _Predicate>inline _InputIteratorfind_if(_InputIterator __first, _InputIterator __last,_Predicate __pred){return std::__find_if(__first, __last,__gnu_cxx::__ops::__pred_iter(__pred));}

    1.  第一个 __find_if 函数的第三个参数是函数或者仿函数，第四个参数是 input_iterator_tag (该参数连对应的变量都没有，只有一个类型，其主要作用是为了在重载时与第二个 __find_if 进行区分，毕竟 顺序迭代查找与可以随机访问的查找效率上是不同的)，该函数的作用是遍历迭代器，从中找出与传入值相等的元素，若是存在则返回该元素的迭代器，否则返回 _last

 2. 第二个 __find_if 函数的第三个参数是 函数或者仿函数，第四个参数是 random_access_iterator_tag (该参数连对应的变量都没有，只有一个类型，其主要作用是为了在重载时与第二个 __find_if 进行区分，毕竟 顺序迭代查找与可以随机访问的查找效率上是不同的)，该函数的作用是历迭代器，从中找出与传入值相等的元素，若是存在则返回该元素的迭代器，否则返回 _last，效率上应该比第一个 __find_if 高一些。

3. 第三个 __find_if 函数的第三个参数是 函数或者仿函数，该函数的作用是个中转，其底层调用的是第一个或者第二个函数，只不过多了个询问迭代器类型的操作：std::__iterator_category

4. find 函数第三个参数 const _Tp&是传入一个待查找的值，该函数的作用是若是查找到与该值相等的元素，则返回对应的迭代器，否则返回 __last

5. find_if  函数的第三个参数是 函数或者仿函数，该函数底层调用的是第三个函数 __find_if ，该函数的作用是若是查到元素符合传入的函数规则则返回该元素的迭代器，否则返回 __last

6. sort

待补充

7. binary_search

template<typename _ForwardIterator, typename _Tp, typename _Compare>_ForwardIterator__lower_bound(_ForwardIterator __first, _ForwardIterator __last,const _Tp& __val, _Compare __comp){typedef typename iterator_traits<_ForwardIterator>::difference_type_DistanceType;_DistanceType __len = std::distance(__first, __last);while (__len > 0){_DistanceType __half = __len >> 1;_ForwardIterator __middle = __first;std::advance(__middle, __half);if (__comp(__middle, __val)){__first = __middle;++__first;__len = __len - __half - 1;}else__len = __half;}return __first;}/***  @brief Finds the first position in which @a val could be inserted*         without changing the ordering.*  @param  __first   An iterator.*  @param  __last    Another iterator.*  @param  __val     The search term.*  @return         An iterator pointing to the first element <em>not less*                  than</em> @a val, or end() if every element is less than *                  @a val.*  @ingroup binary_search_algorithms*/template<typename _ForwardIterator, typename _Tp>inline _ForwardIteratorlower_bound(_ForwardIterator __first, _ForwardIterator __last,const _Tp& __val){return std::__lower_bound(__first, __last, __val,__gnu_cxx::__ops::__iter_less_val());}/***  @brief Determines whether an element exists in a range.*  @ingroup binary_search_algorithms*  @param  __first   An iterator.*  @param  __last    Another iterator.*  @param  __val     The search term.*  @return True if @p __val (or its equivalent) is in [@p*  __first,@p __last ].**  Note that this does not actually return an iterator to @p __val.  For*  that, use std::find or a container's specialized find member functions.*/template<typename _ForwardIterator, typename _Tp>boolbinary_search(_ForwardIterator __first, _ForwardIterator __last,const _Tp& __val){_ForwardIterator __i= std::__lower_bound(__first, __last, __val,__gnu_cxx::__ops::__iter_less_val());return __i != __last && !(__val < *__i);}/***  @brief Determines whether an element exists in a range.*  @ingroup binary_search_algorithms*  @param  __first   An iterator.*  @param  __last    Another iterator.*  @param  __val     The search term.*  @param  __comp    A functor to use for comparisons.*  @return  True if @p __val (or its equivalent) is in @p [__first,__last].**  Note that this does not actually return an iterator to @p __val.  For*  that, use std::find or a container's specialized find member functions.**  The comparison function should have the same effects on ordering as*  the function used for the initial sort.*/template<typename _ForwardIterator, typename _Tp, typename _Compare>boolbinary_search(_ForwardIterator __first, _ForwardIterator __last,const _Tp& __val, _Compare __comp){_ForwardIterator __i= std::__lower_bound(__first, __last, __val,__gnu_cxx::__ops::__iter_comp_val(__comp));return __i != __last && !bool(__comp(__val, *__i));}

1. 第一个 binary_search 函数的  三个参数 __val 是查找的目标值，该函数的作用是利用二分查找法查找目标值，若是查找到目标值，则返回 true，否则返回 false

2. 第二个 binar_search 函数的第三个参数 __val 是查找的目标值 ，第四个参数 __comp   是函数或者仿函数对象，该函数 是利用二分查找法查找目标值，若是查找到某个值使得 __comp(__val, target) 返回 true，则说明查到了目标值，此时返回 true，否则返回 法拉瑟

三   示例

#include<iostream>
#include<algorithm>using namespace std;struct PredicateReplace: public std::unary_function<int, bool>
{bool operator()(const int x) const{return x % 3 == 0;}
};struct PredictCount: public std::unary_function<int, bool>
{bool operator()(int x){return x % 3 == 1;}
};struct PredictBinarySearch:public std::binary_function<int, int, bool>
{bool operator()(int x, int y){std::cout << "x: " << x << ", y: " << y << std::endl;return x < y;}};int main()
{std::vector<int> vec = {10, 50, 60, 20, 30, 40};int init = 0;// 1. accumulatestd::cout << "------ test accumulate ------" << std::endl;std::cout << std::accumulate(vec.begin(), vec.end(), init) << std::endl; // 210init = 600;std::cout << std::accumulate(vec.begin(), vec.end(), init, std::minus<int>()) << std::endl; // 390std::cout << "------ test accumulate ------" << std::endl;// 2. for_eachstruct printVal{void operator()(int x){std::cout << x << " ";}};std::cout << "------ test for_each ------" << std::endl;std::for_each(vec.begin(), vec.end(),printVal());cout << endl;std::cout << "------ test for_each ------" << std::endl;// 3. replace  replace_ifstd::cout << "------ test replace ------" << std::endl;std::replace(vec.begin(), vec.end(), 50, 90);std::for_each(vec.begin(), vec.end(),printVal());cout << endl;std::vector<int> vec_replace1 = vec;std::replace_if(vec_replace1.begin(), vec_replace1.end(), PredicateReplace(), 666);std::for_each(vec_replace1.begin(), vec_replace1.end(),printVal());cout << endl;PredicateReplace pp;std::vector<int> vec_replace2 = vec;std::replace_if(vec_replace2.begin(), vec_replace2.end(), std::not1(pp), 666);std::for_each(vec_replace2.begin(), vec_replace2.end(),printVal());cout << endl;std::cout << "------ test replace ------" << std::endl;// 4. count  count_ifstd::cout << "------ test count ------" << std::endl;std::vector<int> vec_cout1 = vec;std::cout << std::count(vec_cout1.begin(), vec_cout1.end(), 60) << std::endl;std::cout << std::count_if(vec_cout1.begin(), vec_cout1.end(), PredictCount()) << std::endl;std::cout << "------ test count ------" << std::endl;// 5. find  find_ifstd::cout << "------ test find ------" << std::endl;auto iter = std::find(vec.begin(), vec.end(), 30);if(iter != vec.end())std::cout << *iter << std::endl;iter = std::find_if(vec.begin(), vec.end(), PredictCount());if(iter != vec.end())std::cout << *iter << std::endl;std::cout << "------ test find ------" << std::endl;// 6. sortstd::cout << "------ test sort ------" << std::endl;std::sort(vec.begin(), vec.end(), std::greater<int>());std::for_each(vec.begin(), vec.end(),printVal()); // 60 50 40 30 20 10cout << endl;std::sort(vec.begin(), vec.end(), std::less<int>()); // 10 20 30 40 50 60std::for_each(vec.begin(), vec.end(),printVal());cout << endl;std::cout << "------ test sort ------" << std::endl;// 7. binary_searchstd::cout << "------ test binary_search ------" << std::endl;bool isExists = std::binary_search(vec.begin(), vec.end(), 50);if(isExists){std::cout << "50 is existed. " << std::endl;}else{std::cout << "50 is not existed. " << std::endl;}bool isExists2 = std::binary_search(vec.begin(), vec.end(), 60, PredictBinarySearch());if(isExists2){std::cout << "x == 60 is existed. " << std::endl;}else{std::cout << "x == 60 is not existed. " << std::endl;}std::cout << "------ test binary_search ------" << std::endl;return 0;
}