From Jason Turner

[priority.queue]

C++17 → C++20 7.9 KB 63 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/tmpn6yh7rlt/{from.md → to.md} +28 -28
tmp/tmpn6yh7rlt/{from.md → to.md} RENAMED
@@ -1,14 +1,16 @@
1
  ### Class template `priority_queue` <a id="priority.queue">[[priority.queue]]</a>
2
 
 
 
3
  Any sequence container with random access iterator and supporting
4
  operations `front()`, `push_back()` and `pop_back()` can be used to
5
- instantiate `priority_queue`. In particular, `vector` ([[vector]]) and
6
- `deque` ([[deque]]) can be used. Instantiating `priority_queue` also
7
  involves supplying a function or function object for making priority
8
  comparisons; the library assumes that the function or function object
9
- defines a strict weak ordering ([[alg.sorting]]).
10
 
11
  ``` cpp
12
  namespace std {
13
  template<class T, class Container = vector<T>,
14
  class Compare = less<typename Container::value_type>>
@@ -24,26 +26,28 @@ namespace std {
24
  protected:
25
  Container c;
26
  Compare comp;
27
 
28
  public:
 
 
29
  priority_queue(const Compare& x, const Container&);
30
- explicit priority_queue(const Compare& x = Compare(), Container&& = Container());
31
  template<class InputIterator>
32
- priority_queue(InputIterator first, InputIterator last,
33
- const Compare& x, const Container&);
34
  template<class InputIterator>
35
  priority_queue(InputIterator first, InputIterator last,
36
  const Compare& x = Compare(), Container&& = Container());
37
  template<class Alloc> explicit priority_queue(const Alloc&);
38
  template<class Alloc> priority_queue(const Compare&, const Alloc&);
39
  template<class Alloc> priority_queue(const Compare&, const Container&, const Alloc&);
40
  template<class Alloc> priority_queue(const Compare&, Container&&, const Alloc&);
41
  template<class Alloc> priority_queue(const priority_queue&, const Alloc&);
42
  template<class Alloc> priority_queue(priority_queue&&, const Alloc&);
43
 
44
- bool empty() const { return c.empty(); }
45
  size_type size() const { return c.size(); }
46
  const_reference top() const { return c.front(); }
47
  void push(const value_type& x);
48
  void push(value_type&& x);
49
  template<class... Args> void emplace(Args&&... args);
@@ -77,93 +81,90 @@ namespace std {
77
  struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
78
  : uses_allocator<Container, Alloc>::type { };
79
  }
80
  ```
81
 
82
- #### `priority_queue` constructors <a id="priqueue.cons">[[priqueue.cons]]</a>
83
 
84
  ``` cpp
85
  priority_queue(const Compare& x, const Container& y);
86
- explicit priority_queue(const Compare& x = Compare(), Container&& y = Container());
87
  ```
88
 
89
- *Requires:* `x` shall define a strict weak ordering ([[alg.sorting]]).
90
 
91
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
92
  constructing or move constructing as appropriate); calls
93
  `make_heap(c.begin(), c.end(), comp)`.
94
 
95
  ``` cpp
96
  template<class InputIterator>
97
- priority_queue(InputIterator first, InputIterator last,
98
- const Compare& x,
99
- const Container& y);
100
  template<class InputIterator>
101
- priority_queue(InputIterator first, InputIterator last,
102
- const Compare& x = Compare(),
103
  Container&& y = Container());
104
  ```
105
 
106
- *Requires:* `x` shall define a strict weak ordering ([[alg.sorting]]).
107
 
108
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
109
  constructing or move constructing as appropriate); calls
110
  `c.insert(c.end(), first, last)`; and finally calls
111
  `make_heap(c.begin(), c.end(), comp)`.
112
 
113
- #### `priority_queue` constructors with allocators <a id="priqueue.cons.alloc">[[priqueue.cons.alloc]]</a>
114
 
115
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
116
  in this subclause shall not participate in overload resolution.
117
 
118
  ``` cpp
119
  template<class Alloc> explicit priority_queue(const Alloc& a);
120
  ```
121
 
122
- *Effects:*  Initializes `c` with `a` and value-initializes `comp`.
123
 
124
  ``` cpp
125
  template<class Alloc> priority_queue(const Compare& compare, const Alloc& a);
126
  ```
127
 
128
- *Effects:*  Initializes `c` with `a` and initializes `comp` with
129
  `compare`.
130
 
131
  ``` cpp
132
  template<class Alloc>
133
  priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
134
  ```
135
 
136
- *Effects:*  Initializes `c` with `cont` as the first argument and `a` as
137
  the second argument, and initializes `comp` with `compare`; calls
138
  `make_heap(c.begin(), c.end(), comp)`.
139
 
140
  ``` cpp
141
  template<class Alloc>
142
  priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
143
  ```
144
 
145
- *Effects:*  Initializes `c` with `std::move(cont)` as the first argument
146
  and `a` as the second argument, and initializes `comp` with `compare`;
147
  calls `make_heap(c.begin(), c.end(), comp)`.
148
 
149
  ``` cpp
150
  template<class Alloc> priority_queue(const priority_queue& q, const Alloc& a);
151
  ```
152
 
