25 - Algorithms library [lib.algorithms]

-1- This clause describes components that C++ programs may use to perform algorithmic operations on containers (clause lib.containers) and other sequences.

-2- The following subclauses describe components for non-modifying sequence operation, modifying sequence operations, sorting and related operations, and algorithms from the ISO C library, as summarized in Table ??:

Algorithms library summary
Subclause	Header(s)
lib.alg.nonmodifying Non-modifying sequence operations	<algorithm>
lib.alg.modifying.operations Mutating sequence operations
lib.alg.sorting Sorting and related operations
lib.alg.c.library C library algorithms	<cstdlib>

Header <algorithm> synopsis

namespace std {
  //  lib.alg.nonmodifying, non-modifying sequence operations:
  template<class InputIterator, class Function>
    Function for_each(InputIterator first, InputIterator last, Function f);
  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);
  template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1
      find_end(ForwardIterator1 first1, ForwardIterator1 last1,
	       ForwardIterator2 first2, ForwardIterator2 last2);
  template<class ForwardIterator1, class ForwardIterator2,
	   class BinaryPredicate>
    ForwardIterator1
      find_end(ForwardIterator1 first1, ForwardIterator1 last1,
	       ForwardIterator2 first2, ForwardIterator2 last2,
	       BinaryPredicate pred);

template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

template<class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

template<class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value); template<class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);

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);

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);

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); template<class ForwardIterator, class Size, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); template <class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator1 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred);

  //  lib.alg.modifying.operations, modifying sequence operations:
  //  lib.alg.copy, copy:
  template<class InputIterator, class OutputIterator>
    OutputIterator copy(InputIterator first, InputIterator last,
			OutputIterator result);
  template<class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2
      copy_backward
	(BidirectionalIterator1 first, BidirectionalIterator1 last,
	 BidirectionalIterator2 result);

  //  lib.alg.swap, swap:
  template<class T> void swap(T& a, T& b);
  template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator2 swap_ranges(ForwardIterator1 first1,
	ForwardIterator1 last1, ForwardIterator2 first2);
  template<class ForwardIterator1, class ForwardIterator2>
    void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

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);

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); 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);

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);

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);

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); 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);

template<class ForwardIterator> ForwardIterator unique(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 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);

template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last); template<class BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

template<class ForwardIterator> void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); template<class ForwardIterator, class OutputIterator> OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

template<class RandomAccessIterator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);

  //  lib.alg.partitions, partitions:
  template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator partition(BidirectionalIterator first,
				    BidirectionalIterator last,
				    Predicate pred);
  template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator stable_partition(BidirectionalIterator first,
					   BidirectionalIterator last,
					   Predicate pred);

  //  lib.alg.sorting, sorting and related operations:
  //  lib.alg.sort, sorting:
  template<class RandomAccessIterator>
    void sort(RandomAccessIterator first, RandomAccessIterator last);
  template<class RandomAccessIterator, class Compare>
    void sort(RandomAccessIterator first, RandomAccessIterator last,
	      Compare comp);

template<class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

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); template<class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template<class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

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);

  //  lib.alg.binary.search, binary search:
  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);

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);

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);

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);

  //  lib.alg.merge, 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);

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);

  //  lib.alg.set.operations, set operations:
  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);

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);

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);

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);

template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

  //  lib.alg.heap.operations, heap operations:
  template<class RandomAccessIterator>
    void push_heap(RandomAccessIterator first, RandomAccessIterator last);
  template<class RandomAccessIterator, class Compare>
    void push_heap(RandomAccessIterator first, RandomAccessIterator last,
		   Compare comp);

template<class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

  //  lib.alg.min.max, minimum and maximum:
  template<class T> const T& min(const T& a, const T& b);
  template<class T, class Compare>
    const T& min(const T& a, const T& b, Compare comp);
  template<class T> const T& max(const T& a, const T& b);
  template<class T, class Compare>
    const T& max(const T& a, const T& b, Compare comp);

