From Jason Turner

[alg.lex.comparison]

C++17 → C++20 4.4 KB 50 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp9zkitkhj/{from.md → to.md} +32 -15
tmp/tmp9zkitkhj/{from.md → to.md} RENAMED
@@ -1,55 +1,72 @@
1
  ### Lexicographical comparison <a id="alg.lex.comparison">[[alg.lex.comparison]]</a>
2
 
3
  ``` cpp
4
  template<class InputIterator1, class InputIterator2>
5
- bool
6
  lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
7
  InputIterator2 first2, InputIterator2 last2);
8
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
9
  bool
10
  lexicographical_compare(ExecutionPolicy&& exec,
11
  ForwardIterator1 first1, ForwardIterator1 last1,
12
  ForwardIterator2 first2, ForwardIterator2 last2);
13
 
14
  template<class InputIterator1, class InputIterator2, class Compare>
15
- bool
16
  lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
17
  InputIterator2 first2, InputIterator2 last2,
18
  Compare comp);
19
- template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
 
20
  bool
21
  lexicographical_compare(ExecutionPolicy&& exec,
22
  ForwardIterator1 first1, ForwardIterator1 last1,
23
  ForwardIterator2 first2, ForwardIterator2 last2,
24
  Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
25
  ```
26
 
27
- *Returns:* `true` if the sequence of elements defined by the range
28
- \[`first1`, `last1`) is lexicographically less than the sequence of
29
- elements defined by the range \[`first2`, `last2`) and `false`
30
- otherwise.
31
 
32
  *Complexity:* At most 2 min(`last1 - first1`, `last2 - first2`)
33
- applications of the corresponding comparison.
 
34
 
35
  *Remarks:* If two sequences have the same number of elements and their
36
  corresponding elements (if any) are equivalent, then neither sequence is
37
- lexicographically less than the other. If one sequence is a prefix of
38
- the other, then the shorter sequence is lexicographically less than the
39
- longer sequence. Otherwise, the lexicographical comparison of the
40
- sequences yields the same result as the comparison of the first
41
  corresponding pair of elements that are not equivalent.
42
 
43
  [*Example 1*:
44
 
45
- The following sample implementation satisfies these requirements:
 
46
 
47
  ``` cpp
48
  for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
49
- if (*first1 < *first2) return true;
50
- if (*first2 < *first1) return false;
51
  }
52
  return first1 == last1 && first2 != last2;
53
  ```
54
 
55
  — *end example*]
 
1
  ### Lexicographical comparison <a id="alg.lex.comparison">[[alg.lex.comparison]]</a>
2
 
3
  ``` cpp
4
  template<class InputIterator1, class InputIterator2>
5
+ constexpr bool
6
  lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
7
  InputIterator2 first2, InputIterator2 last2);
8
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
9
  bool
10
  lexicographical_compare(ExecutionPolicy&& exec,
11
  ForwardIterator1 first1, ForwardIterator1 last1,
12
  ForwardIterator2 first2, ForwardIterator2 last2);
13
 
14
  template<class InputIterator1, class InputIterator2, class Compare>
15
+ constexpr bool
16
  lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
17
  InputIterator2 first2, InputIterator2 last2,
18
  Compare comp);
19
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
20
+ class Compare>
21
  bool
22
  lexicographical_compare(ExecutionPolicy&& exec,
23
  ForwardIterator1 first1, ForwardIterator1 last1,
24
  ForwardIterator2 first2, ForwardIterator2 last2,
25
  Compare comp);
26
+
27
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
28
+ class Proj1 = identity, class Proj2 = identity,
29
+ indirect_strict_weak_order<projected<I1, Proj1>,
30
+ projected<I2, Proj2>> Comp = ranges::less>
31
+ constexpr bool
32
+ ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
33
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
34
+ template<input_range R1, input_range R2, class Proj1 = identity,
35
+ class Proj2 = identity,
36
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
37
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
38
+ constexpr bool
39
+ ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
40
+ Proj1 proj1 = {}, Proj2 proj2 = {});
41
  ```
42
 
43
+ *Returns:* `true` if and only if the sequence of elements defined by the
44
+ range \[`first1`, `last1`) is lexicographically less than the sequence
45
+ of elements defined by the range \[`first2`, `last2`).
 
46
 
47
  *Complexity:* At most 2 min(`last1 - first1`, `last2 - first2`)
48
+ applications of the corresponding comparison and each projection, if
49
+ any.
50
 
51
  *Remarks:* If two sequences have the same number of elements and their
52
  corresponding elements (if any) are equivalent, then neither sequence is
53
+ lexicographically less than the other. If one sequence is a proper
54
+ prefix of the other, then the shorter sequence is lexicographically less
55
+ than the longer sequence. Otherwise, the lexicographical comparison of
56
+ the sequences yields the same result as the comparison of the first
57
  corresponding pair of elements that are not equivalent.
58
 
59
  [*Example 1*:
60
 
61
+ `ranges::lexicographical_compare(I1, S1, I2, S2, Comp, Proj1, Proj2)`
62
+ could be implemented as:
63
 
64
  ``` cpp
65
  for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
66
+ if (invoke(comp, invoke(proj1, *first1), invoke(proj2, *first2))) return true;
67
+ if (invoke(comp, invoke(proj2, *first2), invoke(proj1, *first1))) return false;
68
  }
69
  return first1 == last1 && first2 != last2;
70
  ```
71
 
72
  — *end example*]