153
- *Effects:*  Initializes `c` with `q.c` as the first argument and `a` as
154
  the second argument, and initializes `comp` with `q.comp`.
155
 
156
  ``` cpp
157
  template<class Alloc> priority_queue(priority_queue&& q, const Alloc& a);
158
  ```
159
 
160
- *Effects:*  Initializes `c` with `std::move(q.c)` as the first argument
161
  and `a` as the second argument, and initializes `comp` with
162
  `std::move(q.comp)`.
163
 
164
- #### `priority_queue` members <a id="priqueue.members">[[priqueue.members]]</a>
165
 
166
  ``` cpp
167
  void push(const value_type& x);
168
  ```
169
 
@@ -184,11 +185,11 @@ void push(value_type&& x);
184
  c.push_back(std::move(x));
185
  push_heap(c.begin(), c.end(), comp);
186
  ```
187
 
188
  ``` cpp
189
- template <class... Args> void emplace(Args&&... args)
190
  ```
191
 
192
  *Effects:* As if by:
193
 
194
  ``` cpp
@@ -205,19 +206,18 @@ void pop();
205
  ``` cpp
206
  pop_heap(c.begin(), c.end(), comp);
207
  c.pop_back();
208
  ```
209
 
210
- #### `priority_queue` specialized algorithms <a id="priqueue.special">[[priqueue.special]]</a>
211
 
212
  ``` cpp
213
  template<class T, class Container, class Compare>
214
  void swap(priority_queue<T, Container, Compare>& x,
215
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
216
  ```
217
 
218
- *Remarks:* This function shall not participate in overload resolution
219
- unless `is_swappable_v<Container>` is `true` and
220
  `is_swappable_v<Compare>` is `true`.
221
 
222
  *Effects:* As if by `x.swap(y)`.
223
 
 
1
  ### Class template `priority_queue` <a id="priority.queue">[[priority.queue]]</a>
2
 
3
+ #### Overview <a id="priqueue.overview">[[priqueue.overview]]</a>
4
+
5
  Any sequence container with random access iterator and supporting
6
  operations `front()`, `push_back()` and `pop_back()` can be used to
7
+ instantiate `priority_queue`. In particular, `vector` [[vector]] and
8
+ `deque` [[deque]] can be used. Instantiating `priority_queue` also
9
  involves supplying a function or function object for making priority
10
  comparisons; the library assumes that the function or function object
11
+ defines a strict weak ordering [[alg.sorting]].
12
 
13
  ``` cpp
14
  namespace std {
15
  template<class T, class Container = vector<T>,
16
  class Compare = less<typename Container::value_type>>
 
26
  protected:
27
  Container c;
28
  Compare comp;
29
 
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);
 
81
  struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
82
  : uses_allocator<Container, Alloc>::type { };
83
  }
84
  ```
85
 
86
+ #### Constructors <a id="priqueue.cons">[[priqueue.cons]]</a>
87
 
88
  ``` cpp
89
  priority_queue(const Compare& x, const Container& y);
90
+ priority_queue(const Compare& x, Container&& y);
91
  ```
92
 
93
+ *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
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
 
119
  ``` cpp
120
  template<class Alloc> explicit priority_queue(const Alloc& a);
121
  ```
122
 
123
+ *Effects:* Initializes `c` with `a` and value-initializes `comp`.
124
 
125
  ``` cpp
126
  template<class Alloc> priority_queue(const Compare& compare, const Alloc& a);
127
  ```
128
 
129
+ *Effects:* Initializes `c` with `a` and initializes `comp` with
130
  `compare`.
131
 
132
  ``` cpp
133
  template<class Alloc>
134
  priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
135
  ```
136
 
137
+ *Effects:* Initializes `c` with `cont` as the first argument and `a` as
138
  the second argument, and initializes `comp` with `compare`; calls
139
  `make_heap(c.begin(), c.end(), comp)`.
140
 
141
  ``` cpp
142
  template<class Alloc>
143
  priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
144
  ```
145
 
146
+ *Effects:* Initializes `c` with `std::move(cont)` as the first argument
147
  and `a` as the second argument, and initializes `comp` with `compare`;
148
  calls `make_heap(c.begin(), c.end(), comp)`.
149
 
150
  ``` cpp
151
  template<class Alloc> priority_queue(const priority_queue& q, const Alloc& a);
152
  ```
153
 
154
+ *Effects:* Initializes `c` with `q.c` as the first argument and `a` as
155
  the second argument, and initializes `comp` with `q.comp`.
156
 
157
  ``` cpp
158
  template<class Alloc> priority_queue(priority_queue&& q, const Alloc& a);
159
  ```
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
  ```
170
 
 
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:
194
 
195
  ``` cpp
 
206
  ``` cpp
207
  pop_heap(c.begin(), c.end(), comp);
208
  c.pop_back();
209
  ```
210
 
211
+ #### Specialized algorithms <a id="priqueue.special">[[priqueue.special]]</a>
212
 
213
  ``` cpp
214
  template<class T, class Container, class Compare>
215
  void swap(priority_queue<T, Container, Compare>& x,
216
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
217
  ```
218
 
219
+ *Constraints:* `is_swappable_v<Container>` is `true` and
 
220
  `is_swappable_v<Compare>` is `true`.
221
 
222
  *Effects:* As if by `x.swap(y)`.
223