From Jason Turner

[multimap.overview]

C++14 → C++17 9.8 KB 110 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/tmpk3ptuvye/{from.md → to.md} +69 -33
tmp/tmpk3ptuvye/{from.md → to.md} RENAMED
@@ -7,13 +7,13 @@ for fast retrieval of values of another type `T` based on the keys. The
7
 
8
  A `multimap` satisfies all of the requirements of a container and 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 `multimap` also provides
12
- most operations described in ([[associative.reqmts]]) for equal keys.
13
- This means that a `multimap` supports the `a_eq` operations in (
14
- [[associative.reqmts]]) but not the `a_uniq` operations. For a
15
  `multimap<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 `multimap` that are not described in one of those tables or for
18
  operations where there is additional semantic information.
19
 
@@ -22,44 +22,41 @@ namespace std {
22
  template <class Key, class T, class Compare = less<Key>,
23
  class Allocator = allocator<pair<const Key, T>>>
24
  class multimap {
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 multimap;
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
- // construct/copy/destroy:
58
  multimap() : multimap(Compare()) { }
59
- explicit multimap(const Compare& comp,
60
- const Allocator& = Allocator());
61
  template <class InputIterator>
62
  multimap(InputIterator first, InputIterator last,
63
  const Compare& comp = Compare(),
64
  const Allocator& = Allocator());
65
  multimap(const multimap& x);
@@ -75,11 +72,13 @@ namespace std {
75
  : multimap(first, last, Compare(), a) { }
76
  multimap(initializer_list<value_type> il, const Allocator& a)
77
  : multimap(il, Compare(), a) { }
78
  ~multimap();
79
  multimap& operator=(const multimap& x);
80
- multimap& operator=(multimap&& x);
 
 
81
  multimap& operator=(initializer_list<value_type>);
82
  allocator_type get_allocator() const noexcept;
83
 
84
  // iterators:
85
  iterator begin() noexcept;
@@ -100,27 +99,46 @@ namespace std {
100
  // capacity:
101
  bool empty() const noexcept;
102
  size_type size() const noexcept;
103
  size_type max_size() const noexcept;
104
 
105
- // modifiers:
106
  template <class... Args> iterator emplace(Args&&... args);
107
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
108
  iterator insert(const value_type& x);
 
109
  template <class P> iterator insert(P&& x);
110
  iterator insert(const_iterator position, const value_type& x);
 
111
  template <class P> iterator insert(const_iterator position, P&& x);
112
  template <class InputIterator>
113
  void insert(InputIterator first, InputIterator last);
114
  void insert(initializer_list<value_type>);
115
 
 
 
 
 
 
 
116
  iterator erase(const_iterator position);
117
  size_type erase(const key_type& x);
118
  iterator erase(const_iterator first, const_iterator last);
119
- void swap(multimap&);
 
 
120
  void clear() noexcept;
121
 
 
 
 
 
 
 
 
 
 
122
  // observers:
123
  key_compare key_comp() const;
124
  value_compare value_comp() const;
125
 
126
  // map operations:
@@ -140,20 +158,37 @@ namespace std {
140
  iterator upper_bound(const key_type& x);
141
  const_iterator upper_bound(const key_type& x) const;
142
  template <class K> iterator upper_bound(const K& x);
143
  template <class K> const_iterator upper_bound(const K& x) const;
144
 
145
- pair<iterator,iterator>
146
- equal_range(const key_type& x);
147
- pair<const_iterator,const_iterator>
148
- equal_range(const key_type& x) const;
149
  template <class K>
150
  pair<iterator, iterator> equal_range(const K& x);
151
  template <class K>
152
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
153
  };
154
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
155
  template <class Key, class T, class Compare, class Allocator>
156
  bool operator==(const multimap<Key, T, Compare, Allocator>& x,
157
  const multimap<Key, T, Compare, Allocator>& y);
158
  template <class Key, class T, class Compare, class Allocator>
159
  bool operator< (const multimap<Key, T, Compare, Allocator>& x,
@@ -169,12 +204,13 @@ namespace std {
169
  const multimap<Key, T, Compare, Allocator>& y);
170
  template <class Key, class T, class Compare, class Allocator>
171
  bool operator<=(const multimap<Key, T, Compare, Allocator>& x,
172
  const multimap<Key, T, Compare, Allocator>& y);
173
 
174
- // specialized algorithms:
175
  template <class Key, class T, class Compare, class Allocator>
176
  void swap(multimap<Key, T, Compare, Allocator>& x,
177
- multimap<Key,T,Compare,Allocator>& y);
 
178
  }
179
  ```
180
 
 
7
 
8
  A `multimap` satisfies all of the requirements of a container and 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 `multimap` also provides