template<class ForwardIterator> ForwardIterator min_element (ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp); template<class ForwardIterator> ForwardIterator max_element (ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

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);

  //  lib.alg.permutation.generators, permutations
  template<class BidirectionalIterator>
    bool next_permutation(BidirectionalIterator first,
			  BidirectionalIterator last);
  template<class BidirectionalIterator, class Compare>
    bool next_permutation(BidirectionalIterator first,
			  BidirectionalIterator last, Compare comp);
  template<class BidirectionalIterator>
    bool prev_permutation(BidirectionalIterator first,
			  BidirectionalIterator last);
  template<class BidirectionalIterator, class Compare>
    bool prev_permutation(BidirectionalIterator first,
			  BidirectionalIterator last, Compare comp);
}

-3- All of the algorithms are separated from the particular implementations of data structures and are parameterized by iterator types. Because of this, they can work with program-defined data structures, as long as these data structures have iterator types satisfying the assumptions on the algorithms.

-4- Throughout this clause, the names of template parameters are used to express type requirements. If an algorithm's template parameter is InputIterator, InputIterator1, or InputIterator2, the actual template argument shall satisfy the requirements of an input iterator (lib.input.iterators). If an algorithm's template parameter is OutputIterator, OutputIterator1, or OutputIterator2, the actual template argument shall satisfy the requirements of an output iterator (lib.output.iterators). If an algorithm's template parameter is ForwardIterator, ForwardIterator1, or ForwardIterator2, the actual template argument shall satisfy the requirements of a forward iterator (lib.forward.iterators). If an algorithm's template parameter is BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the actual template argument shall satisfy the requirements of a bidirectional iterator (lib.bidirectional.iterators). If an algorithm's template parameter is RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the actual template argument shall satisfy the requirements of a random-access iterator (lib.random.access.iterators).

-5- If an algorithm's Effects section says that a value pointed to by any iterator passed as an argument is modified, then that algorithm has an additional type requirement: The type of that argument shall satisfy the requirements of a mutable iterator (lib.iterator.requirements). [Note: this requirement does not affect arguments that are declared as OutputIterator, OutputIterator1, or OutputIterator2, because output iterators must always be mutable.
--- end note]

-6- Both in-place and copying versions are provided for certain algorithms.*

[Footnote: The decision whether to include a copying version was usually based on complexity considerations. When the cost of doing the operation dominates the cost of copy, the copying version is not included. For example, sort_copy is not included because the cost of sorting is much more significant, and users might as well do copy followed by sort. --- end foonote]

When such a version is provided for algorithm it is called algorithm_copy. Algorithms that take predicates end with the suffix _if (which follows the suffix _copy).

-7- The Predicate parameter is used whenever an algorithm expects a function object that when applied to the result of dereferencing the corresponding iterator returns a value testable as true. In other words, if an algorithm takes Predicate pred as its argument and first as its iterator argument, it should work correctly in the construct if (pred(*first)){...}. The function object pred shall not apply any non-constant function through the dereferenced iterator. This function object may be a pointer to function, or an object of a type with an appropriate function call operator.

-8- The BinaryPredicate parameter 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 type T when T is part of the signature returns a value testable as true. In other words, if an algorithm takes BinaryPredicate binary_pred as its argument and first1 and first2 as its iterator arguments, it should work correctly in the construct if (binary_pred(*first1, *first2)){...}. BinaryPredicate always takes the first iterator type as its first argument, that is, in those cases when T value is part of the signature, it should work correctly in the context of if (binary_pred(*first1, value)){...}. binary_pred shall not apply any non-constant function through the dereferenced iterators.

-9- In 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 of a+n is the same as that of

{ X tmp = a; advance(tmp, n); return tmp; }

and that of a-b is the same as of

return distance(a, b);

25.1 - Non-modifying sequence operations [lib.alg.nonmodifying]

25.1.1 - For each [lib.alg.foreach]

template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);

-1- Effects: Applies f to the result of dereferencing every iterator in the range [first, last), starting from first and proceeding to last - 1.

-2- Returns: f.

-3- Complexity: Applies f exactly last - first times.

-4- Notes: If f returns a result, 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- Requires: Type T is EqualityComparable (lib.equalitycomparable).

