From Jason Turner

[multimap]

C++17 → C++20 9.8 KB 115 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpn58qca7a/{from.md → to.md} +51 -56
tmp/tmpn58qca7a/{from.md → to.md} RENAMED
@@ -1,33 +1,33 @@
1
  ### Class template `multimap` <a id="multimap">[[multimap]]</a>
2
 
3
- #### Class template `multimap` overview <a id="multimap.overview">[[multimap.overview]]</a>
4
 
5
  A `multimap` is an associative container that supports equivalent keys
6
  (possibly containing multiple copies of the same key value) and provides
7
  for fast retrieval of values of another type `T` based on the keys. The
8
  `multimap` class supports bidirectional iterators.
9
 
10
- A `multimap` satisfies all of the requirements of a container and of a
11
- reversible container ([[container.requirements]]), of an associative
12
- container ([[associative.reqmts]]), and of an allocator-aware container
13
- (Table  [[tab:containers.allocatoraware]]). A `multimap` also provides
14
- most operations described in  [[associative.reqmts]] for equal keys.
15
- This means that a `multimap` supports the `a_eq` operations in 
16
- [[associative.reqmts]] but not the `a_uniq` operations. For a
17
- `multimap<Key,T>` the `key_type` is `Key` and the `value_type` is
18
- `pair<const Key,T>`. Descriptions are provided here only for operations
19
- on `multimap` that are not described in one of those tables or for
20
- operations where there is additional semantic information.
21
 
22
  ``` cpp
23
  namespace std {
24
  template<class Key, class T, class Compare = less<Key>,
25
  class Allocator = allocator<pair<const Key, T>>>
26
  class multimap {
27
  public:
28
- // types:
29
  using key_type = Key;
30
  using mapped_type = T;
31
  using value_type = pair<const Key, T>;
32
  using key_compare = Compare;
33
  using allocator_type = Allocator;
@@ -80,11 +80,11 @@ namespace std {
80
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
81
  is_nothrow_move_assignable_v<Compare>);
82
  multimap& operator=(initializer_list<value_type>);
83
  allocator_type get_allocator() const noexcept;
84
 
85
- // iterators:
86
  iterator begin() noexcept;
87
  const_iterator begin() const noexcept;
88
  iterator end() noexcept;
89
  const_iterator end() const noexcept;
90
 
@@ -96,12 +96,12 @@ namespace std {
96
  const_iterator cbegin() const noexcept;
97
  const_iterator cend() const noexcept;
98
  const_reverse_iterator crbegin() const noexcept;
99
  const_reverse_iterator crend() const noexcept;
100
 
101
- // capacity:
102
- bool empty() const noexcept;
103
  size_type size() const noexcept;
104
  size_type max_size() const noexcept;
105
 
106
  // [multimap.modifiers], modifiers
107
  template<class... Args> iterator emplace(Args&&... args);
@@ -137,23 +137,26 @@ namespace std {
137
  template<class C2>
138
  void merge(map<Key, T, C2, Allocator>& source);
139
  template<class C2>
140
  void merge(map<Key, T, C2, Allocator>&& source);
141
 
142
- // observers:
143
  key_compare key_comp() const;
144
  value_compare value_comp() const;
145
 
146
- // map operations:
147
  iterator find(const key_type& x);
148
  const_iterator find(const key_type& x) const;
149
  template<class K> iterator find(const K& x);
150
  template<class K> const_iterator find(const K& x) const;
151
 
152
  size_type count(const key_type& x) const;
153
  template<class K> size_type count(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
 
@@ -168,57 +171,39 @@ namespace std {
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, class Compare = less<iter_key_t<InputIterator>>,
174
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
175
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
176
- -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>;
 
177
 
178
  template<class Key, class T, class Compare = less<Key>,
179
  class Allocator = allocator<pair<const Key, T>>>
180
- multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
181
  -> multimap<Key, T, Compare, Allocator>;
182
 
183
  template<class InputIterator, class Allocator>
184
  multimap(InputIterator, InputIterator, Allocator)
185
- -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
186
- less<iter_key_t<InputIterator>>, Allocator>;
187
 
188
  template<class Key, class T, class Allocator>
189
- multimap(initializer_list<pair<const Key, T>>, Allocator)
190
  -> multimap<Key, T, less<Key>, Allocator>;
191
 
192
- template <class Key, class T, class Compare, class Allocator>
193
- bool operator==(const multimap<Key, T, Compare, Allocator>& x,
194
- const multimap<Key, T, Compare, Allocator>& y);
195
- template <class Key, class T, class Compare, class Allocator>
196
- bool operator< (const multimap<Key, T, Compare, Allocator>& x,
197
- const multimap<Key, T, Compare, Allocator>& y);
198
- template <class Key, class T, class Compare, class Allocator>
199
- bool operator!=(const multimap<Key, T, Compare, Allocator>& x,
200
- const multimap<Key, T, Compare, Allocator>& y);
201
- template <class Key, class T, class Compare, class Allocator>
202
- bool operator> (const multimap<Key, T, Compare, Allocator>& x,
203
- const multimap<Key, T, Compare, Allocator>& y);
204
- template <class Key, class T, class Compare, class Allocator>
205
- bool operator>=(const multimap<Key, T, Compare, Allocator>& x,
206
- const multimap<Key, T, Compare, Allocator>& y);
207
- template <class Key, class T, class Compare, class Allocator>
208
- bool operator<=(const multimap<Key, T, Compare, Allocator>& x,
209
- const multimap<Key, T, Compare, Allocator>& y);
210
-
211
- // [multimap.special], specialized algorithms
212
  template<class Key, class T, class Compare, class Allocator>
213
  void swap(multimap<Key, T, Compare, Allocator>& x,
214
  multimap<Key, T, Compare, Allocator>& y)
215
  noexcept(noexcept(x.swap(y)));
216
  }
217
  ```
