From Jason Turner

[multiset]

C++23 → Trunk 14.9 KB 187 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpj8ww_o9h/{from.md → to.md} +92 -87
tmp/tmpj8ww_o9h/{from.md → to.md} RENAMED
@@ -8,20 +8,23 @@ 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
20
  tables and for operations where there is additional semantic
21
  information.
22
 
 
 
 
23
  ``` cpp
24
  namespace std {
25
  template<class Key, class Compare = less<Key>,
26
  class Allocator = allocator<Key>>
27
  class multiset {
@@ -30,12 +33,12 @@ namespace std {
30
  using key_type = Key;
31
  using key_compare = Compare;
32
  using value_type = Key;
33
  using value_compare = Compare;
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]
@@ -43,133 +46,134 @@ namespace std {
43
  using reverse_iterator = std::reverse_iterator<iterator>;
44
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
45
  using node_type = unspecified;
46
 
47
  // [multiset.cons], construct/copy/destroy
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)
74
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
75
  is_nothrow_move_assignable_v<Compare>);
76
- multiset& operator=(initializer_list<value_type>);
77
- allocator_type get_allocator() const noexcept;
78
 
79
  // iterators
80
- iterator begin() noexcept;
81
- const_iterator begin() const noexcept;
82
- iterator end() noexcept;
83
- const_iterator end() const noexcept;
84
 
85
- reverse_iterator rbegin() noexcept;
86
- const_reverse_iterator rbegin() const noexcept;
87
- reverse_iterator rend() noexcept;
88
- const_reverse_iterator rend() const noexcept;
89
 
90
- const_iterator cbegin() const noexcept;
91
- const_iterator cend() const noexcept;
92
- const_reverse_iterator crbegin() const noexcept;
93
- const_reverse_iterator crend() const noexcept;
94
 
95
  // capacity
96
- [[nodiscard]] bool empty() const noexcept;
97
- size_type size() const noexcept;
98
- size_type max_size() const noexcept;
99
 
100
  // modifiers
101
- template<class... Args> iterator emplace(Args&&... args);
102
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
103
- iterator insert(const value_type& 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;
129
 
130
  template<class C2>
131
- void merge(multiset<Key, C2, Allocator>& source);
132
  template<class C2>
133
- void merge(multiset<Key, C2, Allocator>&& source);
134
  template<class C2>
135
- void merge(set<Key, C2, Allocator>& source);
136
  template<class C2>
137
- void merge(set<Key, C2, Allocator>&& source);
138
 
139
  // observers
140
- key_compare key_comp() const;
141
- value_compare value_comp() const;
142
 
143
  // set operations
144
- iterator find(const key_type& x);
145
- const_iterator find(const key_type& x) const;
146
- template<class K> iterator find(const K& x);
147
- template<class K> const_iterator find(const K& x) const;
148
 
149
- size_type count(const key_type& x) const;
150
- template<class K> size_type count(const K& x) const;
151
 
152
- bool contains(const key_type& x) const;
153
- template<class K> bool contains(const K& x) const;
154
 
155
- iterator lower_bound(const key_type& x);
156
- const_iterator lower_bound(const key_type& x) const;
157
- template<class K> iterator lower_bound(const K& x);
158
- template<class K> const_iterator lower_bound(const K& x) const;
159
 
160
- iterator upper_bound(const key_type& x);
161
- const_iterator upper_bound(const key_type& x) const;
162
- template<class K> iterator upper_bound(const K& x);
163
- template<class K> const_iterator upper_bound(const K& x) const;
164
 
165
- pair<iterator, iterator> equal_range(const key_type& x);
166
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
167
  template<class K>
168
- pair<iterator, iterator> equal_range(const K& x);
169
  template<class K>
170
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
171
  };
172
 
173
  template<class InputIterator,
174
  class Compare = less<iter-value-type<InputIterator>>,
175
  class Allocator = allocator<iter-value-type<InputIterator>>>
@@ -201,21 +205,21 @@ namespace std {
201
  ```
202
 
203
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
204
 
205
  ``` cpp
206
- explicit multiset(const Compare& comp, const Allocator& = Allocator());
207
  ```
208
 
209
  *Effects:* Constructs an empty `multiset` using the specified comparison
210
  object and allocator.
211
 
212
  *Complexity:* Constant.
213
 
214
  ``` cpp
215
  template<class InputIterator>
216
- multiset(InputIterator first, InputIterator last,
217
  const Compare& comp = Compare(), const Allocator& = Allocator());
218
  ```
219
 
220
  *Effects:* Constructs an empty `multiset` using the specified comparison
