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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
Before using the generic algorithms presented in this chapter, except for
those in the tt(Operators) category (defined below), the tthi(algorithm) header
file must be included. Before using a generic algorithm in the
tt(Operators) category the tthi(numeric) header file must be included.
In the previous chapter the Standard Template Library (STL) was introduced. An
important element of the STL, the emi(generic algorithms), was not covered in
that chapter as they form a fairly extensive part of the STL. Over time the
STL has grown considerably, mainly as a result of a growing importance and
appreciation of em(templates). Covering generic algorithm in the STL chapter
itself would turn that chapter into an unwieldy one and so the generic
algorithms were moved to a chapter of their own.
Generic algorithms perform an amazing task. Due to the strength of templates,
algorithms could be developed that can be applied to a wide range of different
data types while maintaining type safety. The prototypical example of this is
the link(tt(sort))(SORT) generic algorithm. To contrast: while bf(C) requires
programmers to write callback functions in which type-unsafe tt(void const *)
parameters have to be used, internally forcing the programmer to resort to
casts, STL's tt(sort) frequently allows the programmer merely to state
something akin to
verb( sort(first-element, last-element))
Generic algorithms should be used wherever possible. Avoid the urge to design
your own code for commonly encountered algorithms. Make it a habit to
em(first) thoroughly search the generic algorithms for an available
candidate. The generic algorithms should become your em(weapon of choice) when
writing code: acquire full familiarity with them and make their use your
`second nature'.
On the other hand, without downgrading the importance of the generic
algorithms, it's clear that over the years the number of available generic
algorithms have seen an almost unlimited growth. Many new algorithms were
added, even though for quite a few of them it's either very easy to provide
direct implementations, or which may hardly ever be used. An
example is the tt(is_sorted) generic algorithm, simply returning tt(true) if a
range of elements is considered sorted and tt(false) if not. How hard is it to
define such a function in the occasional situation you might need it? This
applies to quite a few other generic algorithms. It's of course nice to have
an extensive toolbox, but do you need, e.g., screwdrivers that
perfectly match the screws' heads? Most likely not.... To avoid an excessive
growth of this chapter, some sections contain comparable algorithms, and in
some sections links to url(cppreference)(https://en.cppreference.com) are
provided when referring to comparable algorithms.
Nevertheless, this chapter's sections cover many of the STL's
i(generic algorithms) (in alphabetical order). For each algorithm the
following information is provided:
itemization(
it() The required header file;
it() The function prototype;
it() A short description;
it() A short example.
)
In the prototypes of the algorithms tt(Type) is used to specify a
i(generic data type). Furthermore, the particular type of iterator (see
section ref(ITERATORS)) that is required is mentioned as well as other generic
types that might be required (e.g., performing tt(BinaryOperations), like
tt(plus<Type>)). Although iterators are commonly provided by abstract
containers and comparable pre-defined data structures, at some point you may
want to design your own iterators. Section ref(ITERATORCONS) offers guidelines
for constructing your own iterator classes and provides an overview of of
operators that must be implemented for the various types of iterators.
Almost every generic algorithm expects an iterator range rangeti(first, last),
defining the series of elements on which the algorithm operates. The iterators
point to objects or values. When an iterator points to a tt(Type) value or
object, function objects used by the algorithms usually receive tt(Type const
&) objects or values. Usually function objects cannot modify the objects they
receive as their arguments. This does not hold true for em(modifying generic
algorithms), which em(are) of course able to modify the objects they operate
upon.
hi(generic algorithm: categories) Generic algorithms may be categorized. The
annotations() distinguishes the following categories of generic algorithms:
itemization(
it() Comparators: comparing (ranges of) elements:
quote(
link(all_of; any_of)(XOF);
link(equal)(EQUAL);
link(includes)(INCLUDES);
link(lexicographical_compare)(LEXCOMP);
link(mismatch)(MISMATCH);
link(none_of)(XOF);
)
it() Copiers / movers: performing copy / move operations:
quote(
link(copy)(COPY);
link(copy_backward)(COPYBACK);
link(copy_if)(COPY);
link(move; move_backward)(MOVEFWD);
link(partition_copy)(PARTCP);
link(partial_sort_copy)(PARTSORT);
link(remove_copy; remove_copy_if)(REMOVE);
link(replace_copy; replace_copy_if)(REPLACE);
link(reverse_copy)(REVERSE);
link(rotate_copy)(ROTATE);
link(sample)(SAMPLE);
link(shift_left; shift_right)(MOVEFWD);
link(unique_copy)(UNIQUECP);
)
it() Counters: performing count operations:
quote(
link(count; count_if)(COUNT);
)
it() Heap operators: manipulating a i(max-heap):
quote(
link(make_heap)(MAKEHEAP);
link(pop_heap)(POPHEAP);
link(push_heap)(PUSHHEAP);
link(sort_heap)(SORTHEAP);
)
it() Initializers: initializing data:
quote(
link(fill; fill_n)(FILL);
link(generate; generate_n)(GEN);
link(iota)(IOTA);
link(uninitialized (raw) memory)(UNINIT);
)
it() Limiters: determining boundaries of data:
quote(
link(begin; end)(BEGEND);
)
it() Operators: performing some kind of (arithmetic?) operations:
quote(
link(accumulate)(ACCU);
link(adjacent_difference)(ADJDIFF);
link(exclusive_scan; inclusive_scan)(PARTSUM);
link(inner_product)(INNERPROD);
link(partial_sum)(PARTSUM);
link(reduce)(REDUCE);
link(transform_reduce)(TRANSRED);
)
it() Searchers: performing search (and find) operations:
quote(
link(adjacent_find)(ADJFIND);
link(binary_search)(BINSRCH);
link(equal_range)(EQUALRANGE);
link(find)(FIND);
link(find_end)(FINDEND);
link(find_first_of)(FINDFIRST);
link(find_if; find_if_not)(FIND);
link(lower_bound)(LOWERBOUND);
link(max)(MAX);
link(max_element; min_element)(MAXEL);
link(min)(MAX);
link(minmax)(MINMAX);
link(minmax_element)(MAXEL);
link(partition_point)(PARTIT);
link(search; search_n)(SEARCH);
link(set_difference)(SETDIF);
link(set_intersection)(SETINT);whenlatex(nl())
link(set_symmetric_difference)(SETSYM);
link(set_union)(SETUNI);
link(upper_bound)(UPPERBOUND);
)
it() Shufflers: performing reordering operations (i(sorting),
i(merging), i(permuting), i(swapping)):
quote(
link(inplace_merge)(INMERGE);
link(iter_swap)(ITERSWAP);
link(merge)(MERGE);
link(next_permutation)(NEXTPERM);
link(nth_element)(NTHEL);
link(partial_sort)(PARTSORT);
link(partition)(PARTIT);
link(prev_permutation)(NEXTPERM);
link(remove; remove_copy; remove_copy_if; remove_if)(REMOVE);
link(reverse; reverse_copy)(REVERSE);
link(rotate; rotate_copy)(ROTATE);
link(shuffle)(SAMPLE);
link(sort)(SORT);
link(stable_partition)(PARTIT);
link(stable_sort)(SORT);
link(swap; swap_ranges)(SWAP);
link(unique)(UNIQUE);
)
it() Verifiers: checking for specific conditions:
quote(
link(is_partitioned)(ISPART);
link(is_permutation)(ISPERM);
link(is_sorted)(ISSORTED);
link(is_sorted_until)(ISSORTEDUNT);
)
it() Visitors: visiting elements in a range:
quote(
link(for_each)(FOREACH);
link(replace; replace_copy; replace_copy_if; replace_if)(REPLACE);
link(transform)(TRANSFORM);
link(unique_copy)(UNIQUECP);
)
)
|
