From Jason Turner

[multimap]

C++14 → C++17 11.7 KB 130 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmppmv4hoh8/{from.md → to.md} +74 -46
tmp/tmppmv4hoh8/{from.md → to.md} RENAMED
@@ -9,13 +9,13 @@ for fast retrieval of values of another type `T` based on the keys. The
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
 
@@ -24,44 +24,41 @@ 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
- typedef Key key_type;
30
- typedef T mapped_type;
31
- typedef pair<const Key,T> value_type;
32
- typedef Compare key_compare;
33
- typedef Allocator allocator_type;
34
- typedef value_type& reference;
35
- typedef const value_type& const_reference;
36
- typedef implementation-defined iterator; // see [container.requirements]
37
- typedef implementation-defined const_iterator; // see [container.requirements]
38
- typedef implementation-defined size_type; // see [container.requirements]
39
- typedef implementation-defined difference_type;// see [container.requirements]
40
- typedef typename allocator_traits<Allocator>::pointer pointer;
41
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
42
- typedef std::reverse_iterator<iterator> reverse_iterator;
43
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
44
 
45
  class value_compare {
46
  friend class multimap;
47
  protected:
48
  Compare comp;
49
  value_compare(Compare c) : comp(c) { }
50
  public:
51
- typedef bool result_type;
52
- typedef value_type first_argument_type;
53
- typedef value_type second_argument_type;
54
  bool operator()(const value_type& x, const value_type& y) const {
55
  return comp(x.first, y.first);
56
  }
57
  };
58
 
59
- // construct/copy/destroy:
60
  multimap() : multimap(Compare()) { }
61
- explicit multimap(const Compare& comp,
62
- const Allocator& = Allocator());
63
  template <class InputIterator>
64
  multimap(InputIterator first, InputIterator last,
65
  const Compare& comp = Compare(),
66
  const Allocator& = Allocator());
67
  multimap(const multimap& x);
@@ -77,11 +74,13 @@ namespace std {
77
  : multimap(first, last, Compare(), a) { }
78
  multimap(initializer_list<value_type> il, const Allocator& a)
79
  : multimap(il, Compare(), a) { }
80
  ~multimap();
81
  multimap& operator=(const multimap& x);
82
- multimap& operator=(multimap&& x);
 
 
83
  multimap& operator=(initializer_list<value_type>);
84
  allocator_type get_allocator() const noexcept;
85
 
86
  // iterators:
87
  iterator begin() noexcept;
@@ -102,27 +101,46 @@ namespace std {
102
  // capacity:
103
  bool empty() const noexcept;
104
  size_type size() const noexcept;
105
  size_type max_size() const noexcept;
106
 
107
- // modifiers:
108
  template <class... Args> iterator emplace(Args&&... args);
109
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
110
  iterator insert(const value_type& x);
 
111
  template <class P> iterator insert(P&& x);
112
  iterator insert(const_iterator position, const value_type& x);
 
113
  template <class P> iterator insert(const_iterator position, P&& x);
114
  template <class InputIterator>
115
  void insert(InputIterator first, InputIterator last);
116
  void insert(initializer_list<value_type>);
117
 
 
 
 
 
 
 
118
  iterator erase(const_iterator position);
119
  size_type erase(const key_type& x);
120
  iterator erase(const_iterator first, const_iterator last);
121
- void swap(multimap&);
 
 
122
  void clear() noexcept;
123
 
 
 
 
 
 
 
 
 
 
124
  // observers:
125
  key_compare key_comp() const;
126
  value_compare value_comp() const;
127
 
128
  // map operations:
@@ -142,20 +160,37 @@ namespace std {
142
  iterator upper_bound(const key_type& x);
143
  const_iterator upper_bound(const key_type& x) const;
144
  template <class K> iterator upper_bound(const K& x);
145
  template <class K> const_iterator upper_bound(const K& x) const;
146
 
147
- pair<iterator,iterator>
148
- equal_range(const key_type& x);
149
- pair<const_iterator,const_iterator>
150
- equal_range(const key_type& x) const;
151
  template <class K>
152
  pair<iterator, iterator> equal_range(const K& x);
153
  template <class K>
154
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
155
  };
156
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
157
  template <class Key, class T, class Compare, class Allocator>
158
  bool operator==(const multimap<Key, T, Compare, Allocator>& x,
159
  const multimap<Key, T, Compare, Allocator>& y);
160
  template <class Key, class T, class Compare, class Allocator>
161
  bool operator< (const multimap<Key, T, Compare, Allocator>& x,
@@ -171,22 +206,22 @@ namespace std {
171
  const multimap<Key, T, Compare, Allocator>& y);
172
  template <class Key, class T, class Compare, class Allocator>
173
  bool operator<=(const multimap<Key, T, Compare, Allocator>& x,
174
  const multimap<Key, T, Compare, Allocator>& y);
175
 
176
- // specialized algorithms:
177
  template <class Key, class T, class Compare, class Allocator>
178
  void swap(multimap<Key, T, Compare, Allocator>& x,
179
- multimap<Key,T,Compare,Allocator>& y);
 
180
  }
181
  ```
182
 
183
  #### `multimap` constructors <a id="multimap.cons">[[multimap.cons]]</a>
184
 
185
  ``` cpp
186
- explicit multimap(const Compare& comp,
187
- const Allocator& = Allocator());
188
  ```
189
 
190
  *Effects:* Constructs an empty `multimap` using the specified comparison
191
  object and allocator.
192
 
@@ -197,14 +232,10 @@ template <class InputIterator>
197
  multimap(InputIterator first, InputIterator last,
198
  const Compare& comp = Compare(),
199
  const Allocator& = Allocator());
200
  ```
201
 
202
- *Requires:* If the iterator’s indirection operator returns an lvalue or
203
- a const rvalue `pair<key_type, mapped_type>`, then both `key_type` and
204
- `mapped_type` shall be `CopyInsertable` into `*this`.
205
-
206
  *Effects:* Constructs an empty `multimap` using the specified comparison
207
  object and allocator, and inserts elements from the range \[`first`,
208
  `last`).
209
 
210
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
@@ -220,21 +251,18 @@ template <class P> iterator insert(const_iterator position, P&& x);
220
  *Effects:* The first form is equivalent to
221
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
222
  `return emplace_hint(position, std::forward<P>(x))`.
223
 
224
  *Remarks:* These signatures shall not participate in overload resolution
225
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
226
 
227
  #### `multimap` specialized algorithms <a id="multimap.special">[[multimap.special]]</a>
228
 
229
  ``` cpp
230
  template <class Key, class T, class Compare, class Allocator>
231
  void swap(multimap<Key, T, Compare, Allocator>& x,
232
- multimap<Key,T,Compare,Allocator>& y);
 
233
  ```
234
 
235
- *Effects:*
236
-
237
- ``` cpp
238
- x.swap(y);
239
- ```
240
 
 
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
 
 
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;
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;
45
 
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
  };
56
 
57
+ // [multimap.cons], construct/copy/destroy
58
  multimap() : multimap(Compare()) { }
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);
 
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)
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;
 
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);
108
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
109
  iterator insert(const value_type& x);
110
+ iterator insert(value_type&& x);
111
  template <class P> iterator insert(P&& x);
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;
132
 
133
+ template<class C2>
134
+ void merge(multimap<Key, T, C2, Allocator>& source);
135
+ template<class C2>
136
+ void merge(multimap<Key, T, C2, Allocator>&& source);
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:
 
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, 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,
 
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
 
225
  *Effects:* Constructs an empty `multimap` using the specified comparison
226
  object and allocator.
227
 
 
232
  multimap(InputIterator first, InputIterator last,
233
  const Compare& comp = Compare(),
234
  const Allocator& = Allocator());
235
  ```
236
 
 
 
 
 
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
 
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