______________________________________________________________________25 Algorithms library [lib.algorithms]______________________________________________________________________1 This clause describes components that C++ programs may use to perform algorithmic operations on containers (_lib.containers_) and other sequences. 2 The following subclauses describe components for non-mutating sequence operation (_lib.alg.nonmutating_), mutating sequence operations (_lib.alg.mutating.operations_), and sorting and related operations (_lib.alg.sorting_). 3 Headers: --<stl algorithms (TBD)>--<cstdlib>(partial) 4 Table 1:Table 1--Header<stl algorithms (TBD)>synopsis+-----------------------------------------------------------+ |Type Name(s)| +-----------------------------------------------------------+ |Template functions:| |adjacent_find [2] prev_permutation [2]| |binary_search [2] push_heap [2]| |copy random_shuffle [2]| |copy_backward remove| |count remove_copy| |count_if remove_copy_if| |equal [2] remove_if| |equal_range [2] replace| |fill replace_copy| |fill_n replace_copy_if| |find replace_if| |find_if reverse| |for_each reverse_copy| |generate rotate| |generate_n rotate_copy| |includes [2] search [2]| |inplace_merge [2] set_difference [2]| |lexicographical_compare [2] set_intersection [2]| |lower_bound [2] set_symmetric_difference [2]| |make_heap [2] set_union [2]| |max [2] sort [2]| |max_element [2] sort_heap [2]| |merge [2] stable_partition| |min [2] stable_sort [2]| |min_element [2] swap| |mismatch [2] swap_ranges| |next_permutation [2] transform [2]| |nth_element [2] unique [2]| |partial_sort [2] unique_copy [2]| |partial_sort_copy [2] upper_bound [2]| |partition| |pop_heap [2]| +-----------------------------------------------------------+ 5Table 2:Table 2--Header<cstdlib>synopsis+-----------------------------+ |Type Name(s)| +-----------------------------+ |Functions: bsearch qsort| +-----------------------------+SEE ALSO:ISO C subclause 7.10.5. 6 All of the algorithms are separated from the particular implementa tions of data structures and are parameterized by iterator types. Because of this, they can work with user defined data structures, as long as these data structures have iterator types satisfying the assumptions on the algorithms. 7 Both in-place and copying versions are provided for certain algo rithms. The decision whether to include a copying version was usually based on complexity considerations. When the cost of doing the opera tion dominates the cost of copy, the copying version is not included. For example,sort_copyis not included since the cost of sorting is much more significant, and users might as well docopyfollowed bysort. When such a version is provided foralgorithmit is calledalgorithm_copy. Algorithms that take predicates end with the suffix_if(which follows the suffix_copy). 8 ThePredicateclass is used whenever an algorithm expects a function object that when applied to the result of dereferencing the corre sponding iterator returns a value testable astrue. In other words, if an algorithm takesPredicate predas its argument andfirstas its iterator argument, it should work correctly in the constructif(pred(*first)){...}. The function objectpredis assumed not to apply any non-constant function through the dereferenced iterator. 9 TheBinaryPredicateclass is used whenever an algorithm expects a function object that when applied to the result of dereferencing two corresponding iterators or to dereferencing an iterator and typeTwhenTis part of the signature returns a value testable astrue. In other words, if an algorithm takesBinaryPredicate binary_predas its argument andfirst1andfirst2as its iterator arguments, it should work correctly in the constructif (pred(*first, *first2)){...}.BinaryPredicatealways takes the first iterator type as its first argument, that is, in those cases whenT valueis part of the signa ture, it should work correctly in the context ofif (pred(*first,value)){...}. It is expected thatbinary_predwill not apply any non- constant function through the dereferenced iterators. 10In the description of the algorithms operators+and-are used for some of the iterator categories for which they do not have to be defined. In these cases the semantics ofa+nis the same is that of{ X tmp = a;advance(tmp, n);return tmp;}and that ofa-bis the same as of{ Distance n;distance(a, b, n);return n;}+------- BEGIN BOX 1 -------+ For the following algorithms:reverse,rotate,random_shuffle,partition,stable_partition,sort,stable_sortandinplace_mergethe itera tor requirement can be relaxed toForwardIterator. These algorithms could then be dispatched upon the iterator category tags to use the most efficient implementation for each iterator category. We have not included the relaxation at this stage since it is not yet fully imple mented. +------- END BOX 1 -------+25.1 Non-mutating sequence operations[lib.alg.nonmutating]25.1.1 For each[lib.alg.foreach]template <class InputIterator, class Function>void for_each(InputIterator first, InputIterator last, Function f);1 Appliesfto the result of dereferencing every iterator in the range[first, last).fshall not apply any non-constant function through the dereferenced iterator. 2 Complexity:fis applied exactlylast - firsttimes. 3 Notes: Iffreturns aresult, the result is ignored.25.1.2 Find[lib.alg.find]template <class InputIterator, class T>InputIterator find(InputIterator first, InputIterator last, const T& value);template <class InputIterator, class Predicate>InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);1 Returns the first iteratoriin the range[first, last)for which the following corresponding conditions hold:*i == value, pred(*i) ==true. Returnslastif no such iterator is found. 2 Complexity: At mostlast - firstapplications of the corresponding predicate are done.25.1.3 Adjacent find[lib.alg.adjacent.find]template <class InputIterator>InputIterator adjacent_find(InputIterator first, InputIterator last);template <class InputIterator, class BinaryPredicate>InputIterator adjacent_find(InputIterator first, InputIterator last,BinaryPredicate pred);1 Returns the first iteratorisuch that bothiandi + 1are in the range[first, last)for which the following corresponding conditions hold:*i == *(i + 1), pred(*i, *(i + 1)) == true. Returnslastif no such iterator is found. 2 Complexity: At mostmax((last - first) - 1, 0)applications of the corresponding predicate are done.25.1.4 Count[lib.alg.count]template <class InputIterator, class T, class Size>void count(InputIterator first, InputIterator last, const T& value, Size& n);template <class InputIterator, class Predicate, class Size>void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);1 Adds tonthe number of iteratorsiin the range[first, last)for which the following corresponding conditions hold:*i == value,pred(*i) == true. 2 Complexity: Exactlylast - firstapplications of the corresponding predicate are done. 3 Notes:countmust store the result into a reference argument instead of returning the result because the size type cannot be deduced from built-in iterator types such asint*.25.1.5 Mismatch[lib.mismatch]template <class InputIterator1, class InputIterator2>pair<InputIterator1, InputIterator2>mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);template <class InputIterator1, class InputIterator2, class BinaryPredicate>pair<InputIterator1, InputIterator2>mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,BinaryPredicate pred);1 Returns a pair of iteratorsiandjsuch thatj == first2 + (i -first1)andiis the first iterator in the range[first1, last1)for which the following corresponding conditions hold:!(*i == *(first2 +(i - first1))), pred(*i, *(first2 + (i - first1))) == false. Returns the pairlast1andfirst2 + (last1 - first1)if such an iteratoriis not found. 2 Complexity: At mostlast1 - first1applications of the corresponding predicate are done.25.1.6 Equal[lib.alg.equal]template <class InputIterator1, class InputIterator2>bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);template <class InputIterator1, class InputIterator2, class BinaryPredicate>bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,BinaryPredicate pred);1 Returnstrueif for every iteratoriin the range[first1, last1)the following corresponding conditions hold:*i == *(first2 + (i -first1)), pred(*i, *(first2 + (i - first1))) == true. Otherwise, returnsfalse. 2 Complexity: At mostlast1 - first1applications of the corresponding predicate are done.25.1.7 Search[lib.alg.search]template <class ForwardIterator1, class ForwardIterator2>ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2);template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2,BinaryPredicate pred);1 Finds a subsequence of equal values in a sequence. 2 Returns the first iteratoriin the range[first1, last1 - (last2 -first2))such that for any non-negative integernless thanlast2 -first2the following corresponding conditions hold:*(i + n) ==*(first2 + n), pred(*(i + n), *(first2 + n)) == true. Returnslast1if no such iterator is found.1)25.2 Mutating sequence operations[lib.alg.mutating.operations]25.2.1 Copy[lib.alg.copy]25.2.1.1copy [lib.copy]template <class InputIterator, class OutputIterator>OutputIterator copy(InputIterator first, InputIterator last,OutputIterator result);_________________________ 1) The Knuth-Morris-Pratt algorithm is not used here. While the KMP algorithm guarantees linear time, it tends to be slower in most prac tical cases than the naive algorithm with worst-case quadratic behav ior. The worst case is extremely unlikely. We expect that most im plementations will provide a specialization:char* search(char* first1, char* last1, char* first2, char* last2);3 that will use a variation of the Boyer-Moore algorithm for fast string searching. 1 Copies elements. For each non-negative integern < (last - first),*(result + n) = *(first + n)is performed.copyreturnsresult +(last - first). 2resultshall not be in the range[first, last). 3 Complexity: Exactlylast - firstassignments are done.25.2.1.2copy_backward [lib.copy.backward]template <class BidirectionalIterator1, class BidirectionalIterator2>BidirectionalIterator2copy_backward(BidirectionalIterator1 first,BidirectionalIterator1 last, BidirectionalIterator2 result);1 Copies elements in therange [first, last)into the range[result -(last - first), result)starting fromlast - 1and proceeding tofirst.2) For each positive integern <= (last - first),*(result - n)= *(last - n)is performed. 2resultshall not be in the range[first, last). 3 Returnsresult - (last - first). 4 Complexity: Exactlylast - firstassignments are done.25.2.2 Swap[lib.alg.swap]25.2.2.1swap [lib.swap]template <class T>void swap(T& a, T& b);1 Exchanges values stored in two locations.25.2.2.2swap_ranges [lib.swap.ranges]template <class ForwardIterator1, class ForwardIterator2>ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2);1 For each non-negative integern < (last1 - first1)the swap is per formed:swap(*(first1 + n), *(first2 + n)). 2 The two ranges[first1, last1)and[first2, first2 + (last1 - first1))shall not overlap. 3 Returnsfirst2 + (last1 - first1). 4 Complexity: Exactlylast1 - first1swaps are done. _________________________ 2)copy_backward(_lib.copy.backward_) should be used instead of copy whenlastis in the range[result - (last - first), result).25.2.3 Transform[lib.alg.transform]template <class InputIterator, class OutputIterator, class UnaryOperation>OutputIterator transform(InputIterator first, InputIterator last,OutputIterator result, UnaryOperation op);template <class InputIterator1, class InputIterator2, class OutputIterator,class BinaryOperation>OutputIterator transform(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, OutputIterator result,BinaryOperation binary_op);1 Assigns through every iteratoriin the range[result, result + (last1- first1))a new corresponding value equal toop(*(first1 + (i -result))orbinary_op(*(first1 + (i - result), *(first2 + (i -result))). 2opandbinary_opshall not have any side effects. 3 Returnsresult + (last1 - first1). 4 Complexity: Exactlylast1 - first1applications ofoporbinary_opare performed. 5 Notes:resultmay be equal tofirstin case of unary transform, or tofirst1orfirst2in case of binary transform.25.2.4 Replace[lib.alg.replace]25.2.4.1replace [lib.replace]template <class ForwardIterator, class T>void replace(ForwardIterator first, ForwardIterator last, const T& old_value,const T& new_value);template <class ForwardIterator, class Predicate, class T>void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,const T& new_value);1 Substitutes elements referred by the iteratoriin the range[first,last)withnew_value, when the following corresponding conditions hold:*i == old_value, pred(*i) == true. 2 Complexity: Exactlylast - firstapplications of the corresponding predicate are done.25.2.4.2replace_copy [lib.replace.copy]template <class InputIterator, class OutputIterator, class T>OutputIterator replace_copy(InputIterator first, InputIterator last,OutputIterator result,const T& old_value, const T& new_value);template <class Iterator, class OutputIterator, class Predicate, class T>OutputIterator replace_copy_if(Iterator first, Iterator last,OutputIterator result,Predicate pred, const T& new_value);1 Assigns to every iteratoriin the range[result, result + (last -first))eithernew_valueor*(first + (i - result))depending on whether the following corresponding conditions hold:*(first + (i -result)) == old_value, pred(*(first + (i - result))) == true. 2 Returnsresult + (last - first). 3 Complexity: Exactlylast - firstapplications of the corresponding predicate are done.25.2.5 Fill[lib.alg.fill]template <class ForwardIterator, class T>void fill(ForwardIterator first, ForwardIterator last, const T& value);template <class OutputIterator, class Size, class T>void fill_n(OutputIterator first, Size n, const T& value);1 Assigns value through all the iterators in the range[first, last)or[first, first + n). 2 Complexity: Exactlylast - first(orn) assignments are done.25.2.6 Generate[lib.alg.generate]template <class ForwardIterator, class Generator>void generate(ForwardIterator first, ForwardIterator last, Generator gen);template <class OutputIterator, class Size, class Generator>void generate_n(OutputIterator first, Size n, Generator gen);1 Invokes the function object gen and assigns the return value ofgenthough all the iterators in the range[first, last)or[first, first +n).gentakes no arguments. 2 Complexity: Exactlylast - first(orn) invocations ofgenand assign ments are done.25.2.7 Remove[lib.alg.remove]25.2.7.1remove [lib.remove]template <class ForwardIterator, class T>ForwardIterator remove(ForwardIterator first, ForwardIterator last,const T& value);template <class ForwardIterator, class Predicate>ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,Predicate pred);1 Eliminates all the elements referred to by iteratoriin the range[first, last)for which the following corresponding conditions hold:*i == value, pred(*i) == true. 2 Returns the end of the resulting range.removeis stable, that is, the relative order of the elements that are not removed is the same as their relative order in the original range. 3 Complexity: Exactlylast - firstapplications of the corresponding predicate are done.25.2.7.2remove_copy [lib.remove.copy]template <class InputIterator, class OutputIterator, class T>OutputIterator remove_copy(InputIterator first, InputIterator last,OutputIterator result, const T& value);template <class InputIterator, class OutputIterator, class Predicate>OutputIterator remove_copy_if(InputIterator first, InputIterator last,OutputIterator result, Predicate pred);1 Copies all the elements referred to by the iteratoriin the range[first, last)for which the following corresponding conditions do not hold:*i == value, pred(*i) == true. 2 Returns the end of the resulting range. 3 Complexity: Exactlylast - firstapplications of the corresponding predicate are done. 4 Notes:remove_copyis stable, that is, the relative order of the ele ments in the resulting range is the same as their relative order in the original range.25.2.8 Unique[lib.alg.unique]25.2.8.1unique [lib.unique]template <class ForwardIterator>ForwardIterator unique(ForwardIterator first, ForwardIterator last);template <class ForwardIterator, class BinaryPredicate>ForwardIterator unique(ForwardIterator first, ForwardIterator last,BinaryPredicate pred);1 Eliminates all but the first element from every consecutive group of equal elements referred to by the iteratoriin the range[first,last)for which the following corresponding conditions hold:*i == *(i- 1)orpred(*i, *(i - 1)) == true. 2 Returns the end of the resulting range. 3 Complexity: Exactly(last - first) - 1applications of the correspond ing predicate are done.25.2.8.2unique_copy [lib.unique.copy]template <class InputIterator, class OutputIterator>OutputIterator unique_copy(InputIterator first, InputIterator last,OutputIterator result);template <class InputIterator, class OutputIterator, class BinaryPredicate>OutputIterator unique_copy(InputIterator first, InputIterator last,OutputIterator result, BinaryPredicate pred);1 Copies only the first element from every consecutive group of equal elements referred to by the iteratoriin the range[first, last)for which the following corresponding conditions hold:*i == *(i - 1)orpred(*i, *(i - 1)) == true. 2 Returns the end of the resulting range. 3 Complexity: Exactlylast - firstapplications of the corresponding predicate are done.25.2.9 Reverse[lib.alg.reverse]25.2.9.1reverse [lib.reverse]template <class BidirectionalIterator>void reverse(BidirectionalIterator first, BidirectionalIterator last);1 For each non-negative integeri <= (last - first)/2,reverseappliesswapto all pairs of iteratorsfirst + i, (last - i) - 1. 2 Complexity: Exactly(last - first)/2swaps are performed.25.2.9.2reverse_copy [lib.reverse.copy]template <class BidirectionalIterator, class OutputIterator>OutputIterator reverse_copy(BidirectionalIterator first,BidirectionalIterator last, OutputIterator result);1 Copies the range [first, last) to the range [result, result + (last -first)) such that for any non-negative integer i < (last - first) thefollowing assignment takes place: *(result + (last - first) - i) =*(first + i).2The ranges [first, last) and [result, result + (last - first)) shallnot overlap.3Returns result + (last - first).4Complexity: Exactly last - first assignments are done.25.2.10 Rotate[lib.alg.rotate]25.2.10.1rotate [lib.rotate]template <class BidirectionalIterator>void rotate(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last);1 For each non-negative integeri < (last - first),rotateplaces the element from the positionfirst + iinto positionfirst + (i + (middle- first)) % (last - first). 2 Complexity: At mostlast - firstswaps are done.25.2.10.2rotate_copy [lib.rotate.copy]template <class ForwardIterator, class OutputIterator>OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,ForwardIterator last, OutputIterator result);1 Copies the range[first, last)to the range[result, result + (last -first))such that for each non-negative integeri < (last - first)the following assignment takes place:*(first + i) = *(result + (i + (middle - first)) % (last - first)).rotate_copyreturnsresult + (last -first). 2 The ranges[first, last)and[result, result + (last - first))shall not overlap. 3 Complexity: Exactlylast - firstassignments are done.25.2.11 Random shuffle[lib.alg.random.shuffle]template <class RandomAccessIterator>void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class RandomNumberGenerator>void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,RandomNumberGenerator& rand);1 Shuffles the elements in the range[first, last)with uniform distri bution. 2 Complexity: Exactly(last - first) - 1swaps are done. 3 Notes:random_shufflecan take a particular random number generating function objectrandsuch thatrandreturns a randomly chosendoublein the interval[0, 1).25.2.12 Partitions[lib.alg.partitions]25.2.12.1partition [lib.partition]template <class BidirectionalIterator, class Predicate>BidirectionalIterator partition(BidirectionalIterator first,BidirectionalIterator last, Predicate pred);1 Places all the elements in the range[first, last)that satisfypredbefore all the elements that do not satisfy it. 2 Returns an iteratorisuch that for any iteratorjin the range[first, i), pred(*j) == true, and for any iteratorkin the range[i,last), pred(*j) == false. 3 Complexity: At most(last - first)/2swaps. Exactlylast - firstapplications of the predicate is done.25.2.12.2stable_partition [lib.stable.partition]template <class BidirectionalIterator, class Predicate>ForwardIterator stable_partition(BidirectionalIterator first,BidirectionalIterator last, Predicate pred);1 Places all the elements in the range[first, last)that satisfy pred before all the elements that do not satisfy it. 2 Returns an iteratorisuch that for any iteratorjin the range[first, i),pred(*j) == true, and for any iteratorkin the range[i,last), pred(*j) == false. The relative order of the elements in both groups is preserved. 3 Complexity: At most(last - first) * log(last - first)swaps, but only linear number of swaps if there is enough extra memory. Exactlylast- firstapplications of the predicate are done.25.3 Sorting and related operations[lib.alg.sorting]1 All the operations in this section have two versions: one that takes a function object of typeCompareand one that uses anoperator<. 2Compareis used as a function object which returnstrueif the first argument is less than the second, andfalseotherwise.Compare compis used throughout for algorithms assuming an ordering relation. It is assumed thatcompwill not apply any non-constant function through the dereferenced iterator. For all algorithms that takeCompare, there is a version that usesoperator<instead. That is,comp(*i, *j)== truedefaults to*i < *j == true. For the algorithms to work cor rectly,comphas to induce a total ordering on the values. 3 A sequence is sorted with respect to a comparatorcompif for any iteratoripointing to the sequence and any non-negative integernsuch thati + nis a valid iterator pointing to an element of the sequence,comp(*(i + n), *i) == false. 4 In the descriptions of the functions that deal with ordering relation ships we frequently use a notion of equality to describe concepts such as stability. The equality to which we refer is not necessarily anoperator==, but an equality relation induced by the total ordering. That is, two elementaandbare considered equal if and only if!(a <b) && !(b < a).25.3.1 Sorting[lib.alg.sort]25.3.1.1sort [lib.sort]template <class RandomAccessIterator>void sort(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);1 Sorts the elements in the range[first, last). 2 Complexity: ApproximatelyNlogN(whereNequals tolast - first) com parisons on the average.3)25.3.1.2stable_sort [lib.stable.sort]template <class RandomAccessIterator>void stable_sort(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void stable_sort(RandomAccessIterator first, RandomAccessIterator last,Compare comp);1 Sorts the elements in the range[first, last). 2 Complexity: It does at mostNlog2N(whereNequals tolast - first) comparisons; if enough extra memory is available, it isNlogN. 3 Notes: Stable, the relative order of the equal elements is preserved.25.3.1.3partial_sort [lib.partial.sort]template <class RandomAccessIterator>void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last, Compare comp);1 Places the firstmiddle - firstsorted elements from the range[first,last)into the range[first, middle). The rest of the elements in the range[middle, last)are placed in an undefined order. 2 Complexity: It takes approximately(last - first) * log(middle -first)comparisons.25.3.1.4partial_sort_copy [lib.partial.sort.copy]template <class InputIterator, class RandomAccessIterator>RandomAccessIteratorpartial_sort_copy(InputIterator first, InputIterator last,RandomAccessIterator result_first, RandomAccessIterator result_last);template <class InputIterator, class RandomAccessIterator, class Compare>RandomAccessIteratorpartial_sort_copy(InputIterator first, InputIterator last,RandomAccessIterator result_first, RandomAccessIterator result_last,Compare comp);1 Places the firstmin(last - first, result_last - result_first)sorted elements into the range[result_first, result_first + min(last -first, result_last - result_first)). _________________________ 3) If the worst case behavior is importantstable_sort(_lib.stable.sort_) orpartial_sort(_lib.partial.sort_) should be used. 2 Returns eitherresult_lastorresult_first + (last - first)whichever is smaller. 3 Complexity: Approximately(last - first) * log(min(last - first,result_last - result_first))comparisons.25.3.2 Nth element[lib.alg.nth.element]template <class RandomAccessIterator>void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last, Compare comp);1 Afternth_elementthe element in the position pointed to bynthis the element that would be in that position if the whole range were sorted. Also for any iteratoriin the range[first, nth)and any iteratorjin the range[nth, last)it holds that!(*i > *j)orcomp(*i, *j) ==false. 2 Complexity: Linear on average.25.3.3 Binary search[lib.alg.binary.search]1 All of the algorithms in this section are versions of binary search. They work on non-random access iterators minimizing the number of com parisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, since these algorithms do a logarithmic number of steps through the data struc ture. For non-random access iterators they execute a linear number of steps.25.3.3.1lower_bound [lib.lower.bound]template <class ForwardIterator, class T>ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,const T& value);template <class ForwardIterator, class T, class Compare>ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,const T& value, Compare comp);1 Finds the first position into which value can be inserted without vio lating the ordering.lower_boundreturns the furthermost iteratoriin the range[first, last)such that for any iteratorjin the range[first, i)the following corresponding conditions hold:*j < valueorcomp(*j, value) == true. 2 Complexity: At mostlog(last - first) + 1comparisons are done.25.3.3.2upper_bound [lib.upper.bound]template <class ForwardIterator, class T>ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,const T& value);template <class ForwardIterator, class T, class Compare>ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,const T& value, Compare comp);1 Finds the furthermost position into which value can be inserted with out violating the ordering.upper_boundreturns the furthermost iter atoriin the range[first, last)such that for any iteratorjin the range[first, i)the following corresponding conditions hold:!(value< *j)orcomp(value, *j) == false. 2 Complexity: At mostlog(last - first) + 1comparisons are done.25.3.3.3equal_range [lib.equal.range]template <class ForwardIterator, class T>pair<ForwardIterator, ForwardIterator>equal_range(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class T, class Compare>pair<ForwardIterator, ForwardIterator>equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);1 Finds the largest subrange[i, j)such that the value can be inserted at any iteratorkin it.ksatisfies the corresponding conditions:!(*k < value) && !(value < *k)orcomp(*k, value) == false &&comp(value, *k) == false. 2 Complexity: At most2 * log(last - first)comparisons are done.25.3.3.4binary_search [lib.binary.search]template <class ForwardIterator, class T>bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class T, class Compare>bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,Compare comp);1 Returnstrueif there is an iteratoriin the range[first last)that satisfies the corresponding conditions:!(*i < value) && !(value < *i)orcomp(*i, value) == false && comp(value, *i) == false. 2 Complexity: At mostlog(last - first) + 1comparisons are done.25.3.4 Merge[lib.alg.merge]25.3.4.1merge [lib.merge]template <class InputIterator1, class InputIterator2, class OutputIterator>OutputIterator merge(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>OutputIterator merge(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);1 Merges two sorted ranges[first1, last1)and[first2, last2)into the range[result, result + (last1 - first1) + (last2 - first2)). 2 The resulting range shall not overlap with either of the original ranges. 3 Returnsresult + (last1 - first1) + (last2 - first2). 4 Complexity: At most(last1 - first1) + (last2 - first2) - 1compar isons are performed. 5 Notes: The merge is stable, that is, for equal elements in the two ranges, the elements from the first range always precede the elements from the second.25.3.4.2inplace_merge [lib.inplace.merge]template <class BidirectionalIterator>void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last);template <class BidirectionalIterator, class Compare>void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last, Compare comp);1 Merges two sorted consecutive ranges[first, middle)and[middle,last)putting the result of the merge into the range[first, last). 2 Complexity: At mostlast - firstcomparisons are performed. If no additional memory is available, the number of assignments can be equal toNlogNwhereNis equal tolast - first. 3 Notes: The merge is stable, that is, for equal elements in the two ranges, the elements from the first range always precede the elements from the second.25.3.5 Set operations on sorted[lib.alg.set.operations]structures1 This section defines all the basic set operations on sorted struc tures. They even work withmultisets containing multiple copies of equal elements. The semantics of the set operations is generalized to multisets in a standard way by defining union to contain the maximum number of occurrences of every element, intersection to contain the minimum, and so on.25.3.5.1includes [lib.includes]template <class InputIterator1, class InputIterator2>bool includes(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2);template <class InputIterator1, class InputIterator2, class Compare>bool includes(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2, Compare comp);1 Returnstrueif every element in the range[first2, last2)is con tained in the range[first1, last1). Returnsfalseotherwise. 2 Complexity: At most((last1 - first1) + (last2 - first2)) * 2 - 1com parisons are performed.25.3.5.2set_union [lib.set.union]template <class InputIterator1, class InputIterator2, class OutputIterator>OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);1 Constructs a sorted union of the elements from the two ranges. 2 The resulting range shall not overlap with either of the original ranges. 3 Returns the end of the constructed range. 4 Complexity: At most((last1 - first1) + (last2 - first2)) * 2 - 1com parisons are performed. 5 Notes:set_unionis stable, that is, if an element is present in both ranges, the one from the first range is copied.25.3.5.3set_intersection [lib.set.intersection]template <class InputIterator1, class InputIterator2, class OutputIterator>OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);1 Constructs a sorted intersection of the elements from the two ranges. 2 The resulting range shall not overlap with either of the original ranges. 3 Returns the end of the constructed range. 4 Complexity: At most((last1 - first1) + (last2 - first2)) * 2 - 1com parisons are performed. 5 Notes: Stable, that is, if an element is present in both ranges, the one from the first range is copied.25.3.5.4set_difference [lib.set.difference]template <class InputIterator1, class InputIterator2, class OutputIterator>OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);1 Constructs a sorted difference of the elements from the two ranges. 2 The resulting range shall not overlap with either of the original ranges. 3 Returns the end of the constructed range. 4 Complexity: At most((last1 - first1) + (last2 - first2)) * 2 - 1com parisons are performed.25.3.5.5set_symmetric_difference [lib.set.symmetric.difference]template <class InputIterator1, class InputIterator2, class OutputIterator>OutputIteratorset_symmetric_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>OutputIteratorset_symmetric_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp);1 Constructs a sorted symmetric difference of the elements from the two ranges. 2 The resulting range shall not overlap with either of the original ranges. 3 Returns the end of the constructed range. 4 Complexity: At most((last1 - first1) + (last2 - first2)) * 2 - 1com parisons are performed.25.3.6 Heap operations[lib.alg.heap.operations]1 A heap is a particular organization of elements in a range between two random access iterators[a, b). Its two key properties are: (1)*ais the largest element in the range and (2)*amay be removed bypop_heap, or a new element added bypush_heap, inO(logN)time. These properties make heaps useful as priority queues.make_heapconverts a range into a heap andsort_heapturns a heap into a sorted sequence.25.3.6.1push_heap [lib.push.heap]template <class RandomAccessIterator>void push_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void push_heap(RandomAccessIterator first, RandomAccessIterator last,Compare comp);1 The range[first, last - 1)shall be a valid heap. 2 Places the value in the locationlast - 1into the resulting heap[first, last). 3 Complexity: At mostlog(last - first)comparisons are performed.25.3.6.2pop_heap [lib.pop.heap]template <class RandomAccessIterator>void pop_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void pop_heap(RandomAccessIterator first, RandomAccessIterator last,Compare comp);1 The range[first, last)shall be a valid heap. 2 Swaps the value in the locationfirstwith the value in the locationlast - 1and makes[first, last - 1)into a heap. 3 Complexity: At most2 * log(last - first)comparisons are performed.25.3.6.3make_heap [lib.make.heap]template <class RandomAccessIterator>void make_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void make_heap(RandomAccessIterator first, RandomAccessIterator last,Compare comp);1 Constructs a heap out of the range[first, last). 2 Complexity: At most3*(last - first)comparisons are performed.25.3.6.4sort_heap [lib.sort.heap]template <class RandomAccessIterator>void sort_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare>void sort_heap(RandomAccessIterator first, RandomAccessIterator last,Compare comp);1 Sorts elements in the heap[first, last). 2 Complexity: At mostNlogNcomparisons are performed whereNis equal tolast - first. 3 Notes: Not stable.25.3.7 Minimum and maximum[lib.alg.min.max]25.3.7.1min [lib.min]template <class T>T min(const T& a, const T& b);template <class T, class Compare>T min(const T& a, const T& b, Compare comp);25.3.7.2max [lib.max]1 Returns the smaller value. Returns the first argument when their arguments are equal.template <class T>T max(const T& a, const T& b);template <class T, class Compare>T max(const T& a, const T& b, Compare comp);2 Returns the larger value. Returns the first argument when their argu ments are equal.25.3.7.3max_element [lib.max.element]template <class InputIterator>InputIterator max_element(InputIterator first, InputIterator last);template <class InputIterator, class Compare>InputIterator max_element(InputIterator first, InputIterator last, Compare comp);1 Returns the first iteratoriin the range[first, last)such that for any iteratorjin the range[first, last)the following corresponding conditions hold:!(*i < *j)orcomp(*i, *j) == false. 2 Complexity: Exactlymax((last - first) - 1, 0)applications of the corresponding comparisons are done.25.3.7.4min_element [lib.min.element]template <class InputIterator>InputIterator min_element(InputIterator first, InputIterator last);template <class InputIterator, class Compare>InputIterator min_element(InputIterator first, InputIterator last, Compare comp);1 Returns the first iteratoriin the range[first, last)such that for any iteratorjin the range[first, last)the following corresponding conditions hold:!(*j < *i)orcomp(*j, *i) == false. 2 Complexity: Exactlymax((last - first) - 1, 0)applications of the corresponding comparisons are done.25.3.8 Lexicographical comparison[lib.alg.lex.comparison]template <class InputIterator1, class InputIterator2>bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2);template <class InputIterator1, class InputIterator2, class Compare>bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,Compare comp);1 Returnstrueif the sequence of elements defined by the range[first1,last1)is lexicographically less than the sequence of elements defined by the range[first2, last2). Returnsfalseotherwise. 2 Complexity: At mostmin((last1 - first1), (last2 - first2))applica tions of the corresponding comparison are done.25.3.9 Permutation generators[lib.alg.permutation.generators]25.3.9.1next_permutation [lib.next.permutation]template <class BidirectionalIterator>bool next_permutation(BidirectionalIterator first,BidirectionalIterator last);template <class BidirectionalIterator, class Compare>bool next_permutation(BidirectionalIterator first,BidirectionalIterator last,Compare comp);1 Takes a sequence defined by the range[first, last)and transforms it into the next permutation. The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect tooperator<orcomp. If such a permutation exists, it returnstrue. Otherwise, it transforms the sequence into the smallest permutation, that is, the ascendingly sorted one, and returnsfalse. 2 Complexity: At most(last - first)/2swaps are performed.25.3.9.2prev_permutation [lib.prev.permutation]template <class BidirectionalIterator>bool prev_permutation(BidirectionalIterator first,BidirectionalIterator last);template <class BidirectionalIterator, class Compare>bool prev_permutation(BidirectionalIterator first,BidirectionalIterator last,Compare comp);1 Takes a sequence defined by the range[first, last)and transforms it into the previous permutation. The previous permutation is found by assuming that the set of all permutations is lexicographically sorted with respect tooperator<orcomp. 2 Returnstrueif such a permutation exists. Otherwise, it transforms the sequence into the largest permutation, that is, the descendingly sorted one, and returnsfalse. 3 Complexity: At most(last - first)/2swaps are performed.