From Jason Turner

[map]

C++23 → Trunk 25.6 KB 348 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/tmp2_bv7tv_/{from.md → to.md} +218 -118
tmp/tmp2_bv7tv_/{from.md → to.md} RENAMED
@@ -8,19 +8,22 @@ 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>>>
26
  class map {
@@ -29,12 +32,12 @@ namespace std {
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 // 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]
@@ -43,170 +46,181 @@ namespace std {
43
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
44
  using node_type = unspecified;
45
  using insert_return_type = insert-return-type<iterator, node_type>;
46
 
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
  };
58
 
59
  // [map.cons], construct/copy/destroy
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)
86
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
87
  is_nothrow_move_assignable_v<Compare>);
88
- map& operator=(initializer_list<value_type>);
89
- allocator_type get_allocator() const noexcept;
90
 
91
  // iterators
92
- iterator begin() noexcept;
93
- const_iterator begin() const noexcept;
94
- iterator end() noexcept;
95
- const_iterator end() const noexcept;
96
 
97
- reverse_iterator rbegin() noexcept;
98
- const_reverse_iterator rbegin() const noexcept;
99
- reverse_iterator rend() noexcept;
100
- const_reverse_iterator rend() const noexcept;
101
 
102
- const_iterator cbegin() const noexcept;
103
- const_iterator cend() const noexcept;
104
- const_reverse_iterator crbegin() const noexcept;
105
- const_reverse_iterator crend() const noexcept;
106
 
107
  // capacity
108
- [[nodiscard]] bool empty() const noexcept;
109
- size_type size() const noexcept;
110
- size_type max_size() const noexcept;
111
 
112
  // [map.access], element access
113
- mapped_type& operator[](const key_type& x);
114
- mapped_type& operator[](key_type&& x);
115
- mapped_type& at(const key_type& x);
116
- const mapped_type& at(const key_type& x) const;
 
 
 
117
 
118
  // [map.modifiers], modifiers
119
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
120
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
121
- pair<iterator, bool> insert(const value_type& x);
122
- pair<iterator, bool> insert(value_type&& x);
123
- template<class P> pair<iterator, bool> insert(P&& x);
124
- iterator insert(const_iterator position, const value_type& 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);
142
  template<class... Args>
143
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
 
 
144
  template<class... Args>
145
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
146
  template<class... Args>
147
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
 
 
148
  template<class M>
149
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
150
  template<class M>
151
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
 
 
152
  template<class M>
153
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
154
  template<class M>
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;
166
 
167
  template<class C2>
168
- void merge(map<Key, T, C2, Allocator>& source);
169
  template<class C2>
170
- void merge(map<Key, T, C2, Allocator>&& source);
171
  template<class C2>
172
- void merge(multimap<Key, T, C2, Allocator>& source);
173
  template<class C2>
174
- void merge(multimap<Key, T, C2, Allocator>&& source);
175
 
176
  // observers
177
- key_compare key_comp() const;
178
- value_compare value_comp() const;
179
 
180
  // map operations
181
- iterator find(const key_type& x);
182
- const_iterator find(const key_type& x) const;
183
- template<class K> iterator find(const K& x);
184
- template<class K> const_iterator find(const K& x) const;
185
 
186
- size_type count(const key_type& x) const;
187
- template<class K> size_type count(const K& x) const;
188
 
189
- bool contains(const key_type& x) const;
190
- template<class K> bool contains(const K& x) const;
191
 
192
- iterator lower_bound(const key_type& x);
193
- const_iterator lower_bound(const key_type& x) const;
194
- template<class K> iterator lower_bound(const K& x);
195
- template<class K> const_iterator lower_bound(const K& x) const;
196
 
197
- iterator upper_bound(const key_type& x);
198
- const_iterator upper_bound(const key_type& x) const;
199
- template<class K> iterator upper_bound(const K& x);
200
- template<class K> const_iterator upper_bound(const K& x) const;
201
 
