From Jason Turner

[priority.queue]

C++14 → C++17 8.0 KB 91 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/tmp21r1k3fb/{from.md → to.md} +49 -34
tmp/tmp21r1k3fb/{from.md → to.md} RENAMED
@@ -12,15 +12,17 @@ defines a strict weak ordering ([[alg.sorting]]).
12
  namespace std {
13
  template <class T, class Container = vector<T>,
14
  class Compare = less<typename Container::value_type>>
15
  class priority_queue {
16
  public:
17
- typedef typename Container::value_type value_type;
18
- typedef typename Container::reference reference;
19
- typedef typename Container::const_reference const_reference;
20
- typedef typename Container::size_type size_type;
21
- typedef Container container_type;
 
 
22
  protected:
23
  Container c;
24
  Compare comp;
25
 
26
  public:
@@ -32,29 +34,43 @@ namespace std {
32
  template <class InputIterator>
33
  priority_queue(InputIterator first, InputIterator last,
34
  const Compare& x = Compare(), Container&& = Container());
35
  template <class Alloc> explicit priority_queue(const Alloc&);
36
  template <class Alloc> priority_queue(const Compare&, const Alloc&);
37
- template <class Alloc> priority_queue(const Compare&,
38
- const Container&, const Alloc&);
39
- template <class Alloc> priority_queue(const Compare&,
40
- 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);
50
  void pop();
51
- void swap(priority_queue& q) noexcept(
52
- noexcept(swap(c, q.c)) && noexcept(swap(comp, q.comp)))
53
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }
54
  };
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
55
  // no equality is provided
 
56
  template <class T, class Container, class Compare>
57
  void swap(priority_queue<T, Container, Compare>& x,
58
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
59
 
60
  template <class T, class Container, class Compare, class Alloc>
@@ -64,14 +80,12 @@ namespace std {
64
  ```
65
 
66
  #### `priority_queue` constructors <a id="priqueue.cons">[[priqueue.cons]]</a>
67
 
68
  ``` cpp
69
- priority_queue(const Compare& x,
70
- const Container& y);
71
- explicit priority_queue(const Compare& x = Compare(),
72
- Container&& y = Container());
73
  ```
74
 
75
  *Requires:* `x` shall define a strict weak ordering ([[alg.sorting]]).
76
 
77
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
@@ -96,24 +110,21 @@ constructing or move constructing as appropriate); calls
96
  `c.insert(c.end(), first, last)`; and finally calls
97
  `make_heap(c.begin(), c.end(), comp)`.
98
 
99
  #### `priority_queue` constructors with allocators <a id="priqueue.cons.alloc">[[priqueue.cons.alloc]]</a>
100
 
101
- If `uses_allocator<container_type, Alloc>::value` is `false` the
102
- constructors in this subclause shall not participate in overload
103
- resolution.
104
 
105
  ``` cpp
106
- template <class Alloc>
107
- explicit priority_queue(const Alloc& a);
108
  ```
109
 
110
  *Effects:*  Initializes `c` with `a` and value-initializes `comp`.
111
 
112
  ``` cpp
113
- template <class Alloc>
114
- priority_queue(const Compare& compare, const Alloc& a);
115
  ```
116
 
117
  *Effects:*  Initializes `c` with `a` and initializes `comp` with
118
  `compare`.
119
 
@@ -121,31 +132,31 @@ template <class Alloc>
121
  template <class Alloc>
122
  priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
123
  ```
124
 
125
  *Effects:*  Initializes `c` with `cont` as the first argument and `a` as
126
- the second argument, and initializes `comp` with `compare`.
 
127
 
128
  ``` cpp
129
  template <class Alloc>
130
  priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
131
  ```
132
 
133
  *Effects:*  Initializes `c` with `std::move(cont)` as the first argument
134
- and `a` as the second argument, and initializes `comp` with `compare`.
 
135
 
136
  ``` cpp
137
- template <class Alloc>
138
- priority_queue(const priority_queue& q, const Alloc& a);
139
  ```
140
 
141
  *Effects:*  Initializes `c` with `q.c` as the first argument and `a` as
142
  the second argument, and initializes `comp` with `q.comp`.
143
 
144
  ``` cpp
145
- template <class Alloc>
146
- priority_queue(priority_queue&& q, const Alloc& a);
147
  ```
148
 
149
  *Effects:*  Initializes `c` with `std::move(q.c)` as the first argument
150
  and `a` as the second argument, and initializes `comp` with
151
  `std::move(q.comp)`.
@@ -154,55 +165,59 @@ and `a` as the second argument, and initializes `comp` with
154
 
155
  ``` cpp
156
  void push(const value_type& x);
157
  ```
158
 
159
- *Effects:*
160
 
161
  ``` cpp
162
  c.push_back(x);
163
  push_heap(c.begin(), c.end(), comp);
164
  ```
165
 
166
  ``` cpp
167
  void push(value_type&& x);
168
  ```
169
 
170
- *Effects:*
171
 
172
  ``` cpp
173
  c.push_back(std::move(x));
174
  push_heap(c.begin(), c.end(), comp);
175
  ```
176
 
177
  ``` cpp
178
  template <class... Args> void emplace(Args&&... args)
179
  ```
180
 
181
- *Effects:*
182
 
183
  ``` cpp
184
  c.emplace_back(std::forward<Args>(args)...);
185
  push_heap(c.begin(), c.end(), comp);
186
  ```
187
 
188
  ``` cpp
189
  void pop();
190
  ```
191
 
192
- *Effects:*
193
 
194
  ``` cpp
195
  pop_heap(c.begin(), c.end(), comp);
196
  c.pop_back();
197
  ```
198
 
199
  #### `priority_queue` specialized algorithms <a id="priqueue.special">[[priqueue.special]]</a>
200
 
201
  ``` cpp
202
- template <class T, class Container, Compare>
203
  void swap(priority_queue<T, Container, Compare>& x,
204
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
205
  ```
206
 
207
- *Effects:* `x.swap(y)`.
 
 
 
 
208
 
 
12
  namespace std {
13
  template <class T, class Container = vector<T>,
14
  class Compare = less<typename Container::value_type>>
15
  class priority_queue {
16
  public:
17
+ using value_type = typename Container::value_type;
18
+ using reference = typename Container::reference;
19
+ using const_reference = typename Container::const_reference;
20
+ using size_type = typename Container::size_type;
21
+ using container_type = Container;
22
+ using value_compare = Compare;
23
+
24
  protected:
25
  Container c;
26
  Compare comp;
27
 
28
  public:
 
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);
50
  void pop();
51
+ void swap(priority_queue& q) noexcept(is_nothrow_swappable_v<Container> &&
52
+ is_nothrow_swappable_v<Compare>)
53
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }
54
  };
55
+
56
+ template<class Compare, class Container>
57
+ priority_queue(Compare, Container)
58
+ -> priority_queue<typename Container::value_type, Container, Compare>;
59
+
60
+ template<class InputIterator,
61
+ class Compare = less<typename iterator_traits<InputIterator>::value_type>,
62
+ class Container = vector<typename iterator_traits<InputIterator>::value_type>>
63
+ priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
64
+ -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>;
65
+
66
+ template<class Compare, class Container, class Allocator>
67
+ priority_queue(Compare, Container, Allocator)
68
+ -> priority_queue<typename Container::value_type, Container, Compare>;
69
+
70
  // no equality is provided
71
+
72
  template <class T, class Container, class Compare>
73
  void swap(priority_queue<T, Container, Compare>& x,
74
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
75
 
76
  template <class T, class Container, class Compare, class Alloc>
 
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
 
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
 
 
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)`.
 
165
 
166
  ``` cpp
167
  void push(const value_type& x);
168
  ```
169
 
170
+ *Effects:* As if by:
171
 
172
  ``` cpp
173
  c.push_back(x);
174
  push_heap(c.begin(), c.end(), comp);
175
  ```
176
 
177
  ``` cpp
178
  void push(value_type&& x);
179
  ```
180
 
181
+ *Effects:* As if by:
182
 
183
  ``` cpp
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
195
  c.emplace_back(std::forward<Args>(args)...);
196
  push_heap(c.begin(), c.end(), comp);
197
  ```
198
 
199
  ``` cpp
200
  void pop();
201
  ```
202
 
203
+ *Effects:* As if by:
204
 
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