Movatterモバイル変換

• Table of Contents
• Previous Chapter
• Next Chapter

Chapter 19: The STL Generic Algorithms

19.1: The Generic Algorithms

In the previous chapter the Standard Template Library (STL) was introduced. Animportant element of the STL, thegeneric algorithms, was not covered inthat chapter as they form a fairly extensive part of the STL. Over time theSTL has grown considerably, mainly as a result of a growing importance andappreciation oftemplates. Covering generic algorithm in the STL chapteritself would turn that chapter into an unwieldy one and so the genericalgorithms 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 differentdata types while maintaining type safety. The prototypical example of this isthesort generic algorithm. To contrast: whileC requiresprogrammers to write callback functions in which type-unsafevoid const *parameters have to be used, internally forcing the programmer to resort tocasts, STL'ssort frequently allows the programmer merely to statesomething akin to

    sort(first-element, last-element)

Generic algorithms should be used wherever possible. Avoid the urge to designyour own code for commonly encountered algorithms. Make it a habit tofirst thoroughly search the generic algorithms for an availablecandidate. The generic algorithms should become yourweapon of choice whenwriting code: acquire full familiarity with them and make their use your`second nature'.

On the other hand, without downgrading the importance of the genericalgorithms, it's clear that over the years the number of available genericalgorithms have seen an almost unlimited growth. Many new algorithms wereadded, even though for quite a few of them it's either very easy to providedirect implementations, or which may hardly ever be used. Anexample is theis_sorted generic algorithm, simply returningtrue if arange of elements is considered sorted andfalse if not. How hard is it todefine such a function in the occasional situation you might need it? Thisapplies to quite a few other generic algorithms. It's of course nice to havean extensive toolbox, but do you need, e.g., screwdrivers thatperfectly match the screws' heads? Most likely not.... To avoid an excessivegrowth of this chapter, some sections contain comparable algorithms, and insome sections links tocppreference areprovided when referring to comparable algorithms.

Nevertheless, this chapter's sections cover many of the STL'sgeneric algorithms (in alphabetical order). For each algorithm thefollowing information is provided:

• The required header file;
• The function prototype;
• A short description;
• A short example.

Almost every generic algorithm expects an iterator range[first, last),defining the series of elements on which the algorithm operates. The iteratorspoint to objects or values. When an iterator points to aType value orobject, function objects used by the algorithms usually receiveType const& objects or values. Usually function objects cannot modify the objects theyreceive as their arguments. This does not hold true formodifying genericalgorithms, whichare of course able to modify the objects they operateupon.

Generic algorithms may be categorized. TheC++ Annotations distinguishes the following categories of generic algorithms:

• Comparators: comparing (ranges of) elements:

  all_of; any_of;equal;includes;lexicographical_compare;mismatch;none_of;

• Copiers / movers: performing copy / move operations:

  copy;copy_backward;copy_if;move; move_backward;partition_copy;partial_sort_copy;remove_copy; remove_copy_if;replace_copy; replace_copy_if;reverse_copy;rotate_copy;sample;shift_left; shift_right;unique_copy;

• Counters: performing count operations:

  count; count_if;

• Heap operators: manipulating amax-heap:

  make_heap;pop_heap;push_heap;sort_heap;

• Initializers: initializing data:

  fill; fill_n;generate; generate_n;iota;uninitialized (raw) memory;

• Limiters: determining boundaries of data:

  begin; end;

• Operators: performing some kind of (arithmetic?) operations:

  accumulate;adjacent_difference;exclusive_scan; inclusive_scan;inner_product;partial_sum;reduce;transform_reduce;

• Searchers: performing search (and find) operations:

  adjacent_find;binary_search;equal_range;find;find_end;find_first_of;find_if; find_if_not;lower_bound;max;max_element; min_element;min;minmax;minmax_element;partition_point;search; search_n;set_difference;set_intersection;set_symmetric_difference;set_union;upper_bound;

• Shufflers: performing reordering operations (sorting,merging,permuting,swapping):

  inplace_merge;iter_swap;merge;next_permutation;nth_element;partial_sort;partition;prev_permutation;remove; remove_copy; remove_copy_if; remove_if;reverse; reverse_copy;rotate; rotate_copy;shuffle;sort;stable_partition;stable_sort;swap; swap_ranges;unique;

• Verifiers: checking for specific conditions:

  is_partitioned;is_permutation;is_sorted;is_sorted_until;

• Visitors: visiting elements in a range:

  for_each;replace; replace_copy; replace_copy_if; replace_if;transform;unique_copy;

19.1.1: Execution policies

These (and many other) generic algorithms can be executed in parallel,depending on the specifiedexecution policy. When no execution policy isspecified then the algorithms operated in their standard, sequential, way. Thegeneric algorithms supporting execution policies have overloaded versionswhere the first parameter specifies the execution policy to use, followed bytheir remaining parameters. Function prototypes listed the following sectionsshowing a first parameter[ExecPol,] may specify one of the executionpolicies introduced in this section as their first arguments. E.g., one of thesort generic algorithm's prototypes is

   void sort([ExecPol,]         RandomAccessIterator first, RandomAccessIterator last);

   sort(vs.bgin(), vs.end());

   sort(execution::par, vs.bgin(), vs.end());

In order to use execution policies the<execution> header file must beincluded, and the linking option-ltbb must be specified with linking thecompiled object files(s).

There are four types of execution policies (all defined in thestdnamespace):

• <execution::sequenced_policy>, whose predefined objectexecution::seq is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy it will not be using parallel execution.

• <execution::parallel_policy>, whose predefined objectexecution::par is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy it may be using parallel execution: the generic algorithm may decide not to use parallel execution when it decides that the overhead of parallel execution is in fact reducing the efficiency of non-parallel execution. E.g., when sorting 100 elements sequential execution is faster than parallel execution and an algorithm likesort won't use parallel execution.

• <execution::parallel_unsequenced_policy>, whose predefined objectexecution::par_unseq is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy it may be using parallel execution, execution may be migrated across threads (using a so-calledparent-stealing scheduler), or execution may bevectorized (i.e., a single thread is used accessing data items at completely different locations (like swapping the first and middle elements of vectors)). When using this policy the order in which processed elements are accessed and the threads from which these elements are accessed is undefined.

• <execution::unsequenced_policy>, whose predefined objectexecution::unseq is used to specify this execution policy when calling generic algorithms.

  When calling a generic algorithm specifying this policy the algorithm uses vectorized execution.

Whenever algorithms are called using the above policy specifications andduring the execution of these algorithms functions are called generatinguncaught exceptionsstd::terminate is called.

When using parallel execution the objects or functions passed to the genericalgorithms might access data defined elsewhere. If those data are modifiedthen it is possible that modifications are requested from different executionthreads, which could result indata races ordeadlocks. The programmer should ensure that data races and/ordadlocks cannot occur when using parallel execution.

19.1.2: accumulate

• Header file:<numeric>
• Function prototypes:
  • Type accumulate(InputIterator first, InputIterator last, Type init);
  • Type accumulate(InputIterator first, InputIterator last, Type init, BinaryOperation op);
• Description:
  • The first prototype:operator+ is applied to the initialvalueinit (lhs argument) and, in sequence, all elements reached fromthe iterator range (rhs argument). The resulting value is returned.
  • The second prototype: the binary operatorop is applied tothe initial valueinit (lhs argument) and, in sequence, all elementsreached from the iterator range. The resulting value is returned.
  At each step the initial value receives the result of that step's computation. E.g., ifminus<int> is used with the intial value 1, and the iterators refer to 2 and 3, then at step 1: 1 - 2 = -1 is computed and at step 2: -1 - 3 = -4. Soaccumulate returns -4.

  (See also thereduce algorithm (section19.1.43)).

• Example:

      #include <numeric>    #include <vector>    #include <iostream>    using namespace std;    int main()    {        int         ia[] = {1, 2, 3, 4};        vector<int> iv(ia, ia + 4);        cout <<            "Sum: " << accumulate(iv.begin(), iv.end(), int()) << "\n"            "Product: " << accumulate(iv.begin(), iv.end(), int(1),                                            multiplies<int>{}) << '\n';    }    //  Displays:    //      Sum: 10    //      Product: 24

19.1.3: adjacent_difference

• Header file:<numeric>
• Function prototypes:
  • OutputIterator adjacent_difference([ExecPol,] InputIterator first,InputIterator last, OutputIterator result);
  • OutputIterator adjacent_difference([ExecPol,] InputIterator first,InputIterator last, OutputIterator result, BinaryOperation op);
• Description: All operations are performed on the original values, all computedvalues are returned values.
  • The first prototype: the first returned element is equal tothe first element of the input range. The remaining returned elements areequal to the difference of the corresponding element in the input range andits previous element.
  • The second prototype: the first returned element is equal to the first element of the input range. The remaining returned elements areequal to the result of the binary operatorop applied to thecorresponding element in the input range (left operand) and its previouselement (right operand).
• Example:

      #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

19.1.4: adjacent_find

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator adjacent_find([ExecPol,] ForwardIterator first, ForwardIterator last);
  • OutputIterator adjacent_find([ExecPol,] ForwardIterator first,ForwardIterator last, Predicate pred);
• Description:
  • The first prototype: the iterator pointing to the firstelement of the first pair of two adjacent equal elements is returned. If nosuch element exists,last is returned.
  • The second prototype: the iterator pointing to the firstelement of the first pair of two adjacent elements for which the binarypredicatepred returnstrue is returned. If no such element exists,last is returned.
• Example:

      #include <algorithm>    #include <string>    #include <iostream>    using namespace std;    bool squaresDiff10(size_t first, size_t second)    {        return second * second - first * first >= 10;    }    int main()    {        string sarr[] =            {                "Alpha", "bravo", "charley", "delta", "echo", "echo",                "foxtrot", "golf"            };        auto last = end(sarr);          // see the 'begin / end' section        string *result = adjacent_find(sarr, last);        cout << *result << '\n';        result = adjacent_find(++result, last);        cout << "Second time, starting from the next position:\n" <<            (                result == last ?                    "** No more adjacent equal elements **"                :                    "*result"            ) << '\n';        size_t iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};        size_t *ires = adjacent_find(iv, end(iv), squaresDiff10);        cout <<            "The first numbers for which the squares differ at least 10: "            << *ires << " and " << *(ires + 1) << '\n';    }    // Displays:    //    //   echo    //   Second time, starting from the next position:    //   ** No more adjacent equal elements **    //   The first numbers for which the squares differ at least 10: 5 and 6

19.1.5: all_of / any_of / none_of

• Header file:<algorithm>
• Function prototypes:
  • bool all_of([ExecPol,] InputIterator first, InputIterator last, Predicate pred);
  • bool any_of([ExecPol,] InputIterator first, InputIterator last, Predicate pred);
  • bool none_of([ExecPol,] InputIterator first, InputIterator last, Predicate pred);
• Description:
  • The first prototype returnstrue if the unary predicatepred returnstrue for all elements reached from the iterator range[first, last); otherwisefalse is returned.
  • The second prototype returnstrue if the unary predicatepred returnstrue for at least on of the elements reached from theiterator range[first, last); otherwisefalse is returned.
  • The third prototype returnstrue if the unary predicatepred returnstrue for none of the elements reached from the iteratorrange[first, last); otherwisefalse is returned.
• Example:

      #include <algorithm>    #include <string>    #include <iostream>    using namespace std;    bool contains_a(string const &str)    {        return str.find('a') != string::npos;    }    int main()    {        string sarr[] =            { "Alpha", "Bravo", "Charley", "Delta", "Echo" };        auto past = end(sarr);      // see the next section        cout << "All elements contain 'a': " <<            all_of(sarr, past, contains_a) << "\n"            "At least one element contains 'a': " <<            any_of(sarr, past, contains_a) << "\n"            "None of the elements contains 'a': " <<            none_of(sarr, past, contains_a) << '\n';    }    //  Displays:    //      All elements contain 'a': 0    //      At least one element contains 'a': 1    //      None of the elements contains 'a': 0

19.1.6: begin / end

• Header file:<iterator> (also available when including<algorithm>)
• Function prototypes:
  • auto begin([const] &obj);
  • auto end([const] &obj);
  • Type [cons] *begin(Type [const] (&array)[N]);
  • Type [cons] *end(Type [const] (&array)[N]);
  • auto cbegin(const &obj);
  • auto cend(const &obj);
• Description: Thebegin andend functions return, respectively, the begin-and end-iterators or pointers of objects offeringbegin() andend()members or of arrays of (compile-time) available sizes.
  • The first two prototypes return, respectively,obj.begin() andobj.end() of (possiblyconst) references toobj
  • Prototypes three and four return (possiblyconst) pointers to, respectively, the first and beyond the last element of thearray argument, which must be an array of (compile-time) known size.
  • The lastt two prototypes return, respectively,obj.begin() andobj.end() ofconst references toobj
• Example:

      #include <iterator>    #include <iostream>    #include <string>    using namespace std;    int main()    {        string sarr[] =            { "Alpha", "Bravo", "Charley", "Delta", "Echo" };        // since sarr == begin(sarr), begin(...) is not used here        auto next = end(sarr);        cout << "sarr has " << size(sarr) <<                " (== " << (next - sarr) << ") elements\n"                "the last char. of the first element is " <<                *(end(sarr[0]) - 1) << '\n';    }    //  Displays:    //    sarr has 5 (== 5) elements    //    the last char. of the first element is a

19.1.7: binary_search

• Header file:<algorithm>
• Function prototypes:
  • bool binary_search(ForwardIterator first, ForwardIteratorlast, Type const &value);
  • bool binary_search(ForwardIterator first, ForwardIteratorlast, Type const &value, Comparator comp);
• Description:
  • The first prototype:value is searched for using binarysearch in the elements reached from the iterator range[first,last). The elements must have been sorted by theType::operator<function.True is returned if the element was found,false otherwise.
  • The second prototype:value is searched for using binarysearch in the elements reached from the iterator range[first,last). The elements in the range must have been sorted by theComparatorfunction object.True is returned if the element was found,falseotherwise. As illustrated by the following example, the function objectfunction's first parameter refers to an element in the iterator range, whilethe function object's second parameter refers tovalue.
• Example:

      #include <algorithm>    #include <string>    #include <iostream>    #include <functional>    using namespace std;    int main()    {        string sarr[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel"            };        auto past = end(sarr);        bool result = binary_search(sarr, past, "foxtrot");        cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';        reverse(sarr, past);                // reverse the order of elements                                            // binary search now fails:        result = binary_search(sarr, past, "foxtrot");        cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';                                            // ok when using appropriate                                            // comparator:        result = binary_search(sarr, past, "foxtrot", greater<string>());        cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';        // alternatively, using a lambda expression showing the used 'sarr'        // indices and the value of the second parameter:        result = binary_search(sarr, past, "foxtrot",            [&](string const &sarrEl, string const &value)            {                cout << "comparing element " << (&sarrEl - sarr) <<                        " (" << sarrEl << ") to " << value << '\n';                return sarrEl > value;            }        );        cout << "found it: " << result << '\n';    }    //  Displays:    //      found foxtrot    //      didn't find foxtrot    //      found foxtrot    //      comparing element 4 (delta) to foxtrot    //      comparing element 2 (foxtrot) to foxtrot    //      comparing element 1 (golf) to foxtrot    //      comparing element -3 (foxtrot) to foxtrot    //      found it: 1

Ifvalue is in fact present in the range of values, then this genericalgorithm doesn't answer the question wherevalue is located. If thatquestion must be answered the generic algorithmslower_boundandupper_bound can be used. Refer to sections19.1.30 and19.1.61 for examples illustrating the use of theselatter two algorithms.

19.1.8: copy / copy_if

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator copy([ExecPol,] InputIterator first,InputIterator last, OutputIterator destination);
  • OutputIterator copy_if([ExecPol,] InputIterator first,InputIterator last, OutputIterator destination, Predicate pred);
• Description:
  • First prototype: the elements reached from the iterator range[first, last) are copied (assigned) to thedestination outputrange. The return value is the OutputIterator pointing just beyond the lastelement that was copied to the destination range (so, `last' in thedestination range is returned).
  • Second prototype: same as the first prototype but thefunction ends after copyingn elements, returning an iterator pointingjust beyond the last element that was copied to the destination range.
