From Jason Turner

[priority.queue]

C++20 → C++23 10.9 KB 163 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp4dwu90iw/{from.md → to.md} +145 -11
tmp/tmp4dwu90iw/{from.md → to.md} RENAMED
@@ -30,28 +30,47 @@ namespace std {
30
  public:
31
  priority_queue() : priority_queue(Compare()) {}
32
  explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
33
  priority_queue(const Compare& x, const Container&);
34
  priority_queue(const Compare& x, Container&&);
 
 
35
  template<class InputIterator>
36
  priority_queue(InputIterator first, InputIterator last, const Compare& x,
37
  const Container&);
38
  template<class InputIterator>
39
- priority_queue(InputIterator first, InputIterator last,
40
- const Compare& x = Compare(), Container&& = Container());
 
 
41
  template<class Alloc> explicit priority_queue(const Alloc&);
42
  template<class Alloc> priority_queue(const Compare&, const Alloc&);
43
  template<class Alloc> priority_queue(const Compare&, const Container&, const Alloc&);
44
  template<class Alloc> priority_queue(const Compare&, Container&&, const Alloc&);
45
  template<class Alloc> priority_queue(const priority_queue&, const Alloc&);
46
  template<class Alloc> priority_queue(priority_queue&&, const Alloc&);
 
 
 
 
 
 
 
 
 
 
 
 
 
47
 
48
  [[nodiscard]] bool empty() const { return c.empty(); }
49
  size_type size() const { return c.size(); }
50
  const_reference top() const { return c.front(); }
51
  void push(const value_type& x);
52
  void push(value_type&& x);
 
 
53
  template<class... Args> void emplace(Args&&... args);
54
  void pop();
55
  void swap(priority_queue& q) noexcept(is_nothrow_swappable_v<Container> &&
56
  is_nothrow_swappable_v<Compare>)
57
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }
@@ -60,25 +79,49 @@ namespace std {
60
  template<class Compare, class Container>
61
  priority_queue(Compare, Container)
62
  -> priority_queue<typename Container::value_type, Container, Compare>;
63
 
64
  template<class InputIterator,
65
- class Compare = less<typename iterator_traits<InputIterator>::value_type>,
66
- class Container = vector<typename iterator_traits<InputIterator>::value_type>>
67
  priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
68
- -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>;
 
 
 
 
69
 
70
  template<class Compare, class Container, class Allocator>
71
  priority_queue(Compare, Container, Allocator)
72
  -> priority_queue<typename Container::value_type, Container, Compare>;
73
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
74
  // no equality is provided
75
 
76
- template<class T, class Container, class Compare>
77
- void swap(priority_queue<T, Container, Compare>& x,
78
- priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
79
-
80
  template<class T, class Container, class Compare, class Alloc>
81
  struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
82
  : uses_allocator<Container, Alloc>::type { };
83
  }
84
  ```
@@ -94,25 +137,46 @@ priority_queue(const Compare& x, Container&& y);
94
 
95
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
96
  constructing or move constructing as appropriate); calls
97
  `make_heap(c.begin(), c.end(), comp)`.
98
 
 
 
 
 
 
 
 
 
 
 
 
99
  ``` cpp
100
  template<class InputIterator>
101
  priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
102
  template<class InputIterator>
103
- priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare(),
104
- Container&& y = Container());
105
  ```
106
 
107
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
108
 
109
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
110
  constructing or move constructing as appropriate); calls
111
  `c.insert(c.end(), first, last)`; and finally calls
112
  `make_heap(c.begin(), c.end(), comp)`.
113
 
 
 
 
 
 
 
 
 
 
 
 
114
  #### Constructors with allocators <a id="priqueue.cons.alloc">[[priqueue.cons.alloc]]</a>
115
 
116
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
117
  in this subclause shall not participate in overload resolution.
118
 
@@ -160,10 +224,68 @@ template<class Alloc> priority_queue(priority_queue&& q, const Alloc& a);
160
 
161
  *Effects:* Initializes `c` with `std::move(q.c)` as the first argument
162
  and `a` as the second argument, and initializes `comp` with
163
  `std::move(q.comp)`.
164
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
165
  #### Members <a id="priqueue.members">[[priqueue.members]]</a>
166
 
167
  ``` cpp
168
  void push(const value_type& x);
169
  ```
@@ -184,10 +306,22 @@ void push(value_type&& x);
184
  ``` cpp
185
  c.push_back(std::move(x));
186
  push_heap(c.begin(), c.end(), comp);
187
  ```
188
 
 
 
 
 
 
 
 
 
 
 
 
 
189
  ``` cpp
190
  template<class... Args> void emplace(Args&&... args);