221
  object and allocator, and inserts elements from the range \[`first`,
@@ -225,11 +229,12 @@ object and allocator, and inserts elements from the range \[`first`,
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
 
@@ -238,11 +243,11 @@ object and allocator, and inserts elements from the range `rg`.
238
 
239
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
240
 
241
  ``` cpp
242
  template<class Key, class Compare, class Allocator, class Predicate>
243
- typename multiset<Key, Compare, Allocator>::size_type
244
  erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
245
  ```
246
 
247
  *Effects:* Equivalent to:
248
 
 
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]], and 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
20
  tables and for operations where there is additional semantic
21
  information.
22
 
23
+ The types `iterator` and `const_iterator` meet the constexpr iterator
24
+ requirements [[iterator.requirements.general]].
25
+
26
  ``` cpp
27
  namespace std {
28
  template<class Key, class Compare = less<Key>,
29
  class Allocator = allocator<Key>>
30
  class multiset {
 
33
  using key_type = Key;
34
  using key_compare = Compare;
35
  using value_type = Key;
36
  using value_compare = Compare;
37
  using allocator_type = Allocator;
38
+ using pointer = allocator_traits<Allocator>::pointer;
39
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
40
  using reference = value_type&;
41
  using const_reference = const value_type&;
42
  using size_type = implementation-defined // type of multiset::size_type; // see [container.requirements]
43
  using difference_type = implementation-defined // type of multiset::difference_type; // see [container.requirements]
44
  using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
 
46
  using reverse_iterator = std::reverse_iterator<iterator>;
47
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
48
  using node_type = unspecified;
49
 
50
  // [multiset.cons], construct/copy/destroy
51
+ constexpr multiset() : multiset(Compare()) { }
52
+ constexpr explicit multiset(const Compare& comp, const Allocator& = Allocator());
53
  template<class InputIterator>
54
+ constexpr multiset(InputIterator first, InputIterator last,
55
  const Compare& comp = Compare(), const Allocator& = Allocator());
56
  template<container-compatible-range<value_type> R>
57
+ constexpr multiset(from_range_t, R&& rg,
58
  const Compare& comp = Compare(), const Allocator& = Allocator());
59
+ constexpr multiset(const multiset& x);
60
+ constexpr multiset(multiset&& x);
61
+ constexpr explicit multiset(const Allocator&);
62
+ constexpr multiset(const multiset&, const type_identity_t<Allocator>&);
63
+ constexpr multiset(multiset&&, const type_identity_t<Allocator>&);
64
+ constexpr multiset(initializer_list<value_type>, const Compare& = Compare(),
65
  const Allocator& = Allocator());
66
  template<class InputIterator>
67
+ constexpr multiset(InputIterator first, InputIterator last, const Allocator& a)
68
  : multiset(first, last, Compare(), a) { }
69
  template<container-compatible-range<value_type> R>
70
+ constexpr multiset(from_range_t, R&& rg, const Allocator& a)
71
  : multiset(from_range, std::forward<R>(rg), Compare(), a) { }
72
+ constexpr multiset(initializer_list<value_type> il, const Allocator& a)
73
  : multiset(il, Compare(), a) { }
74
+ constexpr ~multiset();
75
+ constexpr multiset& operator=(const multiset& x);
76
+ constexpr multiset& operator=(multiset&& x)
77
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
78
  is_nothrow_move_assignable_v<Compare>);
79
+ constexpr multiset& operator=(initializer_list<value_type>);
80
+ constexpr allocator_type get_allocator() const noexcept;
81
 
82
  // iterators
83
+ constexpr iterator begin() noexcept;
84
+ constexpr const_iterator begin() const noexcept;
85
+ constexpr iterator end() noexcept;
86
+ constexpr const_iterator end() const noexcept;
87
 
88
+ constexpr reverse_iterator rbegin() noexcept;
89
+ constexpr const_reverse_iterator rbegin() const noexcept;
90
+ constexpr reverse_iterator rend() noexcept;
91
+ constexpr const_reverse_iterator rend() const noexcept;
92
 
93
+ constexpr const_iterator cbegin() const noexcept;
94
+ constexpr const_iterator cend() const noexcept;
95
+ constexpr const_reverse_iterator crbegin() const noexcept;
96
+ constexpr const_reverse_iterator crend() const noexcept;
97
 
98
  // capacity
99
+ constexpr bool empty() const noexcept;
100
+ constexpr size_type size() const noexcept;
101
+ constexpr size_type max_size() const noexcept;
102
 
103
  // modifiers
104
+ template<class... Args> constexpr iterator emplace(Args&&... args);
105
+ template<class... Args>
106
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
107
+ constexpr iterator insert(const value_type& x);
108
+ constexpr iterator insert(value_type&& x);
109
+ constexpr iterator insert(const_iterator position, const value_type& x);
110
+ constexpr iterator insert(const_iterator position, value_type&& x);
111
  template<class InputIterator>
112
+ constexpr void insert(InputIterator first, InputIterator last);
113
  template<container-compatible-range<value_type> R>
114
+ constexpr void insert_range(R&& rg);
115
+ constexpr void insert(initializer_list<value_type>);
116
 
117
+ constexpr node_type extract(const_iterator position);
118
+ constexpr node_type extract(const key_type& x);
119
+ template<class K> constexpr node_type extract(K&& x);
120
+ constexpr iterator insert(node_type&& nh);
121
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
122
 
123
+ constexpr iterator erase(iterator position)
124
  requires (!same_as<iterator, const_iterator>);
125
+ constexpr iterator erase(const_iterator position);
126
+ constexpr size_type erase(const key_type& x);
127
+ template<class K> constexpr size_type erase(K&& x);
128
+ constexpr iterator erase(const_iterator first, const_iterator last);
129
+ constexpr void swap(multiset&)
130
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
131
  is_nothrow_swappable_v<Compare>);
132
+ constexpr void clear() noexcept;
133
 
134
  template<class C2>
135
+ constexpr void merge(multiset<Key, C2, Allocator>& source);
136
  template<class C2>
137
+ constexpr void merge(multiset<Key, C2, Allocator>&& source);
138
  template<class C2>
139
+ constexpr void merge(set<Key, C2, Allocator>& source);
140
  template<class C2>
141
+ constexpr void merge(set<Key, C2, Allocator>&& source);
142
 
143
  // observers
144
+ constexpr key_compare key_comp() const;
145
+ constexpr value_compare value_comp() const;
146
 
147
  // set operations
148
+ constexpr iterator find(const key_type& x);
149
+ constexpr const_iterator find(const key_type& x) const;
150
+ template<class K> constexpr iterator find(const K& x);
151
+ template<class K> constexpr const_iterator find(const K& x) const;
152
 
153
+ constexpr size_type count(const key_type& x) const;
154
+ template<class K> constexpr size_type count(const K& x) const;
155
 
156
+ constexpr bool contains(const key_type& x) const;
157
+ template<class K> constexpr bool contains(const K& x) const;
158
 
159
+ constexpr iterator lower_bound(const key_type& x);
160
+ constexpr const_iterator lower_bound(const key_type& x) const;
161
+ template<class K> constexpr iterator lower_bound(const K& x);
162
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
163
 
164
+ constexpr iterator upper_bound(const key_type& x);
165
+ constexpr const_iterator upper_bound(const key_type& x) const;
166
+ template<class K> constexpr iterator upper_bound(const K& x);
167
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
168
 
169
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
170
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
171
  template<class K>
172
+ constexpr pair<iterator, iterator> equal_range(const K& x);
173
  template<class K>
174
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
175
  };
176
 
177
  template<class InputIterator,
178
  class Compare = less<iter-value-type<InputIterator>>,
179
  class Allocator = allocator<iter-value-type<InputIterator>>>
 
205
  ```
