[alg.sorting] - C++11 → C++14

Files changed (1) hide show

tmp/tmpw8576ayy/{from.md → to.md} +37 -37

tmp/tmpw8576ayy/{from.md → to.md} RENAMED Viewed

@@ -5,15 +5,15 @@ a function object of type `Compare` and one that uses an `operator<`.
 `Compare`
 is a function object type ([[function.objects]]). The return value of
 the function call operation applied to an object of type `Compare`, when
-contextually converted to `bool` ([[conv]]), yields `true` if the first
-argument of the call 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.
 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 algorithms other than those described in
 [[alg.binary.search]] to work correctly, `comp` has to induce a strict
@@ -32,12 +32,12 @@ for a partial ordering. If we define `equiv(a, b)` as
   - `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.
-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`.
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
@@ -94,11 +94,11 @@ shall satisfy the requirements of `MoveConstructible`
 (Table  [[moveassignable]]).
 *Complexity:* It does at most N log²(N) (where N` == last - first`)
 comparisons; if enough extra memory is available, it is N log(N).
-*Remarks:* Stable.
 #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
@@ -206,13 +206,13 @@ template<class RandomAccessIterator, class Compare>
                    RandomAccessIterator last,  Compare comp);
 ```
 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`.
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
 (Table  [[moveconstructible]]) and of `MoveAssignable`
@@ -248,15 +248,15 @@ template<class ForwardIterator, class T, class Compare>
 *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
 with respect to the expression `e < value` or `comp(e, value)`.
 *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`.
-*Complexity:* At most log₂(last - first) + 𝑂(1) comparisons.
 #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
@@ -272,15 +272,15 @@ template<class ForwardIterator, class T, class Compare>
 *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
 with respect to the expression `!(value < e)` or `!comp(value, e)`.
 *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`.
-*Complexity:* At most log₂(last - first) + 𝑂(1) comparisons.
 #### `equal_range` <a id="equal.range">[[equal.range]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
@@ -313,11 +313,11 @@ or
 ``` cpp
 make_pair(lower_bound(first, last, value, comp),
           upper_bound(first, last, value, comp))
 ```
-*Complexity:* At most 2 * log₂(last - first) + 𝑂(1) comparisons.
 #### `binary_search` <a id="binary.search">[[binary.search]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
@@ -338,11 +338,11 @@ implies `!comp(value, e)`.
 *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`.
-*Complexity:* At most `log2(last - first)` + 𝑂(1) comparisons.
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
@@ -374,11 +374,11 @@ range shall not overlap with either of the original ranges.
 *Returns:* `result + (last1 - first1) + (last2 - first2)`.
 *Complexity:* At most `(last1 - first1) + (last2 - first2) - 1`
 comparisons.
-*Remarks:* Stable.
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
@@ -408,11 +408,11 @@ shall satisfy the requirements of `MoveConstructible`
 *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.
-*Remarks:* Stable.
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
 This section defines all the basic set operations on sorted structures.
 They also work with `multiset`s ([[multiset]]) containing multiple
@@ -728,13 +728,13 @@ returns the last iterator `i` in \[`first`, `last`\] for which the range
 *Complexity:* Linear.
 ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
 ``` cpp
-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);
 ```
 *Requires:* Type `T` is `LessThanComparable`
 (Table  [[lessthancomparable]]).
@@ -742,13 +742,13 @@ template<class T, class Compare>
 *Remarks:* Returns the first argument when the arguments are equivalent.
 ``` cpp
 template<class T>
-  T min(initializer_list<T> t);
 template<class T, class Compare>
-  T min(initializer_list<T> t, Compare comp);
 ```
 *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
 `t.size() > 0`.
@@ -756,13 +756,13 @@ template<class T, class Compare>
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the smallest.
 ``` cpp
-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);
 ```
 *Requires:* Type `T` is `LessThanComparable`
 (Table  [[lessthancomparable]]).
@@ -770,13 +770,13 @@ template<class T, class Compare>
 *Remarks:* Returns the first argument when the arguments are equivalent.
 ``` cpp
 template<class T>
-  T max(initializer_list<T> t);
 template<class T, class Compare>
-  T max(initializer_list<T> t, Compare comp);
 ```
 *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
 `t.size() > 0`.
@@ -784,13 +784,13 @@ template<class T, class Compare>
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the largest.
 ``` cpp
-template<class T> pair<const T&, const T&> minmax(const T& a, const T& b);
 template<class T, class Compare>
-  pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
 ```
 *Requires:* Type `T` shall be `LessThanComparable`
 (Table  [[lessthancomparable]]).
@@ -802,13 +802,13 @@ are equivalent.
 *Complexity:* Exactly one comparison.
 ``` cpp
 template<class T>
-  pair<T, T> minmax(initializer_list<T> t);
 template<class T, class Compare>
-  pair<T, T> minmax(initializer_list<T> t, Compare comp);
 ```
 *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
 `t.size() > 0`.
@@ -830,13 +830,13 @@ template<class ForwardIterator, class Compare>
   ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                             Compare comp);
 ```
 *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`.
-Returns `last` if `first == last`.
 *Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
 corresponding comparisons.
 ``` cpp
@@ -846,13 +846,13 @@ template<class ForwardIterator, class Compare>
   ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                             Compare comp);
 ```
 *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`.