-2- Returns: The first iterator i in the range [first, last) for which the following corresponding conditions hold: *i == value, pred(*i) != false. Returns last if no such iterator is found.

-3- Complexity: At most last - first applications of the corresponding predicate.

25.1.3 - Find End [lib.alg.find.end]

template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

-1- Effects: Finds a subsequence of equal values in a sequence.

-2- Returns: The last iterator i in the range [first1, last1 - (last2-first2)) such that for any non-negative integer n < (last2-first2), the following corresponding conditions hold: *(i+n) == *(first2+n), pred(*(i+n),*(first2+n)) != false. Returns last1 if no such iterator is found.

-3- Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applications of the corresponding predicate.

25.1.4 - Find First [lib.alg.find.first.of]

-1- Effects: Finds an element that matches one of a set of values.

-2- Returns: The first iterator i in the range [first1, last1) such that for some integer j in the range [first2, last2) the following conditions hold: *i == *j, pred(*i,*j) != false. Returns last1 if no such iterator is found.

-3- Complexity: At most (last1-first1) * (last2-first2) applications of the corresponding predicate.

25.1.5 - Adjacent find [lib.alg.adjacent.find]

-1- Returns: The first iterator i such that both i and i + 1 are in the range [first, last) for which the following corresponding conditions hold: *i == *(i + 1), pred(*i, *(i + 1)) != false. Returns last if no such iterator is found.

-2- Complexity: Exactly find(first, last, value) - first applications of the corresponding predicate.

25.1.6 - Count [lib.alg.count]

-1- Requires: Type T is EqualityComparable (lib.equalitycomparable) .

-2- Effects: Returns the number of iterators i in the range [first, last) for which the following corresponding conditions hold: *i == value, pred(*i) != false.

-3- Complexity: Exactly last - first applications of the corresponding predicate.

25.1.7 - 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 iterators i and j such that j == first2 + (i - first1) and i is 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 pair last1 and first2 + (last1 - first1) if such an iterator i is not found.

-2- Complexity: At most last1 - first1 applications of the corresponding predicate.

25.1.8 - 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- Returns: true if for every iterator i in the range [first1, last1) the following corresponding conditions hold: *i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false. Otherwise, returns false.

-2- Complexity: At most last1 - first1 applications of the corresponding predicate.

25.1.9 - 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- Effects: Finds a subsequence of equal values in a sequence.

-2- Returns: The first iterator i in the range [first1, last1 - (last2 - first2)) such that for any non-negative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns last1 if no such iterator is found.

-3- Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate.

template<class ForwardIterator, class Size, class T>
  ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count,
           const T& value);

template<class ForwardIterator, class Size, class T,
         class BinaryPredicate>
  ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count,
           const T& value, BinaryPredicate pred);

-4- Requires: Type T is EqualityComparable (lib.equalitycomparable), type Size is convertible to integral type (conv.integral, class.conv).

-5- Effects: Finds a subsequence of equal values in a sequence.

-6- Returns: The first iterator i in the range [first, last - count) such that for any non-negative integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i + n),value) != false. Returns last if no such iterator is found.

-7- Complexity: At most (last1 - first1) * count applications of the corresponding predicate.

25.2 - Mutating sequence operations [lib.alg.modifying.operations]

25.2.1 - Copy [lib.alg.copy]

template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);

-1- Effects: Copies elements in the range [first, last) into the range [result, result + (last - first)) starting from first and proceeding to last. For each non-negative integer n < (last-first), performs *(result + n) = *(first + n).

-2- Returns: result + (last - first).

-3- Requires: result shall not be in the range [first, last).

-4- Complexity: Exactly last - first assignments.

template<class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2
    copy_backward(BidirectionalIterator1 first,
                  BidirectionalIterator1 last,
                  BidirectionalIterator2 result);

-5- Effects: Copies elements in the range [first, last) into the range [result - (last - first), result) starting from last - 1 and proceeding to first . *

[Footnote: copy_backward (_lib.copy.backward_) should be used instead of copy when last is in the range [result - (last - first), result). --- end foonote]

For each positive integer n <= (last - first), performs *(result - n) = *(last - n).

