From Jason Turner

[map.overview]

C++23 → Trunk 16.3 KB 219 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/tmpb0_ofkk3/{from.md → to.md} +114 -100
tmp/tmpb0_ofkk3/{from.md → to.md} RENAMED
@@ -6,19 +6,22 @@ of values of another type `T` based on the keys. The `map` class
6
  supports bidirectional iterators.
7
 
8
  A `map` meets all of the requirements of a container
9
  [[container.reqmts]], of a reversible container
10
  [[container.rev.reqmts]], of an allocator-aware container
11
- [[container.alloc.reqmts]]. and of an associative container
12
  [[associative.reqmts]]. A `map` also provides most operations described
13
  in  [[associative.reqmts]] for unique keys. This means that a `map`
14
  supports the `a_uniq` operations in  [[associative.reqmts]] but not the
15
  `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key` and the
16
  `value_type` is `pair<const Key,T>`. Descriptions are provided here only
17
  for operations on `map` that are not described in one of those tables or
18
  for operations where there is additional semantic information.
19
 
 
 
 
20
  ``` cpp
21
  namespace std {
22
  template<class Key, class T, class Compare = less<Key>,
23
  class Allocator = allocator<pair<const Key, T>>>
24
  class map {
@@ -27,12 +30,12 @@ namespace std {
27
  using key_type = Key;
28
  using mapped_type = T;
29
  using value_type = pair<const Key, T>;
30
  using key_compare = Compare;
31
  using allocator_type = Allocator;
32
- using pointer = typename allocator_traits<Allocator>::pointer;
33
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
34
  using reference = value_type&;
35
  using const_reference = const value_type&;
36
  using size_type = implementation-defined // type of map::size_type; // see [container.requirements]
37
  using difference_type = implementation-defined // type of map::difference_type; // see [container.requirements]
38
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
@@ -41,170 +44,181 @@ namespace std {
41
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
42
  using node_type = unspecified;
43
  using insert_return_type = insert-return-type<iterator, node_type>;
44
 
45
  class value_compare {
46
- friend class map;
47
  protected:
48
  Compare comp;
49
- value_compare(Compare c) : comp(c) {}
50
 
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
  // [map.cons], construct/copy/destroy
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
  template<container-compatible-range<value_type> R>
64
- map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
65
- map(const map& x);
66
- map(map&& x);
 
67
  explicit map(const Allocator&);
68
- map(const map&, const type_identity_t<Allocator>&);
69
- map(map&&, const type_identity_t<Allocator>&);
70
- map(initializer_list<value_type>,
71
- const Compare& = Compare(),
72
  const Allocator& = Allocator());
73
  template<class InputIterator>
74
- map(InputIterator first, InputIterator last, const Allocator& a)
75
  : map(first, last, Compare(), a) { }
76
  template<container-compatible-range<value_type> R>
77
- map(from_range_t, R&& rg, const Allocator& a))
78
  : map(from_range, std::forward<R>(rg), Compare(), a) { }
79
- map(initializer_list<value_type> il, const Allocator& a)
80
  : map(il, Compare(), a) { }
81
- ~map();
82
- map& operator=(const map& x);
83
- map& operator=(map&& x)
84
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
85
  is_nothrow_move_assignable_v<Compare>);
86
- map& operator=(initializer_list<value_type>);
87
- allocator_type get_allocator() const noexcept;
88
 
89
  // iterators
90
- iterator begin() noexcept;
91
- const_iterator begin() const noexcept;
92
- iterator end() noexcept;
93
- const_iterator end() const noexcept;
94
 
95
- reverse_iterator rbegin() noexcept;
96
- const_reverse_iterator rbegin() const noexcept;
97
- reverse_iterator rend() noexcept;
98
- const_reverse_iterator rend() const noexcept;
99
 
100
- const_iterator cbegin() const noexcept;
101
- const_iterator cend() const noexcept;
102
- const_reverse_iterator crbegin() const noexcept;
103
- const_reverse_iterator crend() const noexcept;
104
 
105
  // capacity
106
- [[nodiscard]] bool empty() const noexcept;
107
- size_type size() const noexcept;
108
- size_type max_size() const noexcept;
109
 
110
  // [map.access], element access
111
- mapped_type& operator[](const key_type& x);
112
- mapped_type& operator[](key_type&& x);
113
- mapped_type& at(const key_type& x);
114
- const mapped_type& at(const key_type& x) const;
 
 
 
115
 
116
  // [map.modifiers], modifiers
117
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
118
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
119
- pair<iterator, bool> insert(const value_type& x);
120
- pair<iterator, bool> insert(value_type&& x);
121
- template<class P> pair<iterator, bool> insert(P&& x);
122
- iterator insert(const_iterator position, const value_type& x);
123
- iterator insert(const_iterator position, value_type&& x);
 
124
  template<class P>
125
- iterator insert(const_iterator position, P&&);
126
  template<class InputIterator>
127
- void insert(InputIterator first, InputIterator last);
128
  template<container-compatible-range<value_type> R>
129
- void insert_range(R&& rg);
130
- void insert(initializer_list<value_type>);
131
 
132
- node_type extract(const_iterator position);
133
- node_type extract(const key_type& x);
134
- template<class K> node_type extract(K&& x);
135
- insert_return_type insert(node_type&& nh);
136
- iterator insert(const_iterator hint, node_type&& nh);
137
 
138
  template<class... Args>
139
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
140
  template<class... Args>
141
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
 
 
142
  template<class... Args>
143
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
144
  template<class... Args>
145
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
 
 
146
  template<class M>
147
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
148
  template<class M>
149
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
 
 
150
  template<class M>
151
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
152
  template<class M>
153
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
 
 
154
 
155
- iterator erase(iterator position);
156
- iterator erase(const_iterator position);
157
- size_type erase(const key_type& x);
158
- template<class K> size_type erase(K&& x);
159
- iterator erase(const_iterator first, const_iterator last);
160
- void swap(map&)
161
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
162
  is_nothrow_swappable_v<Compare>);
163
- void clear() noexcept;
164
 
165
  template<class C2>
166
- void merge(map<Key, T, C2, Allocator>& source);
167
  template<class C2>
168
- void merge(map<Key, T, C2, Allocator>&& source);
169
  template<class C2>
170
- void merge(multimap<Key, T, C2, Allocator>& source);
171
  template<class C2>
172
- void merge(multimap<Key, T, C2, Allocator>&& source);
173
 
174
  // observers
175
- key_compare key_comp() const;
176
- value_compare value_comp() const;
177
 
178
  // map operations
179
- iterator find(const key_type& x);
180
- const_iterator find(const key_type& x) const;
181
- template<class K> iterator find(const K& x);
182
- template<class K> const_iterator find(const K& x) const;
183
 
184
- size_type count(const key_type& x) const;
185
- template<class K> size_type count(const K& x) const;
186
 
187
- bool contains(const key_type& x) const;
188
- template<class K> bool contains(const K& x) const;
189
 
190
- iterator lower_bound(const key_type& x);
191
- const_iterator lower_bound(const key_type& x) const;
192
- template<class K> iterator lower_bound(const K& x);
193
- template<class K> const_iterator lower_bound(const K& x) const;
194
 
195
- iterator upper_bound(const key_type& x);
196
- const_iterator upper_bound(const key_type& x) const;
197
- template<class K> iterator upper_bound(const K& x);
198
- template<class K> const_iterator upper_bound(const K& x) const;
199
 
200
- pair<iterator, iterator> equal_range(const key_type& x);
201
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
202
  template<class K>
203
- pair<iterator, iterator> equal_range(const K& x);
204
  template<class K>
205
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
206
  };
207
 
208
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
209
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
210
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
 
6
  supports bidirectional iterators.
7
 
8
  A `map` meets all of the requirements of a container
9
  [[container.reqmts]], of a reversible container
10
  [[container.rev.reqmts]], of an allocator-aware container
11
+ [[container.alloc.reqmts]], and of an associative container
12
  [[associative.reqmts]]. A `map` also provides most operations described
13
  in  [[associative.reqmts]] for unique keys. This means that a `map`
14
  supports the `a_uniq` operations in  [[associative.reqmts]] but not the
15
  `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key` and the
16
  `value_type` is `pair<const Key,T>`. Descriptions are provided here only
17
  for operations on `map` that are not described in one of those tables or
18
  for operations where there is additional semantic information.
19
 
20
+ The types `iterator` and `const_iterator` meet the constexpr iterator
21
+ requirements [[iterator.requirements.general]].
22
+
23
  ``` cpp
