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 _Tp
    accumulate(_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 _Tp
    accumulate(_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>
    _Function
    for_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>
    void
    replace(_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>
    void
    replace_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_type
    count(_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_type
    count_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 _InputIterator
    find(_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 _InputIterator
    find_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 not less
   *                  than @a val, or end() if every element is less than 
   *                  @a val.
   *  @ingroup binary_search_algorithms
  */
  template<typename _ForwardIterator, typename _Tp>
    inline _ForwardIterator
    lower_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>
    bool
    binary_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>
    bool
    binary_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
#include
 
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. accumulate
    std::cout << "------ test accumulate ------" << std::endl;
    std::cout << std::accumulate(vec.begin(), vec.end(), init) << std::endl; // 210
 
    init = 600;
    std::cout << std::accumulate(vec.begin(), vec.end(), init, std::minus<int>()) << std::endl; // 390
    std::cout << "------ test accumulate ------" << std::endl;
 
 
    // 2. for_each
    struct 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_if
 
    std::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_if
    std::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_if
    std::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. sort
    std::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 10
    cout << endl;
 
    std::sort(vec.begin(), vec.end(), std::less<int>()); // 10 20 30 40 50 60
    std::for_each(vec.begin(), vec.end(),printVal());
    cout << endl;
 
    std::cout << "------ test sort ------" << std::endl;
 
 
    // 7. binary_search
    std::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;
}

相关阅读:
【Linux】部署单体项目以及前后端分离项目（项目部署）
java中log使用总结
 扩散模型加持下，机器人模型DALL-E-Bot可以轻松完成自主重新排列任务
 openpyxl应用
 【Java】线程池源码解析
 《30天吃掉那只 TensorFlow2.0》五、TensorFlow的中阶API
第 1 课 Python 的输出！
Springboot餐饮点餐系统毕业设计源码301749
SpringBoot 集成 kaptcha 验证码
 Qt ffmpeg音视频转换工具
原文地址：https://blog.csdn.net/qq_33775774/article/details/134095736