-6- Requires: result shall not be in the range [first, last).

-7- Returns: result - (last - first).

-8- Complexity: Exactly last - first assignments.

25.2.2 - Swap [lib.alg.swap]

template<class T> void swap(T& a, T& b);

-1- Requires: Type T is Assignable (lib.container.requirements).

-2- Effects: Exchanges values stored in two locations.

template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2
    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                ForwardIterator2 first2);

-3- Effects: For each non-negative integer n < (last1 - first1) performs: swap(*(first1 + n), *(first2 + n)).

-4- Requires: The two ranges [first1, last1) and [first2, first2 + (last1 - first1)) shall not overlap.

-5- Returns: first2 + (last1 - first1).

-6- Complexity: Exactly last1 - first1 swaps.

template<class ForwardIterator1, class ForwardIterator2>
  void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

-7- Effects: Exchanges the values pointed to by the two iterators a and b.

25.2.3 - Transform [lib.alg.transform]

-1- Effects: Assigns through every iterator i in the range [result, result + (last1 - first1)) a new corresponding value equal to op(*(first1 + (i - result)) or binary_op(*(first1 + (i - result), *(first2 + (i - result))).

-2- Requires: op and binary_op shall not have any side effects.

-3- Returns: result + (last1 - first1).

-4- Complexity: Exactly last1 - first1 applications of op or binary_op

-5- Notes: result may be equal to first in case of unary transform, or to first1 or first2 in case of binary transform.

25.2.4 - Replace [lib.alg.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- Requires: Type T is Assignable (lib.container.requirements) (and, for replace(), EqualityComparable (lib.equalitycomparable)).

-2- Effects: Substitutes elements referred by the iterator i in the range [first, last) with new_value, when the following corresponding conditions hold: *i == old_value, pred(*i) != false.

-3- Complexity: Exactly last - first applications of the corresponding predicate.

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);

-4- Requires: Type T is Assignable (lib.container.requirements) (and, for replace_copy(), EqualityComparable (lib.equalitycomparable). The ranges [first, last) and [result, result + (last - first)) shall not overlap.

-5- Effects: Assigns to every iterator i in the range [result, result + (last - first)) either new_value or *(first + (i - result)) depending on whether the following corresponding conditions hold:
*(first + (i - result )) == old_value , pred (*(first + (i - result ))) != false.

-6- Returns: result + (last - first).

-7- Complexity: Exactly last - first applications of the corresponding predicate.

25.2.5 - Fill [lib.alg.fill]

-1- Requires: Type T is Assignable (lib.container.requirements), Size is convertible to an integral type (conv.integral, class.conv).

-2- Effects: Assigns value through all the iterators in the range [first, last)or [first, first + n).

-3- Complexity: Exactly last - first (or n) assignments.

25.2.6 - Generate [lib.alg.generate]

-1- Effects: Invokes the function object gen and assigns the return value of gen though all the iterators in the range [first, last) or [first, first + n).

-2- Requires: gen takes no arguments, Size is convertible to an integral type (conv.integral, class.conv).

-3- Complexity: Exactly last - first (or n) invocations of gen and assignments.

25.2.7 - Remove [lib.alg.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- Requires: Type T is EqualityComparable (lib.equalitycomparable).

-2- Effects: Eliminates all the elements referred to by iterator i in the range [first, last) for which the following corresponding conditions hold: *i == value, pred(*i) != false.

-3- Returns: The end of the resulting range.

-4- Notes: Stable: the relative order of the elements that are not removed is the same as their relative order in the original range.

-5- Complexity: Exactly last - first applications of the corresponding predicate.

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);

-6- Requires: Type T is EqualityComparable (lib.equalitycomparable). The ranges [first, last) and [result, result+(last-first)) shall not overlap.

-7- Effects: Copies all the elements referred to by the iterator i in the range [first, last) for which the following corresponding conditions do not hold: *i == value, pred(*i) != false.

-8- Returns: The end of the resulting range.

-9- Complexity: Exactly last - first applications of the corresponding predicate.

-10- Notes: Stable: the relative order of the elements in the resulting range is the same as their relative order in the original range.

25.2.8 - Unique [lib.alg.unique]

template<class ForwardIterator> ForwardIterator unique(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

-1- Effects: Eliminates all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first, last) for which the following corresponding conditions hold: *i == *(i - 1) or pred(*i, *(i - 1)) != false

-2- Returns: The end of the resulting range.

-3- Complexity: If the range (last - first) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.

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);

-4- Requires: The ranges [first, last) and [result, result+(last-first)) shall not overlap.

-5- Effects: Copies only the first element from every consecutive group of equal elements referred to by the iterator i in the range [first, last) for which the following corresponding conditions hold: *i == *(i - 1) or pred(*i, *(i - 1)) != false

-6- Returns: The end of the resulting range.

-7- Complexity: Exactly last - first applications of the corresponding predicate.

25.2.9 - Reverse [lib.alg.reverse]

template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last);

-1- Effects: For each non-negative integer i <= (last - first)/2, applies swap to all pairs of iterators first + i, (last - i) - 1.

-2- Complexity: Exactly (last - first)/2 swaps.

template<class BidirectionalIterator, class OutputIterator>
  OutputIterator
    reverse_copy(BidirectionalIterator first,
                 BidirectionalIterator last, OutputIterator result);

-3- Effects: Copies the range [first, last) to the range [result, result + (last - first)) such that for any non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - i) = *(first + i)

