From Jason Turner

[multiset]

C++20 → C++23 8.1 KB 73 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpnyn27hvr/{from.md → to.md} +46 -19
tmp/tmpnyn27hvr/{from.md → to.md} RENAMED
@@ -1,18 +1,19 @@
1
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
2
 
3
  #### Overview <a id="multiset.overview">[[multiset.overview]]</a>
4
 
5
  A `multiset` is an associative container that supports equivalent keys
6
- (possibly contains multiple copies of the same key value) and provides
7
- for fast retrieval of the keys themselves. The `multiset` class supports
8
- bidirectional iterators.
9
 
10
- A `multiset` meets all of the requirements of a container, of a
11
- reversible container [[container.requirements]], of an associative
12
- container [[associative.reqmts]], and of an allocator-aware container (
13
- [[container.alloc.req]]). `multiset` also provides most operations
 
14
  described in  [[associative.reqmts]] for duplicate keys. This means that
15
  a `multiset` supports the `a_eq` operations in  [[associative.reqmts]]
16
  but not the `a_uniq` operations. For a `multiset<Key>` both the
17
  `key_type` and `value_type` are `Key`. Descriptions are provided here
18
  only for operations on `multiset` that are not described in one of these
@@ -33,12 +34,12 @@ namespace std {
33
  using allocator_type = Allocator;
34
  using pointer = typename allocator_traits<Allocator>::pointer;
35
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
36
  using reference = value_type&;
37
  using const_reference = const value_type&;
38
- using size_type = implementation-defined; // see [container.requirements]
39
- using difference_type = implementation-defined; // see [container.requirements]
40
  using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
41
  using const_iterator = implementation-defined // type of multiset::const_iterator; // see [container.requirements]
42
  using reverse_iterator = std::reverse_iterator<iterator>;
43
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
44
  using node_type = unspecified;
@@ -47,20 +48,26 @@ namespace std {
47
  multiset() : multiset(Compare()) { }
48
  explicit multiset(const Compare& comp, const Allocator& = Allocator());
49
  template<class InputIterator>
50
  multiset(InputIterator first, InputIterator last,
51
  const Compare& comp = Compare(), const Allocator& = Allocator());
 
 
 
52
  multiset(const multiset& x);
53
  multiset(multiset&& x);
54
  explicit multiset(const Allocator&);
55
- multiset(const multiset&, const Allocator&);
56
- multiset(multiset&&, const Allocator&);
57
  multiset(initializer_list<value_type>, const Compare& = Compare(),
58
  const Allocator& = Allocator());
59
  template<class InputIterator>
60
  multiset(InputIterator first, InputIterator last, const Allocator& a)
61
  : multiset(first, last, Compare(), a) { }
 
 
 
62
  multiset(initializer_list<value_type> il, const Allocator& a)
63
  : multiset(il, Compare(), a) { }
64
  ~multiset();
65
  multiset& operator=(const multiset& x);
66
  multiset& operator=(multiset&& x)
@@ -97,20 +104,25 @@ namespace std {
97
  iterator insert(value_type&& x);
98
  iterator insert(const_iterator position, const value_type& x);
99
  iterator insert(const_iterator position, value_type&& x);
100
  template<class InputIterator>
101
  void insert(InputIterator first, InputIterator last);
 
 
102
  void insert(initializer_list<value_type>);
103
 
104
  node_type extract(const_iterator position);
105
  node_type extract(const key_type& x);
 
106
  iterator insert(node_type&& nh);
107
  iterator insert(const_iterator hint, node_type&& nh);
108
 
109
- iterator erase(iterator position);
 
110
  iterator erase(const_iterator position);
111
  size_type erase(const key_type& x);
 
112
  iterator erase(const_iterator first, const_iterator last);
113
  void swap(multiset&)
114
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
115
  is_nothrow_swappable_v<Compare>);
116
  void clear() noexcept;
@@ -163,27 +175,30 @@ namespace std {
163
  class Allocator = allocator<iter-value-type<InputIterator>>>
164
  multiset(InputIterator, InputIterator,
165
  Compare = Compare(), Allocator = Allocator())
166
  -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
167
 
 
 
 
 
 
168
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
169
  multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
170
  -> multiset<Key, Compare, Allocator>;
171
 
172
  template<class InputIterator, class Allocator>
173
  multiset(InputIterator, InputIterator, Allocator)
174
  -> multiset<iter-value-type<InputIterator>,
175
  less<iter-value-type<InputIterator>>, Allocator>;
176
 
 
 
 
 
177
  template<class Key, class Allocator>
178
  multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
179
-
180
- // swap
181
- template<class Key, class Compare, class Allocator>
182
- void swap(multiset<Key, Compare, Allocator>& x,
183
- multiset<Key, Compare, Allocator>& y)
184
- noexcept(noexcept(x.swap(y)));
185
  }
186
  ```
187
 
188
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
189
 
@@ -205,11 +220,23 @@ template<class InputIterator>
205
  *Effects:* Constructs an empty `multiset` using the specified comparison
206
  object and allocator, and inserts elements from the range \[`first`,
207
  `last`).
208
 
209
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
210
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
211
 
212
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
213
 
214
  ``` cpp
215
  template<class Key, class Compare, class Allocator, class Predicate>
 
1
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
2
 
3
  #### Overview <a id="multiset.overview">[[multiset.overview]]</a>
4
 
5
  A `multiset` is an associative container that supports equivalent keys
6
+ (i.e., possibly contains multiple copies of the same key value) and
7
+ provides for fast retrieval of the keys themselves. The `multiset` class
8
+ supports bidirectional iterators.
9
 
10
+ A `multiset` meets all of the requirements of a container
11
+ [[container.reqmts]], of a reversible container
12
+ [[container.rev.reqmts]], of an allocator-aware container
13
+ [[container.alloc.reqmts]], of an associative container
14
+ [[associative.reqmts]]. `multiset` also provides most operations
15
  described in  [[associative.reqmts]] for duplicate keys. This means that
16
  a `multiset` supports the `a_eq` operations in  [[associative.reqmts]]
17
  but not the `a_uniq` operations. For a `multiset<Key>` both the
18
  `key_type` and `value_type` are `Key`. Descriptions are provided here
19
  only for operations on `multiset` that are not described in one of these
 
34
  using allocator_type = Allocator;
35
  using pointer = typename allocator_traits<Allocator>::pointer;
36
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
37
  using reference = value_type&;
38
  using const_reference = const value_type&;
39
+ using size_type = implementation-defined // type of multiset::size_type; // see [container.requirements]
40
+ using difference_type = implementation-defined // type of multiset::difference_type; // see [container.requirements]
41
  using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
42
  using const_iterator = implementation-defined // type of multiset::const_iterator; // see [container.requirements]
43
  using reverse_iterator = std::reverse_iterator<iterator>;
44
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
45
  using node_type = unspecified;
 
48
  multiset() : multiset(Compare()) { }
49
  explicit multiset(const Compare& comp, const Allocator& = Allocator());
50
  template<class InputIterator>
51
  multiset(InputIterator first, InputIterator last,
52
  const Compare& comp = Compare(), const Allocator& = Allocator());
53
+ template<container-compatible-range<value_type> R>
54
+ multiset(from_range_t, R&& rg,
55
+ const Compare& comp = Compare(), const Allocator& = Allocator());
56
  multiset(const multiset& x);
57
  multiset(multiset&& x);
58
  explicit multiset(const Allocator&);
59
+ multiset(const multiset&, const type_identity_t<Allocator>&);
60
+ multiset(multiset&&, const type_identity_t<Allocator>&);
61
  multiset(initializer_list<value_type>, const Compare& = Compare(),
62
  const Allocator& = Allocator());
63
  template<class InputIterator>
64
  multiset(InputIterator first, InputIterator last, const Allocator& a)
65
  : multiset(first, last, Compare(), a) { }
66
+ template<container-compatible-range<value_type> R>
67
+ multiset(from_range_t, R&& rg, const Allocator& a))
68
+ : multiset(from_range, std::forward<R>(rg), Compare(), a) { }
69
  multiset(initializer_list<value_type> il, const Allocator& a)
70
  : multiset(il, Compare(), a) { }
71
  ~multiset();
72
  multiset& operator=(const multiset& x);
73
  multiset& operator=(multiset&& x)
 
104
  iterator insert(value_type&& x);
105
  iterator insert(const_iterator position, const value_type& x);
106
  iterator insert(const_iterator position, value_type&& x);
107
  template<class InputIterator>
108
  void insert(InputIterator first, InputIterator last);
109
+ template<container-compatible-range<value_type> R>
110
+ void insert_range(R&& rg);
111
  void insert(initializer_list<value_type>);
112
 
113
  node_type extract(const_iterator position);
114
  node_type extract(const key_type& x);
115
+ template<class K> node_type extract(K&& x);
116
  iterator insert(node_type&& nh);
117
  iterator insert(const_iterator hint, node_type&& nh);
118
 
119
+ iterator erase(iterator position)
120
+ requires (!same_as<iterator, const_iterator>);
121
  iterator erase(const_iterator position);
122
  size_type erase(const key_type& x);
123
+ template<class K> size_type erase(K&& x);
124
  iterator erase(const_iterator first, const_iterator last);
125
  void swap(multiset&)
126
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
127
  is_nothrow_swappable_v<Compare>);
