From Jason Turner

[alg.merge]

C++14 → C++17 5.3 KB 69 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpzawpd0mu/{from.md → to.md} +48 -18
tmp/tmpzawpd0mu/{from.md → to.md} RENAMED
@@ -5,66 +5,96 @@ template<class InputIterator1, class InputIterator2,
5
  class OutputIterator>
6
  OutputIterator
7
  merge(InputIterator1 first1, InputIterator1 last1,
8
  InputIterator2 first2, InputIterator2 last2,
9
  OutputIterator result);
 
 
 
 
 
 
 
10
 
11
  template<class InputIterator1, class InputIterator2,
12
  class OutputIterator, class Compare>
13
  OutputIterator
14
  merge(InputIterator1 first1, InputIterator1 last1,
15
  InputIterator2 first2, InputIterator2 last2,
16
  OutputIterator result, Compare comp);
 
 
 
 
 
 
 
17
  ```
18
 
 
 
 
 
19
  *Effects:*  Copies all the elements of the two ranges \[`first1`,
20
  `last1`) and \[`first2`, `last2`) into the range \[`result`,
21
  `result_last`), where `result_last` is
22
  `result + (last1 - first1) + (last2 - first2)`, such that the resulting
23
  range satisfies `is_sorted(result, result_last)` or
24
  `is_sorted(result, result_last, comp)`, respectively.
25
 
26
- *Requires:* The ranges \[`first1`, `last1`) and \[`first2`, `last2`)
27
- shall be sorted with respect to `operator<` or `comp`. The resulting
28
- range shall not overlap with either of the original ranges.
29
-
30
  *Returns:* `result + (last1 - first1) + (last2 - first2)`.
31
 
32
- *Complexity:* At most `(last1 - first1) + (last2 - first2) - 1`
 
 
33
  comparisons.
 
34
 
35
  *Remarks:* Stable ([[algorithm.stable]]).
36
 
37
  ``` cpp
38
  template<class BidirectionalIterator>
39
  void inplace_merge(BidirectionalIterator first,
40
  BidirectionalIterator middle,
41
  BidirectionalIterator last);
 
 
 
 
 
42
 
43
  template<class BidirectionalIterator, class Compare>
44
  void inplace_merge(BidirectionalIterator first,
45
  BidirectionalIterator middle,
46
  BidirectionalIterator last, Compare comp);
 
 
 
 
 
47
  ```
48
 
49
- *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
50
- \[`middle`, `last`), putting the result of the merge into the range
51
- \[`first`, `last`). The resulting range will be in non-decreasing order;
52
- that is, for every iterator `i` in \[`first`, `last`) other than
53
- `first`, the condition `*i < *(i - 1)` or, respectively,
54
- `comp(*i, *(i - 1))` will be false.
55
-
56
  *Requires:* The ranges \[`first`, `middle`) and \[`middle`, `last`)
57
  shall be sorted with respect to `operator<` or `comp`.
58
  `BidirectionalIterator` shall satisfy the requirements of
59
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
60
  shall satisfy the requirements of `MoveConstructible`
61
- (Table  [[moveconstructible]]) and of `MoveAssignable`
62
- (Table  [[moveassignable]]).
63
 
64
- *Complexity:* When enough additional memory is available,
65
- `(last - first) - 1` comparisons. If no additional memory is available,
66
- an algorithm with complexity N log(N) (where `N` is equal to
67
- `last - first`) may be used.
 
 
 
 
 
 
 
 
 
 
68
 
69
  *Remarks:* Stable ([[algorithm.stable]]).
70
 
 
5
  class OutputIterator>
6
  OutputIterator
7
  merge(InputIterator1 first1, InputIterator1 last1,
8
  InputIterator2 first2, InputIterator2 last2,
9
  OutputIterator result);
10
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
11
+ class ForwardIterator>
12
+ ForwardIterator
13
+ merge(ExecutionPolicy&& exec,
14
+ ForwardIterator1 first1, ForwardIterator1 last1,
15
+ ForwardIterator2 first2, ForwardIterator2 last2,
16
+ ForwardIterator result);
17
 
18
  template<class InputIterator1, class InputIterator2,
19
  class OutputIterator, class Compare>
20
  OutputIterator
21
  merge(InputIterator1 first1, InputIterator1 last1,
22
  InputIterator2 first2, InputIterator2 last2,
23
  OutputIterator result, Compare comp);
24
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
25
+ class ForwardIterator, class Compare>
26
+ ForwardIterator
27
+ merge(ExecutionPolicy&& exec,
28
+ ForwardIterator1 first1, ForwardIterator1 last1,
29
+ ForwardIterator2 first2, ForwardIterator2 last2,
30
+ ForwardIterator result, Compare comp);
31
  ```