218
 
219
- #### `multimap` constructors <a id="multimap.cons">[[multimap.cons]]</a>
220
 
221
  ``` cpp
222
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
223
  ```
224
 
@@ -239,30 +224,40 @@ object and allocator, and inserts elements from the range \[`first`,
239
  `last`).
240
 
241
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
242
  sorted using `comp` and otherwise N log N, where N is `last - first`.
243
 
244
- #### `multimap` modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
245
 
246
  ``` cpp
247
  template<class P> iterator insert(P&& x);
248
  template<class P> iterator insert(const_iterator position, P&& x);
249
  ```
250
 
 
 
251
  *Effects:* The first form is equivalent to
252
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
253
  `return emplace_hint(position, std::forward<P>(x))`.
254
 
255
- *Remarks:* These signatures shall not participate in overload resolution
256
- unless `is_constructible_v<value_type, P&&>` is `true`.
257
-
258
- #### `multimap` specialized algorithms <a id="multimap.special">[[multimap.special]]</a>
259
 
260
  ``` cpp
261
- template <class Key, class T, class Compare, class Allocator>
262
- void swap(multimap<Key, T, Compare, Allocator>& x,
263
- multimap<Key, T, Compare, Allocator>& y)
264
- noexcept(noexcept(x.swap(y)));
265
  ```
266
 
267
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
268
 
 
1
  ### Class template `multimap` <a id="multimap">[[multimap]]</a>
2
 
3
+ #### Overview <a id="multimap.overview">[[multimap.overview]]</a>
4
 
5
  A `multimap` is an associative container that supports equivalent keys
6
  (possibly containing multiple copies of the same key value) and provides
7
  for fast retrieval of values of another type `T` based on the keys. The
8
  `multimap` class supports bidirectional iterators.
9
 
10
+ A `multimap` meets all of the requirements of a container and of a
11
+ reversible container [[container.requirements]], of an associative
12
+ container [[associative.reqmts]], and of an allocator-aware container (
13
+ [[container.alloc.req]]). A `multimap` also provides most operations
14
+ described in  [[associative.reqmts]] for equal keys. This means that a
15
+ `multimap` supports the `a_eq` operations in  [[associative.reqmts]] but
16
+ not the `a_uniq` operations. For a `multimap<Key,T>` the `key_type` is
17
+ `Key` and the `value_type` is `pair<const Key,T>`. Descriptions are
18
+ provided here only for operations on `multimap` that are not described
19
+ in one of those tables or for operations where there is additional
20
+ semantic information.
21
 