202
- pair<iterator, iterator> equal_range(const key_type& x);
203
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
204
  template<class K>
205
- pair<iterator, iterator> equal_range(const K& x);
206
  template<class K>
207
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
208
  };
209
 
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())
@@ -237,21 +251,21 @@ namespace std {
237
  ```
238
 
239
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
240
 
241
  ``` cpp
242
- explicit map(const Compare& comp, const Allocator& = Allocator());
243
  ```
244
 
245
  *Effects:* Constructs an empty `map` using the specified comparison
246
  object and allocator.
247
 
248
  *Complexity:* Constant.
249
 
250
  ``` cpp
251
  template<class InputIterator>
252
- map(InputIterator first, InputIterator last,
253
  const Compare& comp = Compare(), const Allocator& = Allocator());
254
  ```
255
 
256
  *Effects:* Constructs an empty `map` using the specified comparison
257
  object and allocator, and inserts elements from the range \[`first`,
@@ -261,11 +275,12 @@ object and allocator, and inserts elements from the range \[`first`,
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
 
@@ -273,55 +288,83 @@ object and allocator, and inserts elements from the range `rg`.
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);
279
  ```
280
 
281
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
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
  ```
294
 
295
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
296
  `*this`.
297
 
298
  *Throws:* An exception object of type `out_of_range` if no such element
299
  is present.
300
 
301
  *Complexity:* Logarithmic.
302
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
303
  #### Modifiers <a id="map.modifiers">[[map.modifiers]]</a>
304
 
305
  ``` cpp
306
  template<class P>
307
- pair<iterator, bool> insert(P&& x);
308
  template<class P>
309
- iterator insert(const_iterator position, P&& x);
310
  ```
311
 
312
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
313
 
314
  *Effects:* The first form is equivalent to
315
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
316
  `return emplace_hint(position, std::forward<P>(x))`.
317
 
318
  ``` cpp
319
  template<class... Args>
320
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
321
  template<class... Args>
322
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
323
  ```
324
 
325
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
326
  from `piecewise_construct`, `forward_as_tuple(k)`,
327
  `forward_as_tuple(std::forward<Args>(args)...)`.
@@ -337,13 +380,13 @@ iterator points to the map element whose key is equivalent to `k`.
337
 
338
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
339
 
340
  ``` cpp
341
  template<class... Args>
342
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
343
  template<class... Args>
344
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
345
  ```
346
 
347
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
348
  from `piecewise_construct`, `forward_as_tuple(std::move(k))`,
349
  `forward_as_tuple(std::forward<Args>(args)...)`.
@@ -358,15 +401,44 @@ type `value_type` constructed with `piecewise_construct`,
358
  pair is `true` if and only if the insertion took place. The returned
359
  iterator points to the map element whose key is equivalent to `k`.
360
 
361
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
362
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
363
  ``` cpp
364
  template<class M>
365
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
366
  template<class M>
367
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
368
  ```
369
 
370
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
371
 
372
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
@@ -383,13 +455,13 @@ iterator points to the map element whose key is equivalent to `k`.
383
 
384
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
385
 
386
  ``` cpp
387
  template<class M>
388
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
389
  template<class M>
390
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
391
  ```
392
 
393
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
394
 
395
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
@@ -404,16 +476,44 @@ Otherwise inserts an object of type `value_type` constructed with
404
  pair is `true` if and only if the insertion took place. The returned
405
  iterator points to the map element whose key is equivalent to `k`.
406
 
407
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
408
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
409
  #### Erasure <a id="map.erasure">[[map.erasure]]</a>
410
 
411
  ``` cpp
412
  template<class Key, class T, class Compare, class Allocator, class Predicate>
413
  typename map<Key, T, Compare, Allocator>::size_type
414
- erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
415
  ```
416
 
417
  *Effects:* Equivalent to:
418
 
419
  ``` cpp
 
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
+ The types `iterator` and `const_iterator` meet the constexpr iterator
23
+ requirements [[iterator.requirements.general]].
24
+
25
  ``` cpp
26
  namespace std {
27
  template<class Key, class T, class Compare = less<Key>,
28
  class Allocator = allocator<pair<const Key, T>>>
29
  class map {
 
32
  using key_type = Key;
33
  using mapped_type = T;
34
  using value_type = pair<const Key, T>;
35
  using key_compare = Compare;
36
  using allocator_type = Allocator;
37
+ using pointer = allocator_traits<Allocator>::pointer;
38
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
39
  using reference = value_type&;
40
  using const_reference = const value_type&;
41
  using size_type = implementation-defined // type of map::size_type; // see [container.requirements]
42
  using difference_type = implementation-defined // type of map::difference_type; // see [container.requirements]
43
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
 
46
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
47
  using node_type = unspecified;
48
  using insert_return_type = insert-return-type<iterator, node_type>;
49
 
50
  class value_compare {
 
51
  protected:
52
  Compare comp;
53
+ constexpr value_compare(Compare c) : comp(c) {}
54
 
55
  public:
56
+ constexpr bool operator()(const value_type& x, const value_type& y) const {
57
  return comp(x.first, y.first);
58
  }
59
  };
60
 
61
  // [map.cons], construct/copy/destroy
62
+ constexpr map() : map(Compare()) { }
63
+ constexpr explicit map(const Compare& comp, const Allocator& = Allocator());
64
  template<class InputIterator>
65
+ constexpr map(InputIterator first, InputIterator last,
66
  const Compare& comp = Compare(), const Allocator& = Allocator());
67
  template<container-compatible-range<value_type> R>
68
+ constexpr map(from_range_t, R&& rg, const Compare& comp = Compare(),
69
+ const Allocator& = Allocator());
70
+ constexpr map(const map& x);
71
+ constexpr map(map&& x);
72
  explicit map(const Allocator&);
73
+ constexpr map(const map&, const type_identity_t<Allocator>&);
74
+ constexpr map(map&&, const type_identity_t<Allocator>&);
75
+ constexpr map(initializer_list<value_type>, const Compare& = Compare(),
 
76
  const Allocator& = Allocator());
77
  template<class InputIterator>
78
+ constexpr map(InputIterator first, InputIterator last, const Allocator& a)
79
  : map(first, last, Compare(), a) { }
80
  template<container-compatible-range<value_type> R>
81
+ constexpr map(from_range_t, R&& rg, const Allocator& a)
82
  : map(from_range, std::forward<R>(rg), Compare(), a) { }
83
+ constexpr map(initializer_list<value_type> il, const Allocator& a)
84
  : map(il, Compare(), a) { }
85
+ constexpr ~map();
86
+ constexpr map& operator=(const map& x);
87
+ constexpr map& operator=(map&& x)
88
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
89
  is_nothrow_move_assignable_v<Compare>);
90
+ constexpr map& operator=(initializer_list<value_type>);
91
+ constexpr allocator_type get_allocator() const noexcept;
92
 
93
  // iterators
94
+ constexpr iterator begin() noexcept;
95
+ constexpr const_iterator begin() const noexcept;
96
+ constexpr iterator end() noexcept;
97
+ constexpr const_iterator end() const noexcept;
98
 
99
+ constexpr reverse_iterator rbegin() noexcept;
100
+ constexpr const_reverse_iterator rbegin() const noexcept;
101
+ constexpr reverse_iterator rend() noexcept;
102
+ constexpr const_reverse_iterator rend() const noexcept;
103
 
104
+ constexpr const_iterator cbegin() const noexcept;
105
+ constexpr const_iterator cend() const noexcept;
106
+ constexpr const_reverse_iterator crbegin() const noexcept;
107
+ constexpr const_reverse_iterator crend() const noexcept;
108
 
109
  // capacity
110
+ constexpr bool empty() const noexcept;
111
+ constexpr size_type size() const noexcept;
112
+ constexpr size_type max_size() const noexcept;
113
 
114
  // [map.access], element access
115
+ constexpr mapped_type& operator[](const key_type& x);
116
+ constexpr mapped_type& operator[](key_type&& x);
117
+ template<class K> constexpr mapped_type& operator[](K&& x);
118
+ constexpr mapped_type& at(const key_type& x);
119
+ constexpr const mapped_type& at(const key_type& x) const;
120
+ template<class K> constexpr mapped_type& at(const K& x);
121
+ template<class K> constexpr const mapped_type& at(const K& x) const;
122
 
123
  // [map.modifiers], modifiers
124
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
125
+ template<class... Args>
126
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
127
+ constexpr pair<iterator, bool> insert(const value_type& x);
128
+ constexpr pair<iterator, bool> insert(value_type&& x);
129
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
130
+ constexpr iterator insert(const_iterator position, const value_type& x);
131
+ constexpr iterator insert(const_iterator position, value_type&& x);
132
  template<class P>
133
+ constexpr iterator insert(const_iterator position, P&&);
134
  template<class InputIterator>
135
+ constexpr void insert(InputIterator first, InputIterator last);
136
  template<container-compatible-range<value_type> R>
137
+ constexpr void insert_range(R&& rg);
138
+ constexpr void insert(initializer_list<value_type>);
139
 
140
+ constexpr node_type extract(const_iterator position);
141
+ constexpr node_type extract(const key_type& x);
142
+ template<class K> constexpr node_type extract(K&& x);
143
+ constexpr insert_return_type insert(node_type&& nh);
144
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
145
 
146
  template<class... Args>
147
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
148
  template<class... Args>
149
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
150
+ template<class K, class... Args>
151
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
152
  template<class... Args>
153
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
154
  template<class... Args>
155
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
156
+ template<class K, class... Args>
157
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
158
  template<class M>
159
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
160
  template<class M>
161
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
162
+ template<class K, class M>
163
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
164
  template<class M>
165
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
166
  template<class M>
167
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
168
+ template<class K, class M>
169
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
170
 
171
+ constexpr iterator erase(iterator position);
172
+ constexpr iterator erase(const_iterator position);
173
+ constexpr size_type erase(const key_type& x);
174
+ template<class K> constexpr size_type erase(K&& x);
175
+ constexpr iterator erase(const_iterator first, const_iterator last);
176
+ constexpr void swap(map&)
177
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
178
  is_nothrow_swappable_v<Compare>);
179
+ constexpr void clear() noexcept;
180
 
181
  template<class C2>
182
+ constexpr void merge(map<Key, T, C2, Allocator>& source);
183
  template<class C2>
184
+ constexpr void merge(map<Key, T, C2, Allocator>&& source);
185
  template<class C2>
186
+ constexpr void merge(multimap<Key, T, C2, Allocator>& source);
187
  template<class C2>
188
+ constexpr void merge(multimap<Key, T, C2, Allocator>&& source);
189
 
190
  // observers
191
+ constexpr key_compare key_comp() const;
192
+ constexpr value_compare value_comp() const;
193
 
194
  // map operations
195
+ constexpr iterator find(const key_type& x);
196
+ constexpr const_iterator find(const key_type& x) const;
197
+ template<class K> constexpr iterator find(const K& x);
198
+ template<class K> constexpr const_iterator find(const K& x) const;
199
 
200
+ constexpr size_type count(const key_type& x) const;
201
+ template<class K> constexpr size_type count(const K& x) const;
202
 
203
+ constexpr bool contains(const key_type& x) const;
204
+ template<class K> constexpr bool contains(const K& x) const;
205
 
206
+ constexpr iterator lower_bound(const key_type& x);
207
+ constexpr const_iterator lower_bound(const key_type& x) const;
208
+ template<class K> constexpr iterator lower_bound(const K& x);
209
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
210
 
211
+ constexpr iterator upper_bound(const key_type& x);
212
+ constexpr const_iterator upper_bound(const key_type& x) const;
213
+ template<class K> constexpr iterator upper_bound(const K& x);
214
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
215
 
216
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
217
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
218
  template<class K>
219
+ constexpr pair<iterator, iterator> equal_range(const K& x);
220
  template<class K>
221
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
222
  };
223
 
224
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
225
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
226
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
 
251
  ```
252
 
253
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
254
 
255
  ``` cpp
256
+ constexpr explicit map(const Compare& comp, const Allocator& = Allocator());
257
  ```
258
 
259
  *Effects:* Constructs an empty `map` using the specified comparison
260
  object and allocator.
261
 
262
  *Complexity:* Constant.
263
 
264
  ``` cpp
265
  template<class InputIterator>
266
+ constexpr map(InputIterator first, InputIterator last,
267
  const Compare& comp = Compare(), const Allocator& = Allocator());
268
  ```
269
 
270
  *Effects:* Constructs an empty `map` using the specified comparison
271
  object and allocator, and inserts elements from the range \[`first`,
 
275
  sorted with respect to `comp` and otherwise N log N, where N is
276
  `last - first`.
277
 
278
  ``` cpp
279
  template<container-compatible-range<value_type> R>
280
+ constexpr map(from_range_t, R&& rg, const Compare& comp = Compare(),
281
+ const Allocator& = Allocator());
282
  ```
283
 
284
  *Effects:* Constructs an empty `map` using the specified comparison
285
  object and allocator, and inserts elements from the range `rg`.
286
 
 
288
  `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
289
 
290
  #### Element access <a id="map.access">[[map.access]]</a>
291
 
292
  ``` cpp
293
+ constexpr mapped_type& operator[](const key_type& x);
294
  ```
295
 
296
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
297
 
298
  ``` cpp
299
+ constexpr mapped_type& operator[](key_type&& x);
300
  ```
301
 
302
  *Effects:* Equivalent to:
303
  `return try_emplace(std::move(x)).first->second;`
304
 
305
  ``` cpp
306
+ template<class K> constexpr mapped_type& operator[](K&& x);
307
+ ```
308
+
309
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
310
+ denotes a type.
311
+
312
+ *Effects:* Equivalent to:
313
+ `return try_emplace(std::forward<K>(x)).first->second;`
314
+
315
+ ``` cpp
316
+ constexpr mapped_type& at(const key_type& x);
317
+ constexpr const mapped_type& at(const key_type& x) const;
318
  ```
319
 
320
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
321
  `*this`.
322
 
323
  *Throws:* An exception object of type `out_of_range` if no such element
324
  is present.
325
 
326
  *Complexity:* Logarithmic.
327
 
328
+ ``` cpp
329
+ template<class K> constexpr mapped_type& at(const K& x);
330
+ template<class K> constexpr const mapped_type& at(const K& x) const;
331
+ ```
332
+
333
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
334
+ denotes a type.
335
+
336
+ *Preconditions:* The expression `find(x)` is well-formed and has
337
+ well-defined behavior.
338
+
339
+ *Returns:* A reference to `find(x)->second`.
340
+
341
+ *Throws:* An exception object of type `out_of_range` if
342
+ `find(x) == end()` is `true`.
343
+
344
+ *Complexity:* Logarithmic.
345
+
346
  #### Modifiers <a id="map.modifiers">[[map.modifiers]]</a>
347
 
348
  ``` cpp
349
  template<class P>
350
+ constexpr pair<iterator, bool> insert(P&& x);
351
  template<class P>
352
+ constexpr iterator insert(const_iterator position, P&& x);
353
  ```
354
 
355
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
356
 
357
  *Effects:* The first form is equivalent to
358
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
359
  `return emplace_hint(position, std::forward<P>(x))`.
360
 
361
  ``` cpp
362
  template<class... Args>
363
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
364
  template<class... Args>
365
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
366
  ```
367
 
368
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
369
  from `piecewise_construct`, `forward_as_tuple(k)`,
370
  `forward_as_tuple(std::forward<Args>(args)...)`.
 
380
 
381
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
382
 
383
  ``` cpp
384
  template<class... Args>
385
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
386
  template<class... Args>
387
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
388
  ```
389
 
390
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
391
  from `piecewise_construct`, `forward_as_tuple(std::move(k))`,
392
  `forward_as_tuple(std::forward<Args>(args)...)`.
 
401
  pair is `true` if and only if the insertion took place. The returned
402
  iterator points to the map element whose key is equivalent to `k`.
403
 
404
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
405
 
406
+ ``` cpp
407
+ template<class K, class... Args>
408
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
409
+ template<class K, class... Args>
410
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
411
+ ```
412
+
413
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
414
+ denotes a type. For the first overload,
415
+ `is_convertible_v<K&&, const_iterator>` and
416
+ `is_convertible_v<K&&, iterator>` are both `false`.
417
+
418
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
419
+ from
420
+ `piecewise_construct, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...)`.
421
+
422
+ *Effects:* If the map already contains an element whose key is
423
+ equivalent to `k`, there is no effect. Otherwise, let `r` be
424
+ `equal_range(k)`. Constructs an object `u` of type `value_type` with
425
+ `piecewise_construct, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...)`.
426
+ If `equal_range(u.first) == r` is `false`, the behavior is undefined.
427
+ Inserts `u` into `*this`.
428
+
429
+ *Returns:* For the first overload, the `bool` component of the returned
430
+ pair is `true` if and only if the insertion took place. The returned
431
+ iterator points to the map element whose key is equivalent to `k`.
432
+
433
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
434
+
435
  ``` cpp