32
 
33
+ *Requires:* The ranges \[`first1`, `last1`) and \[`first2`, `last2`)
34
+ shall be sorted with respect to `operator<` or `comp`. The resulting
35
+ range shall not overlap with either of the original ranges.
36
+
37
  *Effects:*  Copies all the elements of the two ranges \[`first1`,
38
  `last1`) and \[`first2`, `last2`) into the range \[`result`,
39
  `result_last`), where `result_last` is
40
  `result + (last1 - first1) + (last2 - first2)`, such that the resulting
41
  range satisfies `is_sorted(result, result_last)` or
42
  `is_sorted(result, result_last, comp)`, respectively.
43
 
 
 
 
 
44
  *Returns:* `result + (last1 - first1) + (last2 - first2)`.
45
 
46
+ *Complexity:* Let N = `(last1 - first1) + (last2 - first2)`:
47
+
48
+ - For the overloads with no `ExecutionPolicy`, at most N - 1
49
  comparisons.
50
+ - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
51
 
52
  *Remarks:* Stable ([[algorithm.stable]]).
53
 
54
  ``` cpp
55
  template<class BidirectionalIterator>
56
  void inplace_merge(BidirectionalIterator first,
57
  BidirectionalIterator middle,
58
  BidirectionalIterator last);
59
+ template<class ExecutionPolicy, class BidirectionalIterator>
60
+ void inplace_merge(ExecutionPolicy&& exec,
61
+ BidirectionalIterator first,
62
+ BidirectionalIterator middle,
63
+ BidirectionalIterator last);
64
 
65
  template<class BidirectionalIterator, class Compare>
66
  void inplace_merge(BidirectionalIterator first,
67
  BidirectionalIterator middle,
68
  BidirectionalIterator last, Compare comp);
69
+ template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
70
+ void inplace_merge(ExecutionPolicy&& exec,
71
+ BidirectionalIterator first,
72
+ BidirectionalIterator middle,
73
+ BidirectionalIterator last, Compare comp);
74
  ```
75
 
 
 
 
 
 
 
 
76
  *Requires:* The ranges \[`first`, `middle`) and \[`middle`, `last`)
77
  shall be sorted with respect to `operator<` or `comp`.
78
  `BidirectionalIterator` shall satisfy the requirements of
79
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
80
  shall satisfy the requirements of `MoveConstructible`
81
+ (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
82
+ (Table  [[tab:moveassignable]]).
83
 
84
+ *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
85
+ \[`middle`, `last`), putting the result of the merge into the range
86
+ \[`first`, `last`). The resulting range will be in non-decreasing order;
87
+ that is, for every iterator `i` in \[`first`, `last`) other than
88
+ `first`, the condition `*i < *(i - 1)` or, respectively,
89
+ `comp(*i, *(i - 1))` will be `false`.
90
+
91
+ *Complexity:* Let N = `last - first`:
92
+
93
+ - For the overloads with no `ExecutionPolicy`, if enough additional
94
+ memory is available, exactly N - 1 comparisons.
95
+ - For the overloads with no `ExecutionPolicy` if no additional memory is
96
+ available, 𝑂(N log N) comparisons.
97
+ - For the overloads with an `ExecutionPolicy`, 𝑂(N log N) comparisons.
98
 
99
  *Remarks:* Stable ([[algorithm.stable]]).
100