-4- Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.

-5- Returns: result + (last - first).

-6- Complexity: Exactly last - first assignments.

25.2.10 - Rotate [lib.alg.rotate]

template<class ForwardIterator> void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

-1- Effects: For each non-negative integer i < (last - first), places the element from the position first + i into position first + (i + (last - middle)) % (last - first).

-2- Notes: This is a left rotate.

-3- Requires: [first, middle) and [middle, last) are valid ranges.

-4- Complexity: At most last - first swaps.

template<class ForwardIterator, class OutputIterator>
  OutputIterator
    rotate_copy(ForwardIterator first, ForwardIterator middle,
                ForwardIterator last, OutputIterator result);

-5- Effects: Copies the range [first, last) to the range [result, result + (last - first)) such that for each non-negative integer i < (last - first) the following assignment takes place: *(result + i) = *(first + (i + (middle - first)) % (last - first))

-6- Returns: result + (last - first).

-7- Requires The ranges [first, last) and [result, result + (last - first)) shall not overlap.

-8- Complexity: Exactly last - first assignments.

25.2.11 - Random shuffle [lib.alg.random.shuffle]

-1- Effects: Shuffles the elements in the range [first, last) with uniform distribution.

-2- Complexity: Exactly (last - first) - 1 swaps.

-3- Notes: random_shuffle() can take a particular random number generating function object rand such that if n is an argument for rand , with a positive value, that has type iterator_traits<RandomAccessIterator>::difference_type, then rand(n) returns a randomly chosen value, which lies in the interval [0, n), and which has a type that is convertible to iterator_traits<RandomAccessIterator>::difference_type.

25.2.12 - Partitions [lib.alg.partitions]

template<class BidirectionalIterator, class Predicate> BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

-1- Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.

-2- Returns: An iterator i such that for any iterator j in the range [ first , i), pred(*j) != false, and for any iterator k in the range [i, last ), pred(*j) == false.

-3- Complexity: At most (last - first)/2 swaps. Exactly last - first applications of the predicate are done.

template<class BidirectionalIterator, class Predicate>
  BidirectionalIterator
    stable_partition(BidirectionalIterator first,
                     BidirectionalIterator last, Predicate pred);

-4- Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.

-5- Returns: An iterator i such that for any iterator j in the range [first, i), pred(*j) != false, and for any iterator k in the range [i, last), pred(*j) == false. The relative order of the elements in both groups is preserved.

-6- Complexity: At most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate.

25.3 - Sorting and related operations [lib.alg.sorting]

-1- All the operations in lib.alg.sorting have two versions: one that takes a function object of type Compare and one that uses an operator<.

-2- Compare is used as a function object which returns true if the first argument is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

-3- For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For the algorithms to work correctly, comp has to induce a strict weak ordering on the values.