• Example:
  Note the second call tocopy. It uses anostream_iterator forstring objects. This iterator writes thestring values to thespecifiedostream (i.e.,cout), separating the values by the specifiedseparation string (i.e.," ").

      #include <algorithm>    #include <string>    #include <iostream>    #include <iterator>    using namespace std;    bool pred(std::string const &str)    {        return "aceg"s.find(str.front()) == string::npos;    }    int main()    {        string sarr[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel"            };        auto last = end(sarr);        copy(sarr + 2, last, sarr); // move all elements two positions left                     // copy to cout using an ostream_iterator for strings        copy(sarr, last, ostream_iterator<string>(cout, " "));        cout << '\n';                    // using copy_if:        copy_if(sarr, sarr + size(sarr), sarr, pred);        copy(sarr, sarr + size(sarr), ostream_iterator<string>(cout, " "));        cout << '\n';    }    //  Displays:    //  charley delta echo foxtrot golf hotel golf hotel    //  delta foxtrot hotel hotel golf hotel golf hotel

• See also:unique_copy

19.1.9: copy_backward

• Header file:<algorithm>
• Function prototype:
  • BidirectionalIterator copy_backward(InputIterator first,InputIterator last, BidirectionalIterator last2);
• Description:
  • The series of elements reached from the iterator range[first, last) are copied from the element at positionlast - 1until (and including) the element at positionfirst to the element range,ending at positionlast2 - 1 using the assignment operator of theunderlying data type. The destination range is therefore[last2 - (last- first), last2).

    Note that this algorithm doesnot reverse the order of the elements whencopying them to the destination range.

    The return value is the BidirectionalIterator pointing to the last elementthat was copied to the destination range (so, `first' in the destinationrange, pointed to bylast2 - (last - first), is returned).

• Example:

      #include <algorithm>    #include <string>    #include <iostream>    #include <iterator>    using namespace std;    int main()    {        string sarr[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel"            };        auto past = end(sarr);        copy        (            copy_backward(sarr + 3, past, past - 3),            past,            ostream_iterator<string>(cout, " ")        );        cout << '\n';    }    // Displays:    golf hotel foxtrot golf hotel foxtrot golf hotel

19.1.10: count / count_if

• Header file:<algorithm>
• Function prototypes:
  • size_t count([ExecPol,] InputIterator first, InputIterator last, Type const &value);
  • size_t count_if([ExecPol,] InputIterator first, InputIterator last, Predicate predicate);

• Description:
  • The first prototype: returns the number of timesvalueoccurs in the elements reached from the iterator range[first, last).UsesType::operator== to determine whethervalue is equal to anelement in the iterator range.
  • The second prototype: returns the number of timesunary predicate `predicate' returnstrue when applied to theelements reached from the iterator range[first, last).
• Example:

      #include <algorithm>    #include <iostream>    using namespace std;    bool pred(int value)    {        return value & 1;    }    int main()    {        int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};        cout << "Number of times the value 3 is available: " <<                count(ia, ia + size(ia), 3) << "\n"                "Number of odd values in the array is: " <<                count_if(ia, ia + size(ia), pred) << '\n';    }    // Displays:    Number of times the value 3 is available: 3    //              Number of odd values in the array is: 5

19.1.11: equal

• Header file:<algorithm>
• Function prototypes:
  • bool equal([ExecPol,] InputIterator first, InputIterator last, InputIterator otherFirst);
  • bool equal([ExecPol,] InputIterator first, InputIterator last, InputIterator otherFirst, BinaryPredicate pred);
• Description:
  • The first prototype: the elements in the range[first,last) are compared to a range of equal length starting atotherFirst. Thefunction returnstrue if the visited elements in both ranges are equalpairwise. The ranges need not be of equal length, only the elements in theindicated range are considered (and must be available).
  • The second prototype: the elements in the range[first, last) are compared to a range of equal length starting atotherFirst. The function returnstrue if the binary predicate, appliedto all corresponding elements in both ranges returnstrue for every pairof corresponding elements. The ranges need not be of equal length, only theelements in the indicated range are considered (and must be available).
• Example:

      #include <algorithm>    #include <string>    #include <cstring>    #include <iostream>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) == 0;    }    int main()    {        string first[] =            {                "Alpha", "bravo", "Charley", "delta", "Echo",                "foxtrot", "Golf", "hotel"            };        string second[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel"            };        auto past = end(first);        cout << "The elements of `first' and `second' are pairwise " <<            (equal(first, past, second) ? "equal" : "not equal") <<            '\n' <<            "compared case-insensitively, they are " <<            (                equal(first, past, second, caseString) ?                    "equal" : "not equal"            ) << '\n';    }    //  Displays:    //      The elements of `first' and `second' are pairwise not equal    //      compared case-insensitively, they are equal

19.1.12: equal_range

• Header file:<algorithm>
• Function prototypes:
  • pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Typeconst &value);
  • pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Typeconst &value, Compare comp);
• Description (see also identically named member functions of,e.g., themap (section12.3.7) andmultimap (section12.3.8)):
  • The first prototype: starting from a sorted sequence (wheretheoperator< of the data type to which the iterators point was used tosort the elements in the provided range), a pair of iterators is returnedrepresenting the return value of, respectively,lower_bound (returningthe first element that is not smaller than the provided reference value, seesection19.1.30) andupper_bound (returning the first elementbeyond the provided reference value, see section19.1.61).
  • The second prototype: starting from a sorted sequence (wherethecomp function object was used to sort the elements in the providedrange), a pair of iterators is returned representing the return values of,respectively, the functionslower_bound (section19.1.30) andupper_bound (section19.1.61).
• Example:

      #include <algorithm>    #include <functional>    #include <iterator>    #include <iostream>    using namespace std;    int main()    {        int    range[] = {1, 3, 5, 7, 7, 9, 9, 9};        auto past = end(range);        pair<int *, int *>  pi;        pi = equal_range(range, past, 6);        cout << "Lower bound for 6: " << *pi.first << "\n"                "Upper bound for 6: " << *pi.second << '\n';        pi = equal_range(range, past, 7);        cout << "Lower bound for 7: ";        copy(pi.first, past, ostream_iterator<int>(cout, " "));        cout << '\n';        cout << "Upper bound for 7: ";        copy(pi.second, past, ostream_iterator<int>(cout, " "));        cout << '\n';        sort(range, past, greater<int>());        cout << "Sorted in descending order\n";        copy(range, past, ostream_iterator<int>(cout, " "));        cout << '\n';        pi = equal_range(range, past, 7, greater<int>());        cout << "Lower bound for 7: ";        copy(pi.first, past, ostream_iterator<int>(cout, " "));        cout << '\n';        cout << "Upper bound for 7: ";        copy(pi.second, past, ostream_iterator<int>(cout, " "));        cout << '\n';    }    //  Displays:    //      Lower bound for 6: 7    //      Upper bound for 6: 7    //      Lower bound for 7: 7 7 9 9 9    //      Upper bound for 7: 9 9 9    //      Sorted in descending order    //      9 9 9 7 7 5 3 1    //      Lower bound for 7: 7 7 5 3 1    //      Upper bound for 7: 5 3 1

19.1.13: exchange

• Header file:<utility>
• Function prototype:
  • Type exchange(Type &object1, ValueType &&newValue);
• Description:
  • newValue is assigned toobject1, andobject1's previous value is returned.
• Example:

      #include <utility>    #include <iostream>    using namespace std;    int main(int argc, char **argv)    {        bool more = argc > 5;        cout << "more than 5: " << exchange(more, argc > 2) <<                ", more than 2: " << more << '\n';    }    //  With `a.out one two three' displays:    //    //  more than 5: 0, more than 2: 1

19.1.14: fill / fill_n

• Header file:<algorithm>
• Function prototypes:
  • void fill([ExecPol,] ForwardIterator first,ForwardIterator last, Type const &value);
  • void fill_n([ExecPol,] ForwardIterator first, Size n, Type const &value);
• Description:
  • The first prototype: all elements reached from the iteratorrange[first, last) are initialized tovalue, overwritingpreviously stored values.
  • The second prototype:n elements starting at the elementpointed to byfirst are initialized tovalue, overwriting previouslystored values.
• Example:

      #include <algorithm>    #include <vector>    #include <iterator>    #include <iostream>    using namespace std;    int main()    {        vector<int> iv(8);        fill(iv.begin(), iv.end(), 8);        copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));        cout << '\n';        fill_n(iv.begin() + 2, 4, 4);        copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));        cout << '\n';     }    // Displays:    8 8 8 8 8 8 8 8    //              8 8 4 4 4 4 8 8

19.1.15: find / find_if / find_if_not

• Header file:<algorithm>
• Function prototypes:
  • InputIterator find([ExecPol,] InputIterator first, InputIterator last, Type const &value);
  • InputIterator find_if([ExecPol,] InputIterator first, InputIterator last, Predicate pred);
  • InputIterator find_if_not([ExecPol,] InputIterator first, InputIterator last, Predicate pred);
• Description:
  • The first prototype: elementvalue is searched for in theelements reached from the iterator range[first, last). An iteratorpointing to the first element found is returned. If the element was not found,last is returned. Theoperator== of the underlying data type is usedto compare the elements.
  • The second prototype returns an iterator pointing to thefirst element reached from the iterator range[first, last) for whichthe (unary) predicatepred returnstrue. If the element was not found,last is returned.
  • The third prototype returns an iterator pointing to the firstelement reached from the iterator range[first, last) for which the(unary) predicatepred returnsfalse. If the element was not found,last is returned. Thus,pred defines what is considered acceptable, inwhich casefind_if_not returns an iterator to the first element thatisn't.
• Example:

      #include <algorithm>    #include <string>    #include <cstring>    #include <iterator>    #include <iostream>    using namespace std;    class CaseName    {        std::string  d_string;        public:            CaseName(char const *str): d_string(str)            {}            bool operator()(std::string const &element) const            {                return strcasecmp(element.c_str(), d_string.c_str()) == 0;            }    };    void show(string const *begin, string const *end)    {        if (begin == end)            cout << "No elements were found";        else            copy(begin, end, ostream_iterator<string>{ cout, " " });        cout << '\n';    }    int main()    {        string sarr[] =            {                "Alpha", "Bravo", "Charley", "Delta", "Echo"            };        auto past = end(sarr);        show(find(sarr, past, "Delta"), past);        show(find(sarr, past, "India"), past);        show(find_if(sarr, sarr + size(sarr), CaseName{ "charley" }), past);        if (find_if(sarr, sarr + size(sarr), CaseName{ "india" }) == past)            cout << "`india' was not found in the range\n";        show(find_if_not(sarr, sarr + size(sarr), CaseName{ "alpha" }), past);    }    //  Displays:    //      Delta Echo    //      No elements were found    //      Charley Delta Echo    //      `india' was not found in the range    //      Bravo Charley Delta Echo