206
 
207
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
208
 
209
  ``` cpp
210
+ constexpr explicit multiset(const Compare& comp, const Allocator& = Allocator());
211
  ```
212
 
213
  *Effects:* Constructs an empty `multiset` using the specified comparison
214
  object and allocator.
215
 
216
  *Complexity:* Constant.
217
 
218
  ``` cpp
219
  template<class InputIterator>
220
+ constexpr multiset(InputIterator first, InputIterator last,
221
  const Compare& comp = Compare(), const Allocator& = Allocator());
222
  ```
223
 
224
  *Effects:* Constructs an empty `multiset` using the specified comparison
225
  object and allocator, and inserts elements from the range \[`first`,
 
229
  sorted with respect to `comp` and otherwise N log N, where N is
230
  `last - first`.
231
 
232
  ``` cpp
233
  template<container-compatible-range<value_type> R>
234
+ constexpr multiset(from_range_t, R&& rg, const Compare& comp = Compare(),
235
+ const Allocator& = Allocator());
236
  ```
237
 
238
  *Effects:* Constructs an empty `multiset` using the specified comparison
239
  object and allocator, and inserts elements from the range `rg`.
240
 
 
243
 
244
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
245
 
246
  ``` cpp
247
  template<class Key, class Compare, class Allocator, class Predicate>
248
+ constexpr typename multiset<Key, Compare, Allocator>::size_type
249
  erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
250
  ```
251
 
252
  *Effects:* Equivalent to:
253