STL Algorithm

Algorithm, STL

STL Algorithms

Global functions that operate with iterators.

不是面向对象编程范式，而是函数编程范式。

需要包含头文件<algorithm>。数字相关的还要包含<numeric>。要用function object或function adapter时要包含<functional>。

Algorithm涉及到的第一个范围[beg, end)需要保证合法且从beg可以到达end，第二个范围只需提供beg2，需要保证第二个范围不小于第一个范围或者使用insert_iterator。
Algorithm work in overwrite mode rather than in insert mode.

有些Algorithm允许用户自己提供谓词：

  • 用function, function object, lambda作为一维谓词，为search提供搜索标准。一维谓词用于检查某个元素是否符合这个标准。
  • 用function, function object, lambda作为二维谓词，为sort提供排序标准。二维谓词用来比较两个元素。
  • 可以用一维谓词指定某个操作只应用于符合谓词指定条件的元素。
  • 可以为数字操作指定数字运算。

注意谓词不可以有可修改的内部状态！[解释见此。](/2015/01/08/stl-function-object-and-using-lambda/#谓词 vs 函数对象)

Algorithm的分类

两个特殊后缀：

  1. _if后缀 两个Algorithm参数一样，有if的传判断标准，没有if的直接比较值。有些也可以指定判断标准的Algorithm没有这个后缀。
  2. _copy后缀 有copy的Algorithm操作结果被复制到一个新的目标区间，没有的直接在原区间做改动。

Nonmodifying

不对元素或元素的顺序做任何修改。只需要input和forward迭代器，所以可用于所有标准容器。
Nonmodifying Algorithms
原先很重要的for_each()在C++11有了range-based for loop之后可能就没那么重要了。
String和STL是被分别设计的，Search部分的命名一片乱。
Comparison of Searching String Operations and Algorithms

Modifying

会改变元素的值或改变后拷贝到另一个范围。
Modifying Algorithms
最基本的操作是for_each()和transform()。它们都用来修改一序列元素。它们的区别：

  • for_each() 接受一个修改自己参数的操作。即，参数必须用引用传入。
1
2
3
4
5
void square (int& elem)	{// call-by-reference
	elem = elem * elem;
}
for_each (coll.begin(), coll.end(),	// range
	square);			// operation
  • transform() 接受一个返回修改过的参数值的操作。可以把结果再重新赋值给原始元素。也因此它稍微慢一点。
1
2
3
4
5
6
int square (int elem) {	// call-by-value
	return elem * elem;
}
transform (coll.cbegin(), coll.cend(),	// source range
	coll.begin(),			// destination range
	square);			// operation

Removing

可以在原序列里删除元素或者在拷贝到其他范围的时候删除掉。
对于修改性操作，不能用于关联容器或者unordered容器作为目标容器，因为这些容器的元素是constant的。
Removing Algorithms
注意这里的remove操作只是逻辑上的删除，复制后面的元素覆盖要删除的元素，不会改变容器的大小。他们返回的是“新”end。用户可以根据这个新end物理删除其之后的元素。

Mutating

会修改原序列元素顺序，而不是元素值的操作。不能用关联容器或者unordered容器作为目标。
Mutating Algorithms

Sorting

特殊的mutating算法。目标需要random-access迭代器。
Sorting Algorithms
Algorithms Checking for Sortings

序列全部排序

  • sort() 基于quicksort。平均时间复杂度O(nlogn)O(nlogn)，最坏时间复杂度O(n2)O(n^2)。
  • partial_sort() 基于heapsort。保证任何时候的O(nlogn)O(nlogn)时间复杂度。一般比sort()时间慢一倍。
  • stable_sort() 基于mergesort。需要额外空间保证O(nlogn)O(nlogn)时间复杂度。好处是不会改变等值元素的顺序。

部分排序

  • nth_element() 可将序列分成两组，小于等于第n个元素的和大于等于第n个元素的。但是不知道具体的排序标准是什么。
  • partition() 可以传入自定义的排序标准，区分第一部分和第二部分。
  • stable_partition() 除了partition()的功能之外，额外保证是稳定的。

list和forward list不提供random-access迭代器，不能用通用algorithm。人家有自己的sort成员函数。

Sorted-range

要求自己操作的序列必须是已经排好序的。
Algorithms for Sorted Ranges
其中Merge操作：

1
2
3
4
5
6
7
8
c1:				1 2 2 4 6 7 7 9
c2:				2 2 2 3 6 6 8 9
-------------
merge():			1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9	所有元素全合并
set_union():			1 2 2 2 3 4 6 6 7 7 8 9		相同元素的出现次数是两段中的最大次数
set_intersection():		2 2 6 9				A∩B，相同元素的出现次数是两段中的最小次数
set_difference():		1 4 7 7				A-B，相同元素在A中的数目减去B中的数目的最接近非负数
set_symmetric_difference():	1 2 3 4 6 7 7 8			要么在A要么在B，就是不都在。相同元素在A中的数目减去B中的数目的绝对值

Numeric

Numeric Algorithms

Heap操作

第一个元素是最大值，可以在logn时间内添加删除元素，适于用来实现优先队列。
Elements of a Heap as a Binary Tree

  1. make_heap() 把一序列元素变成heap。
  2. push_heap() 添加一个元素到heap。
  3. pop_heap() 从heap中移除下一个元素。
  4. sort_heap() 把一个heap转换成一个有序队列，此后就不再是heap了。

Algorithm函数声明速查

1
2
// for_each
UnaryProc	for_each (InputIterator beg, InputIterator end, UnaryProc op)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Nonmodifying Algorithms
// -----------------------------------
// Counting Elements
// -----------------------------------
difference_type	count (InputIterator beg, InputIterator end, const T& value)
difference_type count_if (InputIterator beg, InputIterator end, UnaryPredicate op)
// -----------------------------------
// Minimum and Maximum
// -----------------------------------
ForwardIterator	min_element (ForwardIterator beg, ForwardIterator end)
ForwardIterator	min_element (ForwardIterator beg, ForwardIterator end, CompFunc op)
ForwardIterator	max_element (ForwardIterator beg, ForwardIterator end)
ForwardIterator	max_element (ForwardIterator beg, ForwardIterator end, CompFunc op)
pair<ForwardIterator, ForwardIterator>	minmax_element(ForwardIterator beg, ForwardIterator end)
pair<ForwardIterator, ForwardIterator>	minmax_element(ForwardIterator beg, ForwardIterator end, CompFunc op)
// -----------------------------------
// Searching Elements
// -----------------------------------
// - Search First Matching Element
InputIterator	find (InputIterator beg, InputIterator end, const T& value)
InputIterator	find_if (InputIterator beg, InputIterator end, UnaryPredicate op)
InputIterator	find_if_not (InputIterator beg, InputIterator end, UnaryPredicate op)
// - Search First n Matching Consecutive(连贯的) Elements
ForwardIterator	search_n (ForwardIterator beg, ForwardIterator end, Size count, const T& value)
ForwardIterator	search_n (ForwardIterator beg, ForwardIterator end, Size count, const T& value, BinaryPredicate op)
// - Search First Subrange
ForwardIterator1	search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
ForwardIterator1	search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)
// - Search Last Subrange
ForwardIterator1	find_end (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
ForwardIterator1	find_end (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)
// - Search First of Several Possible Elements
InputIterator	find_first_of (InputIterator beg, InputIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd)
InputIterator	find_first_of (InputIterator beg, InputIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd, BinaryPredicate op)
// - Search Two Adjacent, Equal Elements
ForwardIterator	adjacent_find (ForwardIterator beg, ForwardIterator end)
ForwardIterator	adjacent_find (ForwardIterator beg, ForwardIterator end, BinaryPredicate op)
// -----------------------------------
// Comparing Ranges
// -----------------------------------
// - Testing Equality
bool equal	(InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
bool equal	(InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op)
// - Testing for Unordered Equality
bool is_permutation	(ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2)
bool is_permutation	(ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2, CompFunc op)
// - Search the First Difference
pair<InputIterator1, InputIterator2>	mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
pair<InputIterator1, InputIterator2>	mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op)
// - Testing for "Less Than"
bool	lexicographical_compare (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, InputIterator2 end2)
bool	lexicographical_compare (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, InputIterator2 end2, CompFunc op)
// -----------------------------------
// Predicates for Ranges
// -----------------------------------
// - Check for (Partial) Sorting
bool	is_sorted (ForwardIterator beg, ForwardIterator end)
bool	is_sorted (ForwardIterator beg, ForwardIterator end, BinaryPredicate op)
ForwardIterator	is_sorted_until (ForwardIterator beg, ForwardIterator end)
ForwardIterator is_sorted_until (ForwardIterator beg, ForwardIterator end, BinaryPredicate op)
// - Check for Being Partitioned
bool	is_partitioned (InputIterator beg, InputIterator end, UnaryPredicate op)
ForwardIterator	partition_point (ForwardIterator beg, ForwareIterator end, BinaryPredicate op)
// - Check for Being a Heap (Maximum Element First)
bool	is_heap (RandomAccessIterator beg, RandomAccessIterator end)
bool	is_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
RandomAccessIterator	is_heap_until (RandomAccessIterator beg, RandomAccessIterator end)
RandomAccessIterator	is_heap_until (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
// - All, Any, or None
bool	all_of (InputIterator beg, InputIterator end, UnaryPredicate op)
bool	any_of (InputIterator beg, InputIterator end, UnaryPredicate op)
bool	none_of (InputIterator beg, InputIterator end, UnaryPredicate op)
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
// Modifying Algorithms
// -----------------------------------
// Copying Elements
// -----------------------------------
OutputIterator	copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)	// destBeg should be in front of sourceBeg
OutputIterator	copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op)
OutputIterator	copy_n (InputIterator sourceBeg, Size num, OutputIterator destBeg)
BidirectionalIterator2	copy_backward (BidirectionalIterator1 sourceBeg, BidirectionalIterator1 sourceEnd, BidirectionalIterator2 destEnd)	// destEnd should be after sourceEnd. copy and copy_backward matters only if the source and destination ranges overlap.
// -----------------------------------
// Moving Elements
// -----------------------------------
OutputIterator	move (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
BidirectionalIterator2	move_backward (BidirectionalIterator1 sourceBeg, BidirectionalIterator1 sourceEnd, BidirectionalIterator2 destEnd)
// -----------------------------------
// Transforming and Combining Elements
// -----------------------------------
// - Transforming Elements
OutputIterator	transform (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryFunc op)	// A op-> B
// - Combining Elements of Two Sequences
OutputIterator	transform (InputIterator1 source1Beg, InputIterator1 source1End, InputIterator2 source2Beg, OutputIterator destBeg, BinaryFunc op)	// A + B op-> C
// -----------------------------------
// Swapping Elements
// -----------------------------------
ForwardIterator2	swap_ranges (ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2)
// -----------------------------------
// Assigning New Values
// -----------------------------------
// - Assigning the Same Value
void	fill (ForwardIterator beg, ForwardIterator end, const T& newValue)
void	fill_n (OutputIterator beg, Size num, const T& newValue)
// - Assigning Generated Values
void	generate (ForwardIterator beg, ForwardIterator end, Func op)
void	generate_n (OutputIterator beg, Size num, Func op)
// - Assigning Sequence of Increments Values
void	iota (ForwardIterator beg, ForwardIterator end, T startValue)
// -----------------------------------
// Replacing Elements
// -----------------------------------
// - Replacing Values Inside a Sequence
void	replace (ForwardIterator beg, ForwardIterator end, const T& oldValue, const T& newValue)
void	replace_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op, const T& newValue)
// - Copying and Replacing Elements
OutputIterator	replace_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& oldValue, const T& newValue)
OutputIterator	replace_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op, const T& newValue)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Removing Algorithms
// -----------------------------------
// Removing Certain Values
// -----------------------------------
// - Removing Elements in a Sequence
ForwardIterator	remove (ForwardIterator beg, ForwardIterator end, const T& value)
ForwardIterator	remove_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op)
// - Removing Elements While Copying
OutputIterator	remove_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& value)
OutputIterator	remove_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op)
// -----------------------------------
// Removing Duplicates
// -----------------------------------
// - Removing Consecutive Duplicates
ForwardIterator	unique (ForwardIterator beg, ForwardIterator end)
ForwardIterator	unique (ForwardIterator beg, ForwardIterator end, BinaryPredicate op)
// - Removing Duplicates While Copying
OutputIterator	unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
OutputIterator	unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryPredicate op)
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
// Mutating Algorithms
// -----------------------------------
// Reversing the Order of Elements
// -----------------------------------
void	reverse (BidirectionalIterator beg, BidirectionalIterator end)
void	reverse_copy (BidirectionalIterator sourceBeg, BidirectionalIterator sourceEnd, OutputIterator destBeg)
// -----------------------------------
// Rotating Elements
// -----------------------------------
// - Rotating Elements inside a Sequence
ForwardIterator rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end)
// - Rotating Elements While Copying
OutputIterator	rotate_copy (ForwardIterator sourceBeg, ForwardIterator newBeg, ForwardItrator sourceEnd, OutputIterator destBeg)
// -----------------------------------
// Permuting Elements
// -----------------------------------
bool	next_permutation (BidirectionalIterator beg, BidirectionalIterator end)
bool	next_permutation (BidirectionalIterator beg, BidirectionalIterator end, BinaryPredicate op)
bool	prev_permutation (BidirectionalIterator beg, BidirectionalIterator end)
bool	prev_permutation (BidirectionalIterator beg, BidirectionalIterator end, BinaryPredicate op)
// -----------------------------------
// Shuffling Elements
// -----------------------------------
// - Shuffling Using the Random-Number Library
void	shuffle (RandomAccessIterator beg, RandomAccessIterator end, UniformRandomNumberGenerator&& eng)
void	random_shuffle (RandomAccessIterator beg, RandomAccessIterator end)
void	random_shuffle (RandomAccessIterator beg, RandomAccessIterator end, RandomFunc&& op)
// -----------------------------------
// Moving Elements to the Front
// -----------------------------------
ForwardIterator	partition (ForwardIterator beg, ForwardIterator end, UnaryPredicate op)
BidirectionalIterator	stable_partition (BidirectionalIterator beg, BidirectionalIterator end, UnaryPredicate op)
// -----------------------------------
// Partition into Two Subranges
// -----------------------------------
pair<OutputIterator1, OutputIterator2>	partition_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator1 destTrueBeg, OutputIterator2 destFalseBeg, UnaryPredicate op)
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
// Sorting Algorithms
// -----------------------------------
// Sorting All Elements
// -----------------------------------
void	sort (RandomAccessIterator beg, RandomAccessIterator end)
void	sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
void	stable_sort (RandomAccessIterator beg, RandomAccessIterator end)
void	stable_sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
// -----------------------------------
// Partial Sorting
// -----------------------------------
void	partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end)
void	partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end, BinaryPredicate op)
RandomAccessIterator	partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destBeg, RandomAccessIterator destEnd)
RandomAccessIterator	partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destBeg, RandomAccessIterator destEnd, BinaryPredicate op)
// -----------------------------------
// Sorting According to the nth Element
// -----------------------------------
void	nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end)
void	nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end, BinaryPredicate op)
// -----------------------------------
// Heap Algorithms
// -----------------------------------
void	make_heap (RandomAccessIterator beg, RandomAccessIterator end)
void	make_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
void	push_heap (RandomAccessIterator beg, RandomAccessIterator end)
void	push_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
void	pop_heap (RandomAccessIterator beg, RandomAccessIterator end)
void	pop_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
void	sort_heap (RandomAccessIterator beg, RandomAccessIterator end)
void	sort_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
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
// Sorted-Range Algorithms
// -----------------------------------
// Searching Elements
// -----------------------------------
// - Checking Whether One Element Is Present
bool	binary_search (ForwardIterator beg, ForwardIterator end, const T& value)
bool	binary_search (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
// - Checking Whether Several Elements Are Present
bool	includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd)
bool	includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd, BinaryPredicate op)
// - Searching First or/and Last Possible Position
ForwardIterator	lower_bound (ForwardIterator beg, ForwardIterator end, const T& value)
ForwardIterator lower_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
ForwardIterator	upper_bound (ForwardIterator beg, ForwardIterator end, const T& value)
ForwardIterator upper_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
pair<ForwardIterator,ForwardIterator>	equal_range (ForwardIterator beg, ForwardIterator end, const T& value)
pair<ForwardIterator,ForwardIterator>	equal_range (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
// -----------------------------------
// Merging Elements
// -----------------------------------
// - Processing the Sum of Two Sorted Sets
OutputIterator	merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator	merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
// - Processing the Union of Two Sorted Sets
OutputIterator	set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator	set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
// - Processing the Intersection of Two Sorted Sets
OutputIterator	set_intersection (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator	set_intersection (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
// - Processing the Difference of Two Sorted Sets
OutputIterator	set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator	set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
// - Processing the Difference of Two Sorted Sets
OutputIterator	set_symmetric_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator	set_symmetric_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
// - Merging Consecutive Sorted Ranges
void	inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2)
void	inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2, BinaryPredicate op)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Numeric Algorithms
// -----------------------------------
// Processing Results
// -----------------------------------
// - Computing the Result of One Sequence (initValue = op(initValue, elem))
T	accumulate (InputIterator beg, InputIterator end, T initValue)
T	accumulate (InputIterator beg, InputIterator end, T initValue, BinaryFunc op)
// - Computing the Inner Product of Two Sequences (initValue = op1(initValue, op2(elem1, elem2)))
T	inner_product (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, T initValue)
T	inner_product (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, T initValue, BinaryFunc op1, BinaryFunc op2)
// -----------------------------------
// Converting Relative and Absolute Values
// -----------------------------------
// - Converting Relative Values into Absolute Values (a1, a2, a3变成a1, a1 op a2, a1 op a2 op a3)
OutputIterator	partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
OutputIterator	partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op)
// - Converting Absolute Values into Relative Values (a1, a2, a3, a4变成a1, a2 op a1, a3 op a2, a4 op a3)
OutputIterator	adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
OutputIterator	adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op)

[1] The C++ Standard Library 2nd Edition