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 <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 _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<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. 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;
}