tmp/tmpe8xr5z2t/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,68 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
### General <a id="alg.sorting.general">[[alg.sorting.general]]</a>
|
| 2 |
+
|
| 3 |
+
The operations in [[alg.sorting]] defined directly in namespace `std`
|
| 4 |
+
have two versions: one that takes a function object of type `Compare`
|
| 5 |
+
and one that uses an `operator<`.
|
| 6 |
+
|
| 7 |
+
`Compare` is a function object type [[function.objects]] that meets the
|
| 8 |
+
requirements for a template parameter named `BinaryPredicate`
|
| 9 |
+
[[algorithms.requirements]]. The return value of the function call
|
| 10 |
+
operation applied to an object of type `Compare`, when converted to
|
| 11 |
+
`bool`, yields `true` if the first argument of the call is less than the
|
| 12 |
+
second, and `false` otherwise. `Compare comp` is used throughout for
|
| 13 |
+
algorithms assuming an ordering relation.
|
| 14 |
+
|
| 15 |
+
For all algorithms that take `Compare`, there is a version that uses
|
| 16 |
+
`operator<` instead. That is, `comp(*i, *j) != false` defaults to
|
| 17 |
+
`*i < *j != false`. For algorithms other than those described in
|
| 18 |
+
[[alg.binary.search]], `comp` shall induce a strict weak ordering on the
|
| 19 |
+
values.
|
| 20 |
+
|
| 21 |
+
The term *strict* refers to the requirement of an irreflexive relation
|
| 22 |
+
(`!comp(x, x)` for all `x`), and the term *weak* to requirements that
|
| 23 |
+
are not as strong as those for a total ordering, but stronger than those
|
| 24 |
+
for a partial ordering. If we define `equiv(a, b)` as
|
| 25 |
+
`!comp(a, b) && !comp(b, a)`, then the requirements are that `comp` and
|
| 26 |
+
`equiv` both be transitive relations:
|
| 27 |
+
|
| 28 |
+
- `comp(a, b) && comp(b, c)` implies `comp(a, c)`
|
| 29 |
+
- `equiv(a, b) && equiv(b, c)` implies `equiv(a, c)`
|
| 30 |
+
|
| 31 |
+
[*Note 1*:
|
| 32 |
+
|
| 33 |
+
Under these conditions, it can be shown that
|
| 34 |
+
|
| 35 |
+
- `equiv` is an equivalence relation,
|
| 36 |
+
- `comp` induces a well-defined relation on the equivalence classes
|
| 37 |
+
determined by `equiv`, and
|
| 38 |
+
- the induced relation is a strict total ordering.
|
| 39 |
+
|
| 40 |
+
— *end note*]
|
| 41 |
+
|
| 42 |
+
A sequence is *sorted with respect to a `comp` and `proj`* for a
|
| 43 |
+
comparator and projection `comp` and `proj` if for every iterator `i`
|
| 44 |
+
pointing to the sequence and every non-negative integer `n` such that
|
| 45 |
+
`i + n` is a valid iterator pointing to an element of the sequence,
|
| 46 |
+
|
| 47 |
+
``` cpp
|
| 48 |
+
bool(invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i)))
|
| 49 |
+
```
|
| 50 |
+
|
| 51 |
+
is `false`.
|
| 52 |
+
|
| 53 |
+
A sequence is *sorted with respect to a comparator `comp`* for a
|
| 54 |
+
comparator `comp` if it is sorted with respect to `comp` and
|
| 55 |
+
`identity{}` (the identity projection).
|
| 56 |
+
|
| 57 |
+
A sequence \[`start`, `finish`) is *partitioned with respect to an
|
| 58 |
+
expression* `f(e)` if there exists an integer `n` such that for all
|
| 59 |
+
`0 <= i < (finish - start)`, `f(*(start + i))` is `true` if and only if
|
| 60 |
+
`i < n`.
|
| 61 |
+
|
| 62 |
+
In the descriptions of the functions that deal with ordering
|
| 63 |
+
relationships we frequently use a notion of equivalence to describe
|
| 64 |
+
concepts such as stability. The equivalence to which we refer is not
|
| 65 |
+
necessarily an `operator==`, but an equivalence relation induced by the
|
| 66 |
+
strict weak ordering. That is, two elements `a` and `b` are considered
|
| 67 |
+
equivalent if and only if `!(a < b) && !(b < a)`.
|
| 68 |
+
|