Operators category (defined below), the <algorithm> header
file must be included. Before using a generic algorithm in the
Operators category the <numeric> header file must be included.
In the previous chapter the Standard Template Library (STL) was introduced. An important element of the STL, the 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 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 sort generic algorithm. To contrast: while C requires
programmers to write callback functions in which type-unsafe void const *
parameters have to be used, internally forcing the programmer to resort to
casts, STL's sort frequently allows the programmer merely to state
something akin to
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 first thoroughly search the generic algorithms for an available candidate. The generic algorithms should become your 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 is_sorted generic algorithm, simply returning true if a
range of elements is considered sorted and 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 cppreference are
provided when referring to comparable algorithms.
Nevertheless, this chapter's sections cover many of the STL's generic algorithms (in alphabetical order). For each algorithm the following information is provided:
Type is used to specify a
generic data type. Furthermore, the particular type of iterator (see
section 18.2) that is required is mentioned as well as other generic
types that might be required (e.g., performing BinaryOperations, like
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 22.14 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 [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 Type value or
object, function objects used by the algorithms usually receive Type const
& objects or values. Usually function objects cannot modify the objects they
receive as their arguments. This does not hold true for modifying generic
algorithms, which are of course able to modify the objects they operate
upon.
Generic algorithms may be categorized. The C++ Annotations distinguishes the following categories of generic algorithms:
all_of; any_of; equal; includes; lexicographical_compare; mismatch; none_of;
copy; copy_backward; copy_if; move; move_backward; partition_copy; partial_sort_copy; remove_copy; remove_copy_if; replace_copy; replace_copy_if; reverse_copy; rotate_copy; sample; shift_left; shift_right; unique_copy;
count; count_if;
make_heap; pop_heap; push_heap; sort_heap;
fill; fill_n; generate; generate_n; iota; uninitialized (raw) memory;
begin; end;
accumulate; adjacent_difference; exclusive_scan; inclusive_scan; inner_product; partial_sum; reduce; transform_reduce;
adjacent_find; binary_search; equal_range; find; find_end; find_first_of; find_if; find_if_not; lower_bound; max; max_element; min_element; min; minmax; minmax_element; partition_point; search; search_n; set_difference; set_intersection; set_symmetric_difference; set_union; upper_bound;
inplace_merge; iter_swap; merge; next_permutation; nth_element; partial_sort; partition; prev_permutation; remove; remove_copy; remove_copy_if; remove_if; reverse; reverse_copy; rotate; rotate_copy; shuffle; sort; stable_partition; stable_sort; swap; swap_ranges; unique;
is_partitioned; is_permutation; is_sorted; is_sorted_until;
for_each; replace; replace_copy; replace_copy_if; replace_if; transform; unique_copy;
generate (section 19.1.19), filling
the elements with values produced by a generating function. If those values
are randomly generated values then generated could very well be
parallized, where each parallel thread handles a separate section of the range
to be filled. Another example where parallel execution may be useful is when
sorting series of values. For this the the sort generic algorithm can be
used (section 19.1.54, which also contains an example of parallelized
sorting).
These (and many other) generic algorithms can be executed in parallel,
depending on the specified execution policy. When no execution policy is
specified then the algorithms operated in their standard, sequential, way. The
generic algorithms supporting execution policies have overloaded versions
where the first parameter specifies the execution policy to use, followed by
their remaining parameters. Function prototypes listed the following sections
showing a first parameter [ExecPol,] may specify one of the execution
policies introduced in this section as their first arguments. E.g., one of the
sort generic algorithm's prototypes is
void sort([ExecPol,]
RandomAccessIterator first, RandomAccessIterator last);
and to sort, e.g., a vector if strings (vs), it can be called as
sort(vs.bgin(), vs.end());or as (see below)
sort(execution::par, vs.bgin(), vs.end());
In order to use execution policies the <execution> header file must be
included, and the linking option -ltbb must be specified with linking the
compiled object s.
There are four types of execution policies (all defined in the std
namespace):
<execution::sequenced_policy>, whose predefined object
execution::seq is used to specify this execution policy when
calling generic algorithms.
When calling a generic algorithm specifying this policy it will not be using parallel execution.
<execution::parallel_policy>, whose predefined object
execution::par is used to specify this execution policy when
calling generic algorithms.
When calling a generic algorithm specifying this policy it may
be using parallel execution: the generic algorithm may decide not to
use parallel execution when it decides that the overhead of parallel
execution is in fact reducing the efficiency of non-parallel
execution. E.g., when sorting 100 elements sequential execution is
faster than parallel execution and an algorithm like sort won't
use parallel execution.
<execution::parallel_unsequenced_policy>, whose predefined object
execution::par_unseq is used to specify this execution policy when
calling generic algorithms.
When calling a generic algorithm specifying this policy it may be using parallel execution, execution may be migrated across threads (using a so-called parent-stealing scheduler), or execution may be vectorized (i.e., a single thread is used accessing data items at completely different locations (like swapping the first and middle elements of vectors)). When using this policy the order in which processed elements are accessed and the threads from which these elements are accessed is undefined.
<execution::unsequenced_policy>, whose predefined object
execution::unseq is used to specify this execution policy when
calling generic algorithms.
When calling a generic algorithm specifying this policy the algorithm uses vectorized execution.
Whenever algorithms are called using the above policy specifications and
during the execution of these algorithms functions are called generating
uncaught exceptions std::terminate is called.
When using parallel execution the objects or functions passed to the generic algorithms might access data defined elsewhere. If those data are modified then it is possible that modifications are requested from different execution threads, which could result in data races or deadlocks. The programmer should ensure that data races and/or dadlocks cannot occur when using parallel execution.
<numeric>
Type accumulate(InputIterator first, InputIterator last,
Type init);
Type accumulate(InputIterator first, InputIterator
last, Type init, BinaryOperation op);
operator+ is applied to the initial
value init (lhs argument) and, in sequence, all elements reached from
the iterator range (rhs argument). The resulting value is returned.
op is applied to
the initial value init (lhs argument) and, in sequence, all elements
reached from the iterator range. The resulting value is returned.
minus<int> is used with the intial value 1,
and the iterators refer to 2 and 3, then at step 1: 1 - 2 = -1 is
computed and at step 2: -1 - 3 = -4. So accumulate returns -4.
(See also the reduce algorithm (section 19.1.43)).
#include <numeric>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int ia[] = {1, 2, 3, 4};
vector<int> iv(ia, ia + 4);
cout <<
"Sum: " << accumulate(iv.begin(), iv.end(), int()) << "\n"
"Product: " << accumulate(iv.begin(), iv.end(), int(1),
multiplies<int>{}) << '\n';
}
// Displays:
// Sum: 10
// Product: 24
<numeric>
OutputIterator adjacent_difference([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator adjacent_difference([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result, BinaryOperation op);
op applied to the
corresponding element in the input range (left operand) and its previous
element (right operand).
#include <numeric>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
int ia[] = {1, 2, 5, 10};
vector<int> iv(ia, ia + 4);
vector<int> ov(iv.size());
adjacent_difference(iv.begin(), iv.end(), ov.begin());
copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
adjacent_difference(iv.begin(), iv.end(), ov.begin(), minus<int>());
copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays:
// 1 1 3 5
// 1 1 3 5
<algorithm>
ForwardIterator adjacent_find([ExecPol,]
ForwardIterator first, ForwardIterator last);
OutputIterator adjacent_find([ExecPol,] ForwardIterator first,
ForwardIterator last, Predicate pred);
last is returned.
pred returns true is returned. If no such element exists,
last is returned.
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
bool squaresDiff10(size_t first, size_t second)
{
return second * second - first * first >= 10;
}
int main()
{
string sarr[] =
{
"Alpha", "bravo", "charley", "delta", "echo", "echo",
"foxtrot", "golf"
};
auto last = end(sarr); // see the 'begin / end' section
string *result = adjacent_find(sarr, last);
cout << *result << '\n';
result = adjacent_find(++result, last);
cout << "Second time, starting from the next position:\n" <<
(
result == last ?
"** No more adjacent equal elements **"
:
"*result"
) << '\n';
size_t iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
size_t *ires = adjacent_find(iv, end(iv), squaresDiff10);
cout <<
"The first numbers for which the squares differ at least 10: "
<< *ires << " and " << *(ires + 1) << '\n';
}
// Displays:
//
// echo
// Second time, starting from the next position:
// ** No more adjacent equal elements **
// The first numbers for which the squares differ at least 10: 5 and 6
<algorithm>
bool all_of([ExecPol,] InputIterator first,
InputIterator last, Predicate pred);
bool any_of([ExecPol,] InputIterator first,
InputIterator last, Predicate pred);
bool none_of([ExecPol,] InputIterator first,
InputIterator last, Predicate pred);
true if the unary predicate
pred returns true for all elements reached from the iterator range
[first, last); otherwise false is returned.
true if the unary predicate
pred returns true for at least on of the elements reached from the
iterator range [first, last); otherwise false is returned.
true if the unary predicate
pred returns true for none of the elements reached from the iterator
range [first, last); otherwise false is returned.
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
bool contains_a(string const &str)
{
return str.find('a') != string::npos;
}
int main()
{
string sarr[] =
{ "Alpha", "Bravo", "Charley", "Delta", "Echo" };
auto past = end(sarr); // see the next section
cout << "All elements contain 'a': " <<
all_of(sarr, past, contains_a) << "\n"
"At least one element contains 'a': " <<
any_of(sarr, past, contains_a) << "\n"
"None of the elements contains 'a': " <<
none_of(sarr, past, contains_a) << '\n';
}
// Displays:
// All elements contain 'a': 0
// At least one element contains 'a': 1
// None of the elements contains 'a': 0
<iterator> (also available when including
<algorithm>)
auto begin([const] &obj);
auto end([const] &obj);
Type [cons] *begin(Type [const] (&array)[N]);
Type [cons] *end(Type [const] (&array)[N]);
auto cbegin(const &obj);
auto cend(const &obj);
begin and end functions return, respectively, the begin-
and end-iterators or pointers of objects offering begin() and end()
members or of arrays of (compile-time) available sizes.
obj.begin() and obj.end() of (possibly const)
references to obj
const)
pointers to, respectively, the first and beyond the last
element of the array argument, which must be an array of
(compile-time) known size.
obj.begin() and obj.end() of const
references to obj
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string sarr[] =
{ "Alpha", "Bravo", "Charley", "Delta", "Echo" };
// since sarr == begin(sarr), begin(...) is not used here
auto next = end(sarr);
cout << "sarr has " << size(sarr) <<
" (== " << (next - sarr) << ") elements\n"
"the last char. of the first element is " <<
*(end(sarr[0]) - 1) << '\n';
}
// Displays:
// sarr has 5 (== 5) elements
// the last char. of the first element is a
<algorithm>
bool binary_search(ForwardIterator first, ForwardIterator
last, Type const &value);
bool binary_search(ForwardIterator first, ForwardIterator
last, Type const &value, Comparator comp);
value is searched for using binary
search in the elements reached from the iterator range [first,
last). The elements must have been sorted by the Type::operator<
function. True is returned if the element was found, false otherwise.
value is searched for using binary
search in the elements reached from the iterator range [first,
last). The elements in the range must have been sorted by the Comparator
function object. True is returned if the element was found, false
otherwise. As illustrated by the following example, the function object
function's first parameter refers to an element in the iterator range, while
the function object's second parameter refers to value.
#include <algorithm>
#include <string>
#include <iostream>
#include <functional>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
auto past = end(sarr);
bool result = binary_search(sarr, past, "foxtrot");
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
reverse(sarr, past); // reverse the order of elements
// binary search now fails:
result = binary_search(sarr, past, "foxtrot");
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
// ok when using appropriate
// comparator:
result = binary_search(sarr, past, "foxtrot", greater<string>());
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
// alternatively, using a lambda expression showing the used 'sarr'
// indices and the value of the second parameter:
result = binary_search(sarr, past, "foxtrot",
[&](string const &sarrEl, string const &value)
{
cout << "comparing element " << (&sarrEl - sarr) <<
" (" << sarrEl << ") to " << value << '\n';
return sarrEl > value;
}
);
cout << "found it: " << result << '\n';
}
// Displays:
// found foxtrot
// didn't find foxtrot
// found foxtrot
// comparing element 4 (delta) to foxtrot
// comparing element 2 (foxtrot) to foxtrot
// comparing element 1 (golf) to foxtrot
// comparing element -3 (foxtrot) to foxtrot
// found it: 1
If value is in fact present in the range of values, then this generic
algorithm doesn't answer the question where value is located. If that
question must be answered the generic algorithms lower_bound
and upper_bound can be used. Refer to sections
19.1.30 and 19.1.61 for examples illustrating the use of these
latter two algorithms.
<algorithm>
OutputIterator copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator destination);
OutputIterator copy_if([ExecPol,] InputIterator first,
InputIterator last, OutputIterator destination, Predicate pred);
[first, last) are copied (assigned) to the destination output
range. The return value is the OutputIterator pointing just beyond the last
element that was copied to the destination range (so, `last' in the
destination range is returned).
n elements, returning an iterator pointing
just beyond the last element that was copied to the destination range.
copy. It uses an ostream_iterator for
string objects. This iterator writes the string values to the
specified ostream (i.e., cout), separating the values by the specified
separation string (i.e., " ").
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;
bool pred(std::string const &str)
{
return "aceg"s.find(str.front()) == string::npos;
}
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
auto last = end(sarr);
copy(sarr + 2, last, sarr); // move all elements two positions left
// copy to cout using an ostream_iterator for strings
copy(sarr, last, ostream_iterator<string>(cout, " "));
cout << '\n';
// using copy_if:
copy_if(sarr, sarr + size(sarr), sarr, pred);
copy(sarr, sarr + size(sarr), ostream_iterator<string>(cout, " "));
cout << '\n';
}
// Displays:
// charley delta echo foxtrot golf hotel golf hotel
// delta foxtrot hotel hotel golf hotel golf hotel
unique_copy
<algorithm>
BidirectionalIterator copy_backward(InputIterator first,
InputIterator last, BidirectionalIterator last2);
[first, last) are copied from the element at position last - 1
until (and including) the element at position first to the element range,
ending at position last2 - 1 using the assignment operator of the
underlying data type. The destination range is therefore [last2 - (last
- first), last2).
Note that this algorithm does not reverse the order of the elements when copying them to the destination range.
The return value is the BidirectionalIterator pointing to the last element
that was copied to the destination range (so, `first' in the destination
range, pointed to by last2 - (last - first), is returned).
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
auto past = end(sarr);
copy
(
copy_backward(sarr + 3, past, past - 3),
past,
ostream_iterator<string>(cout, " ")
);
cout << '\n';
}
// Displays: golf hotel foxtrot golf hotel foxtrot golf hotel
<algorithm>
size_t count([ExecPol,] InputIterator first,
InputIterator last, Type const &value);
size_t count_if([ExecPol,] InputIterator first,
InputIterator last, Predicate predicate);
value
occurs in the elements reached from the iterator range [first, last).
Uses Type::operator== to determine whether value is equal to an
element in the iterator range.
predicate' returns true when applied to the
elements reached from the iterator range [first, last).
#include <algorithm>
#include <iostream>
using namespace std;
bool pred(int value)
{
return value & 1;
}
int main()
{
int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};
cout << "Number of times the value 3 is available: " <<
count(ia, ia + size(ia), 3) << "\n"
"Number of odd values in the array is: " <<
count_if(ia, ia + size(ia), pred) << '\n';
}
// Displays: Number of times the value 3 is available: 3
// Number of odd values in the array is: 5
<algorithm>
bool equal([ExecPol,] InputIterator first, InputIterator
last, InputIterator otherFirst);
bool equal([ExecPol,] InputIterator first, InputIterator last,
InputIterator otherFirst, BinaryPredicate pred);
[first,
last) are compared to a range of equal length starting at otherFirst. The
function returns true if the visited elements in both ranges are equal
pairwise. The ranges need not be of equal length, only the elements in the
indicated range are considered (and must be available).
[first, last) are compared to a range of equal length starting at
otherFirst. The function returns true if the binary predicate, applied
to all corresponding elements in both ranges returns true for every pair
of corresponding elements. The ranges need not be of equal length, only the
elements in the indicated range are considered (and must be available).
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string first[] =
{
"Alpha", "bravo", "Charley", "delta", "Echo",
"foxtrot", "Golf", "hotel"
};
string second[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
auto past = end(first);
cout << "The elements of `first' and `second' are pairwise " <<
(equal(first, past, second) ? "equal" : "not equal") <<
'\n' <<
"compared case-insensitively, they are " <<
(
equal(first, past, second, caseString) ?
"equal" : "not equal"
) << '\n';
}
// Displays:
// The elements of `first' and `second' are pairwise not equal
// compared case-insensitively, they are equal
<algorithm>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, Type
const &value);
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, Type
const &value, Compare comp);
map (section 12.4.7) and multimap (section
12.4.8)):
operator< of the data type to which the iterators point was used to
sort the elements in the provided range), a pair of iterators is returned
representing the return value of, respectively, lower_bound (returning
the first element that is not smaller than the provided reference value, see
section 19.1.30) and upper_bound (returning the first element
beyond the provided reference value, see section 19.1.61).
comp function object was used to sort the elements in the provided
range), a pair of iterators is returned representing the return values of,
respectively, the functions lower_bound (section 19.1.30) and
upper_bound (section 19.1.61).
#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
int range[] = {1, 3, 5, 7, 7, 9, 9, 9};
auto past = end(range);
pair<int *, int *> pi;
pi = equal_range(range, past, 6);
cout << "Lower bound for 6: " << *pi.first << "\n"
"Upper bound for 6: " << *pi.second << '\n';
pi = equal_range(range, past, 7);
cout << "Lower bound for 7: ";
copy(pi.first, past, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "Upper bound for 7: ";
copy(pi.second, past, ostream_iterator<int>(cout, " "));
cout << '\n';
sort(range, past, greater<int>());
cout << "Sorted in descending order\n";
copy(range, past, ostream_iterator<int>(cout, " "));
cout << '\n';
pi = equal_range(range, past, 7, greater<int>());
cout << "Lower bound for 7: ";
copy(pi.first, past, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "Upper bound for 7: ";
copy(pi.second, past, ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays:
// Lower bound for 6: 7
// Upper bound for 6: 7
// Lower bound for 7: 7 7 9 9 9
// Upper bound for 7: 9 9 9
// Sorted in descending order
// 9 9 9 7 7 5 3 1
// Lower bound for 7: 7 7 5 3 1
// Upper bound for 7: 5 3 1
<utility>
Type exchange(Type &object1, ValueType &&newValue);
newValue is assigned to object1, and object1's
previous value is returned.
#include <utility>
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
bool more = argc > 5;
cout << "more than 5: " << exchange(more, argc > 2) <<
", more than 2: " << more << '\n';
}
// With `a.out one two three' displays:
//
// more than 5: 0, more than 2: 1
<algorithm>
void fill([ExecPol,] ForwardIterator first,
ForwardIterator last, Type const &value);
void fill_n([ExecPol,] ForwardIterator first, Size n, Type
const &value);
[first, last) are initialized to value, overwriting
previously stored values.
n elements starting at the element
pointed to by first are initialized to value, overwriting previously
stored values.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
vector<int> iv(8);
fill(iv.begin(), iv.end(), 8);
copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
fill_n(iv.begin() + 2, 4, 4);
copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays: 8 8 8 8 8 8 8 8
// 8 8 4 4 4 4 8 8
<algorithm>
InputIterator find([ExecPol,] InputIterator first,
InputIterator last, Type const &value);
InputIterator find_if([ExecPol,] InputIterator first,
InputIterator last, Predicate pred);
InputIterator find_if_not([ExecPol,] InputIterator first,
InputIterator last, Predicate pred);
value is searched for in the
elements reached from the iterator range [first, last). An iterator
pointing to the first element found is returned. If the element was not found,
last is returned. The operator== of the underlying data type is used
to compare the elements.
[first, last) for which
the (unary) predicate pred returns true. If the element was not found,
last is returned.
[first, last) for which the
(unary) predicate pred returns false. If the element was not found,
last is returned. Thus, pred defines what is considered acceptable, in
which case find_if_not returns an iterator to the first element that
isn't.
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
#include <iostream>
using namespace std;
class CaseName
{
std::string d_string;
public:
CaseName(char const *str): d_string(str)
{}
bool operator()(std::string const &element) const
{
return strcasecmp(element.c_str(), d_string.c_str()) == 0;
}
};
void show(string const *begin, string const *end)
{
if (begin == end)
cout << "No elements were found";
else
copy(begin, end, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
int main()
{
string sarr[] =
{
"Alpha", "Bravo", "Charley", "Delta", "Echo"
};
auto past = end(sarr);
show(find(sarr, past, "Delta"), past);
show(find(sarr, past, "India"), past);
show(find_if(sarr, sarr + size(sarr), CaseName{ "charley" }), past);
if (find_if(sarr, sarr + size(sarr), CaseName{ "india" }) == past)
cout << "`india' was not found in the range\n";
show(find_if_not(sarr, sarr + size(sarr), CaseName{ "alpha" }), past);
}
// Displays:
// Delta Echo
// No elements were found
// Charley Delta Echo
// `india' was not found in the range
// Bravo Charley Delta Echo
<algorithm>
ForwardIterator1 find_end([ExecPol,] ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator1 find_end([ExecPol,] ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred)
[first1, last1) is searched for the last occurrence of the sequence of
elements in the range [first2, last2). If the sequence
[first2, last2) is not found, last1 is returned, otherwise an
iterator pointing to the first element of the matching sequence is
returned. The operator== of the underlying data type is used to compare
the elements in the two sequences.
[first1, last1) is searched for the last occurrence of the sequence of
elements in the range [first2, last2). If the sequence [first2,
last2) is not found, last1 is returned, otherwise an iterator pointing to
the first element of the matching sequence is returned. The provided binary
predicate is used to compare the elements in the two sequences.
#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
bool twice(size_t first, size_t second)
{
return first == (second << 1);
}
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel",
"foxtrot", "golf", "hotel",
"india", "juliet", "kilo"
};
string search[] =
{
"foxtrot",
"golf",
"hotel"
};
auto past = end(sarr);
copy
(
find_end(sarr, past, search, search + 3), // sequence starting
past, ostream_iterator<string>{ cout, " " } // at 2nd 'foxtrot'
);
cout << '\n';
size_t range[] = { 2, 4, 6, 8, 10, 4, 6, 8, 10 };
size_t nrs[] = { 2, 3, 4 };
copy // sequence of values starting at last sequence
( // of range[] that are twice the values in nrs[]
find_end(range, range + 9, nrs, nrs + 3, twice),
range + 9, ostream_iterator<size_t>{ cout, " " }
);
cout << '\n';
}
// Displays:
// foxtrot golf hotel india juliet kilo
// 4 6 8 10
<algorithm>
ForwardIterator1 find_first_of([ExecPol,]
ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2)
ForwardIterator1 find_first_of([ExecPol,]
ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2, BinaryPredicate pred)
[first1, last1) is searched for the first occurrence of an element in
the sequence of elements in the range [first2, last2). If no
element in the sequence [first2, last2) is found, last1 is
returned, otherwise an iterator pointing to the first element in
[first1, last1) that is equal to an element in [first2, last2)
is returned. The operator== of the underlying data type is used to compare
the elements in the two sequences.
[first1, last1) is searched for the first occurrence of an element in
the sequence of elements in the range [first2, last2). Each element in
the range [first1, last1) is compared to each element in the range
[first2, last2), and an iterator to the first element in
[first1, last1) for which the binary predicate pred (receiving an
the element out of the range [first1, last1) and an element from the
range [first2, last2)) returns true is returned. Otherwise,
last1 is returned.
#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
bool twice(size_t first, size_t second)
{
return first == (second << 1);
}
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel",
"foxtrot", "golf", "hotel",
"india", "juliet", "kilo"
};
string search[] =
{
"foxtrot",
"golf",
"hotel"
};
auto past = end(sarr);
copy
( // sequence starting
find_first_of(sarr, past, search, search + 3),// at 1st 'foxtrot'
past, ostream_iterator<string>{ cout, " " }
);
cout << '\n';
size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};
size_t nrs[] = {2, 3, 4};
// copy the sequence of values in 'range', starting at the
// first element in 'range' that is equal to twice one of the
// values in 'nrs', and ending at the past element of 'range'
copy
(
find_first_of(range, range + 9, nrs, nrs + 3, twice),
range + 9, ostream_iterator<size_t>{ cout, " " }
);
cout << '\n';
}
// Displays:
// foxtrot golf hotel foxtrot golf hotel india juliet kilo
// 4 6 8 10 4 6 8 10
<algorithm>
Function for_each([ExecPol,] ForwardIterator first,
ForwardIterator last, Function func);
[first, last) are passed in sequence as a reference to the function (or
function object) func. The function may modify the elements it receives
(as the used iterator is a forward iterator). Alternatively, if the elements
should be transformed, transform (see section 19.1.56) can be
used. The function itself or a copy of the provided function object is
returned: see the example below, in which an extra argument list is added to
the for_each call, which argument is eventually also passed to the
function given to for_each. Within for_each the return value of the
function that is passed to it is ignored. The for_each generic algorithm
looks a lot like the range-based for loop, but different from the range-based
for-loop the for_each algorithm can also be used with sub-ranges and with
reverse-iterators.
#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>
using namespace std;
void lowerCase(char &ch) // `ch' *is* modified
{
ch = tolower(static_cast<unsigned char>(ch));
}
void capitalizedOutput(string const &str) // `str' is *not* modified
{
char *tmp = new char[str.size() + 1]();
str.copy(tmp, str.size());
for_each(tmp + 1, tmp + str.size(), lowerCase);
tmp[0] = toupper(*tmp);
cout << tmp << ' ';
delete[] tmp;
}
int main()
{
string sarr[] =
{
"alpha", "BRAVO", "charley", "DELTA", "echo",
"FOXTROT", "golf", "HOTEL"
};
for_each(sarr, end(sarr), capitalizedOutput)("that's all, folks");
cout << '\n';
}
// Displays:
// Alpha Bravo Charley Delta Echo Foxtrot Golf Hotel That's all, folks
#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>
using namespace std;
void lowerCase(char &c)
{
c = tolower(static_cast<unsigned char>(c));
}
class Show
{
int d_count;
public:
Show()
:
d_count(0)
{}
void operator()(std::string &str)
{
std::for_each(str.begin(), str.end(), lowerCase);
str[0] = toupper(str[0]); // assuming str is not empty
std::cout << ++d_count << " " << str << "; ";
}
int count() const
{
return d_count;
}
};
int main()
{
string sarr[] =
{
"alpha", "BRAVO", "charley", "DELTA", "echo",
"FOXTROT", "golf", "HOTEL"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
cout << for_each(sarr, last, Show{}).count() << '\n';
}
/*
Displays (all on one line):
1 Alpha; 2 Bravo; 3 Charley; 4 Delta; 5 Echo; 6 Foxtrot;
7 Golf; 8 Hotel; 8
*/
for_each algorithm may be used with
functions defining const and non-const parameters. Also, see section
19.1.56 for differences between the for_each and transform
generic algorithms.
The for_each algorithm cannot directly be used (i.e., by passing
*this as the function object argument) inside a member function to modify
its own object as the for_each algorithm first creates its own copy of the
passed function object. A lambda function or a wrapper class whose
constructor accepts a pointer or reference to the current object and possibly
to one of its member functions solves this problem.
<algorithm>
void generate([ExecPol,] ForwardIterator first,
ForwardIterator last, Generator generator);
void generate_n([ExecPol,] ForwardIterator first, Size n,
Generator generator);
[first, last) are initialized by the return value of
generator, which can be a function or function
object. Generator::operator() does not receive any arguments. The example
uses a well-known fact from algebra: in order to obtain the square of n +
1, add 1 + 2 * n to n * n.
n elements starting at the element
pointed to by iterator first are initialized by the return value of
generator.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
class NaturalSquares
{
size_t d_newsqr;
size_t d_last;
public:
NaturalSquares(): d_newsqr(0), d_last(0)
{}
size_t operator()()
{ // using: (a + 1)^2 == a^2 + 2*a + 1
return d_newsqr += (d_last++ << 1) + 1;
}
};
int main()
{
vector<size_t> uv(10);
generate(uv.begin(), uv.end(), NaturalSquares{});
copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
cout << '\n';
uv = vector<size_t>(10);
generate_n(uv.begin(), 5, NaturalSquares{});
copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
cout << '\n';
}
// Displays: 1 4 9 16 25 36 49 64 81 100
// 1 4 9 16 25 0 0 0 0 0
<algorithm>
bool includes([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool includes([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
Compare comp);
[first1, last1) and [first2, last2) should have been
sorted using the operator< of the data type to which the iterators
point. The function returns true if every element in the second sequence
[first2, last2) is contained in the first sequence [first1,
last1) (the second range is a subset of the first range).
[first1, last1) and [first2, last2) should have been
sorted using the comp function object. The function returns true if
every element in the second sequence [first2, last2) is contained in
the first sequence [first1, last1) (the second range is a subset of
the first range).
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string first1[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
auto past1 = end(first1);
string first2[] =
{
"Alpha", "bravo", "Charley", "delta", "Echo",
"foxtrot", "Golf", "hotel"
};
auto past2 = end(first2);
string second[] = { "charley", "foxtrot", "hotel" };
cout << "The elements of `second' are " <<
(includes(first1, past1, second, second + 3) ? "" : "not") <<
" contained in the first sequence:\n"
"second is a subset of first1\n"
"The elements of `first1' are " <<
(includes(second, second + 3, first1, past1) ? "" : "not") <<
" contained in the second sequence\n"
"The elements of `second' are " <<
(includes(first2, past2, second, second + 3) ? "" : "not") <<
" contained in the first2 sequence\n"
"Using case-insensitive comparison,\n"
"the elements of `second' are " <<
(includes(first2, past2, second, second + 3, caseString) ?
"" : "not") <<
" contained in the first2 sequence\n";
}
// Displays:
// The elements of `second' are contained in the first sequence:
// second is a subset of first1
// The elements of `first1' are not contained in the second sequence
// The elements of `second' are not contained in the first2 sequence
// Using case-insensitive comparison,
// the elements of `second' are contained in the first2 sequence
<numeric>
Type inner_product(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, Type init);
Type inner_product(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, Type init,
BinaryOperator1 op1, BinaryOperator2 op2);
[first1, last1) and the same number of
elements starting at the element pointed to by first2 are added to
init, and this sum is returned. The function uses the operator+ and
operator* of the data type to which the iterators point.
op1 instead of the
default addition operator, and binary operator op2 instead of the default
multiplication operator are applied to all pairwise elements in the
range [first1, last1) and the same number of elements starting at the
element pointed to by first2. The results of the binary operator calls are
added to init and init's final value is returned.
#include <numeric>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
class Cat
{
std::string d_sep;
public:
Cat(string const &sep)
:
d_sep(sep)
{}
string operator()
(string const &s1, string const &s2) const
{
return s1 + d_sep + s2;
}
};
int main()
{
size_t ia1[] = { 1, 2, 3, 4, 5, 6, 7 };
cout << "The sum of all squares in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "is " << inner_product(ia1, ia1 + 7, ia1, 0) << '\n';
size_t ia2[] = { 7, 6, 5, 4, 3, 2, 1 };
cout << "The sum of all cross-products in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "and ";
copy(ia2, ia2 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "is " << inner_product(ia1, ia1 + 7, ia2, 0) << '\n';
string names1[] = { "Frank", "Karel", "Piet" };
string names2[] = { "Brokken", "Kubat", "Plomp"};
cout << "All combined names of ";
copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });
cout << "and\n";
copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });
cout << "are:" <<
inner_product(names1, names1 + 3, names2, string{ "\t" },
Cat{ "\n\t"}, Cat{ " " }) << '\n';
}
// Displays:
// The sum of all squares in 1 2 3 4 5 6 7 is 140
// The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84
// All combined names of Frank Karel Piet and Brokken Kubat Plomp are:
// Frank Brokken
// Karel Kubat
// Piet Plomp
<algorithm>
void inplace_merge([ExecPol,] BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last);
void inplace_merge([ExecPol,] BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last,
Compare comp);
[first,
middle) and [middle, last) are merged, keeping a sorted list (using the
operator< of the data type to which the iterators point). The final
series is stored in the range [first, last).
[first,
middle) and [middle, last) are merged, keeping a sorted list (using the
boolean result of the binary comparison operator comp). The final series
is stored in the range [first, last).
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
#include <iostream>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string range[] =
{
"alpha", "charley", "echo", "golf",
"bravo", "delta", "foxtrot",
};
inplace_merge(range, range + 4, range + 7);
copy(range, range + 7, ostream_iterator<string>{ cout, " " });
cout << '\n';
string range2[] =
{
"ALPHA", "CHARLEY", "DELTA", "foxtrot", "hotel",
"bravo", "ECHO", "GOLF"
};
inplace_merge(range2, range2 + 5, range2 + 8, caseString);
copy(range2, range2 + 8, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
// Displays:
// alpha bravo charley delta echo foxtrot golf
// ALPHA bravo CHARLEY DELTA ECHO foxtrot GOLF hotel
<numeric>
void iota(ForwardIterator first,
ForwardIterator last, Type value);
[first,
last) are assigned the values of the incremented sequence of values starting at
value. *first receives value, *(first + 1) receives
++value, etc.
#include <numeric>
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
vector<size_t> uv(10);
iota(uv.begin(), uv.end(), 0);
copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
cout << '\n';
}
// Displays: 0 1 2 3 4 5 6 7 8 9
<algorithm>
bool is_partitioned([ExecPol,] InputIterator first,
InputIterator last, UnaryPred pred);
true if pred, receiving all elements reached
from the iterator range [first, last), returns true until it
returns false, and if pred, receiving the remaining elements, returns
false. It also returns true if the range is empty.
#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>
using namespace std;
bool pCheck(int value)
{
return value < 3;
}
int main()
{
vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};
cout << "partitioned before: " <<
is_partitioned(uv.begin(), uv.end(), pCheck) << "\n"
"first value returning 'false' when partitioning: " <<
*partition(uv.begin(), uv.end(), pCheck) << '\n';
copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
cout << '\n';
cout << "partitioned after: " <<
is_partitioned(uv.begin(), uv.end(), pCheck) <<'\n';
}
// Displays: 1 4 9 16 25 36 49 64 81 100
// 1 4 9 16 25 0 0 0 0 0
<algorithm>
bool is_permutation(ForwardIterator first1,
ForwardIterator last1, ForwardIterator first2);
bool is_permutation(ForwardIterator first1,
ForwardIterator last1, ForwardIterator first2,
ForwardIterator last2);
bool is_permutation(ForwardIterator first1,
ForwardIterator last1, ForwardIterator firs2,
BinaryPred pred);
bool is_permutation(ForwardIterator first1,
ForwardIterator last1, ForwardIterator first2,
ForwardIterator last2, BinaryPred pred);
true if the elements in the
iterator range [first1, last1), are a permutation of the elements in
the identically sized range starting at first2.
pred to determine whether two elements are equal.
pred to determine whether two elements are equal.
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int one[] = { 1, -2, 3, -4, 5, -6, 7, -8, 9};
int two[] = { -8, -2, -4, -6, 3, 1, 5, 9, 7};
int three[] = { -8, -8, -4, -6, 3, 1, 5, 9, 7};
cout << "one is a permutation of two: " <<
is_permutation(one, end(one), two) << "\n"
"one is a permutation of three: " <<
is_permutation(one, end(one), three, end(three)) << '\n';
}
// Displays: one is a permutation of two: 1
// one is a permutation of three: 0
<algorithm>
bool is_sorted([ExecPol,] ForwardIterator first,
ForwardIterator last);
bool is_sorted([ExecPol,] ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
true if the elements in the
iterator range [first, last), are sorted using the elements'
operator< comparison operator.
true if the elements in the
iterator range [first, last), are sorted using the binary predicate
pred.
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};
cout << "sorted before: " <<
is_sorted(uv.begin(), uv.end()) << '\n';
sort(uv.begin(), uv.end());
cout << "sorted after " <<
is_sorted(uv.begin(), uv.end()) << '\n';
}
// Displays:
// sorted before: 0
// sorted after 1
<algorithm>
ForwardIterator is_sorted_until([ExecPol,]
ForwardIterator first, ForwardIterator last);
ForwardIterator is_sorted_until([ExecPol,]
ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
first whose elements are sorted using the elements'
operator< comparison operator.
first whose elements using the binary predicate
pred.
first + 1.
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};
cout << "sorted before: " <<
is_sorted(uv.begin(), uv.end()) << '\n';
sort(uv.begin(), uv.end());
cout << "sorted after " <<
is_sorted(uv.begin(), uv.end()) << '\n';
}
// Displays:
// sorted before: 0
// sorted after 1
<algorithm>
void iter_swap(ForwardIterator1 iter1,
ForwardIterator2 iter2);
iter1 and iter2 are
swapped.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string first[] = { "alpha", "bravo", "charley" };
string second[] = { "echo", "foxtrot", "golf" };
cout << "Before:\n";
copy(first, first + 3, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + 3, ostream_iterator<string>(cout, " "));
cout << '\n';
for (size_t idx = 0; idx != 3; ++idx)
iter_swap(first + idx, second + idx);
cout << "After:\n";
copy(first, first + 3, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + 3, ostream_iterator<string>(cout, " "));
cout << '\n';
}
// Displays:
// Before:
// alpha bravo charley
// echo foxtrot golf
// After:
// echo foxtrot golf
// alpha bravo charley
<algorithm>
bool lexicographical_compare([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool lexicographical_compare([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare
comp);
[first1, last1) and [first2,
last2) are compared. The function returns true
operator<
of the underlying data type),
last1 is reached, but last2 isn't reached yet.
false is
returned:
operator<
of the data type to which the iterators point, reversing the operands),
last2 is reached, but last1 isn't reached yet,
last1 and last2 are reached.
comp is used instead of
operator< of the data type to which the iterators point.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
void compare(string const &word1, string const &word2)
{
cout << '`' << word1 << "' is " <<
(
lexicographical_compare(word1.begin(), word1.end(),
word2.begin(), word2.end()) ?
"before `" : "beyond or at `"
) <<
word2 << "' in the alphabet\n";
}
int main()
{
string word1 = "hello";
string word2 = "help";
compare(word1, word2);
compare(word1, word1);
compare(word2, word1);
string one[] = {"alpha", "bravo", "charley"};
string two[] = {"ALPHA", "BRAVO", "DELTA"};
copy(one, one + 3, ostream_iterator<string>{ cout, " " });
cout << " is ordered " <<
(
lexicographical_compare(one, one + 3,
two, two + 3, caseString) ?
"before " : "beyond or at "
);
copy(two, two + 3, ostream_iterator<string>{ cout, " " });
cout << "\n"
"using case-insensitive comparisons.\n";
}
// Displays:
// `hello' is before `help' in the alphabet
// `hello' is beyond or at `hello' in the alphabet
// `help' is beyond or at `hello' in the alphabet
// alpha bravo charley is ordered before ALPHA BRAVO DELTA
// using case-insensitive comparisons.
<algorithm>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last, const Type &value);
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last, const Type &value, BinaryPredicate
pred);
[first, last) are searched for
the first element that is not less than (i.e., greater than or equal to)
value. The returned iterator marks the location in the sequence where
value can be inserted without breaking the sorted order of the
elements. The operator< of the data type to which the iterators point is
used. If no such element is found, last is returned.
[first, last) must have been sorted using the comp function
(-object). Each element in the range is compared to value using the
comp function, receiving an element from the iterator range as its first
argument and type as its second argument. An iterator to the first element
for which the binary predicate comp, applied to the elements of the range
and value, returns false is returned. If no such element is found,
last is returned.
As illustrated by the following example, the function object
function's first parameter refers to an element in the iterator range, while
the function object's second parameter refers to value.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <functional>
using namespace std;
int main()
{
int ia[] = { 10, 20, 30 };
cout << "Sequence: ";
copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
cout << "\n"
"15 can be inserted before " <<
*lower_bound(ia, ia + 3, 15) << "\n"
"35 can be inserted after " <<
(lower_bound(ia, ia + 3, 35) == ia + 3 ?
"the last element" : "???") << '\n';
cout << "Sequence: ";
copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
cout << "\n"
"15 can be inserted before " <<
*lower_bound(ia, ia + 3, 15, less<int>()) << "\n"
"35 can be inserted before " <<
(lower_bound(ia, ia + 3, 35, less<int>()) == ia ?
"the first element " : "???") << '\n';
vector<int> array{ 5, 10, 20, 20, 20, 30 };
auto iter = lower_bound(array.begin(), array.end(), 20,
[&](int &arrayEl, int value)
{
cout << "Comparing " << arrayEl <<
" (index: " << (&arrayEl - &array[0]) << ")"
" to " << value << '\n';
return arrayEl < value;
}
);
cout << "New 20 to insert at idx " << (iter - array.begin()) << '\n';
}
// Displays:
// Sequence: 10 20 30
// 15 can be inserted before 20
// 35 can be inserted after the last element
// Sequence: 10 20 30
// 15 can be inserted before 20
// 35 can be inserted before ???
// Comparing 20 (index: 3) to 20
// Comparing 10 (index: 1) to 20
// Comparing 20 (index: 2) to 20
// New 20 to insert at idx 2
The binary_search generic algorithm (cf. section 19.1.7)can be used
to determine whether or not value is present in the iterator range. The
upper_bound algorithm can be used to find the last element of a series of
values equal to value. The upper_bound section (19.1.61) also
contains an extensive example illustrating the use of lower_bound and as
upper_bound.
<algorithm>
Type const &max(Type const &one, Type const &two);
Type const &max(Type const &one, Type const &two, Comparator
comp);
Type const &min(Type const &one, Type const &two);
Type const &min(Type const &one, Type const &two, Comparator
comp);
one
and two is returned, using the operator> of the data type to which
the iterators point to determine which element is the larger one.
one is returned if the binary
predicate comp(one, two) returns true, otherwise two is returned.
std::min instead of std::max,
returning the smaller of the two arguments.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) <= 0;
}
string const &call(bool first, string const &lhs, string const &rhs)
{
return first? max(lhs, rhs) : min(lhs, rhs);
}
string const &call(bool first, string const &lhs, string const &rhs,
bool (*cmp)(string const &, string const &))
{
return first? max(lhs, rhs, cmp) : min(lhs, rhs, cmp);
}
int main(int argc, char **argv) // no args: use max, else min
{
bool fun = argc == 1;
char const *where = fun ? "last\n" : "first\n";
cout << "Word '" << call(fun, "first", "second") <<
"' is lexicographically " << where <<
"Word '" << call(fun, "first", "SECOND") <<
"' is lexicographically " << where <<
"Word '" << call(fun, "first", "SECOND", caseString) <<
"' is lexicographically " << where;
}
// Displays when calling without args:
// Word 'second' is lexicographically last
// Word 'first' is lexicographically last
// Word 'SECOND' is lexicographically last
// and with an argument:
// Word 'first' is lexicographically first
// Word 'SECOND' is lexicographically first
// Word 'first' is lexicographically first
<algorithm>
ForwardIterator max_element([ExecPol,] ForwardIterator first,
ForwardIterator last);
ForwardIterator max_element([ExecPol,] ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
ForwardIterator min_element([ExecPol,] ForwardIterator first,
ForwardIterator last);
ForwardIterator min_element([ExecPol,] ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
pair<ForwardIterator, ForwardIterator> max_element([ExecPol,]
ForwardIterator first,ForwardIterator last);
pair<ForwardIterator, ForwardIterator> max_element([ExecPol,]
ForwardIterator first,ForwardIterator last,
BinaryPredicate pred);
[first, last) is returned. The
operator< of the data type to which the iterators point is used to decide
which of the elements is the largest.
operator<, the
binary predicate pred is used to make the comparisons between the elements
reached from the iterator range [first, last). The element for which
pred returns most often true, compared with other elements, is
returned.
std::min_element instead of
std::max_element, returning iterators to the smallest elements in the
iterator ranges [first, last).
std::pair objects whose first
members contain the iterators returned by the min generic algorithms and
whose second members contain the iterators returned by the max generic
algorithms.
#include <algorithm>
#include <iostream>
using namespace std;
bool absCompare(int first, int second)
{
return abs(first) < abs(second);
};
int *maxMin(bool high, int *begin, int *end)
{
return high ? max_element(begin, end) : min_element(begin, end);
}
int *maxMin(bool high, int *begin, int *end, bool (*comp)(int, int))
{
return high ? max_element(begin, end, comp)
: min_element(begin, end, comp);
}
// no args: calls max_element, else min_element
int main(int argc, char **argv)
{
bool max = argc == 1;
char const *type = max? "max" : "min";
int ia[] = {-4, 7, -2, 10, -12};
cout << "The " << type << ". int value is " <<
*maxMin(max, ia, ia + 5) << "\n"
"The max. absolute int value is " <<
*maxMin(max, ia, ia + 5, absCompare) << '\n';
}
// Displays, when called without arguments:
// The max. int value is 10
// The max. absolute int value is -12
// otherwise:
// The minimum int value is -12
// The minimum absolute int value is -2
<algorithm>
OutputIterator merge([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
OutputIterator merge([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
[first1,
last1) and [first2, last2) are merged, keeping a sorted list (using the
operator< of the data type to which the iterators point). The final
series is stored in the range starting at result and ending just before
the OutputIterator returned by the function.
[first1,
last1) and [first2, last2) are merged, keeping a sorted list (using the
boolean result of the binary comparison operator comp). The final series
is stored in the range starting at result and ending just before the
OutputIterator returned by the function.
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
#include <iostream>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
int main()
{
string range1[] = // 5 elements
{ "alpha", "bravo", "foxtrot", "hotel", "zulu" };
string range2[] = // 4 elements
{ "delta", "echo", "golf", "romeo" };
string result[5 + 4];
copy(result,
merge(range1, range1 + 5, range2, range2 + 4, result),
ostream_iterator<string>{ cout, " " });
cout << '\n';
string range3[] =
{ "ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU" };
string range4[] = { "delta", "ECHO", "GOLF", "romeo" };
copy(result,
merge(range3, range3 + 5, range4, range4 + 4, result,
caseString),
ostream_iterator<string>{ cout, " " });
cout << '\n';
}
// Displays:
// alpha bravo delta echo foxtrot golf hotel romeo zulu
// ALPHA bravo delta ECHO foxtrot GOLF HOTEL romeo ZULU
<algorithm>
pair<Type const &, Type const &> minmax(
Type const &t1, Type const &t2);
pair<Type const &, Type const &> minmax(Type const &t1,
Type const &t2, BinaryPred pred);
pair<Type const &, Type const &> minmax(
std:initializer<list<Type> values);
pair<Type const &, Type const &> minmax(
std:initializer<list<Type> values, BinaryPred pred);
std::pair whose first
and second members contain, respectively, the smaller and the larger value
of the function's arguments, using Type's operator< to compare the two
values.
t1 is the smaller element if pred(t1, t2) returns
true.
iterator_range objects.
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;
int main()
{
vector<size_t> uv(10);
auto values = minmax(5, 2, less<int>{});
cout << values.first << " is smaler than " << values.second << '\n';
}
// Displays: 2 is smaler than 5
<algorithm>
pair<InputIterator1, InputIterator2>
mismatch([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2);
pair<InputIterator1, InputIterator2>
mismatch([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, Compare comp);
first1 and first2 are compared using the equality operator of the
data type to which the iterators point. Comparison stops if the compared
elements differ (i.e., operator== returns false) or last1 is
reached. A pair containing iterators pointing to the final positions is
returned. The second sequence may contain more elements than the first
sequence. The behavior of the algorithm is undefined if the second sequence
contains fewer elements than the first sequence.
first1 and first2 are compared using the binary comparison
operation as defined by comp, instead of
operator==. Comparison stops if the comp function returns false
or last1 is reached. A pair containing iterators pointing to the final
positions is returned. The second sequence may contain more elements than the
first sequence. The behavior of the algorithm is undefined if the second
sequence contains fewer elements than the first sequence.
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <utility>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string range1[] = { "alpha", "bravo", "foxtrot", "hotel", "zulu" };
string range2[] = { "alpha", "bravo", "foxtrot", "Hotel", "zulu" };
pair<string *, string *> pss = mismatch(range1, range1 + 5, range2);
cout << "The elements " << *pss.first << " and " << *pss.second <<
" differ at index " << (pss.first - range1) << '\n';
if
(
mismatch(range1, range1 + 5, range2, caseString).first
==
range1 + 5
)
cout << "When compared case-insensitively they match\n";
}
/*
Displays:
The elements hotel and Hotel at offset 3 differ
When compared case-insensitively they match
*/
<algorithm>
OutputIter move([ExecPol,] InputIter first, InputIter last,
OutputIter dest);
BidirIter move_backward(BidirIter first, BidirIter last,
BidirIter lastDest);
[first, last) are moved to the range starting at dest,
returning the iterator pointing just past the last element in the range
starting at dest.
[first, last) are moved in reverse order to the range starting,
iterating backward, at lastDest, returning the iterator pointing to the
beginning of the range ending at lastDest. The destination iterator
lastDest may not point to elements within the range [first, last).
move(_backward) the elements in the iterator range
[first, last) are still valid, but may have changed.
See also shift_left and shift_right:
(cppreference).
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;
void show(string const *begin, string const *end)
{
copy(begin, end, ostream_iterator<string>(cout, ", "));
cout << '\n';
}
int main()
{
string sarr[] = { "alpha", "bravo", "charley", "delta" };
string dest[4] = { "", };
auto last = end(sarr);
auto lastDest = move(sarr, last, dest); // move all elements to dest
cout << "sarr after move:\n";
show(sarr, last);
cout << "dest after move:\n";
show(dest, lastDest);
move_backward(dest, lastDest, last); // move_backward to sarr
cout << "sarr after move_backward:\n";
show(sarr, last);
cout << "dest after move_backward:\n";
show(dest, lastDest);
}
// Displays:
// sarr after move:
// , , , ,
// dest after move:
// alpha, bravo, charley, delta,
<algorithm>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Comp comp);
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Comp comp);
[first, last), is determined. For example, if
the elements 1, 2 and 3 are the range for which next_permutation
is called, then subsequent calls of next_permutation reorders the
following series:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
This example shows that the elements are reordered such that each new
permutation represents the next bigger value (132 is bigger than 123, 213 is
bigger than 132, etc.) using operator< of the data type to which the
iterators point. The value true is returned if a reordering took place,
the value false is returned if no reordering took place, which is the case
if the sequence represents the last (biggest) value. In that case, the
sequence is also sorted using operator<.
[first, last) is determined, using the binary
predicate comp to compare elements. The elements in the range are
reordered. The value true is returned if a reordering took place, the
value false is returned if no reordering took place, which is the case if
the resulting sequence would haven been ordered using the binary predicate
comp to compare elements.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
bool caseString(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
// to obtain previous permutations change 'next_' to 'prev_'
int main()
{
string saints[] = {"Oh", "when", "the", "saints"};
cout << "All permutations of 'Oh when the saints':\n"
"Sequences:\n";
do
{
copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
while (next_permutation(saints, saints + 4, caseString));
cout << "After first sorting the sequence:\n";
sort(saints, saints + 4, caseString);
cout << "Sequences:\n";
do
{
copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
while (next_permutation(saints, saints + 4, caseString));
}
// Displays (partially):
// All permutations of 'Oh when the saints':
// Sequences:
// Oh when the saints
// saints Oh the when
// saints Oh when the
// saints the Oh when
// ...
// After first sorting the sequence:
// Sequences:
// Oh saints the when
// Oh saints when the
// Oh the saints when
// Oh the when saints
// ...
<algorithm>
void nth_element([ExecPol,] RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last);
void nth_element([ExecPol,] RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last, Compare
comp);
[first,
last) are sorted relative to the element pointed to by nth: all elements
in the range [left, nth) are smaller than the element pointed to by
nth, and alle elements in the range [nth + 1, last) are greater
than the element pointed to by nth. The two subsets themselves are not
sorted. The operator< of the data type to which the iterators point is
used to compare the elements.
[first,
last) are sorted relative to the element pointed to by nth: all elements
in the range [left, nth) are smaller than the element pointed to by
nth, and alle elements in the range [nth + 1, last) are greater
than the element pointed to by nth. The two subsets themselves are not
sorted. The comp function object is used to compare the elements.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <functional>
using namespace std;
int main()
{
int ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
nth_element(ia, ia + 3, ia + 10);
cout << "sorting with respect to " << ia[3] << '\n';
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
nth_element(ia, ia + 5, ia + 10, greater<int>());
cout << "sorting with respect to " << ia[5] << '\n';
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays:
// sorting with respect to 4
// 1 2 3 4 9 7 5 6 8 10
// sorting with respect to 5
// 10 8 7 9 6 5 3 4 2 1
<algorithm>
void partial_sort([ExecPol,] RandomAccessIterator begin,
RandomAccessIterator middle, RandomAccessIterator end);
void partial_sort([ExecPol,] RandomAccessIterator begin,
RandomAccessIterator middle, RandomAccessIterator end,
BinaryPredicate pred);
void partial_sort_copy([ExecPol,] InputIterator begin,
InputIterator end,
RandomAccessIterator dest_begin, RandomAccessIterator dest_end);
void partial_sort_copy([ExecPol,] InputIterator begin,
InputIterator end,
RandomAccessIterator dest_begin, RandomAccessIterator dest_end,
BinaryPredicate pred);
middle - begin) smallest
elements are sorted and stored in the range [begin, middle) using the
operator< of the data type to which the iterators point to compare
elements. The remaining elements of the series remain unsorted, and are stored
in the range [middle, end).
middle - begin) smallest
elements (according to the provided binary predicate pred) are sorted and
stored in the range [begin, middle). The remaining elements of the
series remain unsorted.
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = { 1, 9, 5, 3, 7, 2, 4, 6, 8, 10 };
int ia2[6];
partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);
cout << "the 6 smallest elements: ";
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
partial_sort(ia, ia + 3, ia + 10);
cout << "find the 3 smallest elements:\n";
copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "find the 5 largest elements:\n";
partial_sort(ia, ia + 5, ia + 10, greater<int>());
copy(ia, ia + 5, ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays:
// the 6 smallest elements: 1 2 3 4 5 6
// find the 3 smallest elements:
// 1 2 3
// find the 5 biggest elements:
// 10 9 8 7 6
<numeric>
OutputIterator partial_sum(InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator partial_sum(InputIterator first, InputIterator
last, OutputIterator result, BinaryOperation op);
[result, <returned OutputIterator>) receives a value which is obtained
by adding the elements in the corresponding range of the range [first,
last). The first element in the resulting range will be equal to the element
pointed to by first.
[result, <returned OutputIterator>) is obtained by applying the binary
operator op to the previous element in the resulting range and the
corresponding element in the range [first, last). The first
element in the resulting range will be equal to the element pointed to by
first.
inclusive_scan and exclusive_scan, supporting
execution policies:
(cppreference).
#include <numeric>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = {1, 2, 3, 4, 5};
int ia2[5];
copy(ia2,
partial_sum(ia, ia + 5, ia2),
ostream_iterator<int>(cout, " "));
cout << '\n';
copy(ia2,
partial_sum(ia, ia + 5, ia2, multiplies<int>()),
ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
Displays:
1 3 6 10 15
1 2 6 24 120
*/
<algorithm>
BidirectionalIterator partition([ExecPol,]
BidirectionalIterator first, BidirectionalIterator last,
UnaryPredicate pred);
BidirectionalIterator stable_partition([ExecPol,]
BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate
pred);
ForwardIterator partition_point( ForwardIterator first,
ForwardIterator last, UnaryPredicate pred );
[first,
last) for which the unary predicate pred evaluates as true are placed
before the elements which evaluate as false.
false and the relative order of all elements for which the predicate
evaluates to true is kept.
[first, last) range, but returns an iterator to the first element for
which pred returns false. If pred returns true for all
elements then last is returned.
pred evaluates as true.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
void show(int *begin, int *end)
{
copy(begin, end, ostream_iterator<int>{ cout, " " });
cout << '\n';
}
int main()
{
int org[] = { 1, 3, 5, 7, 9, 10, 2, 8, 6, 4 };
int ia[10];
copy(org, org + 10, ia);
auto lessThan4 = [=](int value)
{
return value <= 4;
};
int *split = partition(ia, ia + 10, lessThan4);
cout << "Last ia[]- element <= 4 is ia[" << split - ia - 1 << "]\n";
show(ia, end(ia));
copy(org, org + 10, ia);
split = stable_partition(ia, ia + 10, lessThan4);
cout << "Last org[]-element <= 4 is ia[" << split - ia - 1 << "]\n";
show(ia, end(ia));
cout << "org[]-elements up to the partition point 4 are:\n";
show(org, partition_point(org, org + 10, lessThan4));
}
// Displays:
// Last ia[]- element <= 4 is ia[3]
// 1 3 4 2 9 10 7 8 6 5
// Last org[]-element <= 4 is ia[3]
// 1 3 2 4 5 7 9 10 8 6
// org[]-elements up to the partition point 4 are:
// 1 3
<algorithm>
std::pair<ForwardIter2, ForwardIter3>
partition_copy([ExecPol,] ForwardIter1 first, ForwardIter1 last,
ForwardIter2 trueDest, ForwardIter3 falseDest,
UnaryPredicate pred );
[first,
last) for which pred returns true are copied to the range starting at
trueDest, while the remaining elements are copied to the range starting at
falseDest. the range [first, last) may not overlap with the ranges
starting at trueDest or falseDest.
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;
bool pred(std::string const &str)
{
return "aeiou"s.find(str.front()) != string::npos;
}
void show(string const *begin, string const *end)
{
copy(begin, end, ostream_iterator<string>(cout, ", "));
cout << '\n';
}
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string trueDest[size(sarr)];
string falseDest[size(sarr)];
pair<string *, string *> lastTF = // lastTrue, lastFalse
partition_copy(sarr, end(sarr), trueDest, falseDest, pred);
cout << "pred() == true elements:\n";
show(trueDest, lastTF.first);
cout << "pred() == false elements:\n";
show(falseDest, lastTF.second);
}
// Displays:
// pred() == true elements:
// alpha, echo,
// pred() == false elements:
// bravo, charley, delta, foxtrot, golf, hotel,
<numeric>
Type reduce([ExecPol,] InputIterator first, InputIterator last);
Type reduce([ExecPol,] InputIterator first, InputIterator last,
Type init);
Type reduce([ExecPol,] InputIterator first, InputIterator last,
BinaryOperation op);
Type reduce([ExecPol,] InputIterator first, InputIterator last,
Type init, BinaryOperation op);
accumulate
(cf. accumulate), but the algorithm requires that the used
operator is both associative and commutative: regrouping and rearranging the
elements in any order may not affect the final outcome. E.g., the numeric
addition operator satisfies both requirements.
operator+ is applied to the elements in
the range [first, last), returning the resulting sum.
op is applied to
the initial value init (lhs argument) and, respectively, the elements from
the iterator range [first, last). The resulting sum value is returned.
operator+ the binary operator op is
used, receiving the variable that's eventually returned from the function as
its lhs argument and the elements in the iterator range as its rhs argument,
assigning the operator's returned values to the variable that's eventually
returned.
// compile as: g++ -O2 reduce.cc -ltbb
#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
using namespace std;
int main()
{
int ia[] = {1, 2, 3, 4};
vector<int> iv(ia, ia + 4);
// for demonstration purpose: it's unlikely that
cout << // for 4 values parallel execution is used
"Sum: " << reduce(execution::par,
iv.begin(), iv.end(), int()) << "\n"
"Product: " << reduce(iv.begin(), iv.end(), int(1),
multiplies<int>{}) << '\n';
}
// Displays:
// Sum: 10
// Product: 24
<algorithm>
ForwardIterator remove([ExecPol,] ForwardIterator first,
ForwardIterator last, Type const &value);
OutputIterator remove_copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator dest, Type const &value);
OutputIterator remove_copy_if([ExecPol,]
InputIterator first, InputIterator last,
OutputIterator dest,
UnaryPredicate pred);
ForwardIterator remove_if([ExecPol,] ForwardIterator first,
ForwardIterator last, UnaryPredicate pred);
[first, last) are reordered such that all values unequal to value
are placed at the beginning of the range. The returned forward iterator points
to the first element that can be removed after reordering. The range
[returnvalue, last) is called the leftover of the algorithm. Note
that the leftover may contain elements different from value, but these
elements can be removed safely, as such elements are also present in the range
[first, returnvalue). Such duplication is the result of the fact that
the algorithm copies, rather than moves elements into new locations.
The function uses operator== of the data type to which the iterators point
to determine which elements to remove.
[first, last) not matching value are copied to the range
[dest, returnvalue), where returnvalue is the value returned by
the function. The range [first, last) is not modified. The function
uses operator== of the data type to which the iterators point to determine
which elements not to copy.
[first, last) for which the unary predicate pred returns true
are not inserted into the result iterator. All other elements are copied
to the range [dest, returnvalue), where returnvalue is the value
returned by the function. The range [first, last) is not modified.
[first, last) are reordered such that all values for which the unary
predicate pred returns false are placed at the beginning of the
range, keeping their relative order. The returned forward iterator
points to the first element, after reordering, for which pred returned
true. The range [returnvalue, last) is called the leftover of
the algorithm. The leftover may contain elements for which the predicate
pred returns false, but these can safely be removed, as such elements
are also present in the range [first, returnvalue). Such duplication is
the result of the fact that the algorithm copies, rather than moves
elements into new locations.
copy-overloads expect output iterators. If the
kept elements are to be stored in, e.g., a vector kept then
kept.begin() could be passed as the function's dest argument. However,
that requires that size(kept) is large enough to contain all the kept
elements, which must therefore be known before the function is
called. Alternatively, back_insert_iterator could be used ensuring that
kept merely contains the kept elements once the function has
returned. This approach is used in the example program.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
using namespace std;
using StrVect = vector<string>;
bool judge(string const &word)
{
return count(word.begin(), word.end(), 'a') > 1;
}
void show(auto const &begin, auto const &end)
{
copy(begin, end, ostream_iterator<string>(cout, ", "));
cout << "\n";
}
int main()
{
StrVect words =
{
"kilo", "alpha", "lima", "mike", "alpha", "november",
"alpha", "alpha", "alpha", "papa", "quebec"
};
auto src{ words };
cout << "Removing all \"alpha\"s:\n";
auto end = remove(src.begin(), src.end(), "alpha");
show(src.begin(), end);
cout << "Leftover elements are:\n";
show(end, src.end());
src = words;
cout << "Remove_copy_if removes words having > 1 'a' chars:\n";
StrVect kept;
remove_copy_if(src.begin(), src.end(), back_inserter(kept), judge);
show(kept.begin(), kept.end());
}
// Displays:
// Removing all "alpha"s:
// kilo, lima, mike, november, papa, quebec,
// Leftover elements are:
// alpha, alpha, alpha, , ,
// Remove_copy_if removes words having > 1 'a' chars:
// kilo, lima, mike, november, quebec,
<algorithm>
void replace([ExecPol,] ForwardIterator first,
ForwardIterator last, Type const &oldvalue, Type const &newvalue);
ForwardIterator replace_if([ExecPol,] ForwardIterator first,
ForwardIterator last, UnaryPredicate pred, Type const &value);
OutputIterator replace_copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result, Type const &oldvalue,
Type const &newvalue);
OutputIterator replace_copy_if([ExecPol,]
ForwardIterator first, ForwardIterator last, OutputIterator result,
UnaryPredicate pred, Type const &value);
oldvalue in
the range pointed to by [first, last) are replaced by a copy of
newvalue. The algorithm uses operator== of the data type to which the
iterators point.
[first, last) for which the unary predicate pred evaluates as
true are replaced by value.
oldvalue in
the range pointed to by [first, last) are sent to the result output
iterator, replacing elements equal to oldValue by newValue, using
operator== of the data type to which the iterators point.
[first, last) for which the unary predicate pred returns false
are sent to the result output iterator, and value is sent to
result if pred returns true. The range [first, last) is not
modified.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
using namespace std;
using StrVect = vector<string>;
void show(StrVect const &vect)
{
copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));
cout.put('\n');
}
bool isAlpha(string const &str)
{
return str == "alpha";
}
int main()
{
StrVect words =
{
"kilo", "alpha", "lima", "mike", "alpha", "november",
"alpha", "oscar", "alpha", "alpha", "papa"
};
// replace(words.begin(), words.end(), "alpha"s, "ALPHA"s);
// show(words);
// or, using replace_if:
//
// replace_if(words.begin(), words.end(), isAlpha, "ALPHA"s);
// show(words);
// or, using replace_copy:
//
// StrVect result;
// replace_copy(words.begin(), words.end(), result.begin(),
// "alpha"s, "ALPHA"s);
// show(result);
// or, using replace_copy_if:
//
//StrVect result;
replace_copy_if(words.begin(), words.end(), back_inserter(result),
isAlpha, "ALPHA"s);
show(result);
}
/*
Displays
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
void reverse([ExecPol,] BidirectionalIterator first,
BidirectionalIterator last);
OutputIterator reverse_copy([ExecPol,] BidirectionalIterator first,
BidirectionalIterator last, OutputIterator dest);
[first, last) are reversed.
[first, last) are inserted in reversed order into dest, returning
the output iterator following the last insertion.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
using namespace std;
using StrVect = vector<string>;
void show(StrVect const &vect)
{
copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));
cout.put('\n');
}
int main(int argc, char **argv)
{
StrVect words =
{
"alpha", "kilo", "lima", "mike",
"november", "oscar", "papa"
};
if (argc == 1) // no args: plain reverse
{
reverse(words.begin(), words.end());
show(words);
return 0;
}
using StrVect = vector<string>;
StrVect dest;
reverse_copy(words.begin(), words.end(),
back_inserter(dest));
show(dest);
}
// Displays:
// papa oscar november mike lima kilo alpha
<algorithm>
void rotate([ExecPol,] ForwardIterator first, ForwardIterator
middle, ForwardIterator last);
OutputIterator rotate_copy([ExecPol,] ForwardIterator first,
ForwardIterator middle, ForwardIterator last, OutputIterator result);
[first,
middle) are moved to the end of the container, the elements in the range
[middle, last) are moved to the beginning of the container, keeping the
order of the elements in the two sub-ranges intact.
[middle, last) and
then the elements in the range [first, middle) are inserted into
result, returning the output iterator following the last insertion.
The order of the elements in the source ranges is not altered.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
using namespace std;
using StrVect = vector<string>;
void show(StrVect const &vect)
{
copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));
cout.put('\n');
}
int main(int argc, char **argv)
{
StrVect words =
{
"kilo", "lima", "mike", "november", "oscar",
"foxtrot", "golf", "hotel", "india", "juliet"
};
if (argc == 1) // no args: plain rotate
{
rotate(words.begin(), words.begin() + words.size() / 2,
words.end());
show(words);
return 0;
}
using StrVect = vector<string>;
StrVect dest;
rotate_copy(words.begin(), words.begin() + words.size() / 2,
words.end(), back_inserter(dest));
show(dest);
}
// Displays:
// foxtrot golf hotel india juliet kilo lima mike november oscar
<algorithm>
OutputIterator sample(InputIterator first, InputIterator last,
OutputIterator out, size_t sampleSize,
Generator &&generator);
sampleSize elements are randomly selected (without
replacement) from the input range [first, last), and copied to the
destination range starting at out and ending at the function's return
value. If sampleSize >= (last - first) all elements are selected. The
generator is a (uniform) random number generator, like the mt19937
mercenne twister.
shuffle:
(cppreference).
#include <algorithm>
#include <iostream>
#include <random>
#include <string>
using namespace std;
int main()
{
string src{ "abcdefghijklmnopqrstuvwxyz" };
string dest;
sample(src.begin(), src.end(), back_inserter(dest), 7, mt19937{});
std::cout << "Seven random letters out of " << src << " : " <<
dest << '\n';
}
// Could display:
// Seven random letters out of abcdefghijklmnopqrstuvwxyz : bciorux
<algorithm>
ForwardIterator search([ExecPol,] ForwardIterator first1,
ForwardIterator last1, ForwardIterator first2, ForwardIterator last2);
ForwardIterator1 search([ExecPol,] ForwardIterator first1,
ForwardIterator last1, ForwardIterator first2, ForwardIterator last2,
BinaryPredicate pred);
constexpr ForwardIterator1 search([ExecPol,]
ForwardIterator first, ForwardIterator last, Searcher const &searcher);
ForwardIterator search_n([ExecPol,] ForwardIterator first,
ForwardIterator last, Size count, Type const &value);
ForwardIterator search_n([ExecPol,] ForwardIterator first1,
ForwardIterator last1, Size count, Type const &value,
BinaryPredicate pred);
[first1, last1) is returned where the elements in the range
[first2, last2) are found using operator== of the data
type to which the iterators point. If no such location exists, last1 is
returned.
[first1, last1) is returned where the elements in the range
[first2, last2) are found using the provided binary predicate pred
to compare the elements in the two ranges. If no such location exists,
last1 is returned.
searcher(first, last).first:
searcher receives the range of elements, and returns an iterator into this
range (or last if searcher found no match) as searcher(first,
last).first.
[first, last) for the first series of count elements equal to
value, returning the first iterator to those count elements. If no
such series exists then last is returned. The last protottype calls
pred to determine whether an element is equal to value.
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
bool absEq(int i1, int i2)
{
return abs(i1) == abs(i2);
}
int main()
{
int range1[] = {-2, -4, -6, -8, 2, 4, 4, 6, 8};
int range2[] = {6, 8};
copy
(
search(range1, end(range1), range2, range2 + 2),
end(range1), ostream_iterator<int>(cout, " ")
);
cout << '\n';
copy
(
search(range1, end(range1), range2, range2 + 2, absEq),
end(range1), ostream_iterator<int>(cout, " ")
);
cout << '\n';
copy
(
search_n(range1, end(range1), 2, 4, absEq),
end(range1), ostream_iterator<int>(cout, " ")
);
cout << '\n';
}
// Displays:
// 6 8
// -6 -8 2 4 4 6 8
// 4 4 6 8
<algorithm>
OutputIterator set_difference([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
OutputIterator set_difference([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
[first1, last1) that are not present in the
range [first2, last2) is returned, starting at result, and ending
at the OutputIterator returned by the function. The elements in the two
ranges must have been sorted using operator< of the data type to which
the iterators point.
[first1, last1) that are not present in the
range [first2, last2) is returned, starting at result, and ending
at the OutputIterator returned by the function. The elements in the two
ranges must have been sorted using the comp function object.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[7];
copy(result,
set_difference(set1, set1 + 7, set2, set2 + 3, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_difference(set1, set1 + 7, set3, set3 + 3, result,
caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
// Displays:
// kilo lima mike november oscar
// kilo lima mike november oscar
<algorithm>
OutputIterator set_intersection([ExecPol,]
InputIterator1 first1, InputIterator1) linebreak() tt(last1, InputIterator2
first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_intersection([ExecPol,] InputIterator1
first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
[first1, last1) that are also present in the
range [first2, last2) is returned, starting at result, and ending
at the OutputIterator returned by the function. The elements in the two
ranges must have been sorted using operator< of the data type to which
the iterators point.
[first1, last1) that are also present in the
range [first2, last2) is returned, starting at result, and ending
at the OutputIterator returned by the function. The elements in the two
ranges must have been sorted using the comp function object.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[7];
copy(result,
set_intersection(set1, set1 + 7, set2, set2 + 3, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_intersection(set1, set1 + 7, set3, set3 + 3, result,
caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
// Displays:
// papa quebec
// papa quebec
<algorithm>
OutputIterator set_symmetric_difference([ExecPol,]
InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
OutputIterator set_symmetric_difference([ExecPol,]
InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result, Compare comp);
[first1, last1) that are not present in the
range [first2, last2) and those in the range [first2, last2)
that are not present in the range [first1, last1) is returned, starting
at result, and ending at the OutputIterator returned by the
function. The elements in the two ranges must have been sorted using
operator< of the data type to which the iterators point.
[first1, last1) that are not present in the
range [first2, last2) and those in the range [first2, last2)
that are not present in the range [first1, last1) is returned, starting
at result, and ending at the OutputIterator returned by the
function. The elements in the two ranges must have been sorted using the
comp function object.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[7];
copy(result,
set_symmetric_difference(set1, set1 + 7, set2, set2 + 3,
result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_symmetric_difference(set1, set1 + 7, set3, set3 + 3,
result, caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
// Displays:
// kilo lima mike november oscar romeo
// kilo lima mike november oscar ROMEO
<algorithm>
OutputIterator set_union([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
OutputIterator set_union([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
[first1, last1) or the range
[first2, last2) or in both ranges is returned, starting at result,
and ending at the OutputIterator returned by the function. The elements in
the two ranges must have been sorted using operator< of the data type to
which the iterators point;
[first1, last1) or the range
[first2, last2) or in both ranges is returned, starting at result,
and ending at the OutputIterator returned by the function. The elements in
the two ranges must have been sorted using comp function object.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
#include <vector>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] =
{
"kilo", "lima", "mike", "november",
"oscar", "papa", "quebec"
};
string set2[] = { "papa", "quebec", "romeo"};
string result[8];
copy(result,
set_union(set1, set1 + 7, set2, set2 + 3, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_union(set1, set1 + 7, set3, set3 + 3, result, caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
std::vector<int> v1 = {1, 2, 3, 4, 5, 5, 5};
std::vector<int> v2 = { 3, 3, 3, 4, 5, 6, 7};
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(),
ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays:
// kilo lima mike november oscar papa quebec romeo
// kilo lima mike november oscar papa quebec ROMEO
// 1 2 3 3 3 4 5 5 5 6 7
<algorithm>
void sort([ExecPol,] RandomAccessIterator first,
RandomAccessIterator last);
void sort([ExecPol,] RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
void stable_sort([ExecPol,] RandomAccessIterator first,
RandomAccessIterator last);
void stable_sort([ExecPol,] RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
[first,
last) are sorted in ascending order using operator< of the data type to
which the iterators point.
[first, last) are sorted in ascending order using the comp
function object to compare the elements. The binary predicate comp
should return true if its first argument should be placed earlier in the
sorted sequence than its second argument.
// compile as: g++ -O2 sort.cc -ltbb
#include <algorithm>
#include <cstdlib>
#include <execution>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;
int main()
{
string words[] =
{
"november", "kilo", "mike", "lima",
"oscar", "quebec", "papa"
};
sort(words, words + 7);
copy(words, words + 7, ostream_iterator<string>(cout, " "));
cout << '\n';
sort(words, words + 7, greater<string>());
copy(words, words + 7, ostream_iterator<string>(cout, " "));
cout << '\n';
int *vect = new int[10'000];
generate(execution::par, vect, vect + 10'000, random);
cout << "sorted: " << is_sorted(vect, vect + 10'000) << '\n';
sort(execution::par, vect, vect + 10'000);
cout << "sorted: " << is_sorted(vect, vect + 10'000) << '\n';
delete[] vect;
// stable-sorting:
using Pair = pair<size_t, string>; // days & nrs of the months
vector<Pair> months =
{
{ 31, "Jan." }, { 28, "Feb." }, { 31, "Mar." }, { 30, "Apr." },
{ 31, "May." }, { 30, "Jun." }, { 31, "Jul." }, { 31, "Aug." },
{ 30, "Sep." }, { 31, "Oct." }, { 30, "Nov." }, { 31, "Dec." },
};
stable_sort(months.begin(), months.end(),
[&](Pair const &lhs, Pair const &rhs)
{
return lhs.first > rhs.first;
}
);
for (size_t idx = 0; auto const &month: months)
cout << month.first << ": " << month.second <<
(++idx % 4 == 0 ? "\n" : " ");
}
// Displays:
// kilo lima mike november oscar papa quebec
// quebec papa oscar november mike lima kilo
// unordered sequence
// sorted sequence
// 31: Jan. 31: Mar. 31: May. 31: Jul.
// 31: Aug. 31: Oct. 31: Dec. 30: Apr.
// 30: Jun. 30: Sep. 30: Nov. 28: Feb.
The example also shows two generic algorithms using the
execution::par execution policy: first generate is used to fill an
array with randomly determined int-values, then sort is used to sort
those values.
<algorithm>
void swap(Type &object1, Type &object2) noexcept;
void swap(Type (&object1)[N], Type (&object2))[N] noexcept;
ForwardIterator2 swap_ranges([ExecPol,] ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 result);
object1 and object2
exchange their values. They do so by either cyclic copy assignment or cyclic
move assignment (if available).
object1 and object2 arrays exchange their values.
[first1, last1) are swapped with that number of elements in the range
[result, returnvalue), where returnvalue is the value returned by
the function. The two ranges must be disjoint.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
void show(string const *begin, string const *end)
{
copy(begin, end, ostream_iterator<string>(cout, " "));
cout << '\n';
}
int main()
{
string first[] = { "alpha", "bravo", "charley" };
string second[] = { "echo", "foxtrot", "golf" };
cout << "Before:\n";
show(first, end(first));
show(second, end(second));
for (size_t idx = 0; idx < size(first); ++idx)
swap(first[idx], second[idx]);
cout << "After:\n";
show(first, end(first));
show(second, end(second));
swap_ranges(first, end(first), second);
cout << "After swap_ranges:\n";
show(first, end(first));
show(second, end(second));
}
// Displays:
// Before:
// alpha bravo charley
// echo foxtrot golf
// After:
// echo foxtrot golf
// alpha bravo charley
// After swap_ranges:
// alpha bravo charley
// echo foxtrot golf
<algorithm>
OutputIterator transform([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result, UnaryOperator op);
OutputIterator transform([ExecPol,] InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, OutputIterator result,
BinaryOperator op);
op is applied to
each of the elements in the range [first, last), and the resulting
values are stored in the range starting at result. The return value points
just beyond the last generated element.
op is applied
to each of the elements in the range [first1, last1) and the
corresponding element in the second range starting at first2. The
resulting values are stored in the range starting at result. The return
value points just beyond the last generated element.
#include <functional>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>
#include <iterator>
using namespace std;
string caps(string const &src)
{
string tmp;
tmp.resize(src.length());
transform(src.begin(), src.end(), tmp.begin(), ::toupper);
return tmp;
}
int main()
{
string words[] = {"alpha", "bravo", "charley"};
copy(words, transform(words, words + 3, words, caps),
ostream_iterator<string>(cout, " "));
cout << '\n';
int values[] = {1, 2, 3, 4, 5};
vector<int> squares;
transform(values, values + 5, values,
back_inserter(squares), multiplies<int>());
copy(squares.begin(), squares.end(),
ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
Displays:
ALPHA BRAVO CHARLEY
1 4 9 16 25
*/
for_each (section
19.1.18) and transform generic algorithms should be noted:
transform the return value of the function
object's operator() member is used; the argument that is passed to the
operator() member itself is not changed.
for_each the function object's operator()
receives a reference to an argument, which itself may be changed by the
function object's operator().
transform generic algorithm. However, but different from the
range-based for-loop the transform algorithm can also be used width
sub-ranges and with reverse-iterators.
<numeric>
Type transform_reduce([ExecPol,]
InputIterator first1, InputIterator last1,
InputIterator first2,
Type value);
Type transform_reduce([ExecPol,]
InputIterator first1, InputIterator last1,
InputIterator first2,
Type value,
BinaryOperation reduce,
BinaryOperation transform);
Type transform_reduce([ExecPol,]
InputIterator first1, InputIterator last1,
Type value,
BinaryOperation reduce,
UnaryOperation transform);
std::plus<> for the reduce binary operator and std::mutiplies<>
for the transform binary operator. It's also equivalent to a parallelized
version of inner_product (cf. section 19.1.21).
transform binary
operation to, as left-hand side operand, each element in the [first1,
end1) range and as right-hand side operand the corresponding element of the
range starting at first2. Each thus computed value is passed as right-hand
side operand, using value as left-hand side operand to the reduce
binary operation, returning the final value returned by reduce.
transform to each element of
the range [first1, end1), and then passes value and each of the
values returned by transform to reduce, returning the final value
returned by reduce.
#include <numeric>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
class Cat
{
std::string d_sep;
public:
Cat(string const &sep)
:
d_sep(sep)
{}
string operator()
(string const &s1, string const &s2) const
{
return s1 + d_sep + s2;
}
};
int main()
{
size_t ia1[] = { 1, 2, 3, 4, 5, 6, 7 };
// instead of inner_product:
cout << "The sum of all squares in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "is " << transform_reduce(ia1, ia1 + 7, ia1, 0) << '\n';
size_t ia2[] = { 7, 6, 5, 4, 3, 2, 1 };
cout << "The sum of all cross-products in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "and ";
copy(ia2, ia2 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "is " << transform_reduce(ia1, ia1 + 7, ia2, 0) << '\n';
string names1[] = { "Frank", "Karel", "Piet" };
string names2[] = { "Brokken", "Kubat", "Plomp"};
cout << "All combined names of ";
copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });
cout << "and ";
copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });
cout << "are:" <<
transform_reduce(names1, names1 + 3, names2, "\t"s,
Cat{ "\n\t"}, Cat{ " " }) << '\n';
}
// Displays:
// The sum of all squares in 1 2 3 4 5 6 7 is 140
// The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84
// All combined names of Frank Karel Piet and Brokken Kubat Plomp are:
// Frank Brokken
// Karel Kubat
// Piet Plomp
As covered before, when calling something like auto ptr = new string{
"hello" } the string is constructed in memory specifically allocated to
contain the object, and the object type's constructor initializes the object
in that memory. Likewise, when calling delete ptr the string's destructor
is called, followed by returning the memory allocated by new to the common
pool.
When using placement new the memory to contain the object is already
available, and the construction auto ptr = new (storageAddress) string{
"hello" } is used to merely construct the string at the location specified by
storageAddress. That string can then (as usual) be accessed via ptr,
but delete ptr cannot be used, since the memory at storageAddress was
already available before invoking the placement new operator. Therefore, in
these cases the remarkable situation is encountered where the object's
destructor must explicitly be called (using ptr->~string()) and using
delete ptr is completely wrong, causing a memory error which aborts the
program.
Several generic algorithms, all supporting execution policies, are available
simplifying the use of placement new. To use these algorithm the
<memory> header file must be included.
Facilities are available to copy, fill, initialize, and move objects to/in uninitialized (raw) memory, as well as facilities to delete the objects stored in raw memory. Here is an overvieuw of the available facilities (cf. cppreference for more details about the algorithms handling uninitialized memory):
uninitialized_copy([ExecPol,]
ForwardIterator first, ForwardIterator last,
ForwardIterator dest);[first, last) to the raw memory
starting at dest, returning the location beyond the last copied
element.
uninitialized_copy_n([ExecPol,]
ForwardIterator first, size_t nObjects,
ForwardIterator dest);nObjects.
uninitialized_default_construct([ExecPol,]
ForwardIterator first, ForwardIterator last);[first, last). The algorithm requires
that the types referred to by the iterators are either trivial types
(like built-in types) or define value_type returning their type
names. When using trivial types the installed do not assume that the
installed values are 0-initialized.
uninitialized_default_construct_n([ExecPol,]
ForwardIterator first, size_t nObjects);nObjects in the
uninitialized memory.
uninitialized_fill([ExecPol,]
ForwardIterator first, ForwardIterator last,
Type const &value);value in the
uninitialized memory.
uninitialized_fill([ExecPol,]
ForwardIterator first, size_t nObjects,Type const &value);value to the
nObjects subsequent locations in the uninitialized memory.
uninitialized_move([ExecPol,]
ForwardIterator first, ForwardIterator last,
ForwardIterator dest);[first,
last) are moved to the raw memory.
uninitialized_move_n([ExecPol,]
ForwardIterator first, size_t nObjects,
ForwardIterator dest);nObjects are moved.
uninitialized_value_construct([ExecPol,]
ForwardIterator first, ForwardIterator last);uninitialized_default_construct, but requires that the
types referred to by the iterators define value_type returning
their type names.
uninitialized_value_construct_n([ExecPol,]
ForwardIterator first, size_t nObjects);nObjects in the
uninitialized memory.
The algorithm Type *construct_at(Type *raw, Args
&&...args) constructs an object of type Type in the raw memory at
raw, passing args... to Type's constructor.
To delete the objects installed in raw memory the following facilities are available:
void destroy([ExecPol,] ForwardIterator first,
ForwardIterator last);first refers: it calls
iterator->~Type() for all elements in the range [first,
last).
void destroy([ExecPol,] ForwardIterator first, size_t nObjects);nObjects objects.
void destroy_at(Type *raw);raw using placement
new. If the raw pointer points to an array of placement new
allocated objects then the destructors of the elements of the array
are called.
Here is an example:
#include <memory>
#include <vector>
#include <iostream>
#include <string>
using namespace std;
int main()
{
char raw[4 * sizeof(string)]; // raw memory to receive strings
string *ptr = reinterpret_cast<string *>(raw); // pointer to strings
// construct 4 strings in raw
uninitialized_default_construct_n(ptr, 4);
destroy(ptr, ptr + 4); // call the strings' destructors
vector<string> vs(4, "string"); // move 4 strings to raw memory
uninitialized_move(vs.begin(), vs.end(), ptr);
cout << vs.front() << ", " << vs.back() << '\n' <<
ptr[0] << ", " << ptr[3] << '\n';
destroy(ptr, ptr + 4); // call the strings' destructors
}
// Displays:
// ,
// string, string
<algorithm>
ForwardIterator unique([ExecPol,] ForwardIterator first,
ForwardIterator last);
ForwardIterator unique([ExecPol,] ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
OutputIterator unique_copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator unique_copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result, BinaryPredicate pred);
std::unique generic algorithm assumes that the elements in the
range have previously been sorted (cf. section 19.1.54).
operator== of the data type to
which the iterators point, all but the first of consecutively equal elements
in the range pointed to by [first, last) are relocated to the end of
the range. The returned forward iterator marks the beginning of the
leftover. All elements in the range [first, return-value) are
unique, all elements in the range [return-value, last) have
undetermined (but valid) values.
[first, last) for which the binary
predicate pred returns true are relocated to the end of the range. The
predicate pred expects two arguments of the data type to which the
iterators point. The returned forward iterator marks the beginning of the
leftover. For all pairs of elements in the range [first,
return-value) pred returns false (i.e., they are unique). All
elements in the leftover (i.e., the range [return-value, last))
have undetermined (but valid) values.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool casestring(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string words[] = {"alpha", "alpha", "Alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
string *removed = unique(words, words + size);
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Trailing elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
removed = unique(words, words + size, casestring);
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Trailing elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
alpha Alpha papa quebec
Trailing elements are:
quebec
alpha papa quebec
Trailing elements are:
quebec quebec
*/
<algorithm>
OutputIterator unique_copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator unique_copy([ExecPol,] InputIterator first,
InputIterator last, OutputIterator result, BinaryPredicate pred);
[first,
last) are copied to the resulting container, starting at result.
Consecutively equal elements (using operator== of the data type to which
the iterators point) are copied only once (keeping the first of a series of
equal elements). The returned output iterator points
just beyond the last copied element.
[first, last) are copied to the resulting container, starting at
result. Consecutive elements in the range pointed to by [first,
last) for which the binary predicate pred returns true are copied only
once (keeping the first of a series of equal elements). The returned output
iterator points just beyond the last copied element.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <cstring>
using namespace std;
bool casestring(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string words[] = {"oscar", "Alpha", "alpha", "alpha",
"papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
vector<string> remaining;
unique_copy(words, words + size, back_inserter(remaining));
copy(remaining.begin(), remaining.end(),
ostream_iterator<string>(cout, " "));
cout << '\n';
vector<string> remaining2;
unique_copy(words, words + size,
back_inserter(remaining2), casestring);
copy(remaining2.begin(), remaining2.end(),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
oscar Alpha alpha papa quebec
oscar Alpha papa quebec
*/
<algorithm>
ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last, Type const &value);
ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last, Type const &value, Compare comp);
[first, last) are searched for the first
element that is greater than value. The returned iterator marks the first
location in the sequence where value can be inserted without breaking the
sorted order of the elements using operator< of the data type to which the
iterators point. If no such element is found, last is returned.
[first, last) must have been sorted using the comp function
or function object. Each element in the range is compared to value using
the comp function. An iterator is returned pointing to the first element
for which the binary predicate comp, applied to the elements of the range
and value, returns true. The comp function object function's
first parameter refers to value and the function object's second parameter
refers to an element in the iterator range.
Caveat: note that the comp object's parameters when using
upper_bound are swapped compared to the parameters expected by
lower_bound.
operator<) then upper_bound returns an iterator
pointing beyond the last of a series of values equal to value, while
lower_bound returns an iterator pointing to the first of such a series of
equal values.
When the iterator range contains a series of values which are, according to
comp, equal to value then upper_bound returns an iterator to the
first element beyond that series, while lower_bound returns an iterator to
the first element of that series.
The following program illustrates the various possibilities. Th program
illustrates both lower_bound and upper_bound and also illustrates the
situation where value' Type is unequal to the types of the values in the
iterator range. Specific comment is provided below the program's code.
1: #include <algorithm>
2: #include <iostream>
3: using namespace std;
4:
5: int main()
6: {
7: using pic = pair<int, char>;
8:
9: pic picArr[] =
10: { {1, 'f'}, {5, 'r'}, {5, 'a'}, {7, 'n'}, {8, 'k'} };
11: pic *picArrEnd = picArr + size(picArr);
12:
13: cout << "Sequence: ";
14: for (auto &pair: picArr)
15: cout << '{' << pair.first << ',' << pair.second << "}, ";
16: cout << '\n';
17:
18: auto iter = lower_bound(picArr, picArrEnd, 5,
19: [&](pic const &range, int value)
20: {
21: return range.first < value;
22: }
23: );
24: cout << " lower bound, <, {5,?} can be inserted before {" <<
25: iter->first << ',' << iter->second << "}\n";
26:
27: iter = upper_bound(picArr, picArrEnd, 5,
28: [&](int value, pic const &range)
29: {
30: return value < range.first;
31: }
32: );
33: cout << " upper_bound, <, {5,?} can be inserted before {" <<
34: iter->first << ',' << iter->second << "}\n";
35:
36: iter = upper_bound(picArr, picArrEnd, 9,
37: [&](int value, pic const &range)
38: {
39: return value < range.first;
40: }
41: );
42: cout << " upper_bound, <, {9,?} can be inserted " <<
43: ( &*iter == picArrEnd ? "at the end" : "???") << '\n';
44:
45: sort(picArr, picArrEnd,
46: [](pic const &lhs, pic const &rhs)
47: {
48: return lhs.first > rhs.first;
49: }
50: );
51:
52: cout << "\nSequence: ";
53: for (auto &pair: picArr)
54: cout << '{' << pair.first << ',' << pair.second << "}, ";
55: cout << '\n';
56:
57: iter = lower_bound(picArr, picArrEnd, 5,
58: [&](pic const &range, int value)
59: {
60: return range.first > value;
61: }
62: );
63: cout << " lower_bound, >, {5,?} can be inserted before {" <<
64: iter->first << ',' << iter->second << "}\n";
65:
66: iter = upper_bound(picArr, picArrEnd, 5,
67: [&](int value, pic const &range)
68: {
69: return value > range.first;
70: }
71: );
72: cout << " upper_bound, >, {5,?} can be inserted before {" <<
73: iter->first << ',' << iter->second << "}\n";
74:
75: iter = upper_bound(picArr, picArrEnd, 0,
76: [&](int value, pic const &range)
77: {
78: return value > range.first;
79: }
80: );
81: cout << " upper_bound, >, {0,?} can be inserted " <<
82: ( &*iter == picArrEnd ? "at the end" : "???") << '\n';
83: }
84: // Displays:
85: // Sequence: {1,f}, {5,r}, {5,a}, {7,n}, {8,k},
86: // lower bound, <, {5,?} can be inserted before {5,r}
87: // upper_bound, <, {5,?} can be inserted before {7,n}
88: // upper_bound, <, {9,?} can be inserted at the end
89: //
90: // Sequence: {8,k}, {7,n}, {5,r}, {5,a}, {1,f},
91: // lower_bound, >, {5,?} can be inserted before {5,r}
92: // upper_bound, >, {5,?} can be inserted before {1,f}
93: // upper_bound, >, {0,?} can be inserted at the end
pairs, sorted by their first members.
lower_bound is called using a lambda
expression to define the Compare function object. Note (line
19) that a reference to a value in the iterator range is the
lambda expression's first parameter, while the target value is its
second parameter.
upper_bound is called, also using a
lambda expression. With upper_bound the target value is the
lambda expression's first parameter, while a reference to a value
in the iterator range is its second parameter.
picArr array in descending order lower_bound
and upper_bound are again used. This time instead of using the
< operator the > operator should be used.
The binary_search generic algorithm can be used to simply
determine whether or nog value is present in the iterator range. The
lower_bound generic algorithm can be used to find the first
element of a series of values equal to value.
12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5
In the following description, keep two pointers into this array in mind:
a pointer node indicates the location of the next node of the tree, a
pointer child points to the next element which is a child of the node
pointer. Initially, node points to the first element, and child points
to the second element.
*node++ (== 12). 12 is the top node. its children are *child++
(11) and *child++ (10), both less than 12.
*node++ (== 11)), in turn, has *child++ (8)
and *child++ (9) as its children.
*node++ (== 10)) has *child++ (7)
and *child++ (6) as its children.
*node++ (== 8)) has *child++ (1)
and *child++ (2) as its children.
*node++ (== 9)) has children *child++ (4)
and *child++ (3).
*node++ (== 7)) has
one child *child++ (5)
child now points beyond the array, the remaining nodes have no
children. So, nodes 6, 1, 2, 4, 3 and 5 don't have children.
Note that the left and right branches are not ordered: 8 is less than 9, but 7 is larger than 6.
A heap is created by traversing a binary tree level-wise, starting from the top node. The top node is 12, at the zeroth level. At the first level we find 11 and 10. At the second level 8, 9, 7 and 6 are found, etc.
Heaps can be constructed in containers supporting random access. So, a list is
not an appropriate data structure for a heap. Heaps can be constructed from an
(unsorted) array (using make_heap). The top-element can
be pruned from a heap, followed by reordering the heap (using
pop_heap), a new element can be added to the heap,
followed by reordering the heap (using push_heap), and
the elements in a heap can be sorted (using sort_heap,
which, of course, invalidates the heap).
<algorithm>
void make_heap(RandomAccessIterator first,
RandomAccessIterator last);
void make_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
[first,
last) are reordered to form a max-heap using operator< of the data
type to which the iterators point.
[first,
last) are reordered to form a max-heap using the binary comparison function
object comp to compare elements.
make_heap.
<algorithm>
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last);
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
[first, last) is moved to last - 1. Then, the elements in the range
[first, last - 1) are reordered to form a max-heap using the
operator< of the data type to which the iterators point.
[first, last) is moved to last - 1. Then, the elements in the range
[first, last - 1) are reordered to form a max-heap using the binary
comparison function object comp to compare elements.
pop_heap.
<algorithm>
void push_heap(RandomAccessIterator first,
RandomAccessIterator last);
void push_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
[first,
last - 1) contains a valid heap, and the element at last - 1 contains an
element to be added to the heap, the elements in the range [first, last
- 1) are reordered to form a max-heap using the operator< of the data
type to which the iterators point.
[first,
last - 1) contains a valid heap, and the element at last - 1 contains an
element to be added to the heap, the elements in the range [first, last
- 1) are reordered to form a max-heap using the binary comparison function
object comp to compare elements.
push_heap.
<algorithm>
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last);
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
[first, last) form a valid max-heap, the elements in the range
[first, last) are sorted using operator< of the data type to
which the iterators point.
[first, last) form a valid heap, the elements in the range
[first, last) are sorted using the binary comparison function
object comp to compare elements.
sort_heap.
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
void show(int *ia, char const *header)
{
cout << header << ":\n";
copy(ia, ia + 20, ostream_iterator<int>(cout, " "));
cout << '\n';
}
int main()
{
int ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
make_heap(ia, ia + 20);
show(ia, "The values 1-20 in a max-heap");
pop_heap(ia, ia + 20);
show(ia, "Removing the first element (now at the end)");
push_heap(ia, ia + 20);
show(ia, "Adding 20 (at the end) to the heap again");
sort_heap(ia, ia + 20);
show(ia, "Sorting the elements in the heap");
make_heap(ia, ia + 20, greater<int>());
show(ia, "The values 1-20 in a heap, using > (and beyond too)");
pop_heap(ia, ia + 20, greater<int>());
show(ia, "Removing the first element (now at the end)");
push_heap(ia, ia + 20, greater<int>());
show(ia, "Re-adding the removed element");
sort_heap(ia, ia + 20, greater<int>());
show(ia, "Sorting the elements in the heap");
}
/*
Displays:
The values 1-20 in a max-heap:
20 19 15 18 11 13 14 17 9 10 2 12 6 3 7 16 8 4 1 5
Removing the first element (now at the end):
19 18 15 17 11 13 14 16 9 10 2 12 6 3 7 5 8 4 1 20
Adding 20 (at the end) to the heap again:
20 19 15 17 18 13 14 16 9 11 2 12 6 3 7 5 8 4 1 10
Sorting the elements in the heap:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The values 1-20 in a heap, using > (and beyond too):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Removing the first element (now at the end):
2 4 3 8 5 6 7 16 9 10 11 12 13 14 15 20 17 18 19 1
Re-adding the removed element:
1 2 3 8 4 6 7 16 9 5 11 12 13 14 15 20 17 18 19 10
Sorting the elements in the heap:
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
*/