24
  namespace std {
25
  template<class Key, class T, class Compare = less<Key>,
26
  class Allocator = allocator<pair<const Key, T>>>
27
  class map {
 
30
  using key_type = Key;
31
  using mapped_type = T;
32
  using value_type = pair<const Key, T>;
33
  using key_compare = Compare;
34
  using allocator_type = Allocator;
35
+ using pointer = allocator_traits<Allocator>::pointer;
36
+ using const_pointer = 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 map::size_type; // see [container.requirements]
40
  using difference_type = implementation-defined // type of map::difference_type; // see [container.requirements]
41
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
 
44
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
45
  using node_type = unspecified;
46
  using insert_return_type = insert-return-type<iterator, node_type>;
47
 
48
  class value_compare {
 
49
  protected:
50
  Compare comp;
51
+ constexpr value_compare(Compare c) : comp(c) {}
52
 
53
  public:
54
+ constexpr 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
+ constexpr map() : map(Compare()) { }
61
+ constexpr explicit map(const Compare& comp, const Allocator& = Allocator());
62
  template<class InputIterator>
63
+ constexpr map(InputIterator first, InputIterator last,
64
  const Compare& comp = Compare(), const Allocator& = Allocator());
65
  template<container-compatible-range<value_type> R>
66
+ constexpr map(from_range_t, R&& rg, const Compare& comp = Compare(),
67
+ const Allocator& = Allocator());
68
+ constexpr map(const map& x);
69
+ constexpr map(map&& x);
70
  explicit map(const Allocator&);
71
+ constexpr map(const map&, const type_identity_t<Allocator>&);
72
+ constexpr map(map&&, const type_identity_t<Allocator>&);
73
+ constexpr map(initializer_list<value_type>, const Compare& = Compare(),
 
74
  const Allocator& = Allocator());
75
  template<class InputIterator>
76
+ constexpr map(InputIterator first, InputIterator last, const Allocator& a)
77
  : map(first, last, Compare(), a) { }
78
  template<container-compatible-range<value_type> R>
79
+ constexpr map(from_range_t, R&& rg, const Allocator& a)
80
  : map(from_range, std::forward<R>(rg), Compare(), a) { }
81
+ constexpr map(initializer_list<value_type> il, const Allocator& a)
82
  : map(il, Compare(), a) { }
83
+ constexpr ~map();
84
+ constexpr map& operator=(const map& x);
85
+ constexpr map& operator=(map&& x)
86
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
87
  is_nothrow_move_assignable_v<Compare>);
88
+ constexpr map& operator=(initializer_list<value_type>);
89
+ constexpr allocator_type get_allocator() const noexcept;
90
 
91
  // iterators
92
+ constexpr iterator begin() noexcept;
93
+ constexpr const_iterator begin() const noexcept;
94
+ constexpr iterator end() noexcept;
95
+ constexpr const_iterator end() const noexcept;
96
 
97
+ constexpr reverse_iterator rbegin() noexcept;
98
+ constexpr const_reverse_iterator rbegin() const noexcept;
99
+ constexpr reverse_iterator rend() noexcept;
100
+ constexpr const_reverse_iterator rend() const noexcept;
101
 
102
+ constexpr const_iterator cbegin() const noexcept;
103
+ constexpr const_iterator cend() const noexcept;
104
+ constexpr const_reverse_iterator crbegin() const noexcept;
105
+ constexpr const_reverse_iterator crend() const noexcept;
106
 
107
  // capacity
108
+ constexpr bool empty() const noexcept;
109
+ constexpr size_type size() const noexcept;
110
+ constexpr size_type max_size() const noexcept;
111
 
112
  // [map.access], element access
113
+ constexpr mapped_type& operator[](const key_type& x);
114
+ constexpr mapped_type& operator[](key_type&& x);
115
+ template<class K> constexpr mapped_type& operator[](K&& x);
116
+ constexpr mapped_type& at(const key_type& x);
117
+ constexpr const mapped_type& at(const key_type& x) const;
118
+ template<class K> constexpr mapped_type& at(const K& x);
119
+ template<class K> constexpr const mapped_type& at(const K& x) const;
120
 
121
  // [map.modifiers], modifiers
122
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
123
+ template<class... Args>
124
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
125
+ constexpr pair<iterator, bool> insert(const value_type& x);
126
+ constexpr pair<iterator, bool> insert(value_type&& x);
127
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
128
+ constexpr iterator insert(const_iterator position, const value_type& x);
129
+ constexpr iterator insert(const_iterator position, value_type&& x);
130
  template<class P>
131
+ constexpr iterator insert(const_iterator position, P&&);
132
  template<class InputIterator>
133
+ constexpr void insert(InputIterator first, InputIterator last);
134
  template<container-compatible-range<value_type> R>
135
+ constexpr void insert_range(R&& rg);
136
+ constexpr void insert(initializer_list<value_type>);
137
 
138
+ constexpr node_type extract(const_iterator position);
139
+ constexpr node_type extract(const key_type& x);
140
+ template<class K> constexpr node_type extract(K&& x);
141
+ constexpr insert_return_type insert(node_type&& nh);
142
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
143
 
144
  template<class... Args>
145
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
146
  template<class... Args>
147
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
148
+ template<class K, class... Args>
149
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
150
  template<class... Args>
151
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
152
  template<class... Args>
153
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
154
+ template<class K, class... Args>
155
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
156
  template<class M>
157
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
158
  template<class M>
159
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
160
+ template<class K, class M>
161
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
162
  template<class M>
163
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
164
  template<class M>
165
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
166
+ template<class K, class M>
167
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
168
 
169
+ constexpr iterator erase(iterator position);
170
+ constexpr iterator erase(const_iterator position);
171
+ constexpr size_type erase(const key_type& x);
172
+ template<class K> constexpr size_type erase(K&& x);
173
+ constexpr iterator erase(const_iterator first, const_iterator last);
174
+ constexpr void swap(map&)
175
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
176
  is_nothrow_swappable_v<Compare>);
177
+ constexpr void clear() noexcept;
178
 
179
  template<class C2>
180
+ constexpr void merge(map<Key, T, C2, Allocator>& source);
181
  template<class C2>
182
+ constexpr void merge(map<Key, T, C2, Allocator>&& source);
183
  template<class C2>
184
+ constexpr void merge(multimap<Key, T, C2, Allocator>& source);
185
  template<class C2>
186
+ constexpr void merge(multimap<Key, T, C2, Allocator>&& source);
187
 
188
  // observers
189
+ constexpr key_compare key_comp() const;
190
+ constexpr value_compare value_comp() const;
191
 
192
  // map operations
193
+ constexpr iterator find(const key_type& x);
194
+ constexpr const_iterator find(const key_type& x) const;
195
+ template<class K> constexpr iterator find(const K& x);
196
+ template<class K> constexpr const_iterator find(const K& x) const;
197
 
198
+ constexpr size_type count(const key_type& x) const;
199
+ template<class K> constexpr size_type count(const K& x) const;
200
 
201
+ constexpr bool contains(const key_type& x) const;
202
+ template<class K> constexpr bool contains(const K& x) const;
203
 
204
+ constexpr iterator lower_bound(const key_type& x);
205
+ constexpr const_iterator lower_bound(const key_type& x) const;
206
+ template<class K> constexpr iterator lower_bound(const K& x);
207
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
208
 
209
+ constexpr iterator upper_bound(const key_type& x);
210
+ constexpr const_iterator upper_bound(const key_type& x) const;
211
+ template<class K> constexpr iterator upper_bound(const K& x);
212
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
213
 
214
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
215
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
216
  template<class K>
217
+ constexpr pair<iterator, iterator> equal_range(const K& x);
218
  template<class K>
219
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
220
  };
221
 
222
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
223
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
224
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())