128
  void clear() noexcept;
 
175
  class Allocator = allocator<iter-value-type<InputIterator>>>
176
  multiset(InputIterator, InputIterator,
177
  Compare = Compare(), Allocator = Allocator())
178
  -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
179
 
180
+ template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
181
+ class Allocator = allocator<ranges::range_value_t<R>>>
182
+ multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
183
+ -> multiset<ranges::range_value_t<R>, Compare, Allocator>;
184
+
185
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
186
  multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
187
  -> multiset<Key, Compare, Allocator>;
188
 
189
  template<class InputIterator, class Allocator>
190
  multiset(InputIterator, InputIterator, Allocator)
191
  -> multiset<iter-value-type<InputIterator>,
192
  less<iter-value-type<InputIterator>>, Allocator>;
193
 
194
+ template<ranges::input_range R, class Allocator>
195
+ multiset(from_range_t, R&&, Allocator)
196
+ -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
197
+
198
  template<class Key, class Allocator>
199
  multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
 
 
 
 
 
 
200
  }
201
  ```
202
 
203
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
204
 
 
220
  *Effects:* Constructs an empty `multiset` using the specified comparison
221
  object and allocator, and inserts elements from the range \[`first`,
222
  `last`).
223
 
224
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
225
+ sorted with respect to `comp` and otherwise N log N, where N is
226
+ `last - first`.
227
+
228
+ ``` cpp
229
+ template<container-compatible-range<value_type> R>
230
+ multiset(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
231
+ ```
232
+
233
+ *Effects:* Constructs an empty `multiset` using the specified comparison
234
+ object and allocator, and inserts elements from the range `rg`.
235
+
236
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
237
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
238
 
239
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
240
 
241
  ``` cpp
242
  template<class Key, class Compare, class Allocator, class Predicate>