From Jason Turner

[map.overview]

C++14 → C++17 11.0 KB 136 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/tmpyfgrnbdm/{from.md → to.md} +91 -38
tmp/tmpyfgrnbdm/{from.md → to.md} RENAMED
@@ -7,59 +7,57 @@ bidirectional iterators.
7
 
8
  A `map` satisfies all of the requirements of a container, of a
9
  reversible container ([[container.requirements]]), of an associative
10
  container ([[associative.reqmts]]), and of an allocator-aware container
11
  (Table  [[tab:containers.allocatoraware]]). A `map` also provides most
12
- operations described in ([[associative.reqmts]]) for unique keys. This
13
- means that a `map` supports the `a_uniq` operations in (
14
- [[associative.reqmts]]) but not the `a_eq` operations. For a
15
- `map<Key,T>` the `key_type` is `Key` and the `value_type` is
16
- `pair<const Key,T>`. Descriptions are provided here only for operations
17
- on `map` that are not described in one of those tables or for operations
18
- 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 {
25
  public:
26
  // types:
27
- typedef Key key_type;
28
- typedef T mapped_type;
29
- typedef pair<const Key, T> value_type;
30
- typedef Compare key_compare;
31
- typedef Allocator allocator_type;
32
- typedef value_type& reference;
33
- typedef const value_type& const_reference;
34
- typedef implementation-defined iterator; // see [container.requirements]
35
- typedef implementation-defined const_iterator; // see [container.requirements]
36
- typedef implementation-defined size_type; // see [container.requirements]
37
- typedef implementation-defined difference_type;// see [container.requirements]
38
- typedef typename allocator_traits<Allocator>::pointer pointer;
39
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
40
- typedef std::reverse_iterator<iterator> reverse_iterator;
41
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
 
42
 
43
  class value_compare {
44
  friend class map;
45
  protected:
46
  Compare comp;
47
  value_compare(Compare c) : comp(c) {}
48
  public:
49
- typedef bool result_type;
50
- typedef value_type first_argument_type;
51
- typedef value_type second_argument_type;
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,
60
- const Allocator& = Allocator());
61
  template <class InputIterator>
62
  map(InputIterator first, InputIterator last,
63
  const Compare& comp = Compare(), const Allocator& = Allocator());
64
  map(const map& x);
65
  map(map&& x);
@@ -74,11 +72,13 @@ namespace std {
74
  : map(first, last, Compare(), a) { }
75
  map(initializer_list<value_type> il, const Allocator& a)
76
  : map(il, Compare(), a) { }
77
  ~map();
78
  map& operator=(const map& x);
79
- map& operator=(map&& x);
 
 
80
  map& operator=(initializer_list<value_type>);
81
  allocator_type get_allocator() const noexcept;
82
 
83
  // iterators:
84
  iterator begin() noexcept;
@@ -99,34 +99,70 @@ namespace std {
99
  // capacity:
100
  bool empty() const noexcept;
101
  size_type size() const noexcept;
102
  size_type max_size() const noexcept;
103
 
104
- // [map.access], element access:
105
  T& operator[](const key_type& x);
106
  T& operator[](key_type&& x);
107
  T& at(const key_type& x);
108
  const T& at(const key_type& x) const;
109
 
110
- // [map.modifiers], modifiers:
111
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
112
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
113
  pair<iterator, bool> insert(const value_type& x);
 
114
  template <class P> pair<iterator, bool> insert(P&& x);
115
  iterator insert(const_iterator position, const value_type& x);
 
116
  template <class P>
117
  iterator insert(const_iterator position, P&&);
118
  template <class InputIterator>
119
  void insert(InputIterator first, InputIterator last);
120
  void insert(initializer_list<value_type>);
121
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
122
  iterator erase(const_iterator position);
123
  size_type erase(const key_type& x);
124
  iterator erase(const_iterator first, const_iterator last);
125
- void swap(map&);
 
 
126
  void clear() noexcept;
127
 
 
 
 
 
 
 
 
 
 
128
  // observers:
129
  key_compare key_comp() const;
130
  value_compare value_comp() const;
131
 
132
  // map operations:
@@ -146,20 +182,36 @@ namespace std {
146
  iterator upper_bound(const key_type& x);
147
  const_iterator upper_bound(const key_type& x) const;
148
  template <class K> iterator upper_bound(const K& x);
149
  template <class K> const_iterator upper_bound(const K& x) const;
150
 
151
- pair<iterator,iterator>
152
- equal_range(const key_type& x);
153
- pair<const_iterator,const_iterator>
154
- equal_range(const key_type& x) const;
155
  template <class K>
156
  pair<iterator, iterator> equal_range(const K& x);
157
  template <class K>
158
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
159
  };
160
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
161
  template <class Key, class T, class Compare, class Allocator>
162
  bool operator==(const map<Key, T, Compare, Allocator>& x,
163
  const map<Key, T, Compare, Allocator>& y);
164
  template <class Key, class T, class Compare, class Allocator>
165
  bool operator< (const map<Key, T, Compare, Allocator>& x,
@@ -175,12 +227,13 @@ namespace std {
175
  const map<Key, T, Compare, Allocator>& y);
176
  template <class Key, class T, class Compare, class Allocator>
177
  bool operator<=(const map<Key, T, Compare, Allocator>& x,
178
  const map<Key, T, Compare, Allocator>& y);
179
 
180
- // specialized algorithms:
181
  template <class Key, class T, class Compare, class Allocator>
182
  void swap(map<Key, T, Compare, Allocator>& x,
183
- map<Key,T,Compare,Allocator>& y);
 
184
  }
185
  ```
186
 
 
7
 
8
  A `map` satisfies all of the requirements of a container, of a
9
  reversible container ([[container.requirements]]), of an associative
10
  container ([[associative.reqmts]]), and of an allocator-aware container
11
  (Table  [[tab:containers.allocatoraware]]). A `map` also provides most
12
+ operations described in  [[associative.reqmts]] for unique keys. This
13
+ means that a `map` supports the `a_uniq` operations in 
14
+ [[associative.reqmts]] but not the `a_eq` operations. For a `map<Key,T>`
15
+ the `key_type` is `Key` and the `value_type` is `pair<const Key,T>`.
16
+ Descriptions are provided here only for operations on `map` that are not
17
+ described in one of those tables or for operations where there is
18
+ 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 {
25
  public:
26
  // types:
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; // see [container.requirements]
37
+ using difference_type = implementation-defined; // see [container.requirements]
38
+ using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
39
+ using const_iterator = implementation-defined // type of map::const_iterator; // see [container.requirements]
40
+ using reverse_iterator = std::reverse_iterator<iterator>;
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
  public:
 
 
 
51
  bool operator()(const value_type& x, const value_type& y) const {
52
  return comp(x.first, y.first);
53
  }
54
  };
55
 
56
+ // [map.cons], construct/copy/destroy
57
  map() : map(Compare()) { }
58
+ explicit map(const Compare& comp, const Allocator& = Allocator());
 
59
  template <class InputIterator>
60
  map(InputIterator first, InputIterator last,
61
  const Compare& comp = Compare(), const Allocator& = Allocator());
62
  map(const map& x);
63
  map(map&& x);
 
72
  : map(first, last, Compare(), a) { }
73
  map(initializer_list<value_type> il, const Allocator& a)
74
  : map(il, Compare(), a) { }
75
  ~map();
76
  map& operator=(const map& x);
77
+ map& operator=(map&& x)
78
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
79
+ is_nothrow_move_assignable_v<Compare>);
80
  map& operator=(initializer_list<value_type>);
81
  allocator_type get_allocator() const noexcept;
82
 
83
  // iterators:
84
  iterator begin() noexcept;
 
99
  // capacity:
100
  bool empty() const noexcept;
101
  size_type size() const noexcept;
102
  size_type max_size() const noexcept;
103
 
104
+ // [map.access], element access
105
  T& operator[](const key_type& x);
106
  T& operator[](key_type&& x);
107
  T& at(const key_type& x);
108
  const T& at(const key_type& x) const;
109
 
110
+ // [map.modifiers], modifiers
111
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
112
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
113
  pair<iterator, bool> insert(const value_type& x);
114
+ pair<iterator, bool> insert(value_type&& x);
115
  template <class P> pair<iterator, bool> insert(P&& x);
116
  iterator insert(const_iterator position, const value_type& x);
117
+ iterator insert(const_iterator position, value_type&& x);
118
  template <class P>
119
  iterator insert(const_iterator position, P&&);
120
  template <class InputIterator>
121
  void insert(InputIterator first, InputIterator last);
122
  void insert(initializer_list<value_type>);
123
 
124
+ node_type extract(const_iterator position);
125
+ node_type extract(const key_type& x);
126
+ insert_return_type insert(node_type&& nh);
127
+ iterator insert(const_iterator hint, node_type&& nh);
128
+
129
+ template <class... Args>
130
+ pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
131
+ template <class... Args>
132
+ pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
133
+ template <class... Args>
134
+ iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
135
+ template <class... Args>
136
+ iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
137
+ template <class M>
138
+ pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
139
+ template <class M>
140
+ pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
141
+ template <class M>
142
+ iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
143
+ template <class M>
144
+ iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
145
+
146
+ iterator erase(iterator position);
147
  iterator erase(const_iterator position);
148
  size_type erase(const key_type& x);
149
  iterator erase(const_iterator first, const_iterator last);
150
+ void swap(map&)
151
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
152
+ is_nothrow_swappable_v<Compare>);
153
  void clear() noexcept;
154
 
155
+ template<class C2>
156
+ void merge(map<Key, T, C2, Allocator>& source);
157
+ template<class C2>
158
+ void merge(map<Key, T, C2, Allocator>&& source);
159
+ template<class C2>
160
+ void merge(multimap<Key, T, C2, Allocator>& source);
161
+ template<class C2>
162
+ void merge(multimap<Key, T, C2, Allocator>&& source);
163
+
164
  // observers:
165
  key_compare key_comp() const;
166
  value_compare value_comp() const;
167
 
168
  // map operations:
 
182
  iterator upper_bound(const key_type& x);
183
  const_iterator upper_bound(const key_type& x) const;
184
  template <class K> iterator upper_bound(const K& x);
185
  template <class K> const_iterator upper_bound(const K& x) const;
186
 
187
+ pair<iterator, iterator> equal_range(const key_type& x);
188
+ pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
 
 
189
  template <class K>
190
  pair<iterator, iterator> equal_range(const K& x);
191
  template <class K>
192
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
193
  };
194
 
195
+ template<class InputIterator, class Compare = less<iter_key_t<InputIterator>>,
196
+ class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
197
+ map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
198
+ -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>;
199
+
200
+ template<class Key, class T, class Compare = less<Key>,
201
+ class Allocator = allocator<pair<const Key, T>>>
202
+ map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
203
+ -> map<Key, T, Compare, Allocator>;
204
+
205
+ template <class InputIterator, class Allocator>
206
+ map(InputIterator, InputIterator, Allocator)
207
+ -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
208
+ less<iter_key_t<InputIterator>>, Allocator>;
209
+
210
+ template<class Key, class T, class Allocator>
211
+ map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
212
+
213
  template <class Key, class T, class Compare, class Allocator>
214
  bool operator==(const map<Key, T, Compare, Allocator>& x,
215
  const map<Key, T, Compare, Allocator>& y);
216
  template <class Key, class T, class Compare, class Allocator>
217
  bool operator< (const map<Key, T, Compare, Allocator>& x,
 
227
  const map<Key, T, Compare, Allocator>& y);
228
  template <class Key, class T, class Compare, class Allocator>
229
  bool operator<=(const map<Key, T, Compare, Allocator>& x,
230
  const map<Key, T, Compare, Allocator>& y);
231
 
232
+ // [map.special], specialized algorithms
233
  template <class Key, class T, class Compare, class Allocator>
234
  void swap(map<Key, T, Compare, Allocator>& x,
235
+ map<Key, T, Compare, Allocator>& y)
236
+ noexcept(noexcept(x.swap(y)));
237
  }
238
  ```
239