From Jason Turner

[multimap]

C++20 → C++23 8.6 KB 72 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/tmpaqsm1hh0/{from.md → to.md} +45 -18
tmp/tmpaqsm1hh0/{from.md → to.md} RENAMED
@@ -1,18 +1,19 @@
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
@@ -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 multimap::iterator; // see [container.requirements]
41
  using const_iterator = implementation-defined // type of multimap::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;
@@ -46,10 +47,11 @@ namespace std {
46
  class value_compare {
47
  friend class multimap;
48
  protected:
49
  Compare comp;
50
  value_compare(Compare c) : comp(c) { }
 
51
  public:
52
  bool operator()(const value_type& x, const value_type& y) const {
53
  return comp(x.first, y.first);
54
  }
55
  };
@@ -59,21 +61,27 @@ namespace std {
59
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
60
  template<class InputIterator>
61
  multimap(InputIterator first, InputIterator last,
62
  const Compare& comp = Compare(),
63
  const Allocator& = Allocator());
 
 
 
64
  multimap(const multimap& x);
65
  multimap(multimap&& x);
66
  explicit multimap(const Allocator&);
67
- multimap(const multimap&, const Allocator&);
68
- multimap(multimap&&, const Allocator&);
69
  multimap(initializer_list<value_type>,
70
  const Compare& = Compare(),
71
  const Allocator& = Allocator());
72
  template<class InputIterator>
73
  multimap(InputIterator first, InputIterator last, const Allocator& a)
74
  : multimap(first, last, Compare(), a) { }
 
 
 
75
  multimap(initializer_list<value_type> il, const Allocator& a)
76
  : multimap(il, Compare(), a) { }
77
  ~multimap();
78
  multimap& operator=(const multimap& x);
79
  multimap& operator=(multimap&& x)
@@ -112,20 +120,24 @@ namespace std {
112
  iterator insert(const_iterator position, const value_type& x);
113
  iterator insert(const_iterator position, value_type&& x);
114
  template<class P> iterator insert(const_iterator position, P&& x);
115
  template<class InputIterator>
116
  void insert(InputIterator first, InputIterator last);
 
 
117
  void insert(initializer_list<value_type>);
118
 
119
  node_type extract(const_iterator position);
120
  node_type extract(const key_type& x);
 
121
  iterator insert(node_type&& nh);
122
  iterator insert(const_iterator hint, node_type&& nh);
123
 
124
  iterator erase(iterator position);
125
  iterator erase(const_iterator position);
126
  size_type erase(const key_type& x);
 
127
  iterator erase(const_iterator first, const_iterator last);
128
  void swap(multimap&)
129
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
130
  is_nothrow_swappable_v<Compare>);
131
  void clear() noexcept;
@@ -177,29 +189,32 @@ namespace std {
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
 
@@ -222,11 +237,23 @@ template<class InputIterator>
222
  *Effects:* Constructs an empty `multimap` using the specified comparison
223
  object and allocator, and inserts elements from the range \[`first`,
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);
 
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
+ (i.e., possibly containing multiple copies of the same key value) and
7
+ provides for fast retrieval of values of another type `T` based on the
8
+ keys. The `multimap` class supports bidirectional iterators.
9
 
10
+ A `multimap` 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]]. A `multimap` also provides most operations
15
  described in  [[associative.reqmts]] for equal keys. This means that a
16
  `multimap` supports the `a_eq` operations in  [[associative.reqmts]] but
17
  not the `a_uniq` operations. For a `multimap<Key,T>` the `key_type` is
18
  `Key` and the `value_type` is `pair<const Key,T>`. Descriptions are
19
  provided here only for operations on `multimap` that are not described
 
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 multimap::size_type; // see [container.requirements]
40
+ using difference_type = implementation-defined // type of multimap::difference_type; // see [container.requirements]
41
  using iterator = implementation-defined // type of multimap::iterator; // see [container.requirements]
42
  using const_iterator = implementation-defined // type of multimap::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;
 
47
  class value_compare {
48
  friend class multimap;
49
  protected:
50
  Compare comp;
51
  value_compare(Compare c) : comp(c) { }
52
+
53
  public:
54
  bool operator()(const value_type& x, const value_type& y) const {
55
  return comp(x.first, y.first);
56
  }
57
  };
 
61
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
62
  template<class InputIterator>
63
  multimap(InputIterator first, InputIterator last,
64
  const Compare& comp = Compare(),
65
  const Allocator& = Allocator());
66
+ template<container-compatible-range<value_type> R>
67
+ multimap(from_range_t, R&& rg,
68
+ const Compare& comp = Compare(), const Allocator& = Allocator());
69
  multimap(const multimap& x);
70
  multimap(multimap&& x);
71
  explicit multimap(const Allocator&);
72
+ multimap(const multimap&, const type_identity_t<Allocator>&);
73
+ multimap(multimap&&, const type_identity_t<Allocator>&);
74
  multimap(initializer_list<value_type>,
75
  const Compare& = Compare(),
76
  const Allocator& = Allocator());
77
  template<class InputIterator>
78
  multimap(InputIterator first, InputIterator last, const Allocator& a)
79
  : multimap(first, last, Compare(), a) { }
80
+ template<container-compatible-range<value_type> R>
81
+ multimap(from_range_t, R&& rg, const Allocator& a))
82
+ : multimap(from_range, std::forward<R>(rg), Compare(), a) { }
83
  multimap(initializer_list<value_type> il, const Allocator& a)