12
+ most operations described in  [[associative.reqmts]] for equal keys.
13
+ This means that a `multimap` supports the `a_eq` operations in 
14
+ [[associative.reqmts]] but not the `a_uniq` operations. For a
15
  `multimap<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 `multimap` that are not described in one of those tables or for
18
  operations where there is additional semantic information.
19
 
 
22
  template <class Key, class T, class Compare = less<Key>,
23
  class Allocator = allocator<pair<const Key, T>>>
24
  class multimap {
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 multimap::iterator; // see [container.requirements]
39
+ using const_iterator = implementation-defined // type of multimap::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
 
44
  class value_compare {
45
  friend class multimap;
46
  protected:
47
  Compare comp;
48
  value_compare(Compare c) : comp(c) { }
49
  public:
 
 
 
50
  bool operator()(const value_type& x, const value_type& y) const {
51
  return comp(x.first, y.first);
52
  }
53
  };
54
 
55
+ // [multimap.cons], construct/copy/destroy
56
  multimap() : multimap(Compare()) { }
57
+ explicit multimap(const Compare& comp, const Allocator& = Allocator());
 
58
  template <class InputIterator>
59
  multimap(InputIterator first, InputIterator last,
60
  const Compare& comp = Compare(),
61
  const Allocator& = Allocator());
62
  multimap(const multimap& x);
 
72
  : multimap(first, last, Compare(), a) { }
73
  multimap(initializer_list<value_type> il, const Allocator& a)
74
  : multimap(il, Compare(), a) { }
75
  ~multimap();
76
  multimap& operator=(const multimap& x);
77
+ multimap& operator=(multimap&& x)
78
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
79
+ is_nothrow_move_assignable_v<Compare>);
80
  multimap& 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
+ // [multimap.modifiers], modifiers
105
  template <class... Args> iterator emplace(Args&&... args);
106
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
107
  iterator insert(const value_type& x);
108
+ iterator insert(value_type&& x);
109
  template <class P> iterator insert(P&& x);
110
  iterator insert(const_iterator position, const value_type& x);
111
+ iterator insert(const_iterator position, value_type&& x);
112
  template <class P> iterator insert(const_iterator position, P&& x);
113
  template <class InputIterator>
114
  void insert(InputIterator first, InputIterator last);
115
  void insert(initializer_list<value_type>);
116
 
117
+ node_type extract(const_iterator position);
118
+ node_type extract(const key_type& x);
119
+ iterator insert(node_type&& nh);
120
+ iterator insert(const_iterator hint, node_type&& nh);
121
+
122
+ iterator erase(iterator position);
123
  iterator erase(const_iterator position);
124
  size_type erase(const key_type& x);
125
  iterator erase(const_iterator first, const_iterator last);
126
+ void swap(multimap&)
127
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
128
+ is_nothrow_swappable_v<Compare>);
129
  void clear() noexcept;
130
 
131
+ template<class C2>
132
+ void merge(multimap<Key, T, C2, Allocator>& source);
133
+ template<class C2>
134
+ void merge(multimap<Key, T, C2, Allocator>&& source);
135
+ template<class C2>
136
+ void merge(map<Key, T, C2, Allocator>& source);
137
+ template<class C2>
138
+ void merge(map<Key, T, C2, Allocator>&& source);
139
+
140
  // observers:
141
  key_compare key_comp() const;
142
  value_compare value_comp() const;
143
 
144
  // map operations:
 
158
  iterator upper_bound(const key_type& x);
159
  const_iterator upper_bound(const key_type& x) const;
160
  template <class K> iterator upper_bound(const K& x);
161
  template <class K> const_iterator upper_bound(const K& x) const;
162
 
163
+ pair<iterator, iterator> equal_range(const key_type& x);
164
+ pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
 
 
165
  template <class K>
166
  pair<iterator, iterator> equal_range(const K& x);
167
  template <class K>
168
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
169
  };
170
 
171
+ template<class InputIterator, class Compare = less<iter_key_t<InputIterator>>,
172
+ class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
173
+ multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
174
+ -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>;
175
+
176
+ template<class Key, class T, class Compare = less<Key>,
177
+ class Allocator = allocator<pair<const Key, T>>>
178
+ multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
179
+ -> multimap<Key, T, Compare, Allocator>;
180
+
181
+ template<class InputIterator, class Allocator>
182
+ multimap(InputIterator, InputIterator, Allocator)
183
+ -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
184
+ less<iter_key_t<InputIterator>>, Allocator>;
185
+
186
+ template<class Key, class T, class Allocator>
187
+ multimap(initializer_list<pair<const Key, T>>, Allocator)
188
+ -> multimap<Key, T, less<Key>, Allocator>;
189
+
190
  template <class Key, class T, class Compare, class Allocator>
191
  bool operator==(const multimap<Key, T, Compare, Allocator>& x,
192
  const multimap<Key, T, Compare, Allocator>& y);
193
  template <class Key, class T, class Compare, class Allocator>
194
  bool operator< (const multimap<Key, T, Compare, Allocator>& x,
 
204
  const multimap<Key, T, Compare, Allocator>& y);
205
  template <class Key, class T, class Compare, class Allocator>
206
  bool operator<=(const multimap<Key, T, Compare, Allocator>& x,
207
  const multimap<Key, T, Compare, Allocator>& y);
208
 
209
+ // [multimap.special], specialized algorithms
210
  template <class Key, class T, class Compare, class Allocator>
211
  void swap(multimap<Key, T, Compare, Allocator>& x,
212
+ multimap<Key, T, Compare, Allocator>& y)
213
+ noexcept(noexcept(x.swap(y)));
214
  }
215
  ```
216