22
  ``` cpp
23
  namespace std {
24
  template<class Key, class T, class Compare = less<Key>,
25
  class Allocator = allocator<pair<const Key, T>>>
26
  class multimap {
27
  public:
28
+ // types
29
  using key_type = Key;
30
  using mapped_type = T;
31
  using value_type = pair<const Key, T>;
32
  using key_compare = Compare;
33
  using allocator_type = Allocator;
 
80
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
81
  is_nothrow_move_assignable_v<Compare>);
82
  multimap& operator=(initializer_list<value_type>);
83
  allocator_type get_allocator() const noexcept;
84
 
85
+ // iterators
86
  iterator begin() noexcept;
87
  const_iterator begin() const noexcept;
88
  iterator end() noexcept;
89
  const_iterator end() const noexcept;
90
 
 
96
  const_iterator cbegin() const noexcept;
97
  const_iterator cend() const noexcept;
98
  const_reverse_iterator crbegin() const noexcept;
99
  const_reverse_iterator crend() const noexcept;
100
 
101
+ // capacity
102
+ [[nodiscard]] bool empty() const noexcept;
103
  size_type size() const noexcept;
104
  size_type max_size() const noexcept;
105
 
106
  // [multimap.modifiers], modifiers
107
  template<class... Args> iterator emplace(Args&&... args);
 
137
  template<class C2>
138
  void merge(map<Key, T, C2, Allocator>& source);
139
  template<class C2>
140
  void merge(map<Key, T, C2, Allocator>&& source);
141
 
142
+ // observers
143
  key_compare key_comp() const;
144
  value_compare value_comp() const;
145
 
146
+ // map operations
147
  iterator find(const key_type& x);
148
  const_iterator find(const key_type& x) const;
149
  template<class K> iterator find(const K& x);
150
  template<class K> const_iterator find(const K& x) const;
151
 
152
  size_type count(const key_type& x) const;
153
  template<class K> size_type count(const K& x) const;
154
 
155
+ bool contains(const key_type& x) const;
156
+ template<class K> bool contains(const K& x) const;
157
+
158
  iterator lower_bound(const key_type& x);
159
  const_iterator lower_bound(const key_type& x) const;
160
  template<class K> iterator lower_bound(const K& x);
161
  template<class K> const_iterator lower_bound(const K& x) const;
162
 
 
171
  pair<iterator, iterator> equal_range(const K& x);
172
  template<class K>
173
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
174
  };
175
 
176
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
177
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
178
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
179
+ -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
180
+ Compare, Allocator>;
181
 
182
  template<class Key, class T, class Compare = less<Key>,
183
  class Allocator = allocator<pair<const Key, T>>>
184
+ multimap(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
185
  -> multimap<Key, T, Compare, Allocator>;
186
 
187
  template<class InputIterator, class Allocator>
188
  multimap(InputIterator, InputIterator, Allocator)
189
+ -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
190
+ less<iter-key-type<InputIterator>>, Allocator>;
191
 
192
  template<class Key, class T, class Allocator>
193
+ multimap(initializer_list<pair<Key, T>>, Allocator)
194
  -> multimap<Key, T, less<Key>, Allocator>;
195
 
196
+ // swap
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
197
  template<class Key, class T, class Compare, class Allocator>
198
  void swap(multimap<Key, T, Compare, Allocator>& x,
199
  multimap<Key, T, Compare, Allocator>& y)
200
  noexcept(noexcept(x.swap(y)));
201
  }
202
  ```
203
 
204
+ #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
205
 
206
  ``` cpp
207
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
208
  ```
209
 
 
224
  `last`).
225
 
226
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
227
  sorted using `comp` and otherwise N log N, where N is `last - first`.
228
 
229
+ #### Modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
230
 
231
  ``` cpp
232
  template<class P> iterator insert(P&& x);
233
  template<class P> iterator insert(const_iterator position, P&& x);
234
  ```
235
 
236
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
237
+
238
  *Effects:* The first form is equivalent to
239
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
240
  `return emplace_hint(position, std::forward<P>(x))`.
241
 
242
+ #### Erasure <a id="multimap.erasure">[[multimap.erasure]]</a>
 
 
 
243
 
244
  ``` cpp
245
+ template<class Key, class T, class Compare, class Allocator, class Predicate>
246
+ typename multimap<Key, T, Compare, Allocator>::size_type
247
+ erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
 
248
  ```
249
 
250
+ *Effects:* Equivalent to:
251
+
252
+ ``` cpp
253
+ auto original_size = c.size();
254
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
255
+ if (pred(*i)) {
256
+ i = c.erase(i);
257
+ } else {
258
+ ++i;
259
+ }
260
+ }
261
+ return original_size - c.size();
262
+ ```
263