84
  : multimap(il, Compare(), a) { }
85
  ~multimap();
86
  multimap& operator=(const multimap& x);
87
  multimap& operator=(multimap&& x)
 
120
  iterator insert(const_iterator position, const value_type& x);
121
  iterator insert(const_iterator position, value_type&& x);
122
  template<class P> iterator insert(const_iterator position, P&& x);
123
  template<class InputIterator>
124
  void insert(InputIterator first, InputIterator last);
125
+ template<container-compatible-range<value_type> R>
126
+ void insert_range(R&& rg);
127
  void insert(initializer_list<value_type>);
128
 
129
  node_type extract(const_iterator position);
130
  node_type extract(const key_type& x);
131
+ template<class K> node_type extract(K&& x);
132
  iterator insert(node_type&& nh);
133
  iterator insert(const_iterator hint, node_type&& nh);
134
 
135
  iterator erase(iterator position);
136
  iterator erase(const_iterator position);
137
  size_type erase(const key_type& x);
138
+ template<class K> size_type erase(K&& x);
139
  iterator erase(const_iterator first, const_iterator last);
140
  void swap(multimap&)
141
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
142
  is_nothrow_swappable_v<Compare>);
143
  void clear() noexcept;
 
189
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
190
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
191
  -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
192
  Compare, Allocator>;
193
 
194
+ template<ranges::input_range R, class Compare = less<range-key-type<R>>,
195
+ class Allocator = allocator<range-to-alloc-type<R>>>
196
+ multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
197
+ -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>;
198
+
199
  template<class Key, class T, class Compare = less<Key>,
200
  class Allocator = allocator<pair<const Key, T>>>
201
  multimap(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
202
  -> multimap<Key, T, Compare, Allocator>;
203
 
204
  template<class InputIterator, class Allocator>
205
  multimap(InputIterator, InputIterator, Allocator)
206
  -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
207
  less<iter-key-type<InputIterator>>, Allocator>;
208
 
209
+ template<ranges::input_range R, class Allocator>
210
+ multimap(from_range_t, R&&, Allocator)
211
+ -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>;
212
+
213
  template<class Key, class T, class Allocator>
214
  multimap(initializer_list<pair<Key, T>>, Allocator)
215
  -> multimap<Key, T, less<Key>, Allocator>;
 
 
 
 
 
 
216
  }
217
  ```
218
 
219
  #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
220
 
 
237
  *Effects:* Constructs an empty `multimap` using the specified comparison
238
  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 with respect to `comp` and otherwise N log N, where N is
243
+ `last - first`.
244
+
245
+ ``` cpp
246
+ template<container-compatible-range<value_type> R>
247
+ multimap(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
248
+ ```
249
+
250
+ *Effects:* Constructs an empty `multimap` using the specified comparison
251
+ object and allocator, and inserts elements from the range `rg`.
252
+
253
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
254
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
255
 
256
  #### Modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
257
 
258
  ``` cpp
259
  template<class P> iterator insert(P&& x);