436
  template<class M>
437
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
438
  template<class M>
439
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
440
  ```
441
 
442
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
443
 
444
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
 
455
 
456
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
457
 
458
  ``` cpp
459
  template<class M>
460
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
461
  template<class M>
462
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
463
  ```
464
 
465
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
466
 
467
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
 
476
  pair is `true` if and only if the insertion took place. The returned
477
  iterator points to the map element whose key is equivalent to `k`.
478
 
479
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
480
 
481
+ ``` cpp
482
+ template<class K, class M>
483
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
484
+ template<class K, class M>
485
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
486
+ ```
487
+
488
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
489
+ denotes a type.
490
+
491
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
492
+
493
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
494
+ from `std::forward<K>(k), std:: forward<M>(obj)`.
495
+
496
+ *Effects:* If the map already contains an element `e` whose key is
497
+ equivalent to `k`, assigns `std::forward<M> (obj)` to `e.second`.
498
+ Otherwise, let `r` be `equal_range(k)`. Constructs an object `u` of type
499
+ `value_type` with `std::forward<K>(k), std::forward<M>(obj)`. If
500
+ `equal_range(u.first) == r` is `false`, the behavior is undefined.
501
+ Inserts `u` into `*this`.
502
+
503
+ *Returns:* For the first overload, the `bool` component of the returned
504
+ pair is `true` if and only if the insertion took place. The returned
505
+ iterator points to the map element whose key is equivalent to `k`.
506
+
507
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
508
+
509
  #### Erasure <a id="map.erasure">[[map.erasure]]</a>
510
 
511
  ``` cpp
512
  template<class Key, class T, class Compare, class Allocator, class Predicate>
513
  typename map<Key, T, Compare, Allocator>::size_type
514
+ constexpr erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
515
  ```
516
 
517
  *Effects:* Equivalent to:
518
 
519
  ``` cpp