19.1.16: find_end

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator1 find_end([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
  • ForwardIterator1 find_end([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)
• Description:
  • The first prototype: the sequence of elements in the range[first1, last1) is searched for the last occurrence of the sequence ofelements in the range[first2, last2). If the sequence[first2, last2) is not found,last1 is returned, otherwise aniterator pointing to the first element of the matching sequence isreturned. Theoperator== of the underlying data type is used to comparethe elements in the two sequences.
  • The second prototype: the sequence of elements in the range[first1, last1) is searched for the last occurrence of the sequence ofelements in the range[first2, last2). If the sequence[first2,last2) is not found,last1 is returned, otherwise an iterator pointing tothe first element of the matching sequence is returned. The provided binarypredicate is used to compare the elements in the two sequences.
• Example:

      #include <algorithm>    #include <string>    #include <iterator>    #include <iostream>    using namespace std;    bool twice(size_t first, size_t second)    {        return first == (second << 1);    }    int main()    {        string sarr[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel",                "foxtrot", "golf", "hotel",                "india", "juliet", "kilo"            };        string search[] =            {                "foxtrot",                "golf",                "hotel"            };        auto past = end(sarr);        copy        (            find_end(sarr, past, search, search + 3),   // sequence starting            past, ostream_iterator<string>{ cout, " " } // at 2nd 'foxtrot'        );        cout << '\n';        size_t range[] = { 2, 4, 6, 8, 10, 4, 6, 8, 10 };        size_t nrs[]   = { 2, 3, 4 };        copy                // sequence of values starting at last sequence        (                   // of range[] that are twice the values in nrs[]            find_end(range, range + 9, nrs, nrs + 3, twice),            range + 9, ostream_iterator<size_t>{ cout, " " }        );        cout << '\n';    }    //  Displays:    //      foxtrot golf hotel india juliet kilo    //      4 6 8 10

19.1.17: find_first_of

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator1 find_first_of([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
  • ForwardIterator1 find_first_of([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2,ForwardIterator2 last2, BinaryPredicate pred)
• Description:
  • The first prototype: the sequence of elements in the range[first1, last1) is searched for the first occurrence of an element inthe sequence of elements in the range[first2, last2). If noelement in the sequence[first2, last2) is found,last1 isreturned, otherwise an iterator pointing to the first element in[first1, last1) that is equal to an element in[first2, last2)is returned. Theoperator== of the underlying data type is used to comparethe elements in the two sequences.
  • The second prototype: the sequence of elements in the range[first1, last1) is searched for the first occurrence of an element inthe sequence of elements in the range[first2, last2). Each element inthe 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 predicatepred (receiving anthe element out of the range[first1, last1) and an element from therange[first2, last2)) returnstrue is returned. Otherwise,last1 is returned.
• Example:

      #include <algorithm>    #include <string>    #include <iterator>    #include <iostream>    using namespace std;    bool twice(size_t first, size_t second)    {        return first == (second << 1);    }    int main()    {        string sarr[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel",                "foxtrot", "golf", "hotel",                "india", "juliet", "kilo"            };        string search[] =            {                "foxtrot",                "golf",                "hotel"            };        auto past = end(sarr);        copy        (                                                 // sequence starting            find_first_of(sarr, past, search, search + 3),// at 1st 'foxtrot'            past, ostream_iterator<string>{ cout, " " }        );        cout << '\n';        size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};        size_t nrs[]   = {2, 3, 4};            // copy the sequence of values in 'range', starting at the            // first element in 'range' that is equal to twice one of the            // values in 'nrs', and ending at the past element of 'range'        copy        (            find_first_of(range, range + 9, nrs, nrs + 3, twice),            range + 9, ostream_iterator<size_t>{ cout, " " }        );        cout << '\n';    }    //  Displays:    //      foxtrot golf hotel foxtrot golf hotel india juliet kilo    //      4 6 8 10 4 6 8 10

19.1.18: for_each

• Header file:<algorithm>
• Function prototype:
  • Function for_each([ExecPol,] ForwardIterator first, ForwardIterator last, Function func);
• Description:
  • The elements reached from the iterator range[first, last) are passed in sequence as a reference to the function (orfunction object)func. The function may modify the elements it receives(as the used iterator is a forward iterator). Alternatively, if the elementsshould be transformed,transform (see section19.1.56) can beused. The function itself or a copy of the provided function object isreturned: see the example below, in which an extra argument list is added tothefor_each call, which argument is eventually also passed to thefunction given tofor_each. Withinfor_each the return value of thefunction that is passed to it is ignored. Thefor_each generic algorithmlooks a lot like the range-based for loop, but different from the range-basedfor-loop thefor_each algorithm can also be used with sub-ranges and withreverse-iterators.
• Example:

      #include <algorithm>    #include <string>    #include <iostream>    #include <cctype>    using namespace std;    void lowerCase(char &ch)                     // `ch' *is* modified    {        ch = tolower(static_cast<unsigned char>(ch));    }    void capitalizedOutput(string const &str)   // `str' is *not* modified    {        char *tmp = new char[str.size() + 1]();        str.copy(tmp, str.size());        for_each(tmp + 1, tmp + str.size(), lowerCase);        tmp[0] = toupper(*tmp);        cout << tmp << ' ';        delete[] tmp;    }    int main()    {        string sarr[] =            {                "alpha", "BRAVO", "charley", "DELTA",  "echo",                "FOXTROT", "golf", "HOTEL"            };        for_each(sarr, end(sarr), capitalizedOutput)("that's all, folks");        cout << '\n';    }    // Displays:    // Alpha Bravo Charley Delta Echo Foxtrot Golf Hotel That's all, folks

• Here is another example using a function object:

      #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    */

Thefor_each algorithm cannot directly be used (i.e., by passing*this as the function object argument) inside a member function to modifyits own object as thefor_each algorithm first creates its own copy of thepassed function object. Alambda function or awrapper class whoseconstructor accepts a pointer or reference to the current object and possiblyto one of its member functions solves this problem.

19.1.19: generate / generate_n

• Header file:<algorithm>
• Function prototype:
  • void generate([ExecPol,] ForwardIterator first, ForwardIterator last, Generator generator);
  • void generate_n([ExecPol,] ForwardIterator first, Size n, Generator generator);
• Description:
  • The first prototype: all elements reached from the iteratorrange[first, last) are initialized by the return value ofgenerator, which can be a function or functionobject.Generator::operator() does not receive any arguments. The exampleuses a well-known fact from algebra: in order to obtain the square ofn +1, add1 + 2 * n ton * n.
  • The second prototype:n elements starting at the elementpointed to by iteratorfirst are initialized by the return value ofgenerator.
• Example:

      #include <algorithm>    #include <vector>    #include <iterator>    #include <iostream>    using namespace std;    class NaturalSquares    {        size_t d_newsqr;        size_t d_last;        public:            NaturalSquares(): d_newsqr(0), d_last(0)            {}            size_t operator()()            {                   // using: (a + 1)^2 == a^2 + 2*a + 1                return d_newsqr += (d_last++ << 1) + 1;            }    };    int main()    {        vector<size_t> uv(10);        generate(uv.begin(), uv.end(), NaturalSquares{});        copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });        cout << '\n';        uv = vector<size_t>(10);        generate_n(uv.begin(), 5, NaturalSquares{});        copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });        cout << '\n';    }    // Displays:   1 4 9 16 25 36 49 64 81 100    //             1 4 9 16 25 0 0 0 0 0

19.1.20: includes

• Header file:<algorithm>
• Function prototypes:
  • bool includes([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
  • bool includes([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,Compare comp);
• Description:
  • The first prototype: both sequences of elements inthe ranges[first1, last1) and[first2, last2) should have beensorted using theoperator< of the data type to which the iteratorspoint. The function returnstrue 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).
  • The second prototype: both sequences of elements inthe ranges[first1, last1) and[first2, last2) should have beensorted using thecomp function object. The function returnstrue ifevery element in the second sequence[first2, last2) is contained inthe first sequence[first1, last1) (the second range is a subset ofthe first range).
• Example:

      #include <algorithm>    #include <string>    #include <cstring>    #include <iostream>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) == 0;    }    int main()    {        string first1[] =            {                "alpha", "bravo", "charley", "delta",  "echo",                "foxtrot", "golf", "hotel"            };        auto past1 = end(first1);        string first2[] =            {                "Alpha", "bravo", "Charley", "delta",  "Echo",                "foxtrot", "Golf", "hotel"            };        auto past2 = end(first2);        string second[] = { "charley", "foxtrot", "hotel" };        cout << "The elements of `second' are " <<            (includes(first1, past1, second, second + 3) ? "" : "not") <<               " contained in the first sequence:\n"               "second is a subset of first1\n"            "The elements of `first1' are " <<            (includes(second, second + 3, first1, past1) ? "" : "not") <<            " contained in the second sequence\n"            "The elements of `second' are " <<            (includes(first2, past2, second, second + 3) ? "" : "not") <<            " contained in the first2 sequence\n"            "Using case-insensitive comparison,\n"            "the elements of `second' are " <<            (includes(first2, past2, second, second + 3, caseString) ?                                                           "" : "not") <<            " contained in the first2 sequence\n";    }    //  Displays:    //     The elements of `second' are  contained in the first sequence:    //     second is a subset of first1    //     The elements of `first1' are not contained in the second sequence    //     The elements of `second' are not contained in the first2 sequence    //     Using case-insensitive comparison,    //     the elements of `second' are  contained in the first2 sequence

19.1.21: inner_product

• Header file:<numeric>
• Function prototypes:
  • 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);
• Description:
  • The first prototype: the sum of all pairwise products of theelements in the range[first1, last1) and the same number ofelements starting at the element pointed to byfirst2 are added toinit, and this sum is returned. The function uses theoperator+ andoperator* of the data type to which the iterators point.
  • The second prototype: binary operatorop1 instead of thedefault addition operator, and binary operatorop2 instead of the defaultmultiplication operator are applied to all pairwise elements in therange[first1, last1) and the same number of elements starting at theelement pointed to byfirst2. The results of the binary operator calls areadded toinit andinit's final value is returned.
  (See also section19.1.57.)
• Example:

      #include <numeric>    #include <algorithm>    #include <iterator>    #include <iostream>    #include <string>    using namespace std;    class Cat    {        std::string  d_sep;        public:            Cat(string const &sep)            :                d_sep(sep)            {}            string operator()                (string const &s1, string const &s2) const            {                return s1 + d_sep + s2;            }    };    int main()    {        size_t ia1[] = { 1, 2, 3, 4, 5, 6, 7 };        cout << "The sum of all squares in ";        copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });        cout << "is " << inner_product(ia1, ia1 + 7, ia1, 0) << '\n';        size_t ia2[] = { 7, 6, 5, 4, 3, 2, 1 };        cout << "The sum of all cross-products in ";        copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });        cout << "and ";        copy(ia2, ia2 + 7, ostream_iterator<size_t>{ cout, " " });        cout << "is " << inner_product(ia1, ia1 + 7, ia2, 0) << '\n';        string names1[] = { "Frank", "Karel", "Piet" };        string names2[] = { "Brokken", "Kubat", "Plomp"};        cout << "All combined names of ";        copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });        cout << "and\n";        copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });        cout << "are:" <<            inner_product(names1, names1 + 3, names2, string{ "\t" },                Cat{ "\n\t"}, Cat{ " " }) << '\n';    }    // Displays:    //  The sum of all squares in 1 2 3 4 5 6 7 is 140    //  The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84    //  All combined names of Frank Karel Piet and Brokken Kubat Plomp are:    //          Frank Brokken    //          Karel Kubat    //          Piet Plomp

19.1.22: inplace_merge

• Header file:<algorithm>
• Function prototypes:
  • void inplace_merge([ExecPol,] BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
  • void inplace_merge([ExecPol,] BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
• Description:
  • The first prototype: the two (sorted) ranges[first,middle) and[middle, last) are merged, keeping a sorted list (using theoperator< of the data type to which the iterators point). The finalseries is stored in the range[first, last).
  • The second prototype: the two (sorted) ranges[first,middle) and[middle, last) are merged, keeping a sorted list (using theboolean result of the binary comparison operatorcomp). The final seriesis stored in the range[first, last).
• Example:

      #include <algorithm>    #include <string>    #include <cstring>    #include <iterator>    #include <iostream>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) == 0;    }    int main()    {        string range[] =            {                "alpha", "charley", "echo", "golf",                "bravo", "delta", "foxtrot",            };        inplace_merge(range, range + 4, range + 7);        copy(range, range + 7, ostream_iterator<string>{ cout, " " });        cout << '\n';        string range2[] =            {                "ALPHA", "CHARLEY", "DELTA", "foxtrot", "hotel",                "bravo", "ECHO", "GOLF"            };        inplace_merge(range2, range2 + 5, range2 + 8, caseString);        copy(range2, range2 + 8, ostream_iterator<string>{ cout, " " });        cout << '\n';    }    //  Displays:    //      alpha bravo charley delta echo foxtrot golf    //      ALPHA bravo CHARLEY DELTA ECHO foxtrot GOLF hotel

19.1.23: iota

• Header file:<numeric>
• Function prototype:
  • void iota(ForwardIterator first, ForwardIterator last, Type value);
• Description:
  • All elements reached from the iterator range[first,last) are assigned the values of the incremented sequence of values starting atvalue.*first receivesvalue,*(first + 1) receives++value, etc.
• Example:

      #include <numeric>    #include <algorithm>    #include <vector>    #include <iostream>    #include <iterator>    using namespace std;    int main()    {        vector<size_t> uv(10);        iota(uv.begin(), uv.end(), 0);        copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });        cout << '\n';    }    // Displays:   0 1 2 3 4 5 6 7 8 9

19.1.24: is_partitioned

• Header file:<algorithm>
• Function prototype:
  • bool is_partitioned([ExecPol,] InputIterator first, InputIterator last, UnaryPred pred);
• Description:
  • Returnstrue ifpred, receiving all elements reachedfrom the iterator range[first, last), returnstrue until itreturnsfalse, and ifpred, receiving the remaining elements, returnsfalse. It also returnstrue if the range is empty.
• Example:

      #include <algorithm>    #include <iterator>    #include <vector>    #include <iostream>    using namespace std;    bool pCheck(int value)    {        return value < 3;    }    int main()    {        vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};        cout << "partitioned before: " <<                is_partitioned(uv.begin(), uv.end(), pCheck) << "\n"                "first value returning 'false' when partitioning: " <<                *partition(uv.begin(), uv.end(), pCheck) << '\n';        copy(uv.begin(), uv.end(), ostream_iterator<int>{ cout, " " });        cout << '\n';        cout << "partitioned after: " <<                is_partitioned(uv.begin(), uv.end(), pCheck) <<'\n';    }    // Displays:   1 4 9 16 25 36 49 64 81 100    //             1 4 9 16 25 0 0 0 0 0

19.1.25: is_permutation

• Header file:<algorithm>
• Function prototypes:
  • bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2);
  • bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2);
  • bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator firs2, BinaryPred pred);
  • bool is_permutation(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPred pred);
• Description:
  • The first prototype: returnstrue if the elements in theiterator range[first1, last1), are a permutation of the elements inthe identically sized range starting atfirst2.
  • The second prototype: like the first prototype but the endingiterator of the second range is provided as the fourth argument.
  • The third prototype: like the first prototype but using theresult ofpred to determine whether two elements are equal.
  • The fourth prototype: like the second prototype but using theresult ofpred to determine whether two elements are equal.
• Example:

      #include <algorithm>    #include <iostream>    using namespace std;    int main()    {        int one[] = { 1, -2, 3, -4, 5, -6, 7, -8, 9};        int two[] = { -8, -2, -4, -6, 3, 1, 5, 9, 7};        int three[] = { -8, -8, -4, -6, 3, 1, 5, 9, 7};        cout << "one is a permutation of two: " <<            is_permutation(one, end(one), two) << "\n"            "one is a permutation of three: " <<            is_permutation(one, end(one), three, end(three)) << '\n';    }    // Displays: one is a permutation of two: 1    //           one is a permutation of three: 0

19.1.26: is_sorted

• Header file:<algorithm>
• Function prototypes:
  • bool is_sorted([ExecPol,] ForwardIterator first, ForwardIterator last);
  • bool is_sorted([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
• Description:
  • The first prototype: returnstrue if the elements in theiterator range[first, last), are sorted using the elements'operator< comparison operator.
  • The second prototype: returnstrue if the elements in theiterator range[first, last), are sorted using the binary predicatepred.
• Example:

      #include <algorithm>    #include <vector>    #include <iostream>    using namespace std;    int main()    {        vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};        cout << "sorted before: " <<                is_sorted(uv.begin(), uv.end()) << '\n';        sort(uv.begin(), uv.end());        cout << "sorted after " <<                is_sorted(uv.begin(), uv.end()) << '\n';    }    // Displays:    //    sorted before: 0    //    sorted after 1

19.1.27: is_sorted_until

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator is_sorted_until([ExecPol,] ForwardIterator first, ForwardIterator last);
  • ForwardIterator is_sorted_until([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
• Description:
  • The first prototype: returns an iterator to the end of range,starting atfirst whose elements are sorted using the elements'operator< comparison operator.
  • The second prototype: returns an iterator to the end ofrange, starting atfirst whose elements using the binary predicatepred.
  The functions return at leastfirst + 1.
• Example:

      #include <algorithm>    #include <vector>    #include <iostream>    using namespace std;    int main()    {        vector<int> uv = { 1, -2, 3, -4, 5, -6, 7, -8, 9};        cout << "sorted before: " <<                is_sorted(uv.begin(), uv.end()) << '\n';        sort(uv.begin(), uv.end());        cout << "sorted after " <<                is_sorted(uv.begin(), uv.end()) << '\n';    }    // Displays:    //    sorted before: 0    //    sorted after 1

19.1.28: iter_swap

• Header file:<algorithm>
• Function prototype:
  • void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2);
• Description:
  • The elements pointed to byiter1 anditer2 are swapped.
• Example:

      #include <algorithm>    #include <iterator>    #include <iostream>    #include <string>    using namespace std;    int main()    {        string first[] = { "alpha", "bravo", "charley" };        string second[] = { "echo", "foxtrot", "golf" };        cout << "Before:\n";        copy(first, first + 3, ostream_iterator<string>(cout, " "));        cout << '\n';        copy(second, second + 3, ostream_iterator<string>(cout, " "));        cout << '\n';        for (size_t idx = 0; idx != 3; ++idx)            iter_swap(first + idx, second + idx);        cout << "After:\n";        copy(first, first + 3, ostream_iterator<string>(cout, " "));        cout << '\n';        copy(second, second + 3, ostream_iterator<string>(cout, " "));        cout << '\n';    }    //  Displays:    //      Before:    //      alpha bravo charley    //      echo foxtrot golf    //      After:    //      echo foxtrot golf    //      alpha bravo charley

19.1.29: lexicographical_compare

• Header file:<algorithm>
• Function prototypes:
  • bool lexicographical_compare([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
  • bool lexicographical_compare([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Comparecomp);
• Description:
  • The first prototype: the corresponding pairs of elements inthe ranges pointed to by the ranges[first1, last1) and[first2,last2) are compared. The function returnstrue
    • at the first element in the first range which is lessthan the corresponding element in the second range (usingoperator<of the underlying data type),
    • iflast1 is reached, butlast2 isn't reached yet.
    False is returned in the other cases, which indicates that the first sequenceis not lexicographically less than the second sequence. So,false isreturned:
    • at the first element in the first range which is greaterthan the corresponding element in the second range (usingoperator<of the data type to which the iterators point, reversing the operands),
    • iflast2 is reached, butlast1 isn't reached yet,
    • iflast1 andlast2 are reached.
  • The second prototype: with this function the binarycomparison operation as defined bycomp is used instead ofoperator< of the data type to which the iterators point.
• Example:

      #include <algorithm>    #include <iterator>    #include <iostream>    #include <string>    #include <cstring>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) < 0;    }    void compare(string const &word1, string const &word2)    {        cout << '`' << word1 << "' is " <<            (                lexicographical_compare(word1.begin(), word1.end(),                                        word2.begin(), word2.end()) ?                    "before `" : "beyond or at `"            ) <<            word2 << "' in the alphabet\n";    }    int main()    {        string word1 = "hello";        string word2 = "help";        compare(word1, word2);        compare(word1, word1);        compare(word2, word1);        string one[] = {"alpha", "bravo", "charley"};        string two[] = {"ALPHA", "BRAVO", "DELTA"};        copy(one, one + 3, ostream_iterator<string>{ cout, " " });        cout << " is ordered " <<            (                lexicographical_compare(one, one + 3,                                        two, two + 3, caseString) ?                    "before " : "beyond or at "            );        copy(two, two + 3, ostream_iterator<string>{ cout, " " });        cout << "\n"            "using case-insensitive comparisons.\n";    }    //   Displays:    //      `hello' is before `help' in the alphabet    //      `hello' is beyond or at `hello' in the alphabet    //      `help' is beyond or at `hello' in the alphabet    //      alpha bravo charley  is ordered before ALPHA BRAVO DELTA    //      using case-insensitive comparisons.

19.1.30: lower_bound

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value);
  • ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value, BinaryPredicate pred);
• Description:
  • The first prototype: the sorted elements (using ascendingsort) reached from the iterator range[first, last) are searched forthe first element that is not less than (i.e., greater than or equal to)value. The returned iterator marks the location in the sequence wherevalue can be inserted without breaking the sorted order of theelements. Theoperator< of the data type to which the iterators point isused. If no such element is found,last is returned.
  • The second prototype: the elements reached from the iteratorrange[first, last) must have been sorted using thecomp function(-object). Each element in the range is compared tovalue using thecomp function, receiving an element from the iterator range as its firstargument andtype as its second argument. An iterator to the first elementfor which the binary predicatecomp, applied to the elements of the rangeandvalue, returnsfalse is returned. If no such element is found,last is returned.

    As illustrated by the following example, the function objectfunction's first parameter refers to an element in the iterator range, whilethe function object's second parameter refers tovalue.

• Example:

      #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

Thebinary_search generic algorithm (cf. section19.1.7)can be usedto determine whether or notvalue is present in the iterator range. Theupper_bound algorithm can be used to find the last element of a series ofvalues equal tovalue. Theupper_bound section (19.1.61) alsocontains an extensive example illustrating the use oflower_bound and asupper_bound.

19.1.31: max / min

• Header file:<algorithm>
• Function prototypes:
  • Type const &max(Type const &one, Type const &two);
  • Type const &max(Type const &one, Type const &two, Comparator comp);
  • Type const &min(Type const &one, Type const &two);
  • Type const &min(Type const &one, Type const &two, Comparator comp);
• Description:
  • The first prototype: the larger of the two elementsoneandtwo is returned, using theoperator> of the data type to whichthe iterators point to determine which element is the larger one.
  • The second prototype:one is returned if the binarypredicatecomp(one, two) returnstrue, otherwisetwo is returned.
  • Prototypes three and four act identically to, respectively,prototypes one and two, usingstd::min instead ofstd::max,returning the smaller of the two arguments.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <cstring>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) <= 0;    }    string const &call(bool first, string const &lhs, string const &rhs)    {        return first? max(lhs, rhs) : min(lhs, rhs);    }    string const &call(bool first, string const &lhs, string const &rhs,                bool (*cmp)(string const &, string const &))    {        return first? max(lhs, rhs, cmp) : min(lhs, rhs, cmp);    }    int main(int argc, char **argv) // no args: use max, else min    {        bool fun = argc == 1;        char const *where = fun ? "last\n" : "first\n";        cout << "Word '" << call(fun, "first", "second") <<                            "' is lexicographically " << where <<                "Word '" << call(fun, "first", "SECOND") <<                            "' is lexicographically " << where <<                "Word '" << call(fun, "first", "SECOND", caseString) <<                            "' is lexicographically " << where;    }    //  Displays when calling without args:    //      Word 'second' is lexicographically last    //      Word 'first' is lexicographically last    //      Word 'SECOND' is lexicographically last    //  and with an argument:    //      Word 'first' is lexicographically first    //      Word 'SECOND' is lexicographically first    //      Word 'first' is lexicographically first

19.1.32: max_element / min_element / minmax_element

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator max_element([ExecPol,] ForwardIterator first, ForwardIterator last);
  • ForwardIterator max_element([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
  • ForwardIterator min_element([ExecPol,] ForwardIterator first, ForwardIterator last);
  • ForwardIterator min_element([ExecPol,] ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

  • pair<ForwardIterator, ForwardIterator> max_element([ExecPol,] ForwardIterator first,ForwardIterator last);
  • pair<ForwardIterator, ForwardIterator> max_element([ExecPol,] ForwardIterator first,ForwardIterator last, BinaryPredicate pred);
• Description:
  • The first prototype: an iterator pointing to the largestelement reached from the iterator range[first, last) is returned. Theoperator< of the data type to which the iterators point is used to decidewhich of the elements is the largest.
  • The second prototype: rather than usingoperator<, thebinary predicatepred is used to make the comparisons between the elementsreached from the iterator range[first, last). The element for whichpred returns most oftentrue, compared with other elements, isreturned.
  • Prototypes three and four act identically to, respectively,prototypes one and two, usingstd::min_element instead ofstd::max_element, returning iterators to the smallest elements in the iterator ranges[first, last).
  • The final two prototypes act identically to, respectively,prototypes one and two, but returnstd::pair objects whosefirstmembers contain the iterators returned by themin generic algorithms andwhosesecond members contain the iterators returned by themax genericalgorithms.
• Example:

      #include <algorithm>    #include <iostream>    using namespace std;    bool absCompare(int first, int second)    {        return abs(first) < abs(second);    };    int *maxMin(bool high, int *begin, int *end)    {        return high ? max_element(begin, end) : min_element(begin, end);    }    int *maxMin(bool high, int *begin, int *end, bool (*comp)(int, int))    {        return high ? max_element(begin, end, comp)                    : min_element(begin, end, comp);    }                // no args: calls max_element, else min_element    int main(int argc, char **argv)    {        bool max = argc == 1;        char const *type = max? "max" : "min";        int     ia[] = {-4, 7, -2, 10, -12};        cout << "The " << type << ". int value is " <<                *maxMin(max, ia, ia + 5) << "\n"                "The max. absolute int value is " <<                *maxMin(max, ia, ia + 5, absCompare) << '\n';    }    //  Displays, when called without arguments:    //      The max. int value is 10    //      The max. absolute int value is -12    //  otherwise:    //      The minimum int value is -12    //      The minimum absolute int value is -2

19.1.33: merge

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator merge([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator merge([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
• Description:
  • The first prototype: the two (sorted) ranges[first1,last1) and[first2, last2) are merged, keeping a sorted list (using theoperator< of the data type to which the iterators point). The finalseries is stored in the range starting atresult and ending just beforetheOutputIterator returned by the function.
  • The second prototype: the two (sorted) ranges[first1,last1) and[first2, last2) are merged, keeping a sorted list (using theboolean result of the binary comparison operatorcomp). The final seriesis stored in the range starting atresult and ending just before theOutputIterator returned by the function.
• Example:

      #include <algorithm>    #include <string>    #include <cstring>    #include <iterator>    #include <iostream>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) < 0;    }    int main()    {        string range1[] =                           // 5 elements                { "alpha", "bravo", "foxtrot", "hotel", "zulu" };        string range2[] =                           // 4 elements                { "delta", "echo", "golf", "romeo" };        string result[5 + 4];        copy(result,            merge(range1, range1 + 5, range2, range2 + 4, result),            ostream_iterator<string>{ cout, " " });        cout << '\n';        string range3[] =                { "ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU" };        string range4[] = { "delta", "ECHO", "GOLF", "romeo" };        copy(result,            merge(range3, range3 + 5, range4, range4 + 4, result,                                                    caseString),            ostream_iterator<string>{ cout, " " });        cout << '\n';    }    //  Displays:    //      alpha bravo delta echo foxtrot golf hotel romeo zulu    //      ALPHA bravo delta ECHO foxtrot GOLF HOTEL romeo ZULU

19.1.34: minmax

• Header file:<algorithm>
• Function prototypes:
  • pair<Type const &, Type const &> minmax( Type const &t1, Type const &t2);
  • pair<Type const &, Type const &> minmax(Type const &t1, Type const &t2, BinaryPred pred);
  • pair<Type const &, Type const &> minmax( std:initializer<list<Type> values);
  • pair<Type const &, Type const &> minmax( std:initializer<list<Type> values, BinaryPred pred);
• Description:
  • The first prototype: return astd::pair whosefirstandsecond members contain, respectively, the smaller and the larger valueof the function's arguments, usingType's operator< to compare the twovalues.
  • The second prototype: identical to the first prototype, butdeciding thatt1 is the smaller element ifpred(t1, t2) returnstrue.
  • Prototypes three and four act identically to, respectively,prototypes one and two, but return, the smallest and largest values found inthe providediterator_range objects.
• Example:

      #include <algorithm>    #include <iostream>    #include <functional>    using namespace std;    int main()    {        vector<size_t> uv(10);        auto values = minmax(5, 2, less<int>{});        cout << values.first << " is smaler than " << values.second << '\n';    }    // Displays:   2 is smaler than 5

19.1.35: mismatch

• Header file:<algorithm>
• Function prototypes:
  • pair<InputIterator1, InputIterator2> mismatch([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
  • pair<InputIterator1, InputIterator2> mismatch([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, Compare comp);
• Description:
  • The first prototype: the two sequences of elements startingatfirst1 andfirst2 are compared using the equality operator of thedata type to which the iterators point. Comparison stops if the comparedelements differ (i.e.,operator== returns false) orlast1 isreached. Apair containing iterators pointing to the final positions isreturned. The second sequence may contain more elements than the firstsequence. The behavior of the algorithm is undefined if the second sequencecontains fewer elements than the first sequence.
  • The second prototype: the two sequences of elements startingatfirst1 andfirst2 are compared using the binary comparisonoperation as defined bycomp, instead ofoperator==. Comparison stops if thecomp function returnsfalseorlast1 is reached. Apair containing iterators pointing to the finalpositions is returned. The second sequence may contain more elements than thefirst sequence. The behavior of the algorithm is undefined if the secondsequence contains fewer elements than the first sequence.
• Example:

      #include <algorithm>    #include <string>    #include <cstring>    #include <iostream>    #include <utility>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) == 0;    }    int main()    {        string range1[] = { "alpha", "bravo", "foxtrot", "hotel", "zulu" };        string range2[] = { "alpha", "bravo", "foxtrot", "Hotel", "zulu" };        pair<string *, string *> pss = mismatch(range1, range1 + 5, range2);        cout << "The elements " << *pss.first << " and " << *pss.second <<                " differ at index " << (pss.first - range1) << '\n';        if        (            mismatch(range1, range1 + 5, range2, caseString).first            ==            range1 + 5        )            cout << "When compared case-insensitively they match\n";    }    /*        Displays:            The elements hotel and Hotel at offset 3 differ            When compared case-insensitively they match    */

19.1.36: move / move_backward

• Header file:<algorithm>
• Function prototype:
  • OutputIter move([ExecPol,] InputIter first, InputIter last, OutputIter dest);
  • BidirIter move_backward(BidirIter first, BidirIter last, BidirIter lastDest);
• Description:
  • The first prototype: all elements reached from the iteratorrange[first, last) are moved to the range starting atdest,returning the iterator pointing just past the last element in the rangestarting atdest.
  • The Second prototype: all elements reached from the iteratorrange[first, last) are moved in reverse order to the range starting,iterating backward, atlastDest, returning the iterator pointing to thebeginning of the rangeending atlastDest. The destination iteratorlastDest may not point to elements within the range[first, last).
  Followingmove(_backward) the elements in the iterator range[first, last) are still valid, but may have changed.

  See alsoshift_left andshift_right: (cppreference).

• Example:

      #include <algorithm>    #include <string>    #include <iostream>    #include <iterator>    using namespace std;    void show(string const *begin, string const *end)    {        copy(begin, end, ostream_iterator<string>(cout, ", "));        cout << '\n';    }    int main()    {        string sarr[] = { "alpha", "bravo", "charley", "delta" };        string dest[4] = { "", };        auto last = end(sarr);        auto lastDest = move(sarr, last, dest); // move all elements to dest        cout << "sarr after move:\n";        show(sarr, last);        cout << "dest after move:\n";        show(dest, lastDest);        move_backward(dest, lastDest, last); // move_backward to sarr        cout << "sarr after move_backward:\n";        show(sarr, last);        cout << "dest after move_backward:\n";        show(dest, lastDest);    }    //  Displays:    //    sarr after move:    //    , , , ,    //    dest after move:    //    alpha, bravo, charley, delta,

19.1.37: next_permutation / prev_permutation

• Header file:<algorithm>
• Function prototypes:
  • bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
  • bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);
  • bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
  • bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);
• Description:
  • The first prototype: the next permutation, given the sequenceof elements in the range[first, last), is determined. For example, ifthe elements1, 2 and3 are the range for whichnext_permutationis called, then subsequent calls ofnext_permutation reorders thefollowing 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 newpermutation represents the next bigger value (132 is bigger than 123, 213 isbigger than 132, etc.) usingoperator< of the data type to which theiterators point. The valuetrue is returned if a reordering took place,the valuefalse is returned if no reordering took place, which is the caseif the sequence represents the last (biggest) value. In that case, thesequence is also sorted usingoperator<.

  • The second prototype: the next permutation given the sequence ofelements in the range[first, last) is determined, using the binarypredicatecomp to compare elements. The elements in the range arereordered. The valuetrue is returned if a reordering took place, thevaluefalse is returned if no reordering took place, which is the case ifthe resulting sequence would haven been ordered using the binary predicatecomp to compare elements.
  • The final two prototypes act identically to the first twoprototypes, but instead of determining the next permutation the previouspermutation is computed.
• Example:

      #include <algorithm>    #include <iterator>    #include <iostream>    #include <string>    #include <cstring>    using namespace std;    bool caseString(string const &first, string const &second)    {        return strcasecmp(first.c_str(), second.c_str()) < 0;    }    // to obtain previous permutations change 'next_' to 'prev_'    int main()    {        string saints[] = {"Oh", "when", "the", "saints"};        cout << "All permutations of 'Oh when the saints':\n"                "Sequences:\n";        do        {            copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });            cout << '\n';        }        while (next_permutation(saints, saints + 4, caseString));        cout << "After first sorting the sequence:\n";        sort(saints, saints + 4, caseString);        cout << "Sequences:\n";        do        {            copy(saints, saints + 4, ostream_iterator<string>{ cout, " " });            cout << '\n';        }        while (next_permutation(saints, saints + 4, caseString));    }    //  Displays (partially):    //      All permutations of 'Oh when the saints':    //      Sequences:    //      Oh when the saints    //      saints Oh the when    //      saints Oh when the    //      saints the Oh when    //      ...    //      After first sorting the sequence:    //      Sequences:    //      Oh saints the when    //      Oh saints when the    //      Oh the saints when    //      Oh the when saints    //      ...

19.1.38: nth_element

• Header file:<algorithm>
• Function prototypes:
  • void nth_element([ExecPol,] RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
  • void nth_element([ExecPol,] RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
• Description:
  • The first prototype: all elements in the range[first,last) are sorted relative to the element pointed to bynth: all elementsin the range[left, nth) are smaller than the element pointed to bynth, and alle elements in the range[nth + 1, last) are greaterthan the element pointed to bynth. The two subsets themselves are notsorted. Theoperator< of the data type to which the iterators point isused to compare the elements.
  • The second prototype: all elements in the range[first,last) are sorted relative to the element pointed to bynth: all elementsin the range[left, nth) are smaller than the element pointed to bynth, and alle elements in the range[nth + 1, last) are greaterthan the element pointed to bynth. The two subsets themselves are notsorted. Thecomp function object is used to compare the elements.
• Example:

      #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

19.1.39: partial_sort / partial_sort_copy

• Header file:<algorithm>
• Function prototypes:
  • void partial_sort([ExecPol,] RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end);
  • void partial_sort([ExecPol,] RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, BinaryPredicate pred);

  • void partial_sort_copy([ExecPol,] InputIterator begin, InputIterator end, RandomAccessIterator dest_begin, RandomAccessIterator dest_end);
  • void partial_sort_copy([ExecPol,] InputIterator begin, InputIterator end, RandomAccessIterator dest_begin, RandomAccessIterator dest_end, BinaryPredicate pred);
• Description:
  • The first prototype: the (middle - begin) smallestelements are sorted and stored in the range[begin, middle) using theoperator< of the data type to which the iterators point to compareelements. The remaining elements of the series remain unsorted, and are storedin the range[middle, end).
  • The second prototype: the (middle - begin) smallestelements (according to the provided binary predicatepred) are sorted andstored in the range[begin, middle). The remaining elements of theseries remain unsorted.
  • The last two prototypes act like, respectively, the first twoprototypes, but instead of reordering the elements in the source iteratorrange the selected elements are copied to the destination iterator range. Thenumber of elements that are copies is the smaller of the number ofsource-iterators and the number of destination iterators.
• Example:

      #include <algorithm>    #include <iostream>    #include <functional>    #include <iterator>    using namespace std;    int main()    {        int ia[] = { 1, 9, 5, 3, 7, 2, 4, 6, 8, 10 };        int ia2[6];        partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);        cout << "the 6 smallest elements: ";        copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));        cout << '\n';        partial_sort(ia, ia + 3, ia + 10);        cout << "find the 3 smallest elements:\n";        copy(ia, ia + 3, ostream_iterator<int>(cout, " "));        cout << '\n';        cout << "find the 5 largest elements:\n";        partial_sort(ia, ia + 5, ia + 10, greater<int>());        copy(ia, ia + 5, ostream_iterator<int>(cout, " "));        cout << '\n';    }    //  Displays:    //      the 6 smallest elements: 1 2 3 4 5 6    //      find the 3 smallest elements:    //      1 2 3    //      find the 5 biggest elements:    //      10 9 8 7 6

19.1.40: partial_sum

• Header file:<numeric>
• Function prototypes:
  • OutputIterator partial_sum(InputIterator first,InputIterator last, OutputIterator result);
  • OutputIterator partial_sum(InputIterator first, InputIteratorlast, OutputIterator result, BinaryOperation op);
• Description:
  • The first prototype: each element in the range[result, <returned OutputIterator>) receives a value which is obtainedby adding the elements in the corresponding range of the range[first,last). The first element in the resulting range will be equal to the elementpointed to byfirst.
  • The second prototype: the value of each element in the range[result, <returned OutputIterator>) is obtained by applying the binaryoperatorop to the previous element in the resulting range and thecorresponding element in the range[first, last). The firstelement in the resulting range will be equal to the element pointed to byfirst.
  See alsoinclusive_scan andexclusive_scan, supporting execution policies: (cppreference).
• Example:

      #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    */

19.1.41: partition / partition_point / stable_partition

• Header file:<algorithm>
• Function prototype:
  • BidirectionalIterator partition([ExecPol,] BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
  • BidirectionalIterator stable_partition([ExecPol,]BidirectionalIterator first, BidirectionalIterator last, UnaryPredicatepred);
  • ForwardIterator partition_point( ForwardIterator first, ForwardIterator last, UnaryPredicate pred );
• Description:
  • The first prototype: all elements in the range[first,last) for which the unary predicatepred evaluates astrue are placedbefore the elements which evaluate asfalse.
  • The second prototype: identical to the first prototype, butthe relative order of all elements for which the predicate evaluates tofalse and the relative order of all elements for which the predicateevaluates totrue is kept.
  • The third prototype: does not reorder the elements in the[first, last) range, but returns an iterator to the first element forwhichpred returnsfalse. Ifpred returnstrue for allelements thenlast is returned.
  The return value points just beyond the last element in thepartitioned range for whichpred evaluates astrue.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <iterator>    using namespace std;    void show(int *begin, int *end)    {        copy(begin, end, ostream_iterator<int>{ cout, " " });        cout << '\n';    }    int main()    {        int org[] = { 1, 3, 5, 7, 9, 10, 2, 8, 6, 4 };        int ia[10];        copy(org, org + 10, ia);        auto lessThan4 = [=](int value)                        {                            return value <= 4;                        };        int *split = partition(ia, ia + 10, lessThan4);        cout << "Last ia[]- element <= 4 is ia[" << split - ia - 1 << "]\n";        show(ia, end(ia));        copy(org, org + 10, ia);        split = stable_partition(ia, ia + 10, lessThan4);        cout << "Last org[]-element <= 4 is ia[" << split - ia - 1 << "]\n";        show(ia, end(ia));        cout << "org[]-elements up to the partition point 4 are:\n";        show(org, partition_point(org, org + 10, lessThan4));    }    //  Displays:    //    Last ia[]- element <= 4 is ia[3]    //    1 3 4 2 9 10 7 8 6 5    //    Last org[]-element <= 4 is ia[3]    //    1 3 2 4 5 7 9 10 8 6    //    org[]-elements up to the partition point 4 are:    //    1 3

19.1.42: partition_copy

• Header file:<algorithm>
• Function prototype:
  • std::pair<ForwardIter2, ForwardIter3> partition_copy([ExecPol,] ForwardIter1 first, ForwardIter1 last, ForwardIter2 trueDest, ForwardIter3 falseDest, UnaryPredicate pred );
• Description:
  • All elements reached from the iterator range[first,last) for whichpred returnstrue are copied to the range starting attrueDest, while the remaining elements are copied to the range starting atfalseDest. the range[first, last) may not overlap with the rangesstarting attrueDest orfalseDest.
• Example:

      #include <algorithm>    #include <string>    #include <iostream>    #include <iterator>    using namespace std;    bool pred(std::string const &str)    {        return "aeiou"s.find(str.front()) != string::npos;    }    void show(string const *begin, string const *end)    {        copy(begin, end, ostream_iterator<string>(cout, ", "));        cout << '\n';    }    int main()    {        string sarr[] =            {                "alpha", "bravo", "charley", "delta", "echo",                "foxtrot", "golf", "hotel"            };        string trueDest[size(sarr)];        string falseDest[size(sarr)];        pair<string *, string *> lastTF =   // lastTrue, lastFalse            partition_copy(sarr, end(sarr), trueDest, falseDest, pred);        cout << "pred() == true elements:\n";        show(trueDest, lastTF.first);        cout << "pred() == false elements:\n";        show(falseDest, lastTF.second);    }    //  Displays:    //    pred() == true elements:    //    alpha, echo,    //    pred() == false elements:    //    bravo, charley, delta, foxtrot, golf, hotel,

19.1.43: reduce

• Header file:<numeric>
• Function prototypes:
  • Type reduce([ExecPol,] InputIterator first, InputIterator last);
  • Type reduce([ExecPol,] InputIterator first, InputIterator last, Type init);
  • Type reduce([ExecPol,] InputIterator first, InputIterator last, BinaryOperation op);
  • Type reduce([ExecPol,] InputIterator first, InputIterator last, Type init, BinaryOperation op);
• Description: This algorithm acts likeaccumulate(cf.accumulate), but the algorithm requires that the usedoperator is both associative and commutative: regrouping and rearranging theelements in any order may not affect the final outcome. E.g., the numericaddition operator satisfies both requirements.
  • The first prototype:operator+ is applied to the elements inthe range[first, last), returning the resulting sum.
  • The second prototype: the binary operatorop is applied tothe initial valueinit (lhs argument) and, respectively, the elements fromthe iterator range[first, last). The resulting sum value is returned.
  • The last two prototypes act like, respectively, the first twoprototypes but instead of usingoperator+ the binary operatorop isused, receiving the variable that's eventually returned from the function asits lhs argument and the elements in the iterator range as its rhs argument,assigning the operator's returned values to the variable that's eventuallyreturned.
• Example:

      // compile as: g++ -O2 reduce.cc -ltbb    #include <numeric>    #include <vector>    #include <execution>    #include <iostream>    using namespace std;    int main()    {        int         ia[] = {1, 2, 3, 4};        vector<int> iv(ia, ia + 4);                            // for demonstration purpose: it's unlikely that        cout <<             // for 4 values parallel execution is used            "Sum: " << reduce(execution::par,                        iv.begin(), iv.end(), int()) << "\n"            "Product: " << reduce(iv.begin(), iv.end(), int(1),                                            multiplies<int>{}) << '\n';    }    //  Displays:    //      Sum: 10    //      Product: 24

19.1.44: remove / remove_if / remove_copy / remove_copy_if

• Header file:<algorithm>
• Function prototype:
  • ForwardIterator remove([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &value);

  • OutputIterator remove_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator dest, Type const &value);

  • OutputIterator remove_copy_if([ExecPol,] InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred);

  • ForwardIterator remove_if([ExecPol,] ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
• Description:
  • The first prototype: elements in the range pointed to by[first, last) are reordered such that all values unequal tovalueare placed at the beginning of the range. The returned forward iterator pointsto the first element that can be removed after reordering. The range[returnvalue, last) is called theleftover of the algorithm. Notethat the leftover may contain elements different fromvalue, but theseelements can be removed safely, as such elements are also present in the range[first, returnvalue). The function usesoperator== of the data typeto which the iterators point to determine which elements to remove.
  • The second prototype: elements in the range pointed to by[first, last) not matchingvalue are copied to the range[dest, returnvalue), wherereturnvalue is the value returned bythe function. The range[first, last) is not modified. The functionusesoperator== of the data type to which the iterators point to determinewhich elements not to copy.
  • The third prototype: the elements in the range pointed to by[first, last) for which the unary predicatepred returnstrueare not inserted into theresult iterator. All other elements are copiedto the range[dest, returnvalue), wherereturnvalue is the valuereturned by the function. The range[first, last) is not modified.
  • The fourth prototype: the elements in the range pointed to by[first, last) are reordered such that all values for which the unarypredicatepred returnsfalse are placed at the beginning of therange, keeping their relative order. The returned forward iteratorpoints to the first element, after reordering, for whichpred returnedtrue. The range[returnvalue, last) is called theleftover ofthe algorithm. The leftovermay contain elements for which the predicatepred returnsfalse, but these can safely be removed, as such elementsare also present in the range[first, returnvalue). Such duplication isthe result of the fact that the algorithmcopies, rather thanmoveselements into new locations.
  Note that thecopy-overloads expect output iterators. If thekept elements are to be stored in, e.g., a vectorkept thenkept.begin() could be passed as the function'sdest argument. However,that requires thatsize(kept) is large enough to contain all the keptelements, which must therefore be known before the function iscalled. Alternatively,back_insert_iterator could be used ensuring thatkept merely contains the kept elements once the function hasreturned. This approach is used in the example program.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <iterator>    #include <vector>    using namespace std;    using StrVect = vector<string>;    bool judge(string const &word)    {        return count(word.begin(), word.end(), 'a') > 1;    }    void show(auto const &begin, auto const &end)    {        copy(begin, end, ostream_iterator<string>(cout, ", "));        cout << "\n";    }    int main()    {        StrVect words =            {                "kilo", "alpha", "lima", "mike", "alpha", "november",                "alpha", "alpha", "alpha", "papa", "quebec"            };        auto src{ words };        cout << "Removing all \"alpha\"s:\n";        auto end = remove(src.begin(), src.end(), "alpha");        show(src.begin(), end);        cout << "Leftover elements are:\n";        show(end, src.end());        src = words;        cout << "Remove_copy_if removes words having > 1 'a' chars:\n";        StrVect kept;        remove_copy_if(src.begin(), src.end(), back_inserter(kept), judge);        show(kept.begin(), kept.end());    }    //  Displays:    //    Removing all "alpha"s:    //    kilo, lima, mike, november, papa, quebec,    //    Leftover elements are:    //    alpha, alpha, alpha, , ,    //    Remove_copy_if removes words having > 1 'a' chars:    //    kilo, lima, mike, november, quebec,

19.1.45: replace / replace_if / replace_copy / replace_copy_if

• Header file:<algorithm>
• Function prototype:
  • void replace([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &oldvalue, Type const &newvalue);
  • ForwardIterator replace_if([ExecPol,] ForwardIterator first, ForwardIterator last, UnaryPredicate pred, Type const &value);
  • OutputIterator replace_copy([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, Type const &oldvalue, Type const &newvalue);
  • OutputIterator replace_copy_if([ExecPol,] ForwardIterator first, ForwardIterator last, OutputIterator result, UnaryPredicate pred, Type const &value);
• Description:
  • The first predicate: all elements equal tooldvalue inthe range pointed to by[first, last) are replaced by a copy ofnewvalue. The algorithm usesoperator== of the data type to which theiterators point.
  • The second prototype: elements in the range pointed to by[first, last) for which the unary predicatepred evaluates astrue are replaced byvalue.
  • The third prototype: all elements equal tooldvalue inthe range pointed to by[first, last) are sent to theresult outputiterator, replacing elements equal tooldValue bynewValue, usingoperator== of the data type to which the iterators point.
  • The fourth prototype: the elements in the range pointed to by[first, last) for which the unary predicatepred returnsfalseare sent to theresult output iterator, andvalue is sent toresult ifpred returnstrue. The range[first, last) is notmodified.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <vector>    #include <iterator>    using namespace std;    using StrVect = vector<string>;    void show(StrVect const &vect)    {        copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));        cout.put('\n');    }    bool isAlpha(string const &str)    {        return str == "alpha";    }    int main()    {        StrVect words =            {                "kilo", "alpha", "lima", "mike", "alpha", "november",                "alpha", "oscar", "alpha", "alpha", "papa"            };        // replace(words.begin(), words.end(), "alpha"s, "ALPHA"s);        // show(words);        // or, using replace_if:        //        // replace_if(words.begin(), words.end(), isAlpha, "ALPHA"s);        // show(words);        // or, using replace_copy:        //        // StrVect result;        // replace_copy(words.begin(), words.end(), result.begin(),        //              "alpha"s, "ALPHA"s);        // show(result);        // or, using replace_copy_if:        //        //StrVect result;        replace_copy_if(words.begin(), words.end(), back_inserter(result),                     isAlpha, "ALPHA"s);         show(result);    }    /*        Displays            kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa    */

19.1.46: reverse / reverse_copy

• Header file:<algorithm>
• Function prototype:
  • void reverse([ExecPol,] BidirectionalIterator first, BidirectionalIterator last);
  • OutputIterator reverse_copy([ExecPol,] BidirectionalIterator first, BidirectionalIterator last, OutputIterator dest);
• Description:
  • The first prototype: the order of the elements in the rangepointed to by[first, last) are reversed.
  • The second prototype: elements in the range pointed to by[first, last) are inserted in reversed order intodest, returningthe output iterator following the last insertion.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <vector>    #include <iterator>    using namespace std;    using StrVect = vector<string>;    void show(StrVect const &vect)    {        copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));        cout.put('\n');    }    int main(int argc, char **argv)    {        StrVect words =            {                "alpha", "kilo", "lima", "mike",                "november", "oscar", "papa"            };        if (argc == 1)          // no args: plain reverse        {            reverse(words.begin(), words.end());            show(words);            return 0;        }        using StrVect = vector<string>;        StrVect dest;        reverse_copy(words.begin(), words.end(),                     back_inserter(dest));        show(dest);    }    // Displays:    //    papa oscar november mike lima kilo alpha

19.1.47: rotate / rotate_copy

• Header file:<algorithm>
• Function prototype:
  • void rotate([ExecPol,] ForwardIterator first, ForwardIterator middle, ForwardIterator last);
  • OutputIterator rotate_copy([ExecPol,] ForwardIterator first,ForwardIterator middle, ForwardIterator last, OutputIterator result);
• Description:
  • The first prototype: elements in the range[first,middle) are moved to the end of the container, the elements in the range[middle, last) are moved to the beginning of the container, keeping theorder of the elements in the two sub-ranges intact.
  • The elements in the range[middle, last) andthen the elements in the range[first, middle) are inserted intoresult, returning the output iterator following the last insertion.The order of the elements in the source ranges is not altered.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <iterator>    #include <vector>    using namespace std;    using StrVect = vector<string>;    void show(StrVect const &vect)    {        copy(vect.begin(), vect.end(), ostream_iterator<string>(cout, " "));        cout.put('\n');    }    int main(int argc, char **argv)    {        StrVect words =            {                "kilo", "lima", "mike", "november", "oscar",                "foxtrot", "golf", "hotel", "india", "juliet"            };        if (argc == 1)          // no args: plain rotate        {            rotate(words.begin(), words.begin() + words.size() / 2,                   words.end());            show(words);            return 0;        }        using StrVect = vector<string>;        StrVect dest;        rotate_copy(words.begin(), words.begin() + words.size() / 2,                    words.end(), back_inserter(dest));        show(dest);    }    //  Displays:    //      foxtrot golf hotel india juliet kilo lima mike november oscar

19.1.48: sample

• Header file:<algorithm>
• Function prototype:
  • OutputIterator sample(InputIterator first, InputIterator last, OutputIterator out, size_t sampleSize, Generator &&generator);
• Description:
  • sampleSize elements are randomly selected (withoutreplacement) from the input range[first, last), and copied to thedestination range starting atout and ending at the function's returnvalue. IfsampleSize >= (last - first) all elements are selected. Thegenerator is a (uniform) random number generator, like themt19937mercenne twister.
  See alsoshuffle: (cppreference).

• Example:

      #include <algorithm>    #include <iostream>    #include <random>    #include <string>    using namespace std;    int main()    {        string src{ "abcdefghijklmnopqrstuvwxyz" };        string dest;        sample(src.begin(), src.end(), back_inserter(dest), 7, mt19937{});        std::cout << "Seven random letters out of " << src << " : " <<                                                       dest << '\n';    }    //  Could display:    //    Seven random letters out of abcdefghijklmnopqrstuvwxyz : bciorux

19.1.49: search / search_n

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator search([ExecPol,] ForwardIterator first1,ForwardIterator last1, ForwardIterator first2, ForwardIterator last2);
  • ForwardIterator1 search([ExecPol,] ForwardIterator first1,ForwardIterator last1, ForwardIterator first2, ForwardIterator last2,BinaryPredicate pred);
  • constexpr ForwardIterator1 search([ExecPol,] ForwardIterator first, ForwardIterator last, Searcher const &searcher);

  • ForwardIterator search_n([ExecPol,] ForwardIterator first,ForwardIterator last, Size count, Type const &value);
  • ForwardIterator search_n([ExecPol,] ForwardIterator first1,ForwardIterator last1, Size count, Type const &value, BinaryPredicate pred);

• Description:
  • The first prototype: an iterator into the first range[first1, last1) is returned where the elements in the range[first2, last2) are found usingoperator== of the datatype to which the iterators point. If no such location exists,last1 isreturned.
  • The second prototype: an iterator into the first range[first1, last1) is returned where the elements in the range[first2, last2) are found using the provided binary predicatepredto compare the elements in the two ranges. If no such location exists,last1 is returned.
  • The third prototype: returnssearcher(first, last).first:searcher receives the range of elements, and returns an iterator into thisrange (orlast ifsearcher found no match) assearcher(first,last).first.
  • The final two prototypes inspect the elements in the range[first, last) for the first series ofcount elements equal tovalue, returning the first iterator to thosecount elements. If nosuch series exists thenlast is returned. The last protottype callspred to determine whether an element is equal tovalue.
• Example:

      #include <algorithm>    #include <iostream>    #include <iterator>    using namespace std;    bool absEq(int i1, int i2)    {        return abs(i1) == abs(i2);    }    int main()    {        int range1[] =  {-2, -4, -6, -8, 2, 4, 4, 6, 8};        int range2[] =  {6, 8};        copy        (            search(range1, end(range1), range2, range2 + 2),            end(range1), ostream_iterator<int>(cout, " ")        );        cout << '\n';        copy        (            search(range1, end(range1), range2, range2 + 2, absEq),            end(range1), ostream_iterator<int>(cout, " ")        );        cout << '\n';        copy        (            search_n(range1, end(range1), 2, 4, absEq),            end(range1), ostream_iterator<int>(cout, " ")        );        cout << '\n';    }    //  Displays:    //      6 8    //      -6 -8 2 4 4 6 8    //      4 4 6 8

19.1.50: set_difference

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator set_difference([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,OutputIterator result);
  • OutputIterator set_difference([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);
• Description:
  • The first prototype: a sorted sequence of the elementspointed to by the range[first1, last1) that are not present in therange[first2, last2) is returned, starting atresult, and endingat theOutputIterator returned by the function. The elements in the tworanges must have been sorted usingoperator< of the data type to whichthe iterators point.
  • The second prototype: a sorted sequence of the elementspointed to by the range[first1, last1) that are not present in therange[first2, last2) is returned, starting atresult, and endingat theOutputIterator returned by the function. The elements in the tworanges must have been sorted using thecomp function object.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <cstring>    #include <iterator>    using namespace std;    bool caseless(string const &left, string const &right)    {        return strcasecmp(left.c_str(), right.c_str()) < 0;    }    int main()    {        string set1[] = { "kilo", "lima", "mike", "november",                          "oscar", "papa", "quebec" };        string set2[] = { "papa", "quebec", "romeo"};        string result[7];        copy(result,            set_difference(set1, set1 + 7, set2, set2 + 3, result),            ostream_iterator<string>(cout, " "));        cout << '\n';        string set3[] = { "PAPA", "QUEBEC", "ROMEO"};        copy(result,            set_difference(set1, set1 + 7, set3, set3 + 3, result,            caseless),            ostream_iterator<string>(cout, " "));        cout << '\n';    }    //  Displays:    //      kilo lima mike november oscar    //      kilo lima mike november oscar

19.1.51: set_intersection

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator set_intersection([ExecPol,] InputIterator1 first1, InputIterator1) linebreak() tt(last1, InputIterator2first2, InputIterator2 last2, OutputIterator result);
  • OutputIterator set_intersection([ExecPol,] InputIterator1first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);
• Description:
  • The first prototype: a sorted sequence of the elementspointed to by the range[first1, last1) that are also present in therange[first2, last2) is returned, starting atresult, and endingat theOutputIterator returned by the function. The elements in the tworanges must have been sorted usingoperator< of the data type to whichthe iterators point.
  • The second prototype: a sorted sequence of the elementspointed to by the range[first1, last1) that are also present in therange[first2, last2) is returned, starting atresult, and endingat theOutputIterator returned by the function. The elements in the tworanges must have been sorted using thecomp function object.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <cstring>    #include <iterator>    using namespace std;    bool caseless(string const &left, string const &right)    {        return strcasecmp(left.c_str(), right.c_str()) < 0;    }    int main()    {        string set1[] = { "kilo", "lima", "mike", "november",                          "oscar", "papa", "quebec" };        string set2[] = { "papa", "quebec", "romeo"};        string result[7];        copy(result,            set_intersection(set1, set1 + 7, set2, set2 + 3, result),            ostream_iterator<string>(cout, " "));        cout << '\n';        string set3[] = { "PAPA", "QUEBEC", "ROMEO"};        copy(result,            set_intersection(set1, set1 + 7, set3, set3 + 3, result,                                                             caseless),            ostream_iterator<string>(cout, " "));        cout << '\n';    }    //  Displays:    //      papa quebec    //      papa quebec

19.1.52: set_symmetric_difference

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator set_symmetric_difference([ExecPol,]InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,InputIterator2 last2, OutputIterator result);
  • OutputIterator set_symmetric_difference([ExecPol,]InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,InputIterator2 last2, OutputIterator result, Compare comp);
• Description:
  • The first prototype: a sorted sequence of the elementspointed to by the range[first1, last1) that are not present in therange[first2, last2) and those in the range[first2, last2)that are not present in the range[first1, last1) is returned, startingatresult, and ending at theOutputIterator returned by thefunction. The elements in the two ranges must have been sorted usingoperator< of the data type to which the iterators point.
  • The second prototype: a sorted sequence of the elementspointed to by the range[first1, last1) that are not present in therange[first2, last2) and those in the range[first2, last2)that are not present in the range[first1, last1) is returned, startingatresult, and ending at theOutputIterator returned by thefunction. The elements in the two ranges must have been sorted using thecomp function object.
• Example:

      #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

19.1.53: set_union

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator set_union([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,OutputIterator result);
  • OutputIterator set_union([ExecPol,] InputIterator1 first1,InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);
• Description:
  • The first prototype: a sorted sequence of the elements thatare present in either the range[first1, last1) or the range[first2, last2) or in both ranges is returned, starting atresult,and ending at theOutputIterator returned by the function. The elements inthe two ranges must have been sorted usingoperator< of the data type towhich the iterators point;
  • The second prototype: a sorted sequence of the elements thatare present in either the range[first1, last1) or the range[first2, last2) or in both ranges is returned, starting atresult,and ending at theOutputIterator returned by the function. The elements inthe two ranges must have been sorted usingcomp function object.
  Note that in the final range each element appears only once, unless there are already duplicate elements in the sources, in which case they will also appear multiple times in the result;
• Example:

      #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

19.1.54: sort / stable_sort

• Header file:<algorithm>
• Function prototypes:
  • void sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last);
  • void sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • void stable_sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last);
  • void stable_sort([ExecPol,] RandomAccessIterator first, RandomAccessIterator last, Compare comp);
• Description:
  • The first prototype: the elements in the range[first,last) are sorted in ascending order usingoperator< of the data type towhich the iterators point.
  • The second prototype: the elements in the range[first, last) are sorted in ascending order using thecompfunction object to compare the elements. The binary predicatecompshould returntrue if its first argument should be placed earlier in thesorted sequence than its second argument.
  • The last two prototypes are used identically to the first twoprototypes, but use stable-sorting, keeping the initial order of equalelements.
• Example:

      // compile as: g++ -O2 sort.cc -ltbb    #include <algorithm>    #include <cstdlib>    #include <execution>    #include <functional>    #include <iostream>    #include <iterator>    #include <string>    using namespace std;    int main()    {        string words[] =                {                    "november", "kilo", "mike", "lima",                    "oscar", "quebec", "papa"                };        sort(words, words + 7);        copy(words, words + 7, ostream_iterator<string>(cout, " "));        cout << '\n';        sort(words, words + 7, greater<string>());        copy(words, words + 7, ostream_iterator<string>(cout, " "));        cout << '\n';        int *vect = new int[10'000];        generate(execution::par, vect, vect + 10'000, random);        cout << "sorted: " << is_sorted(vect, vect + 10'000) << '\n';        sort(execution::par, vect, vect + 10'000);        cout << "sorted: " << is_sorted(vect, vect + 10'000) << '\n';        delete[] vect;        // stable-sorting:        using Pair = pair<size_t, string>;  // days & nrs of the months        vector<Pair> months =        {            { 31, "Jan." }, { 28, "Feb." }, { 31, "Mar." }, { 30, "Apr." },            { 31, "May." }, { 30, "Jun." }, { 31, "Jul." }, { 31, "Aug." },            { 30, "Sep." }, { 31, "Oct." }, { 30, "Nov." }, { 31, "Dec." },        };        stable_sort(months.begin(), months.end(),                    [&](Pair const &lhs, Pair const &rhs)                    {                        return lhs.first > rhs.first;                    }        );        for (size_t idx = 0; auto const &month: months)            cout << month.first << ": " << month.second <<                (++idx % 4 == 0 ? "\n" : "  ");    }    //  Displays:    //      kilo lima mike november oscar papa quebec    //      quebec papa oscar november mike lima kilo    //      unordered sequence    //      sorted sequence    //      31: Jan.  31: Mar.  31: May.  31: Jul.    //      31: Aug.  31: Oct.  31: Dec.  30: Apr.    //      30: Jun.  30: Sep.  30: Nov.  28: Feb.

  The example also shows two generic algorithms using theexecution::par execution policy: firstgenerate is used to fill anarray with randomly determinedint-values, thensort is used to sortthose values.

19.1.55: swap / swap_ranges

• Header file:<algorithm>
• Function prototypes:
  • void swap(Type &object1, Type &object2) noexcept;
  • void swap(Type (&object1)[N], Type (&object2))[N] noexcept;
  • ForwardIterator2 swap_ranges([ExecPol,] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result);
• Description:
  • The first prototype: the elementsobject1 andobject2exchange their values. They do so by either cyclic copy assignment or cyclicmove assignment (if available).
  • The second prototype: the elements of the (compile-time) knownsizes of theobject1 andobject2 arrays exchange their values.
  • The third prototype: elements in the range pointed to by[first1, last1) are swapped with that number of elements in the range[result, returnvalue), wherereturnvalue is the value returned bythe function. The two ranges must be disjoint.
• Example:

      #include <algorithm>    #include <iostream>    #include <string>    #include <iterator>    using namespace std;    void show(string const *begin, string const *end)    {        copy(begin, end, ostream_iterator<string>(cout, " "));        cout << '\n';    }    int main()    {        string first[] = { "alpha", "bravo", "charley" };        string second[] = { "echo", "foxtrot", "golf" };        cout << "Before:\n";        show(first, end(first));        show(second, end(second));        for (size_t idx = 0; idx < size(first); ++idx)            swap(first[idx], second[idx]);        cout << "After:\n";        show(first, end(first));        show(second, end(second));        swap_ranges(first, end(first), second);        cout << "After swap_ranges:\n";        show(first, end(first));        show(second, end(second));    }    //  Displays:    //    Before:    //    alpha bravo charley    //    echo foxtrot golf    //    After:    //    echo foxtrot golf    //    alpha bravo charley    //    After swap_ranges:    //    alpha bravo charley    //    echo foxtrot golf

19.1.56: transform

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator transform([ExecPol,] InputIterator first, InputIterator last, OutputIterator result, UnaryOperator op);
  • OutputIterator transform([ExecPol,] InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result,BinaryOperator op);
• Description:
  • The first prototype: the unary operatorop is applied toeach of the elements in the range[first, last), and the resultingvalues are stored in the range starting atresult. The return value pointsjust beyond the last generated element.
  • The second prototype: the binary operatorop is appliedto each of the elements in the range[first1, last1) and thecorresponding element in the second range starting atfirst2. Theresulting values are stored in the range starting atresult. The returnvalue points just beyond the last generated element.
• Example:

      #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    */

• Withtransform thereturn value of the functionobject'soperator() member is used; the argument that is passed to theoperator() member itself is not changed.
• Withfor_each the function object'soperator()receives a reference to an argument, which itself may be changed by thefunction object'soperator().

19.1.57: transform_reduce

• Header file:<numeric>
• Function prototypes:
  • Type transform_reduce([ExecPol,] InputIterator first1, InputIterator last1, InputIterator first2, Type value);

  • Type transform_reduce([ExecPol,] InputIterator first1, InputIterator last1, InputIterator first2, Type value, BinaryOperation reduce, BinaryOperation transform);

  • Type transform_reduce([ExecPol,] InputIterator first1, InputIterator last1, Type value, BinaryOperation reduce, UnaryOperation transform);
• Description:
  • The first prototype: equals the second prototype usingstd::plus<> for thereduce binary operator andstd::mutiplies<>for thetransform binary operator. It's also equivalent to a parallelizedversion ofinner_product (cf. section19.1.21).
  • The second prototype: applies thetransform binaryoperation to, as left-hand side operand, each element in the[first1,end1) range and as right-hand side operand the corresponding element of therange starting atfirst2. Each thus computed value is passed as right-handside operand, usingvalue as left-hand side operand to thereducebinary operation, returning the final value returned byreduce.
  • The third prototype: appliestransform to each element ofthe range[first1, end1), and then passesvalue and each of thevalues returned bytransform toreduce, returning the final valuereturned byreduce.

• Example:

      #include <numeric>    #include <algorithm>    #include <iterator>    #include <iostream>    #include <string>    using namespace std;    class Cat    {        std::string  d_sep;        public:            Cat(string const &sep)            :                d_sep(sep)            {}            string operator()                (string const &s1, string const &s2) const            {                return s1 + d_sep + s2;            }    };    int main()    {        size_t ia1[] = { 1, 2, 3, 4, 5, 6, 7 };                    // instead of inner_product:        cout << "The sum of all squares in ";        copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });        cout << "is " << transform_reduce(ia1, ia1 + 7, ia1, 0) << '\n';        size_t ia2[] = { 7, 6, 5, 4, 3, 2, 1 };        cout << "The sum of all cross-products in ";        copy(ia1, ia1 + 7, ostream_iterator<size_t>{ cout, " " });        cout << "and ";        copy(ia2, ia2 + 7, ostream_iterator<size_t>{ cout, " " });        cout << "is " << transform_reduce(ia1, ia1 + 7, ia2, 0) << '\n';        string names1[] = { "Frank", "Karel", "Piet" };        string names2[] = { "Brokken", "Kubat", "Plomp"};        cout << "All combined names of ";        copy(names1, names1 + 3, ostream_iterator<string>{ cout, " " });        cout << "and ";        copy(names2, names2 + 3, ostream_iterator<string>{ cout, " " });        cout << "are:" <<            transform_reduce(names1, names1 + 3, names2, "\t"s,                Cat{ "\n\t"}, Cat{ " " }) << '\n';    }    // Displays:    //  The sum of all squares in 1 2 3 4 5 6 7 is 140    //  The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84    //  All combined names of Frank Karel Piet and Brokken Kubat Plomp are:    //          Frank Brokken    //          Karel Kubat    //          Piet Plomp

19.1.58: handling uninitialized memory

As covered before, when calling something likeauto ptr = new string{"hello" } the string is constructed in memory specifically allocated tocontain the object, and the object type's constructor initializes the objectin that memory. Likewise, when callingdelete ptr the string's destructoris called, followed by returning the memory allocated bynew to the commonpool.

When using placement new the memory to contain the object is alreadyavailable, and the constructionauto ptr = new (storageAddress) string{"hello" } is used to merely construct the string at the location specified bystorageAddress. That string can then (as usual) be accessed viaptr,butdelete ptr cannot be used, since the memory atstorageAddress wasalready available before invoking the placement new operator. Therefore, inthese cases the remarkable situation is encountered where the object'sdestructor must explicitly be called (usingptr->~string()) and usingdelete ptr is completely wrong, causing a memory error which aborts theprogram.

Several generic algorithms, all supporting execution policies, are availablesimplifying the use ofplacement new. To use these algorithm the<memory> header file must be included.

Facilities are available to copy, fill, initialize, and move objects to/inuninitialized (raw) memory, as well as facilities to delete the objects storedin raw memory. Here is an overvieuw of the available facilities (cf.cppreference for more detailsabout the algorithms handling uninitialized memory):

• uninitialized_copy([ExecPol,] ForwardIterator first, ForwardIterator last, ForwardIterator dest);
  copies the elements in the[first, last) to the raw memory starting atdest, returning the location beyond the last copied element.
• uninitialized_copy_n([ExecPol,] ForwardIterator first, size_t nObjects, ForwardIterator dest);
  same as the previous algorithm, but copiesnObjects.
• uninitialized_default_construct([ExecPol,] ForwardIterator first, ForwardIterator last);
  installs default constructed values at the raw memory locations reached by the iterator range[first, last). The algorithm requires that the types referred to by the iterators are either trivial types (like built-in types) or definevalue_type returning their type names. When using trivial types the installed do not assume that the installed values are 0-initialized.
• uninitialized_default_construct_n([ExecPol,] ForwardIterator first, size_t nObjects);
  same as the previous algorithm, but installsnObjects in the uninitialized memory.
• uninitialized_fill([ExecPol,] ForwardIterator first, ForwardIterator last, Type const &value);
  like the first algorithm, but installing copies ofvalue in the uninitialized memory.
• uninitialized_fill([ExecPol,] ForwardIterator first, size_t nObjects,Type const &value);
  same as the previous algorithm, but copiesvalue to thenObjects subsequent locations in the uninitialized memory.
• uninitialized_move([ExecPol,] ForwardIterator first, ForwardIterator last, ForwardIterator dest);
  same as the first algorithm, but the elements in the[first, last) are moved to the raw memory.
• uninitialized_move_n([ExecPol,] ForwardIterator first, size_t nObjects, ForwardIterator dest);
  same as the previous algorithm, butnObjects are moved.
• uninitialized_value_construct([ExecPol,] ForwardIterator first, ForwardIterator last);
  same asuninitialized_default_construct, but requires that the types referred to by the iterators definevalue_type returning their type names.
• uninitialized_value_construct_n([ExecPol,] ForwardIterator first, size_t nObjects);
  same as the previous algorithm, but installsnObjects in the uninitialized memory.

The algorithmType *construct_at(Type *raw, Args&&...args) constructs an object of typeType in the raw memory atraw, passingargs... toType's constructor.

To delete the objects installed in raw memory the following facilities areavailable:

• void destroy([ExecPol,] ForwardIterator first, ForwardIterator last);
  assuming the the types to whichfirst refers: it callsiterator->~Type() for all elements in the range[first, last).
• void destroy([ExecPol,] ForwardIterator first, size_t nObjects);
  same as the previous algorithm, but calls the destructors ofnObjects objects.
• void destroy_at(Type *raw);
  calls the destructor of the object installed atraw using placement new. If theraw pointer points to an array of placement new allocated objects then the destructors of the elements of the array are called.

Here is an example:

    #include <memory>    #include <vector>    #include <iostream>    #include <string>    using namespace std;    int main()    {        char raw[4 * sizeof(string)];       // raw memory to receive strings        string *ptr = reinterpret_cast<string *>(raw);  // pointer to strings                                            // construct 4 strings in raw        uninitialized_default_construct_n(ptr, 4);        destroy(ptr, ptr + 4);              // call the strings' destructors        vector<string> vs(4, "string");     // move 4 strings to raw memory        uninitialized_move(vs.begin(), vs.end(), ptr);        cout << vs.front() << ", " << vs.back() << '\n' <<                ptr[0] << ", " << ptr[3] << '\n';        destroy(ptr, ptr + 4);              // call the strings' destructors    }    //  Displays:    //      ,    //      string, string

19.1.59: unique

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator unique([ExecPol,] ForwardIterator first,ForwardIterator last);
  • ForwardIterator unique([ExecPol,] ForwardIterator first,ForwardIterator last, BinaryPredicate pred);
  • OutputIterator unique_copy([ExecPol,] InputIterator first,InputIterator last, OutputIterator result);
  • OutputIterator unique_copy([ExecPol,] InputIterator first,InputIterator last, OutputIterator result, BinaryPredicate pred);
• Description:
  Thestd::unique generic algorithm assumes that the elements in therange have previously been sorted (cf. section19.1.54).
  • The first prototype: usingoperator== of the data type towhich the iterators point, all but the first of consecutively equal elementsin the range pointed to by[first, last) are relocated to the end ofthe range. The returned forward iterator marks the beginning of theleftover. All elements in the range[first, return-value) areunique, all elements in the range[return-value, last) haveundetermined (but valid) values.
  • The second prototype: all but the first of consecutiveelements in the range pointed to by[first, last) for which the binarypredicatepred returnstrue are relocated to the end of the range. Thepredicatepred expects two arguments of the data type to which theiterators point. The returned forward iterator marks the beginning of theleftover. For all pairs of elements in the range[first,return-value)pred returnsfalse (i.e., they areunique). Allelements in theleftover (i.e., the range[return-value, last))have undetermined (but valid) values.
• Example:

      #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    */

19.1.60: unique_copy

• Header file:<algorithm>
• Function prototypes:
  • OutputIterator unique_copy([ExecPol,] InputIterator first,InputIterator last, OutputIterator result);
  • OutputIterator unique_copy([ExecPol,] InputIterator first,InputIterator last, OutputIterator result, BinaryPredicate pred);
• Description:
  • The first prototype: the elements in the range[first,last) are copied to the resulting container, starting atresult.Consecutively equal elements (usingoperator== of the data type to whichthe iterators point) are copied only once (keeping the first of a series ofequal elements). The returned output iterator pointsjust beyond the last copied element.
  • The second prototype: the elements in the range[first, last) are copied to the resulting container, starting atresult. Consecutive elements in the range pointed to by[first,last) for which the binary predicatepred returnstrue are copied onlyonce (keeping the first of a series of equal elements). The returned outputiterator points just beyond the last copied element.
• Example:

      #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    */

19.1.61: upper_bound

• Header file:<algorithm>
• Function prototypes:
  • ForwardIterator upper_bound(ForwardIterator first,ForwardIterator last, Type const &value);
  • ForwardIterator upper_bound(ForwardIterator first,ForwardIterator last, Type const &value, Compare comp);
• Description:

  • The first prototype: the sorted elements (using ascending sort)reached from the iterator range[first, last) are searched for the firstelement that is greater thanvalue. The returned iterator marks the firstlocation in the sequence wherevalue can be inserted without breaking thesorted order of the elements usingoperator< of the data type to which theiterators point. If no such element is found,last is returned.

  • The second prototype: the elements reached from the iteratorrange[first, last) must have been sorted using thecomp functionor function object. Each element in the range is compared tovalue usingthecomp function. An iterator is returned pointing to the first elementfor which the binary predicatecomp, applied to the elements of the rangeandvalue, returnstrue. Thecomp function object function'sfirst parameter refers tovalue and the function object's second parameterrefers to an element in the iterator range.

    Caveat: note that thecomp object's parameters when usingupper_bound are swapped compared to the parameters expected bylower_bound.

  • When the values in the iterator range were sorted in ascendingorder (i.e., usingoperator<) thenupper_bound returns an iteratorpointing beyond the last of a series of values equal tovalue, whilelower_bound returns an iterator pointing to the first of such a series ofequal values.

    When the iterator range contains a series of values which are, according tocomp, equal tovalue thenupper_bound returns an iterator to thefirst element beyond that series, whilelower_bound returns an iterator tothe first element of that series.

    The following program illustrates the various possibilities. Th programillustrates bothlower_bound andupper_bound and also illustrates thesituation wherevalue' Type is unequal to the types of the values in theiterator range. Specific comment is provided below the program's code.

• Example:

   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 end89: //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

  • Lines 7 thru 12: the iterator range consists of a series ofpairs, sorted by theirfirst members.
  • Lines 18 thru 23:lower_bound is called using a lambda expression to define theCompare 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.
  • Lines 27 thru 32: hereupper_bound is called, also using a lambda expression. Withupper_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.
  • Lines 57 thru 62, 66 thru 71, and 75 thru 80: after sorting the values in thepicArr array in descending orderlower_bound andupper_bound are again used. This time instead of using the< operator the> operator should be used.

Thebinary_search generic algorithm can be used to simplydetermine whether or nogvalue is present in the iterator range. Thelower_bound generic algorithm can be used to find the firstelement of a series of values equal tovalue.

19.1.62: Heap algorithms

        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 pointernode indicates the location of the next node of the tree, apointerchild points to the next element which is a child of thenodepointer. Initially,node points to the first element, andchild pointsto the second element.

• *node++ (== 12). 12 is the top node. its children are*child++(11) and*child++ (10), both less than 12.
• The next node (*node++ (== 11)), in turn, has*child++ (8)and*child++ (9) as its children.
• The next node (*node++ (== 10)) has*child++ (7)and*child++ (6) as its children.
• The next node (*node++ (== 8)) has*child++ (1)and*child++ (2) as its children.
• Then, node (*node++ (== 9)) has children*child++ (4)and*child++ (3).
• Finally (as far as children are concerned) (*node++ (== 7)) hasone child*child++ (5)

Note that the left and right branches are not ordered: 8 is less than 9, but 7is larger than 6.

A heap is created by traversing a binary tree level-wise, starting from thetop node. The top node is 12, at the zeroth level. At the first level we find11 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 isnot an appropriate data structure for a heap. Heaps can be constructed from an(unsorted) array (usingmake_heap). The top-element canbe pruned from a heap, followed by reordering the heap (usingpop_heap), a new element can be added to the heap,followed by reordering the heap (usingpush_heap), andthe elements in a heap can be sorted (usingsort_heap,which, of course, invalidates the heap).

19.1.62.1: The `make_heap' function

• Header file:<algorithm>
• Function prototypes:
  • void make_heap(RandomAccessIterator first,RandomAccessIterator last);
  • void make_heap(RandomAccessIterator first,RandomAccessIterator last, Compare comp);
• Description:
  • The first prototype: the elements in the range[first,last) are reordered to form amax-heap usingoperator< of the datatype to which the iterators point.
  • The second prototype: the elements in the range[first,last) are reordered to form a max-heap using the binary comparison functionobjectcomp to compare elements.
• Follow this link for a smallexample of a programusingmake_heap.

19.1.62.2: The `pop_heap' function

• Header file:<algorithm>
• Function prototypes:
  • void pop_heap(RandomAccessIterator first,RandomAccessIterator last);
  • void pop_heap(RandomAccessIterator first,RandomAccessIterator last, Compare comp);
• Description:
  • The first prototype: the first element in the range[first, last) is moved tolast - 1. Then, the elements in the range[first, last - 1) are reordered to form a max-heap using theoperator< of the data type to which the iterators point.
  • The second prototype: the first element in the range[first, last) is moved tolast - 1. Then, the elements in the range[first, last - 1) are reordered to form a max-heap using the binarycomparison function objectcomp to compare elements.
• Follow this link for a smallexample of a programusingpop_heap.

19.1.62.3: The `push_heap' function

• Header file:<algorithm>
• Function prototypes:
  • void push_heap(RandomAccessIterator first,RandomAccessIterator last);
  • void push_heap(RandomAccessIterator first,RandomAccessIterator last, Compare comp);
• Description:
  • The first prototype: assuming that the range[first,last - 1) contains a valid heap, and the element atlast - 1 contains anelement to be added to the heap, the elements in the range[first, last- 1) are reordered to form a max-heap using theoperator< of the datatype to which the iterators point.
  • The second prototype: assuming that the range[first,last - 1) contains a valid heap, and the element atlast - 1 contains anelement 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 functionobjectcomp to compare elements.
• Follow this link for a smallexample of a programusingpush_heap.

19.1.62.4: The `sort_heap' function

• Header file:<algorithm>
• Function prototypes:
  • void sort_heap(RandomAccessIterator first,RandomAccessIterator last);
  • void sort_heap(RandomAccessIterator first,RandomAccessIterator last, Compare comp);
• Description:
  • The first prototype: assuming the elements in the range[first, last) form a valid max-heap, the elements in the range[first, last) are sorted usingoperator< of the data type towhich the iterators point.
  • The second prototype: assuming the elements in the range[first, last) form a valid heap, the elements in the range[first, last) are sorted using the binary comparison functionobjectcomp to compare elements.
• Follow this link for a smallexample of a programusingsort_heap.

19.1.62.5: An example using the heap functions

    #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    */

• Table of Contents
• Previous Chapter
• Next Chapter