191
  ```
192
 
193
  *Effects:* As if by:
 
30
  public:
31
  priority_queue() : priority_queue(Compare()) {}
32
  explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
33
  priority_queue(const Compare& x, const Container&);
34
  priority_queue(const Compare& x, Container&&);
35
+ template<class InputIterator>
36
+ priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
37
  template<class InputIterator>
38
  priority_queue(InputIterator first, InputIterator last, const Compare& x,
39
  const Container&);
40
  template<class InputIterator>
41
+ priority_queue(InputIterator first, InputIterator last, const Compare& x,
42
+ Container&&);
43
+ template<container-compatible-range<T> R>
44
+ priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
45
  template<class Alloc> explicit priority_queue(const Alloc&);
46
  template<class Alloc> priority_queue(const Compare&, const Alloc&);
47
  template<class Alloc> priority_queue(const Compare&, const Container&, const Alloc&);
48
  template<class Alloc> priority_queue(const Compare&, Container&&, const Alloc&);
49
  template<class Alloc> priority_queue(const priority_queue&, const Alloc&);
50
  template<class Alloc> priority_queue(priority_queue&&, const Alloc&);
51
+ template<class InputIterator, class Alloc>
52
+ priority_queue(InputIterator, InputIterator, const Alloc&);
53
+ template<class InputIterator, class Alloc>
54
+ priority_queue(InputIterator, InputIterator, const Compare&, const Alloc&);
55
+ template<class InputIterator, class Alloc>
56
+ priority_queue(InputIterator, InputIterator, const Compare&, const Container&,
57
+ const Alloc&);
58
+ template<class InputIterator, class Alloc>
59
+ priority_queue(InputIterator, InputIterator, const Compare&, Container&&, const Alloc&);
60
+ template<container-compatible-range<T> R, class Alloc>
61
+ priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&);
62
+ template<container-compatible-range<T> R, class Alloc>
63
+ priority_queue(from_range_t, R&& rg, const Alloc&);
64
 
65
  [[nodiscard]] bool empty() const { return c.empty(); }
66
  size_type size() const { return c.size(); }
67
  const_reference top() const { return c.front(); }
68
  void push(const value_type& x);
69
  void push(value_type&& x);
70
+ template<container-compatible-range<T> R>
71
+ void push_range(R&& rg);
72
  template<class... Args> void emplace(Args&&... args);
73
  void pop();
74
  void swap(priority_queue& q) noexcept(is_nothrow_swappable_v<Container> &&
75
  is_nothrow_swappable_v<Compare>)
76
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }
 
79
  template<class Compare, class Container>
80
  priority_queue(Compare, Container)
81
  -> priority_queue<typename Container::value_type, Container, Compare>;
82
 
83
  template<class InputIterator,
84
+ class Compare = less<iter-value-type<InputIterator>>,
85
+ class Container = vector<iter-value-type<InputIterator>>>
86
  priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
87
+ -> priority_queue<iter-value-type<InputIterator>, Container, Compare>;
88
+
89
+ template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>>
90
+ priority_queue(from_range_t, R&&, Compare = Compare())
91
+ -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>>, Compare>;
92
 
93
  template<class Compare, class Container, class Allocator>
94
  priority_queue(Compare, Container, Allocator)
95
  -> priority_queue<typename Container::value_type, Container, Compare>;
96
 
97
+ template<class InputIterator, class Allocator>
98
+ priority_queue(InputIterator, InputIterator, Allocator)
99
+ -> priority_queue<iter-value-type<InputIterator>,
100
+ vector<iter-value-type<InputIterator>, Allocator>,
101
+ less<iter-value-type<InputIterator>>>;
102
+
103
+ template<class InputIterator, class Compare, class Allocator>
104
+ priority_queue(InputIterator, InputIterator, Compare, Allocator)
105
+ -> priority_queue<iter-value-type<InputIterator>,
106
+ vector<iter-value-type<InputIterator>, Allocator>, Compare>;
107
+
108
+ template<class InputIterator, class Compare, class Container, class Allocator>
109
+ priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
110
+ -> priority_queue<typename Container::value_type, Container, Compare>;
111
+
112
+ template<ranges::input_range R, class Compare, class Allocator>
113
+ priority_queue(from_range_t, R&&, Compare, Allocator)
114
+ -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>,
115
+ Compare>;
116
+
117
+ template<ranges::input_range R, class Allocator>
118
+ priority_queue(from_range_t, R&&, Allocator)
119
+ -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>>;
120
+
121
  // no equality is provided
122
 
 
 
 
 
123
  template<class T, class Container, class Compare, class Alloc>
124
  struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
125
  : uses_allocator<Container, Alloc>::type { };
126
  }
127
  ```
 
137
 
138
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
139
  constructing or move constructing as appropriate); calls
140
  `make_heap(c.begin(), c.end(), comp)`.
141
 
142
+ ``` cpp
143
+ template<class InputIterator>
144
+ priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
145
+ ```
146
+
147
+ *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
148
+
149
+ *Effects:* Initializes `c` with `first` as the first argument and `last`
150
+ as the second argument, and initializes `comp` with `x`; then calls
151
+ `make_heap(c.begin(), c.end(), comp)`.
152
+
153
  ``` cpp
154
  template<class InputIterator>
155
  priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
156
  template<class InputIterator>
157
+ priority_queue(InputIterator first, InputIterator last, const Compare& x, Container&& y);
 
158
  ```