-4- The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

comp(a, b) && comp(b, c) implies comp(a, c)

equiv(a, b) && equiv(b, c) implies equiv(a, c) [Note: Under these conditions, it can be shown that

equiv is an equivalence relation

comp induces a well-defined relation on the equivalence classes determined by equiv

The induced relation is a strict total ordering.
--- end note]

-5- A sequence is sorted with respect to a comparator comp if for any iterator i pointing to the sequence and any non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, comp(*(i + n), *i) == false.

-6- In the descriptions of the functions that deal with ordering relationships we frequently use a notion of equivalence to describe concepts such as stability. The equivalence to which we refer is not necessarily an operator==, but an equivalence relation induced by the strict weak ordering. That is, two elements a and b are considered equivalent if and only if !(a < b) && !(b < a).

25.3.1 - Sorting [lib.alg.sort]

25.3.1.1 - `sort` [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- Effects: Sorts the elements in the range [first, last).

-2- Complexity: Approximately N log N (where N == last - first) comparisons on the average.*

[Footnote: If the worst case behavior is important stable_sort() (lib.stable.sort) or partial_sort() (lib.partial.sort) should be used. --- end foonote]

25.3.1.2 - `stable_sort` [lib.stable.sort]

-1- Effects: Sorts the elements in the range [first, last).

-2- Complexity: It does at most N(log N)² (where N == last - first) comparisons; if enough extra memory is available, it is N log N.

-3- Notes: Stable: the relative order of the equivalent elements is preserved.

25.3.1.3 - `partial_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- Effects: Places the first middle - first sorted 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 unspecified order.

-2- Complexity: It takes approximately (last - first) * log(middle - first) comparisons.

25.3.1.4 - `partial_sort_copy` [lib.partial.sort.copy]

template<class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template<class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

-1- Effects: Places the first min(last - first, result_last - result_first) sorted elements into the range [result_first, result_first + min(last - first, result_last - result_first)).

-2- Returns: The smaller of: result_last or result_first + (last - first)

-3- Complexity: Approximately (last - first) * log(min(last - first, result_last - result_first)) comparisons.

25.3.2 - Nth element [lib.alg.nth.element]

-1- After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for any iterator i in the range [first, nth) and any iterator j in the range [nth, last) it holds that: !(*i > *j) or comp(*j, *i) == 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 and assume that the sequence being searched is in order according to the implied or explicit comparison function. They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure. For non-random access iterators they execute a linear number of steps.

25.3.3.1 - `lower_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- Requires: Type T is LessThanComparable (lib.lessthancomparable).

-2- Effects: Finds the first position into which value can be inserted without violating the ordering.

-3- Returns: The furthermost iterator i in the range [first, last] such that for any iterator j in the range [first, i) the following corresponding conditions hold: *j < value or comp(*j, value) != false

-4- Complexity: At most log(last - first) + 1 comparisons.

25.3.3.2 - `upper_bound` [lib.upper.bound]

-1- Requires: Type T is LessThanComparable (lib.lessthancomparable).

-2- Effects: Finds the furthermost position into which value can be inserted without violating the ordering.

-3- Returns: The furthermost iterator i in the range [first, last) such that for any iterator j in the range [first, i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false

-4- Complexity: At most log(last - first) + 1 comparisons.

25.3.3.3 - `equal_range` [lib.equal.range]

-1- Requires: Type T is LessThanComparable (lib.lessthancomparable).

-2- Effects: Finds the largest subrange [i, j) such that the value can be inserted at any iterator k in it without violating the ordering. k satisfies the corresponding conditions: !(*k < value) && !(value < *k) or comp(*k, value) == false && comp(value, *k) == false.

-3- Complexity: At most 2 * log(last - first) + 1 comparisons.

25.3.3.4 - `binary_search` [lib.binary.search]

-1- Requires: Type T is LessThanComparable (lib.lessthancomparable).

-2- Returns: true if there is an iterator i in the range [first, last) that satisfies the corresponding conditions: !(*i < value) && !(value < *i) or comp(*i, value) == false && comp(value, *i) == false.

-3- Complexity: At most log(last - first) + 2 comparisons.

25.3.4 - Merge [lib.alg.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- Effects: 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. The list will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i in [first, last) other than first, the condition *i < *(i - 1) or comp(*i, *(i - 1)) will be false.

-3- Returns: result + (last1 - first1) + (last2 - first2).

-4- Complexity: At most (last1 - first1) + (last2 - first2) - 1 comparisons.

-5- Notes: Stable: for equivalent elements in the two ranges, the elements from the first range always precede the elements from the second.

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);

-6- Effects: Merges two sorted consecutive ranges [first, middle) and [middle, last), putting the result of the merge into the range [first, last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first, last) other than first, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.

-7- Complexity: When enough additional memory is available, (last - first) - 1 comparisons. If no additional memory is available, an algorithm with complexity N log N (where N is equal to last - first) may be used.

-8- Notes: Stable: for equivalent 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 structures [lib.alg.set.operations]

-1- This section defines all the basic set operations on sorted structures. They also work with multisets (lib.multiset) containing multiple copies of equivalent elements. The semantics of the set operations are 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.1 - `includes` [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- Returns: true if every element in the range [first2, last2) is contained in the range [first1, last1). Returns false otherwise.

-2- Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.

25.3.5.2 - `set_union` [lib.set.union]

-1- Effects: Constructs a sorted union of the elements from the two ranges; that is, the set of elements that are present in one or both of the ranges.

-2- Requires: The resulting range shall not overlap with either of the original ranges.

-3- Returns: The end of the constructed range.

-4- Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.

-5- Notes: Stable: if an element is present in both ranges, the one from the first range is copied.

25.3.5.3 - `set_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- Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements that are present in both of the ranges.

-2- Requires: The resulting range shall not overlap with either of the original ranges.

-3- Returns: The end of the constructed range.

-4- Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.

-5- Notes: Stable, that is, if an element is present in both ranges, the one from the first range is copied.

25.3.5.4 - `set_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- Effects: Copies the elements of the range [first1, last1) which are not present in the range [first2, last2) to the range beginning at result. The elements in the constructed range are sorted.

-2- Requires: The resulting range shall not overlap with either of the original ranges.

-3- Returns: The end of the constructed range.

-4- Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.

25.3.5.5 - `set_symmetric_difference` [lib.set.symmetric.difference]

-1- Effects: Copies the elements of the range [first1, last1) which are not present in the range [first2, last2), and the elements of the range [first2, last2) which are not present in the range [first1, last1) to the range beginning at result. The elements in the constructed range are sorted.

-2- Requires: The resulting range shall not overlap with either of the original ranges.

-3- Returns: The end of the constructed range.

-4- Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.

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:

*a is the largest element in the range and

*a may be removed by pop_heap(), or a new element added by push_heap(), in O(log N) time.

-2- These properties make heaps useful as priority queues.

-3- make_heap() converts a range into a heap and sort_heap() turns a heap into a sorted sequence.

25.3.6.1 - `push_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- Requires: The range [first, last - 1) shall be a valid heap.

-2- Effects: Places the value in the location last - 1 into the resulting heap [first, last).

-3- Complexity: At most log(last - first) comparisons.

25.3.6.2 - `pop_heap` [lib.pop.heap]

-1- Requires: The range [first, last) shall be a valid heap.

-2- Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first, last - 1) into a heap.

-3- Complexity: At most 2 * log(last - first) comparisons.

25.3.6.3 - `make_heap` [lib.make.heap]

-1- Effects: Constructs a heap out of the range [first, last).

-2- Complexity: At most 3 * (last - first) comparisons.

25.3.6.4 - `sort_heap` [lib.sort.heap]

-1- Effects: Sorts elements in the heap [first, last).

-2- Complexity: At most N log N comparisons (where N == last - first).

-3- Notes: Not stable.

25.3.7 - Minimum and maximum [lib.alg.min.max]

template<class T> const T& min(const T& a, const T& b); template<class T, class Compare> const T& min(const T& a, const T& b, Compare comp);

-1- Requires: Type T is LessThanComparable (lib.lessthancomparable) and CopyConstructible (lib.copyconstructible).

-2- Returns: The smaller value.

-3- Notes: Returns the first argument when the arguments are equivalent.

template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
  const T& max(const T& a, const T& b, Compare comp);

-4- Requires: Type T is LessThanComparable (lib.lessthancomparable) and CopyConstructible (lib.copyconstructible).

-5- Returns: The larger value.

-6- Notes: Returns the first argument when the arguments are equivalent.

template<class ForwardIterator>
  ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare>
  ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                            Compare comp);

-7- Returns: The first iterator i in the range [first, last) such that for any iterator j in the range [first, last) the following corresponding conditions hold: !(*j < *i) or comp(*j, *i) == false

-8- Complexity: Exactly max((last - first) - 1, 0) applications of the corresponding comparisons.

template<class ForwardIterator>
  ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
  ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                            Compare comp);

-9- Returns: The first iterator i in the range [first, last) such that for any iterator j in the range [first, last) the following corresponding conditions hold: !(*i < *j) or comp(*i, *j) == false.

-10- Complexity: Exactly max((last - first) - 1, 0) applications of the corresponding comparisons.

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- Returns: true if the sequence of elements defined by the range [first1, last1) is lexicographically less than the sequence of elements defined by the range [first2, last2).
Returns false otherwise.

-2- Complexity: At most min((last1 - first1), (last2 - first2)) applications of the corresponding comparison.

-3- Notes: If two sequences have the same number of elements and their corresponding elements are equivalent, then neither sequence is lexicographically less than the other. If one sequence is a prefix of the other, then the shorter sequence is lexicographically less than the longer sequence. Otherwise, the lexicographical comparison of the sequences yields the same result as the comparison of the first corresponding pair of elements that are not equivalent.

for (i = first1, j = first2; i != last1 && j != last2 && !(*i < *j) && !(*j < *i); ++i, ++j); return j == last2 ? false : i == last1 || *i < *j;

25.3.9 - Permutation generators [lib.alg.permutation.generators]

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- Effects: 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 to operator< or comp. If such a permutation exists, it returns true. Otherwise, it transforms the sequence into the smallest permutation, that is, the ascendingly sorted one, and returns false.

-2- Complexity: At most (last - first)/2 swaps.

template<class BidirectionalIterator>
  bool prev_permutation(BidirectionalIterator first,
                        BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
  bool prev_permutation(BidirectionalIterator first,
                        BidirectionalIterator last, Compare comp);

-3- Effects: 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 to operator< or comp.

-4- Returns: true if such a permutation exists. Otherwise, it transforms the sequence into the largest permutation, that is, the descendingly sorted one, and returns false.

-5- Complexity: At most (last - first)/2 swaps.

25.4 - C library algorithms [lib.alg.c.library]

-1- Header <cstdlib> (partial, Table ??):

Header `<cstdlib>` synopsis
Type	Name(s)
Functions:	bsearch	qsort

-2- The contents are the same as the Standard C library header <stdlib.h> with the following exceptions:

-3- The function signature:

bsearch(const void *, const void *, size_t, size_t,
	int (*)(const void *, const void *));

is replaced by the two declarations: extern "C" void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); extern "C++" void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); both of which have the same behavior as the original declaration.

-4- The function signature:

qsort(void *, size_t, size_t,
	int (*)(const void *, const void *));

is replaced by the two declarations: extern "C" void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*)); extern "C++" void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*)); [Note: Because the function argument compar() may throw an exception, bsearch() and qsort() are allowed to propagate the exception (lib.res.on.exception.handling).
--- end note]

25 - Algorithms library [lib.algorithms]

25.1 - Non-modifying sequence operations [lib.alg.nonmodifying]

25.1.1 - For each [lib.alg.foreach]

25.2.1 - Copy [lib.alg.copy]

25.3.1.1 - sort [lib.sort]

25.3.1.2 - stable_sort [lib.stable.sort]

25.3.9 - Permutation generators [lib.alg.permutation.generators]

25.3.1.1 - `sort` [lib.sort]

25.3.1.2 - `stable_sort` [lib.stable.sort]