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'.
This chapter's sections cover 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:
equal; includes; lexicographical_compare; max; min; mismatch;
copy; copy_backward; partial_sort_copy; remove_copy; remove_copy_if; replace_copy; replace_copy_if; reverse_copy; rotate_copy; unique_copy;
count; count_if;
make_heap; pop_heap; push_heap; sort_heap;
fill; fill_n; generate; generate_n;
accumulate; adjacent_difference; inner_product; partial_sum;
adjacent_find; binary_search; equal_range; find; find_end; find_first_of; find_if; lower_bound; max_element; min_element; 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; partial_sort_copy; partition; prev_permutation; remove; remove_copy; remove_copy_if; remove_if; reverse; reverse_copy; rotate; rotate_copy; sort; stable_partition; stable_sort; swap; unique;
for_each; replace; replace_copy; replace_copy_if; replace_if; transform; unique_copy;
<numeric>
Type accumulate(InputIterator first, InputIterator last,
Type init);
Type accumulate(InputIterator first, InputIterator
last, Type init, BinaryOperation op);
operator+ is applied to all
elements implied by the iterator range and to the initial value init.
The resulting value is returned.
op is applied to
all elements implied by the iterator range and to the initial value init,
and the resulting value is returned.
#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 of values: " << accumulate(iv.begin(), iv.end(), int()) <<
"\n"
"Product of values: " << accumulate(iv.begin(), iv.end(), int(1),
multiplies<int>()) << '\n';
}
/*
Displays:
Sum of values: 10
Product of values: 24
*/
<numeric>
OutputIterator adjacent_difference(InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator adjacent_difference(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(ForwardIterator first,
ForwardIterator last);
OutputIterator adjacent_find(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;
class SquaresDiff
{
size_t d_minimum;
public:
SquaresDiff(size_t minimum)
:
d_minimum(minimum)
{}
bool operator()(size_t first, size_t second)
{
return second * second - first * first >= d_minimum;
}
};
int main()
{
string sarr[] =
{
"Alpha", "bravo", "charley", "delta", "echo", "echo",
"foxtrot", "golf"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
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 *ilast = iv + sizeof(iv) / sizeof(size_t);
size_t *ires = adjacent_find(iv, ilast, SquaresDiff(10));
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 binary_search(ForwardIterator first, ForwardIterator
last, Type const &value);
bool binary_search(ForwardIterator first, ForwardIterator
last, Type const &value, Comparator comp);
value is looked up using binary
search in the series of elements implied by the iterator range [first,
last). The elements in the range must have been sorted by the
Type::operator< function. True is returned if the element was found,
false otherwise.
value is looked up using binary
search in the series of elements implied by 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"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
bool result = binary_search(sarr, last, "foxtrot");
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
reverse(sarr, last); // reverse the order of elements
// binary search now fails:
result = binary_search(sarr, last, "foxtrot");
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
// ok when using appropriate
// comparator:
result = binary_search(sarr, last, "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, last, "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 section
19.1.67 for an extensive example illustrating the use of these latter
two algorithms.
<algorithm>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator destination);
[first, last) is copied to an output range, starting at destination
using the assignment operator of the underlying data type. 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).
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;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
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';
}
// Displays: charley delta echo foxtrot 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"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
copy_backward(sarr + 3, last, last - 3),
last,
ostream_iterator<string>(cout, " ")
);
cout << '\n';
}
// Displays: golf hotel foxtrot golf hotel foxtrot golf hotel
<algorithm>
size_t count(InputIterator first, InputIterator last, Type
const &value);
value occurs in the iterator range
[first, last) is returned. Uses Type::operator== to determine
whether value is equal to an element in the iterator range.
#include <algorithm>
#include <iostream>
using namespace std;
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 + sizeof(ia) / sizeof(int), 3) <<
'\n';
}
// Displays: Number of times the value 3 is available: 3
<algorithm>
size_t count_if(InputIterator first,
InputIterator last, Predicate predicate);
#include <algorithm>
#include <iostream>
using namespace std;
class Odd
{
public:
bool operator()(int value) const
{
return value & 1;
}
};
int main()
{
int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};
cout << "The number of odd values in the array is: " <<
count_if(ia, ia + sizeof(ia) / sizeof(int), Odd{}) << '\n';
}
// Displays: The number of odd values in the array is: 5
<algorithm>
bool equal(InputIterator first, InputIterator
last, InputIterator otherFirst);
bool equal(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;
class CaseString
{
public:
bool operator()(string const &first,
string const &second) const
{
return !strcasecmp(first.c_str(), second.c_str());
}
};
int main()
{
string first[] =
{
"Alpha", "bravo", "Charley", "delta", "Echo",
"foxtrot", "Golf", "hotel"
};
string second[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string *last = first + sizeof(first) / sizeof(string);
cout << "The elements of `first' and `second' are pairwise " <<
(equal(first, last, second) ? "equal" : "not equal") <<
'\n' <<
"compared case-insensitively, they are " <<
(
equal(first, last, 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.27) and upper_bound (returning the first element
beyond the provided reference value, see section 19.1.67).
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.27) and
upper_bound (section 19.1.67).
#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
int range[] = {1, 3, 5, 7, 7, 9, 9, 9};
size_t const size = sizeof(range) / sizeof(int);
pair<int *, int *> pi;
pi = equal_range(range, range + size, 6);
cout << "Lower bound for 6: " << *pi.first << '\n';
cout << "Upper bound for 6: " << *pi.second << '\n';
pi = equal_range(range, range + size, 7);
cout << "Lower bound for 7: ";
copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "Upper bound for 7: ";
copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
sort(range, range + size, greater<int>());
cout << "Sorted in descending order\n";
copy(range, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
pi = equal_range(range, range + size, 7, greater<int>());
cout << "Lower bound for 7: ";
copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "Upper bound for 7: ";
copy(pi.second, range + size, 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';
}
/*
Using g++ at least version 7.0.0:
With `a.out one two three' displays:
more than 5: 0, more than 2: 1
*/
<algorithm>
void fill(ForwardIterator first, ForwardIterator last, Type
const &value);
[first, last) are initialized to value, overwriting the 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';
}
// Displays: 8 8 8 8 8 8 8 8
<algorithm>
void fill_n(ForwardIterator first, Size n, Type
const &value);
n elements starting at the element pointed to by
first are initialized to value, overwriting the previous
stored values.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
vector<int> iv(8);
fill_n(iv.begin() + 2, 4, 8);
copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// Displays: 0 0 8 8 8 8 0 0
<algorithm>
InputIterator find(InputIterator first,
InputIterator last, Type const &value);
value is searched for in the range of the elements
implied by 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.
#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
find(sarr, last, "delta"), last,
ostream_iterator<string>(cout, " ")
);
cout << '\n';
if (find(sarr, last, "india") == last)
{
cout << "`india' was not found in the range\n";
copy(sarr, last, ostream_iterator<string>(cout, " "));
cout << '\n';
}
}
/*
Displays:
delta echo
`india' was not found in the range
alpha bravo charley delta echo
*/
<algorithm>
ForwardIterator1 find_end(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator1 find_end(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred)
[first1, last1) is searched for the last occurrence of the sequence of
elements implied by 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 implied by [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;
class Twice
{
public:
bool operator()(size_t first, size_t second) const
{
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"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
find_end(sarr, last, search, search + 3), // sequence starting
last, 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(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator1 find_first_of(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 implied by 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 implied by [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;
class Twice
{
public:
bool operator()(size_t first, size_t second) const
{
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"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
( // sequence starting
find_first_of(sarr, last, search, search + 3),// at 1st 'foxtrot'
last, 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 last 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>
InputIterator find_if(InputIterator first,
InputIterator last, Predicate pred);
[first, last) for which the (unary)
predicate pred returns true is returned. If the element was not found,
last is returned.
#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;
}
};
int main()
{
string sarr[] =
{
"Alpha", "Bravo", "Charley", "Delta", "Echo"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
find_if(sarr, last, CaseName{ "charley" }),
last, ostream_iterator<string>{ cout, " " }
);
cout << '\n';
if (find_if(sarr, last, CaseName{ "india" }) == last)
{
cout << "`india' was not found in the range\n";
copy(sarr, last, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
}
/*
Displays:
Charley Delta Echo
`india' was not found in the range
Alpha Bravo Charley Delta Echo
*/
<algorithm>
Function for_each(ForwardIterator first,
ForwardIterator last, Function func);
[first, last) is passed in turn 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.64) 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 <cstring>
#include <iostream>
#include <cctype>
using namespace std;
void lowerCase(char &c) // `c' *is* modified
{
c = tolower(static_cast<unsigned char>(c));
}
void capitalizedOutput(string const &str) // `str' is *not* modified
{
char *tmp = strcpy(new char[str.size() + 1], str.c_str());
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"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
for_each(sarr, last, 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.64 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(ForwardIterator first,
ForwardIterator last, 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.
#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';
}
// Displays: 1 4 9 16 25 36 49 64 81 100
<algorithm>
void generate_n(ForwardIterator first, Size n,
Generator generator);
n elements starting at the element pointed to by
iterator first are initialized by the return value of generator,
which can be a function or function object.
#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_n(uv.begin(), 5, NaturalSquares{});
copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });
cout << '\n';
}
// Displays: 1 4 9 16 25 0 0 0 0 0
<algorithm>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
bool includes(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;
class CaseString
{
public:
bool operator()(string const &first,
string const &second) const
{
return !strcasecmp(first.c_str(), second.c_str());
}
};
int main()
{
string first1[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string first2[] =
{
"Alpha", "bravo", "Charley", "delta", "Echo",
"foxtrot", "Golf", "hotel"
};
string second[] =
{
"charley", "foxtrot", "hotel"
};
size_t n = sizeof(first1) / sizeof(string);
cout << "The elements of `second' are " <<
(includes(first1, first1 + n, second, second + 3) ? "" : "not")
<< " contained in the first sequence:\n"
"second is a subset of first1\n";
cout << "The elements of `first1' are " <<
(includes(second, second + 3, first1, first1 + n) ? "" : "not")
<< " contained in the second sequence\n";
cout << "The elements of `second' are " <<
(includes(first2, first2 + n, second, second + 3) ? "" : "not")
<< " contained in the first2 sequence\n";
cout << "Using case-insensitive comparison,\n"
"the elements of `second' are "
<<
(includes(first2, first2 + n, 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 implied by 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};
size_t ia2[] = {7, 6, 5, 4, 3, 2, 1};
size_t init = 0;
cout << "The sum of all squares in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });
cout << "is " <<
inner_product(ia1, ia1 + 7, ia1, init) << '\n';
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, init) << '\n';
string names1[] = {"Frank", "Karel", "Piet"};
string names2[] = {"Brokken", "Kubat", "Plomp"};
cout << "A list of all combined names in ";
copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });
cout << "and\n";
copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });
cout << "is:" <<
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
A list of all combined names in Frank Karel Piet and
Brokken Kubat Plomp is:
Frank Brokken
Karel Kubat
Piet Plomp
*/
<algorithm>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last);
void inplace_merge(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;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
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>
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>
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"};
size_t const n = sizeof(first) / sizeof(string);
cout << "Before:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
for (size_t idx = 0; idx < n; ++idx)
iter_swap(first + idx, second + idx);
cout << "After:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, 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(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool lexicographical_compare(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;
class CaseString
{
public:
bool operator()(string const &first,
string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string word1 = "hello";
string word2 = "help";
cout << word1 << " is " <<
(
lexicographical_compare(word1.begin(), word1.end(),
word2.begin(), word2.end()) ?
"before "
:
"beyond or at "
) <<
word2 << " in the alphabet\n";
cout << word1 << " is " <<
(
lexicographical_compare(word1.begin(), word1.end(),
word1.begin(), word1.end()) ?
"before "
:
"beyond or at "
) <<
word1 << " in the alphabet\n";
cout << word2 << " is " <<
(
lexicographical_compare(word2.begin(), word2.end(),
word1.begin(), word1.end()) ?
"before "
:
"beyond or at "
) <<
word1 << " in the alphabet\n";
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, Compare comp);
[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. 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.4)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.67) 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);
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.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(second.c_str(), first.c_str()) > 0;
}
};
int main()
{
cout << "Word '" << max("first"s, "second"s) <<
"' is lexicographically last\n";
cout << "Word '" << max("first"s, "SECOND"s) <<
"' is lexicographically last\n";
cout << "Word '" << max("first"s, "SECOND"s,
CaseString{}) << "' is lexicographically last\n";
}
/*
Displays:
Word 'second' is lexicographically last
Word 'first' is lexicographically last
Word 'SECOND' is lexicographically last
*/
<algorithm>
ForwardIterator max_element(ForwardIterator first,
ForwardIterator last);
ForwardIterator max_element(ForwardIterator first,
ForwardIterator last, Comparator comp);
[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 comp is used to make the comparisons between the elements
implied by the iterator range [first, last). The element for which
comp returns most often true, compared with other elements, is
returned.
#include <algorithm>
#include <iostream>
using namespace std;
class AbsValue
{
public:
bool operator()(int first, int second) const
{
return abs(first) < abs(second);
}
};
int main()
{
int ia[] = {-4, 7, -2, 10, -12};
cout << "The max. int value is " << *max_element(ia, ia + 5) << '\n';
cout << "The max. absolute int value is " <<
*max_element(ia, ia + 5, AbsValue{}) << '\n';
}
/*
Displays:
The max. int value is 10
The max. absolute int value is -12
*/
<algorithm>
OutputIterator merge(InputIterator1 first1, InputIterator1
last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator merge(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;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
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>
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 decide which of the two elements is the smaller.
one is returned if the binary
predicate comp(one, two) returns false, otherwise two is returned.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(second.c_str(), first.c_str()) > 0;
}
};
int main()
{
cout << "Word '" << min(string{ "first" }, string{ "second" }) <<
"' is lexicographically first\n";
cout << "Word '" << min(string{ "first" }, string{ "SECOND" }) <<
"' is lexicographically first\n";
cout << "Word '" << min(string{ "first" }, string{ "SECOND" },
CaseString{}) << "' is lexicographically first\n";
}
/*
Displays:
Word 'first' is lexicographically first
Word 'SECOND' is lexicographically first
Word 'first' is lexicographically first
*/
<algorithm>
ForwardIterator min_element(ForwardIterator first,
ForwardIterator last);
ForwardIterator min_element(ForwardIterator first,
ForwardIterator last, Comparator comp);
[first, last) is returned
using operator< of the data type to which the iterators point to decide
which of the elements is the smallest.
operator<, the
binary predicate comp is used to make the comparisons between the elements
implied by the iterator range [first, last). The element for which
comp returns false most often is returned.
#include <algorithm>
#include <iostream>
using namespace std;
class AbsValue
{
public:
bool operator()(int first, int second) const
{
return abs(first) < abs(second);
}
};
int main()
{
int ia[] = {-4, 7, -2, 10, -12};
cout << "The minimum int value is " << *min_element(ia, ia + 5) <<
'\n';
cout << "The minimum absolute int value is " <<
*min_element(ia, ia + 5, AbsValue{}) << '\n';
}
/*
Displays:
The minimum int value is -12
The minimum absolute int value is -2
*/
<algorithm>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
pair<InputIterator1, InputIterator2>
mismatch(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;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
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 <<
" at offset " << (pss.first - range1) << " differ\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>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
bool next_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;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string saints[] = {"Oh", "when", "the", "saints"};
cout << "All permutations of 'Oh when the saints':\n";
cout << "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(RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(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(RandomAccessIterator first,
RandomAccessIterator middle, RandomAccessIterator last);
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
middle - first) smallest elements
are sorted and stored in the range [first, 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, last).
middle - first) smallest
elements (according to the provided binary predicate comp) are sorted and
stored in the range [first, 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, 3, 5, 7, 9, 2, 4, 6, 8, 10};
partial_sort(ia, ia + 3, ia + 10);
cout << "find the 3 smallest elements:\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "find the 5 biggest elements:\n";
partial_sort(ia, ia + 5, ia + 10, greater<int>());
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
Displays:
find the 3 smallest elements:
1 2 3 7 9 5 4 6 8 10
find the 5 biggest elements:
10 9 8 7 6 1 2 3 4 5
*/
<algorithm>
void partial_sort_copy(InputIterator first, InputIterator
last, RandomAccessIterator dest_first, RandomAccessIterator dest_last);
void partial_sort_copy(InputIterator first, InputIterator
last, RandomAccessIterator dest_first, RandomAccessIterator dest_last, Compare
comp);
dest_last - dest_first)
smallest elements in the range
[first, last) are copied to the range [dest_first, dest_last),
using the operator< of the data type to which the iterators point to
decide which of the elements to copy.
dest_last - dest_first)
smallest elements in the range [first, last) (as decided by the binary
predicate comp returning true). The elements for which the predicate
comp returns true most often are copied to the range
[dest_first, dest_last).
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = {1, 10, 3, 8, 5, 6, 7, 4, 9, 2};
int ia2[6];
partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "the 6 smallest elements: ";
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "the 4 smallest elements to a larger range:\n";
partial_sort_copy(ia, ia + 4, ia2, ia2 + 6);
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "the 4 biggest elements to a larger range:\n";
partial_sort_copy(ia, ia + 4, ia2, ia2 + 6, greater<int>());
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
Displays:
1 10 3 8 5 6 7 4 9 2
the 6 smallest elements: 1 2 3 4 5 6
the 4 smallest elements to a larger range:
1 3 8 10 5 6
the 4 biggest elements to a larger range:
10 8 3 1 5 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.
#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(BidirectionalIterator
first, BidirectionalIterator last, UnaryPredicate pred);
[first, last) for which the
unary predicate pred evaluates as true are placed before the elements
which evaluate as false. The return value points just beyond the last
element in the partitioned range for which pred evaluates as true.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
class LessThan
{
int d_x;
public:
LessThan(int x)
:
d_x(x)
{}
bool operator()(int value) const
{
return value <= d_x;
}
};
int main()
{
int ia[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4};
int *split;
split = partition(ia, ia + 10, LessThan{ ia[9] });
cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
copy(ia, ia + 10, ostream_iterator<int>{ cout, " " });
cout << '\n';
}
/*
Displays:
Last element <= 4 is ia[3]
1 3 4 2 9 10 7 8 6 5
*/
<algorithm>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Comp comp);
[first, last) is determined. The
elements in the range are reordered such that the first ordering is obtained
representing a `smaller' value (see next_permutation (section
19.1.34) for an example involving the opposite ordering). 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 provided
sequence was already ordered, according to the operator< of the data
type to which the iterators point.
[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 original sequence was already ordered, using the binary predicate comp
to compare two elements.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string saints[] = {"Oh", "when", "the", "saints"};
cout << "All previous permutations of 'Oh when the saints':\n";
cout << "Sequences:\n";
do
{
copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
while (prev_permutation(saints, saints + 4, CaseString{}));
cout << "After first sorting the sequence:\n";
sort(saints, saints + 4, CaseString{});
cout << "Sequences:\n";
while (prev_permutation(saints, saints + 4, CaseString{}))
{
copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });
cout << '\n';
}
cout << "No (more) previous permutations\n";
}
/*
Displays:
All previous permutations of 'Oh when the saints':
Sequences:
Oh when the saints
Oh when saints the
Oh the when saints
Oh the saints when
Oh saints when the
Oh saints the when
After first sorting the sequence:
Sequences:
No (more) previous permutations
*/
<algorithm>
ForwardIterator remove(ForwardIterator first, ForwardIterator
last, Type const &value);
[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.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"alpha", "alpha", "papa", "quebec" };
string *removed;
size_t const size = sizeof(words) / sizeof(string);
cout << "Removing all \"alpha\"s:\n";
removed = remove(words, words + size, "alpha");
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Leftover elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
Removing all "alpha"s:
kilo lima mike november papa quebec
Leftover elements are:
alpha alpha alpha papa quebec
*/
<algorithm>
OutputIterator remove_copy(InputIterator first, InputIterator
last, OutputIterator result, Type const &value);
[first, last)
not matching value are copied to the range [result, 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.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
string remaining
[
size -
count_if
(
words, words + size,
bind2nd(equal_to<string>(), "alpha"s)
)
];
string *returnvalue =
remove_copy(words, words + size, remaining, "alpha");
cout << "Removing all \"alpha\"s:\n";
copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
Removing all "alpha"s:
kilo lima mike november oscar papa quebec
*/
<algorithm>
OutputIterator remove_copy_if(InputIterator first,
InputIterator last, OutputIterator result, UnaryPredicate pred);
[first, last)
for which the unary predicate pred returns true are removed from the
resulting copy. All other elements are copied to the range [result,
returnvalue), where returnvalue is the value returned by the function. The
range [first, last) is not modified.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
string remaining[
size -
count_if
(
words, words + size,
bind2nd(equal_to<string>(), "alpha")
)
];
string *returnvalue =
remove_copy_if
(
words, words + size, remaining,
bind2nd(equal_to<string>(), "alpha")
);
cout << "Removing all \"alpha\"s:\n";
copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
Removing all "alpha"s:
kilo lima mike november oscar papa quebec
*/
<algorithm>
ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last, UnaryPredicate pred);
[first, last)
are reordered such that all values for which the unary predicate pred
evaluates as false are placed at the beginning of the range, while their
relative order is kept. The returned forward iterator points to the
first element, after reordering, for which pred returns 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.
#include <functional>
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
cout << "Removing all \"alpha\"s:\n";
string *removed = remove_if(words, words + size,
bind2nd(equal_to<string>(), "alpha"s));
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Trailing elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
Removing all "alpha"s:
kilo lima mike november oscar papa quebec
Trailing elements are:
oscar alpha alpha papa quebec
*/
<algorithm>
ForwardIterator replace(ForwardIterator first, ForwardIterator
last, Type const &oldvalue, Type const &newvalue);
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.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa" };
size_t const size = sizeof(words) / sizeof(string);
replace(words, words + size, "alpha"s, "ALPHA"s);
copy(words, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
OutputIterator replace_copy(InputIterator first, InputIterator
last, OutputIterator result, Type const &oldvalue, Type const &newvalue);
oldvalue in the range pointed to by
[first, last) are replaced by a copy of newvalue in a new range
[result, returnvalue), where returnvalue is the return value of the
function. The algorithm uses operator== of the data type to which the
iterators point.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa"};
size_t const size = sizeof(words) / sizeof(string);
string remaining[size];
copy
(
remaining,
replace_copy(words, words + size, remaining, "alpha"s, "ALPHA"s),
ostream_iterator<string>(cout, " ")
);
cout << '\n';
}
/*
Displays:
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
OutputIterator replace_copy_if(ForwardIterator first,
ForwardIterator last, OutputIterator result, UnaryPredicate
pred, Type const &value);
[first, last)
are copied to the range [result, returnvalue), where
returnvalue is the value returned by the function. The
elements for which the unary predicate pred returns
true are replaced by value. The range [first,
last) is not modified.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november",
"alpha", "oscar", "alpha", "alpha", "papa"};
size_t const size = sizeof(words) / sizeof(string);
string result[size];
// Note: the comparisons are: "mike" > word[i]
replace_copy_if(words, words + size, result,
bind1st(greater<string>(), "mike"s), "ALPHA"s);
copy (result, result + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays (all strings in words[] which are exceeded by 'mike' are
replaced by ALPHA):
ALPHA ALPHA ALPHA mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
ForwardIterator replace_if(ForwardIterator first,
ForwardIterator last, UnaryPredicate pred, Type const &value);
[first, last)
for which the unary predicate pred evaluates as true
are replaced by value.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa"};
size_t const size = sizeof(words) / sizeof(string);
replace_if(words, words + size,
bind1st(equal_to<string>(), "alpha"s), "ALPHA"s);
copy(words, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
void reverse(BidirectionalIterator first,
BidirectionalIterator last);
[first, last)
are reversed.
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string line;
while (getline(cin, line))
{
reverse(line.begin(), line.end());
cout << line << '\n';
}
}
<algorithm>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result);
[first, last)
are copied to the range [result, returnvalue) in reversed order. The
value returnvalue is the value that is returned by the function.
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string line;
while (getline(cin, line))
{
size_t size = line.size();
char copy[size + 1];
cout << "line: " << line << '\n' <<
"reversed: ";
reverse_copy(line.begin(), line.end(), copy);
copy[size] = 0; // 0 is not part of the reversed
// line !
cout << copy << '\n';
}
}
<algorithm>
void rotate(ForwardIterator first, ForwardIterator
middle, ForwardIterator last);
[first, middle) are
moved to the end of the container, the elements implied by the range
[middle, last) are moved to the beginning of the container, keeping the
order of the elements in the two subsets intact.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "lima", "mike", "november", "oscar",
"foxtrot", "golf", "hotel", "india", "juliet" };
size_t const size = sizeof(words) / sizeof(string);
size_t const midsize = size / 2;
rotate(words, words + midsize, words + size);
copy(words, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
foxtrot golf hotel india juliet kilo lima mike november oscar
*/
<algorithm>
OutputIterator rotate_copy(ForwardIterator first,
ForwardIterator middle, ForwardIterator last, OutputIterator result);
[middle, last) and
then the elements implied by [first, middle) are copied to the
destination container having range [result, returnvalue), where
returnvalue is the iterator returned by the function. The original order
of the elements in the two subsets is not altered.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "lima", "mike", "november", "oscar",
"foxtrot", "golf", "hotel", "india", "juliet" };
size_t const size = sizeof(words) / sizeof(string);
size_t const midsize = size / 2;
string out[size];
copy(out,
rotate_copy(words, words + midsize, words + size, out),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
foxtrot golf hotel india juliet kilo lima mike november oscar
*/
<algorithm>
ForwardIterator1 search(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 search(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2,
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.
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
class absInt
{
public:
bool operator()(int i1, int i2) const
{
return abs(i1) == abs(i2);
}
};
int main()
{
int range1[] = {-2, -4, -6, -8, 2, 4, 6, 8};
int range2[] = {6, 8};
copy
(
search(range1, range1 + 8, range2, range2 + 2),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
copy
(
search(range1, range1 + 8, range2, range2 + 2, absInt()),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
}
/*
Displays:
6 8
-6 -8 2 4 6 8
*/
<algorithm>
ForwardIterator1 search_n(ForwardIterator1 first1,
ForwardIterator1 last1, Size count, Type const &value);
ForwardIterator1 search_n(ForwardIterator1 first1,
ForwardIterator1 last1, Size count, Type const &value, BinaryPredicate
pred);
[first1, last1) is returned where n consecutive elements having
value value are found using operator== of the data type to which
the iterators point to compare the elements. If no such location exists,
last1 is returned.
[first1, last1) is returned where n consecutive elements having
value value are found using the provided binary predicate pred to
compare the elements. If no such location exists, last1 is returned.
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
bool eqInt(int i1, int i2)
{
return abs(i1) == abs(i2);
}
int main()
{
int range1[] = {-2, -4, -4, -6, -8, 2, 4, 4, 6, 8};
copy
(
search_n(range1, range1 + 8, 2, 4),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
copy
(
search_n(range1, range1 + 8, 2, 4, eqInt),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
}
/*
Displays:
4 4
-4 -4 -6 -8 2 4 4
*/
<algorithm>
OutputIterator set_difference(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
OutputIterator set_difference(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];
string *returned;
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(InputIterator1 first1,
InputIterator1) linebreak() tt(last1, InputIterator2 first2, InputIterator2
last2, OutputIterator result);
OutputIterator set_intersection(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];
string *returned;
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(InputIterator1
first1, InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
OutputIterator set_symmetric_difference(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(InputIterator1 first1, InputIterator1
last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_union(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(RandomAccessIterator first,
RandomAccessIterator last);
void sort(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.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
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';
}
/*
Displays:
kilo lima mike november oscar papa quebec
quebec papa oscar november mike lima kilo
*/
<algorithm>
BidirectionalIterator stable_partition(BidirectionalIterator
first, BidirectionalIterator last, UnaryPredicate pred);
[first, last) for which the
unary predicate pred evaluates as true are placed before the elements
which evaluate as false. Apart from this reordering, the relative order of
all elements for which the predicate evaluates to false and the relative
order of all elements for which the predicate evaluates to true is kept.
The return value points just beyond the last element in the
partitioned range for which pred evaluates as true.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int org[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4};
int ia[10];
int *split;
copy(org, org + 10, ia);
split = partition(ia, ia + 10, bind2nd(less_equal<int>(), ia[9]));
cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
copy(org, org + 10, ia);
split = stable_partition(ia, ia + 10,
bind2nd(less_equal<int>(), ia[9]));
cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
Displays:
Last element <= 4 is ia[3]
1 3 4 2 9 10 7 8 6 5
Last element <= 4 is ia[3]
1 3 2 4 5 7 9 10 8 6
*/
<algorithm>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last);
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
[first,
last) are stable-sorted in ascending order using operator< of the data
type to which the iterators point: the relative order of equal elements is
kept.
[first, last) are stable-sorted in ascending order using the comp
binary predicate to compare the elements. This predicate should return
true if its first argument should be placed before its second argument in
the sorted set of element.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
using namespace std;
struct Pss: public pair<string, string> // 1
{
Pss(string const &s1, string const &s2)
:
pair<string, string>(s1, s2)
{}
};
ostream &operator<<(ostream &out, Pss const &p) // 2
{
return out << " " << p.first << " " << p.second << '\n';
}
class Sortby
{
string Pss::*d_field;
public:
Sortby(string Pss::*field) // 3
:
d_field(field)
{}
bool operator()(Pss const &p1, Pss const &p2) const // 4
{
return p1.*d_field < p2.*d_field;
}
};
int main()
{
vector<Pss> namecity { // 5
Pss("Hampson", "Godalming"),
Pss("Moran", "Eugene"),
Pss("Goldberg", "Eugene"),
Pss("Moran", "Godalming"),
Pss("Goldberg", "Chicago"),
Pss("Hampson", "Eugene")
};
sort(namecity.begin(), namecity.end(), Sortby{ &Pss::first });// 6
cout << "sorted by names:\n";
copy(namecity.begin(), namecity.end(),
ostream_iterator<Pss>{ cout });
// 7
stable_sort(namecity.begin(), namecity.end(),
Sortby{ &Pss::second });
cout << "sorted by names within sorted cities:\n";
copy(namecity.begin(), namecity.end(),
ostream_iterator<Pss>{ cout });
}
/*
Displays:
sorted by names:
Goldberg Eugene
Goldberg Chicago
Hampson Godalming
Hampson Eugene
Moran Eugene
Moran Godalming
sorted by names within sorted cities:
Goldberg Chicago
Goldberg Eugene
Hampson Eugene
Moran Eugene
Hampson Godalming
Moran Godalming
*/
// 1 a wrapper struct Pss is created around
std::pair<std::string, std::string>. The intent here is to define a type
that is a wrapper around a class that is defined in the std namespace for
which no insertion operation has been defined. This struct design conflicts
with the principles outlined in section 14.7. However, inheritance
is defensible here as the intention is not to add `missing features' and as
pair itself is in essence just Plain Old Data.
// 2), operator<< is overloaded for Pss objects.
Although the compiler wouldn't have complained if this operator had been
defined in the std namespace for the pair<string, string> type, this
would also have been bad style as the
std
namespace is off limits to ordinary programs. By defining a wrapper type
around pair<string, string> bad style can be prevented.
// 3), a class Sortby is defined, allowing us to
construct an anonymous object receiving a pointer to one of the
Pss data members that are used for sorting. In this case, as both members
are string objects, its constructor can easily be defined. It expects
a pointer to a string member of the class Pss.
Sortby's operator() member (// 4) receives two references
to Pss objects and uses its pointer to member to compare the appropriate
fields of the Pss objects.
main some data is stored in a vector (// 5).
// 6) the first sort takes place. The least important
criterion must be sorted first and for this a simple sort suffices. Since
we want the names to be sorted within cities, the names represent the least
important criterion, so we sort by names: Sortby(&Pss::first).
//
7). Since the relative ordering of the names are not altered anymore by
stable_sort, the ties that are observed when cities are sorted are solved
in such a way that the existing relative ordering is not broken. So, we end up
getting Goldberg in Eugene before Hampson in Eugene, before Moran in
Eugene. To sort by cities, we use another anonymous Sortby object:
Sortby(&Pss::second).
<algorithm>
void swap(Type &object1, Type &object2);
object1 and object2 exchange their values.
They do so by either cyclic copy assignment or cyclic move assignment (if
available).
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string first[] = {"alpha", "bravo", "charley"};
string second[] = {"echo", "foxtrot", "golf"};
size_t const n = sizeof(first) / sizeof(string);
cout << "Before:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
for (size_t idx = 0; idx < n; ++idx)
swap(first[idx], second[idx]);
cout << "After:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
Before:
alpha bravo charley
echo foxtrot golf
After:
echo foxtrot golf
alpha bravo charley
*/
<algorithm>
ForwardIterator2 swap_ranges(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 result);
[first1, last1)
are swapped with the 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;
int main()
{
string first[] = {"alpha", "bravo", "charley"};
string second[] = {"echo", "foxtrot", "golf"};
size_t const n = sizeof(first) / sizeof(string);
cout << "Before:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
swap_ranges(first, first + n, second);
cout << "After:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
Displays:
Before:
alpha bravo charley
echo foxtrot golf
After:
echo foxtrot golf
alpha bravo charley
*/
<algorithm>
OutputIterator transform(InputIterator first, InputIterator
last, OutputIterator result, UnaryOperator op);
OutputIterator transform(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.
<algorithm>
ForwardIterator unique(ForwardIterator first,
ForwardIterator last);
ForwardIterator unique(ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
std::unique generic algorithm assumes that the elements in the
range have previously been sorted (cf. section 19.1.59).
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(InputIterator first,
InputIterator last, OutputIterator result);
OutputIterator unique_copy(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
*/