159
 
160
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
161
 
162
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
163
  constructing or move constructing as appropriate); calls
164
  `c.insert(c.end(), first, last)`; and finally calls
165
  `make_heap(c.begin(), c.end(), comp)`.
166
 
167
+ ``` cpp
168
+ template<container-compatible-range<T> R>
169
+ priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
170
+ ```
171
+
172
+ *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
173
+
174
+ *Effects:* Initializes `comp` with `x` and `c` with
175
+ `ranges::to<Container>(std::forward<R>(rg))` and finally calls
176
+ `make_heap(c.begin(), c.end(), comp)`.
177
+
178
  #### Constructors with allocators <a id="priqueue.cons.alloc">[[priqueue.cons.alloc]]</a>
179
 
180
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
181
  in this subclause shall not participate in overload resolution.
182
 
 
224
 
225
  *Effects:* Initializes `c` with `std::move(q.c)` as the first argument
226
  and `a` as the second argument, and initializes `comp` with
227
  `std::move(q.comp)`.
228
 
229
+ ``` cpp
230
+ template<class InputIterator, class Alloc>
231
+ priority_queue(InputIterator first, InputIterator last, const Alloc& a);
232
+ ```
233
+
234
+ *Effects:* Initializes `c` with `first` as the first argument, `last` as
235
+ the second argument, and `a` as the third argument, and
236
+ value-initializes `comp`; calls `make_heap(c.begin(), c.end(), comp)`.
237
+
238
+ ``` cpp
239
+ template<class InputIterator, class Alloc>
240
+ priority_queue(InputIterator first, InputIterator last, const Compare& compare, const Alloc& a);
241
+ ```
242
+
243
+ *Effects:* Initializes `c` with `first` as the first argument, `last` as
244
+ the second argument, and `a` as the third argument, and initializes
245
+ `comp` with `compare`; calls `make_heap(c.begin(), c.end(), comp)`.
246
+
247
+ ``` cpp
248
+ template<class InputIterator, class Alloc>
249
+ priority_queue(InputIterator first, InputIterator last, const Compare& compare,
250
+ const Container& cont, const Alloc& a);
251
+ ```
252
+
253
+ *Effects:* Initializes `c` with `cont` as the first argument and `a` as
254
+ the second argument, and initializes `comp` with `compare`; calls
255
+ `c.insert(c.end(), first, last)`; and finally calls
256
+ `make_heap(c.begin(), c.end(), comp)`.
257
+
258
+ ``` cpp
259
+ template<class InputIterator, class Alloc>
260
+ priority_queue(InputIterator first, InputIterator last, const Compare& compare, Container&& cont,
261
+ const Alloc& a);
262
+ ```
263
+
264
+ *Effects:* Initializes `c` with `std::move(cont)` as the first argument
265
+ and `a` as the second argument, and initializes `comp` with `compare`;
266
+ calls `c.insert(c.end(), first, last)`; and finally calls
267
+ `make_heap(c.begin(), c.end(), comp)`.
268
+
269
+ ``` cpp
270
+ template<container-compatible-range<T> R, class Alloc>
271
+ priority_queue(from_range_t, R&& rg, const Compare& compare, const Alloc& a);
272
+ ```
273
+
274
+ *Effects:* Initializes `comp` with `compare` and `c` with
275
+ `ranges::to<Container>(std::forward<R>(rg), a)`; calls
276
+ `make_heap(c.begin(), c.end(), comp)`.
277
+
278
+ ``` cpp
279
+ template<container-compatible-range<T> R, class Alloc>
280
+ priority_queue(from_range_t, R&& rg, const Alloc& a);
281
+ ```
282
+
283
+ *Effects:* Initializes `c` with
284
+ `ranges::to<Container>(std::forward<R>(rg), a)`; calls
285
+ `make_heap(c.begin(), c.end(), comp)`.
286
+
287
  #### Members <a id="priqueue.members">[[priqueue.members]]</a>
288
 
289
  ``` cpp
290
  void push(const value_type& x);
291
  ```
 
306
  ``` cpp
307
  c.push_back(std::move(x));
308
  push_heap(c.begin(), c.end(), comp);
309
  ```
310
 
311
+ ``` cpp
312
+ template<container-compatible-range<T> R>
313
+ void push_range(R&& rg);
314
+ ```
315
+
316
+ *Effects:* Inserts all elements of `rg` in `c` via
317
+ `c.append_range(std::forward<R>(rg))` if that is a valid expression, or
318
+ `ranges::copy(rg, back_inserter(c))` otherwise. Then restores the heap
319
+ property as if by `make_heap(c.begin(), c.end(), comp)`.
320
+
321
+ *Ensures:* `is_heap(c.begin(), c.end(), comp)` is `true`.
322
+
323
  ``` cpp
324
  template<class... Args> void emplace(Args&&... args);
325
  ```
326
 
327
  *Effects:* As if by: