From Jason Turner

[map]

C++20 → C++23 10.5 KB 96 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/tmpfn7ehp85/{from.md → to.md} +55 -28
tmp/tmpfn7ehp85/{from.md → to.md} RENAMED
@@ -1,24 +1,25 @@
1
  ### Class template `map` <a id="map">[[map]]</a>
2
 
3
  #### Overview <a id="map.overview">[[map.overview]]</a>
4
 
5
- A `map` is an associative container that supports unique keys (contains
6
- at most one of each key value) and provides for fast retrieval of values
7
- of another type `T` based on the keys. The `map` class supports
8
- bidirectional iterators.
9
 
10
- A `map` meets all of the requirements of a container, of a reversible
11
- container [[container.requirements]], of an associative container
12
- [[associative.reqmts]], and of an allocator-aware container (
13
- [[container.alloc.req]]). A `map` also provides most operations
14
- described in  [[associative.reqmts]] for unique keys. This means that a
15
- `map` supports the `a_uniq` operations in  [[associative.reqmts]] but
16
- not the `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key`
17
- and the `value_type` is `pair<const Key,T>`. Descriptions are provided
18
- here only for operations on `map` that are not described in one of those
19
- tables or for operations where there is additional semantic information.
 
20
 
21
  ``` cpp
22
  namespace std {
23
  template<class Key, class T, class Compare = less<Key>,
24
  class Allocator = allocator<pair<const Key, T>>>
@@ -32,12 +33,12 @@ namespace std {
32
  using allocator_type = Allocator;
33
  using pointer = typename allocator_traits<Allocator>::pointer;
34
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
35
  using reference = value_type&;
36
  using const_reference = const value_type&;
37
- using size_type = implementation-defined; // see [container.requirements]
38
- using difference_type = implementation-defined; // see [container.requirements]
39
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
40
  using const_iterator = implementation-defined // type of map::const_iterator; // see [container.requirements]
41
  using reverse_iterator = std::reverse_iterator<iterator>;
42
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
43
  using node_type = unspecified;
@@ -46,10 +47,11 @@ namespace std {
46
  class value_compare {
47
  friend class map;
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
  };
@@ -58,21 +60,26 @@ namespace std {
58
  map() : map(Compare()) { }
59
  explicit map(const Compare& comp, const Allocator& = Allocator());
60
  template<class InputIterator>
61
  map(InputIterator first, InputIterator last,
62
  const Compare& comp = Compare(), const Allocator& = Allocator());
 
 
63
  map(const map& x);
64
  map(map&& x);
65
  explicit map(const Allocator&);
66
- map(const map&, const Allocator&);
67
- map(map&&, const Allocator&);
68
  map(initializer_list<value_type>,
69
  const Compare& = Compare(),
70
  const Allocator& = Allocator());
71
  template<class InputIterator>
72
  map(InputIterator first, InputIterator last, const Allocator& a)
73
  : map(first, last, Compare(), a) { }
 
 
 
74
  map(initializer_list<value_type> il, const Allocator& a)
75
  : map(il, Compare(), a) { }
76
  ~map();
77
  map& operator=(const map& x);
78
  map& operator=(map&& x)
@@ -118,14 +125,17 @@ namespace std {
118
  iterator insert(const_iterator position, value_type&& x);
119
  template<class P>
120
  iterator insert(const_iterator position, P&&);
121
  template<class InputIterator>
122
  void insert(InputIterator first, InputIterator last);
 
 
123
  void insert(initializer_list<value_type>);
124
 
125
  node_type extract(const_iterator position);
126
  node_type extract(const key_type& x);
 
127
  insert_return_type insert(node_type&& nh);
128
  iterator insert(const_iterator hint, node_type&& nh);
129
 
130
  template<class... Args>
131
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
@@ -145,10 +155,11 @@ namespace std {
145
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
146
 
147
  iterator erase(iterator position);
148
  iterator erase(const_iterator position);
149
  size_type erase(const key_type& x);
 
150
  iterator erase(const_iterator first, const_iterator last);
151
  void swap(map&)
152
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
153
  is_nothrow_swappable_v<Compare>);
154
  void clear() noexcept;
@@ -199,28 +210,31 @@ namespace std {
199
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
200
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
201
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
202
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare, Allocator>;
203
 
 
 
 
 
 
204
  template<class Key, class T, class Compare = less<Key>,
205
  class Allocator = allocator<pair<const Key, T>>>
206
  map(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
207
  -> map<Key, T, Compare, Allocator>;
208
 
209
  template<class InputIterator, class Allocator>
210
  map(InputIterator, InputIterator, Allocator)
211
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
212
  less<iter-key-type<InputIterator>>, Allocator>;
213
 
 
 
 
 
214
  template<class Key, class T, class Allocator>
215
  map(initializer_list<pair<Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
216
-
217
- // swap
218
- template<class Key, class T, class Compare, class Allocator>
219
- void swap(map<Key, T, Compare, Allocator>& x,
220
- map<Key, T, Compare, Allocator>& y)
221
- noexcept(noexcept(x.swap(y)));
222
  }
223
  ```
224
 
225
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
226
 
@@ -242,11 +256,23 @@ template<class InputIterator>
242
  *Effects:* Constructs an empty `map` using the specified comparison
243
  object and allocator, and inserts elements from the range \[`first`,
244
  `last`).
245
 
246
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
247
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
248
 
249
  #### Element access <a id="map.access">[[map.access]]</a>
250
 
251
  ``` cpp
252
  mapped_type& operator[](const key_type& x);
@@ -256,11 +282,12 @@ mapped_type& operator[](const key_type& x);
256
 
257
  ``` cpp
258
  mapped_type& operator[](key_type&& x);
259
  ```
260
 
261
- *Effects:* Equivalent to: `return try_emplace(move(x)).first->second;`
 
262
 
263
  ``` cpp
264
  mapped_type& at(const key_type& x);
265
  const mapped_type& at(const key_type& x) const;
266
  ```
@@ -341,11 +368,11 @@ template<class M>
341
  ```
342
 
343
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
344
 
345
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
346
- from `k`, `forward<M>(obj)`.
347
 
348
  *Effects:* If the map already contains an element `e` whose key is
349
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
350
  Otherwise inserts an object of type `value_type` constructed with `k`,
351
  `std::forward<M>(obj)`.
@@ -364,11 +391,11 @@ template<class M>
364
  ```
365
 
366
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
367
 
368
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
369
- from `move(k)`, `forward<M>(obj)`.
370
 
371
  *Effects:* If the map already contains an element `e` whose key is
372
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
373
  Otherwise inserts an object of type `value_type` constructed with
374
  `std::move(k)`, `std::forward<M>(obj)`.
 
1
  ### Class template `map` <a id="map">[[map]]</a>
2
 
3
  #### Overview <a id="map.overview">[[map.overview]]</a>
4
 
5
+ A `map` is an associative container that supports unique keys (i.e.,
6
+ contains at most one of each key value) and provides for fast retrieval
7
+ of values of another type `T` based on the keys. The `map` class
8
+ supports bidirectional iterators.
9
 
10
+ A `map` 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 `map` also provides most operations described
15
+ in  [[associative.reqmts]] for unique keys. This means that a `map`
16
+ supports the `a_uniq` operations in  [[associative.reqmts]] but not the
17
+ `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key` and the
18
+ `value_type` is `pair<const Key,T>`. Descriptions are provided here only
19
+ for operations on `map` that are not described in one of those tables or
20
+ for 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>>>
 
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 // type of map::size_type; // see [container.requirements]
39
+ using difference_type = implementation-defined // type of map::difference_type; // see [container.requirements]
40
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
41
  using const_iterator = implementation-defined // type of map::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
  class value_compare {
48
  friend class map;
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
  };
 
60
  map() : map(Compare()) { }
61
  explicit map(const Compare& comp, const Allocator& = Allocator());
62
  template<class InputIterator>
63
  map(InputIterator first, InputIterator last,
64
  const Compare& comp = Compare(), const Allocator& = Allocator());
65
+ template<container-compatible-range<value_type> R>
66
+ map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
67
  map(const map& x);
68
  map(map&& x);
69
  explicit map(const Allocator&);
70
+ map(const map&, const type_identity_t<Allocator>&);
71
+ map(map&&, const type_identity_t<Allocator>&);
72
  map(initializer_list<value_type>,
73
  const Compare& = Compare(),
74
  const Allocator& = Allocator());
75
  template<class InputIterator>
76
  map(InputIterator first, InputIterator last, const Allocator& a)
77
  : map(first, last, Compare(), a) { }
78
+ template<container-compatible-range<value_type> R>
79
+ map(from_range_t, R&& rg, const Allocator& a))
80
+ : map(from_range, std::forward<R>(rg), Compare(), a) { }
81
  map(initializer_list<value_type> il, const Allocator& a)
82
  : map(il, Compare(), a) { }
83
  ~map();
84
  map& operator=(const map& x);
85
  map& operator=(map&& x)
 
125
  iterator insert(const_iterator position, value_type&& x);
126
  template<class P>
127
  iterator insert(const_iterator position, P&&);
128
  template<class InputIterator>
129
  void insert(InputIterator first, InputIterator last);
130
+ template<container-compatible-range<value_type> R>
131
+ void insert_range(R&& rg);
132
  void insert(initializer_list<value_type>);
133
 
134
  node_type extract(const_iterator position);
135
  node_type extract(const key_type& x);
136
+ template<class K> node_type extract(K&& x);
137
  insert_return_type insert(node_type&& nh);
138
  iterator insert(const_iterator hint, node_type&& nh);
139
 
140
  template<class... Args>
141
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
 
155
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
156
 
157
  iterator erase(iterator position);
158
  iterator erase(const_iterator position);
159
  size_type erase(const key_type& x);
160
+ template<class K> size_type erase(K&& x);
161
  iterator erase(const_iterator first, const_iterator last);
162
  void swap(map&)
163
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
164
  is_nothrow_swappable_v<Compare>);
165
  void clear() noexcept;
 
210
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
211
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
212
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
213
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare, Allocator>;
214
 
215
+ template<ranges::input_range R, class Compare = less<range-key-type<R>,
216
+ class Allocator = allocator<range-to-alloc-type<R>>>
217
+ map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
218
+ -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>;
219
+
220
  template<class Key, class T, class Compare = less<Key>,
221
  class Allocator = allocator<pair<const Key, T>>>
222
  map(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
223
  -> map<Key, T, Compare, Allocator>;
224
 
225
  template<class InputIterator, class Allocator>
226
  map(InputIterator, InputIterator, Allocator)
227
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
228
  less<iter-key-type<InputIterator>>, Allocator>;
229
 
230
+ template<ranges::input_range R, class Allocator>
231
+ map(from_range_t, R&&, Allocator)
232
+ -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>;
233
+
234
  template<class Key, class T, class Allocator>
235
  map(initializer_list<pair<Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
 
 
 
 
 
 
236
  }
237
  ```
238
 
239
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
240
 
 
256
  *Effects:* Constructs an empty `map` using the specified comparison
257
  object and allocator, and inserts elements from the range \[`first`,
258
  `last`).
259
 
260
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
261
+ sorted with respect to `comp` and otherwise N log N, where N is
262
+ `last - first`.
263
+
264
+ ``` cpp
265
+ template<container-compatible-range<value_type> R>
266
+ map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
267
+ ```
268
+
269
+ *Effects:* Constructs an empty `map` using the specified comparison
270
+ object and allocator, and inserts elements from the range `rg`.
271
+
272
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
273
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
274
 
275
  #### Element access <a id="map.access">[[map.access]]</a>
276
 
277
  ``` cpp
278
  mapped_type& operator[](const key_type& x);
 
282
 
283
  ``` cpp
284
  mapped_type& operator[](key_type&& x);
285
  ```
286
 
287
+ *Effects:* Equivalent to:
288
+ `return try_emplace(std::move(x)).first->second;`
289
 
290
  ``` cpp
291
  mapped_type& at(const key_type& x);
292
  const mapped_type& at(const key_type& x) const;
293
  ```
 
368
  ```
369
 
370
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
371
 
372
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
373
+ from `k`, `std::forward<M>(obj)`.
374
 
375
  *Effects:* If the map already contains an element `e` whose key is
376
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
377
  Otherwise inserts an object of type `value_type` constructed with `k`,
378
  `std::forward<M>(obj)`.
 
391
  ```
392
 
393
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
394
 
395
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
396
+ from `std::move(k)`, `std::forward<M>(obj)`.
397
 
398
  *Effects:* If the map already contains an element `e` whose key is
399
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
400
  Otherwise inserts an object of type `value_type` constructed with
401
  `std::move(k)`, `std::forward<M>(obj)`.