-Returns `last` if `first == last`.
 *Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
 corresponding comparisons.
 ``` cpp

 `Compare`
 is a function object type ([[function.objects]]). The return value of
 the function call operation applied to an object of type `Compare`, when
+contextually converted to `bool` (Clause  [[conv]]), yields `true` if
+the first argument of the call 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.
 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 algorithms other than those described in
 [[alg.binary.search]] to work correctly, `comp` has to induce a strict
   - `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.
+A sequence is *sorted with respect to a comparator* `comp` if for every
+iterator `i` pointing to the sequence and every non-negative integer `n`
 such that `i + n` is a valid iterator pointing to an element of the
 sequence, `comp(*(i + n), *i) == false`.
 A sequence \[`start`, `finish`) is *partitioned with respect to an
 expression* `f(e)` if there exists an integer `n` such that for all
 (Table  [[moveassignable]]).
 *Complexity:* It does at most N log²(N) (where N` == last - first`)
 comparisons; if enough extra memory is available, it is N log(N).
+*Remarks:* Stable ([[algorithm.stable]]).
 #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
 ``` cpp
 template<class RandomAccessIterator>
                    RandomAccessIterator last,  Compare comp);
 ```
 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, unless `nth == last`. Also for every iterator `i` in the range
+\[`first`, `nth`) and every iterator `j` in the range \[`nth`, `last`)
+it holds that: `!(*j < *i)` or `comp(*j, *i) == false`.
 *Requires:* `RandomAccessIterator` shall satisfy the requirements of
 `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
 shall satisfy the requirements of `MoveConstructible`
 (Table  [[moveconstructible]]) and of `MoveAssignable`
 *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
 with respect to the expression `e < value` or `comp(e, value)`.
 *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
+such that for every iterator `j` in the range \[`first`, `i`) the
 following corresponding conditions hold: `*j < value` or
 `comp(*j, value) != false`.
+*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
 *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
 with respect to the expression `!(value < e)` or `!comp(value, e)`.
 *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
+such that for every iterator `j` in the range \[`first`, `i`) the
 following corresponding conditions hold: `!(value < *j)` or
 `comp(value, *j) == false`.
+*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 #### `equal_range` <a id="equal.range">[[equal.range]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
 ``` cpp
 make_pair(lower_bound(first, last, value, comp),
           upper_bound(first, last, value, comp))
 ```
+*Complexity:* At most 2 * log₂(`last - first`) + 𝑂(1) comparisons.
 #### `binary_search` <a id="binary.search">[[binary.search]]</a>
 ``` cpp
 template<class ForwardIterator, class T>
 *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`.
+*Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
 *Returns:* `result + (last1 - first1) + (last2 - first2)`.
 *Complexity:* At most `(last1 - first1) + (last2 - first2) - 1`
 comparisons.
+*Remarks:* Stable ([[algorithm.stable]]).
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
 *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.
+*Remarks:* Stable ([[algorithm.stable]]).
 ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
 This section defines all the basic set operations on sorted structures.
 They also work with `multiset`s ([[multiset]]) containing multiple
 *Complexity:* Linear.
 ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
 ``` cpp
+template<class T> constexpr const T& min(const T& a, const T& b);
 template<class T, class Compare>
+ constexpr const T& min(const T& a, const T& b, Compare comp);
 ```
 *Requires:* Type `T` is `LessThanComparable`
 (Table  [[lessthancomparable]]).
 *Remarks:* Returns the first argument when the arguments are equivalent.
 ``` cpp
 template<class T>
+ constexpr T min(initializer_list<T> t);
 template<class T, class Compare>
+ constexpr T min(initializer_list<T> t, Compare comp);
 ```
 *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
 `t.size() > 0`.
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the smallest.
 ``` cpp
+template<class T> constexpr const T& max(const T& a, const T& b);
 template<class T, class Compare>
+ constexpr const T& max(const T& a, const T& b, Compare comp);
 ```
 *Requires:* Type `T` is `LessThanComparable`
 (Table  [[lessthancomparable]]).
 *Remarks:* Returns the first argument when the arguments are equivalent.
 ``` cpp
 template<class T>
+ constexpr T max(initializer_list<T> t);
 template<class T, class Compare>
+ constexpr T max(initializer_list<T> t, Compare comp);
 ```
 *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
 `t.size() > 0`.
 *Remarks:* Returns a copy of the leftmost argument when several
 arguments are equivalent to the largest.
 ``` cpp
+template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
 template<class T, class Compare>
+ constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
 ```
 *Requires:* Type `T` shall be `LessThanComparable`
 (Table  [[lessthancomparable]]).
 *Complexity:* Exactly one comparison.
 ``` cpp
 template<class T>
+ constexpr pair<T, T> minmax(initializer_list<T> t);
 template<class T, class Compare>
+ constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
 ```
 *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
 `t.size() > 0`.
   ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                             Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
+that for every iterator `j` in the range \[`first`, `last`) the
+following corresponding conditions hold: `!(*j < *i)` or
+`comp(*j, *i) == false`. Returns `last` if `first == last`.
 *Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
 corresponding comparisons.
 ``` cpp
   ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                             Compare comp);
 ```
 *Returns:* The first iterator `i` in the range \[`first`, `last`) such
+that for every iterator `j` in the range \[`first`, `last`) the
+following corresponding conditions hold: `!(*i < *j)` or
+`comp(*i, *j) == false`. Returns `last` if `first == last`.
 *Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
 corresponding comparisons.
 ``` cpp

Diff to HTML by rtfpessoa