C++ 标准库算法源代码剖析

一、 算法 accumulate

1. 功能

对容器内的元素进行累计(不限于累加运算,可以是自己传进去的运算)。

2. 可能的实现

版本一:

1
2
3
4
5
6
7
8
9
template<class InputIt, class T>
constexpr // C++20 起
T accumulate(InputIt first, InputIt last, T init)
{
for (; first != last; ++first) {
init = std::move(init) + *first; // C++20 起有 std::move
}
return init;
}

版本二:

1
2
3
4
5
6
7
8
9
10
template<class InputIt, class T, class BinaryOperation>
constexpr // C++20 起
T accumulate(InputIt first, InputIt last, T init,
BinaryOperation op)
{
for (; first != last; ++first) {
init = op(std::move(init), *first); // C++20 起有 std::move
}
return init;
}

3. 示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<numeric>
#include<functional>

using namespace std;

int myfunc (int a, int b)
{
return a + 2 * b;
}

template <typename T>
class MyFunc
{
public:
T operator()(T a, T b)
{
return a + 3 * b;
}
};

struct mystuct
{
int operator()(int a, int b)
{
return a + 2 * b;
}
}myobj;

int main()
{
int init = 100;
int num[] = { 20,30,40 };
cout << "accumulate default:" << endl;
cout << accumulate(num, num + 3, init) << endl;

cout << "accumulate minus:" << endl;
cout << accumulate(num, num + 3, init, minus<int>()) << endl;;

cout << "accumulate myfunc function:" << endl;
cout << accumulate(num, num + 3, init, myfunc) << endl;

cout << "accumulate template class:" << endl;
cout << accumulate(num, num + 3, init, MyFunc<int>()) << endl;

cout << "accumulate myobj class:" << endl;
cout << accumulate(num, num + 3, init, myobj) << endl;
return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
accumulate default:
190
accumulate minus:
10
accumulate myfunc function:
280
accumulate template class:
370
accumulate myobj class:
280

二、算法 for_each

1. 功能

对一段元素或一个区间内的元素进行一个操作,一个程序员可以指定的操作。

2. 可能的实现

1
2
3
4
5
6
7
8
template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
{
for (; first != last; ++first) {
f(*first);
}
return f; // C++11 起隐式移动
}

3. 示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void myfunc(int i)
{
cout<<" "<<i;
}

struct mystruct
{
void operator()(int i)
{
cout<<" "<<i;
}
}myobj;

int main()
{
vector<int> num{10,20,30};
for_each(num.begin(), num.end(), myfunc);
cout<<endl;

for_each(num.begin(), num.end(), myobj);
cout<<endl;
}

三、算法 replace, replace_if, replace_copy

1. 功能

对范围内的元素批量化进行一个操作。

2. 可能的实现

replace

1
2
3
4
5
6
7
8
9
10
11
template<class ForwardIt, class T>
void replace(ForwardIt first, ForwardIt last,
const T& old_value, const T& new_value)
{
//范围内所有等同于old_value的值都以new_value取代
for (; first != last; ++first) {
if (*first == old_value) {
*first = new_value;
}
}
}

replace_if

1
2
3
4
5
6
7
8
9
10
11
template<class ForwardIt, class UnaryPredicate, class T>
void replace_if(ForwardIt first, ForwardIt last,
UnaryPredicate p, const T& new_value)
{
//范围内所有满足p()操作的值都已new_value取代
for (; first != last; ++first) {
if(p(*first)) {
*first = new_value;
}
}
}

replace_copy

1
2
3
4
5
6
7
8
9
10
template<class InputIt, class OutputIt, class T>
OutputIt replace_copy(InputIt first, InputIt last, OutputIt d_first,
const T& old_value, const T& new_value)
{
//范围内所有等同于old_value的值都以new_value放至新区间,不符合者原值放入新区间
for (; first != last; ++first) {
*d_first++ = (*first == old_value) ? new_value : *first;
}
return d_first;
}

replace/replace_ifreplace_copy

四、算法 count, count_if

1. 功能

计算一个区间内符合一个条件的元素有多少个。

2. 可能的实现

版本一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct count_fn {
template< std::input_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity >
requires std::indirect_binary_predicate<ranges::equal_to, std::projected<I, Proj>,
const T*>
constexpr std::iter_difference_t<I>
operator()( I first, S last, const T& value, Proj proj = {} ) const
{
std::iter_difference_t<I> counter = 0;
for (; first != last; ++first) {
if (std::invoke(proj, *first) == value)
{
++counter;
}
}

return counter;
}

template< ranges::input_range R, class T, class Proj = std::identity >
requires std::indirect_binary_predicate<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>,
const T*>
constexpr ranges::range_difference_t<R>
operator()( R&& r, const T& value, Proj proj = {} ) const
{
return (*this)(ranges::begin(r), ranges::end(r), value, std::ref(proj));
}
};

inline constexpr count_fn count;

版本二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct count_if_fn {
template< std::input_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
constexpr std::iter_difference_t<I>
operator()( I first, S last, Pred pred = {}, Proj proj = {} ) const
{
std::iter_difference_t<I> counter = 0;
for (; first != last; ++first) {
if (std::invoke(pred, std::invoke(proj, *first)))
{
++counter;
}
}

return counter;
}

template< ranges::input_range R, class Proj = std::identity,
std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>> Pred >
constexpr ranges::range_difference_t<R>
operator()( R&& r, Pred pred = {}, Proj proj = {} ) const
{
return (*this)(ranges::begin(r), ranges::end(r),
std::ref(pred), std::ref(proj));
}
};

inline constexpr count_if_fn count_if;
Author: wnxy
Link: https://wnxy.github.io/2021/07/26/cpp_algorithm_analysis/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.