From Jason Turner

[multiset]

C++14 → C++17 10.2 KB 122 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/tmpc68lhezd/{from.md → to.md} +72 -42
tmp/tmpc68lhezd/{from.md → to.md} RENAMED
@@ -9,13 +9,13 @@ bidirectional iterators.
9
 
10
  A `multiset` satisfies all of the requirements of a container, of a
11
  reversible container ([[container.requirements]]), of an associative
12
  container ([[associative.reqmts]]), and of an allocator-aware container
13
  (Table  [[tab:containers.allocatoraware]]). `multiset` also provides
14
- most operations described in ([[associative.reqmts]]) for duplicate
15
- keys. This means that a `multiset` supports the `a_eq` operations in (
16
- [[associative.reqmts]]) but not the `a_uniq` operations. For a
17
  `multiset<Key>` both the `key_type` and `value_type` are `Key`.
18
  Descriptions are provided here only for operations on `multiset` that
19
  are not described in one of these tables and for operations where there
20
  is additional semantic information.
21
 
@@ -24,50 +24,50 @@ namespace std {
24
  template <class Key, class Compare = less<Key>,
25
  class Allocator = allocator<Key>>
26
  class multiset {
27
  public:
28
  // types:
29
- typedef Key key_type;
30
- typedef Key value_type;
31
- typedef Compare key_compare;
32
- typedef Compare value_compare;
33
- typedef Allocator allocator_type;
34
- typedef value_type& reference;
35
- typedef const value_type& const_reference;
36
- typedef implementation-defined iterator; // see [container.requirements]
37
- typedef implementation-defined const_iterator; // see [container.requirements]
38
- typedef implementation-defined size_type; // see [container.requirements]
39
- typedef implementation-defined difference_type;// see [container.requirements]
40
- typedef typename allocator_traits<Allocator>::pointer pointer;
41
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
42
- typedef std::reverse_iterator<iterator> reverse_iterator;
43
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
44
 
45
- // construct/copy/destroy:
46
  multiset() : multiset(Compare()) { }
47
- explicit multiset(const Compare& comp,
48
- const Allocator& = Allocator());
49
  template <class InputIterator>
50
  multiset(InputIterator first, InputIterator last,
51
- const Compare& comp = Compare(),
52
- const Allocator& = Allocator());
53
  multiset(const multiset& x);
54
  multiset(multiset&& x);
55
  explicit multiset(const Allocator&);
56
  multiset(const multiset&, const Allocator&);
57
  multiset(multiset&&, const Allocator&);
58
- multiset(initializer_list<value_type>,
59
- const Compare& = Compare(),
60
  const Allocator& = Allocator());
61
  template <class InputIterator>
62
  multiset(InputIterator first, InputIterator last, const Allocator& a)
63
  : multiset(first, last, Compare(), a) { }
64
  multiset(initializer_list<value_type> il, const Allocator& a)
65
  : multiset(il, Compare(), a) { }
66
  ~multiset();
67
  multiset& operator=(const multiset& x);
68
- multiset& operator=(multiset&& x);
 
 
69
  multiset& operator=(initializer_list<value_type>);
70
  allocator_type get_allocator() const noexcept;
71
 
72
  // iterators:
73
  iterator begin() noexcept;
@@ -99,16 +99,33 @@ namespace std {
99
  iterator insert(const_iterator position, value_type&& x);
100
  template <class InputIterator>
101
  void insert(InputIterator first, InputIterator last);
102
  void insert(initializer_list<value_type>);
103
 
 
 
 
 
 
 
104
  iterator erase(const_iterator position);
105
  size_type erase(const key_type& x);
106
  iterator erase(const_iterator first, const_iterator last);
107
- void swap(multiset&);
 
 
108
  void clear() noexcept;
109
 
 
 
 
 
 
 
 
 
 
110
  // observers:
111
  key_compare key_comp() const;
112
  value_compare value_comp() const;
113
 
114
  // set operations:
@@ -136,10 +153,29 @@ namespace std {
136
  pair<iterator, iterator> equal_range(const K& x);
137
  template <class K>
138
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
139
  };
140
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
141
  template <class Key, class Compare, class Allocator>
142
  bool operator==(const multiset<Key, Compare, Allocator>& x,
143
  const multiset<Key, Compare, Allocator>& y);
144
  template <class Key, class Compare, class Allocator>
145
  bool operator< (const multiset<Key, Compare, Allocator>& x,
@@ -155,38 +191,35 @@ namespace std {
155
  const multiset<Key, Compare, Allocator>& y);
156
  template <class Key, class Compare, class Allocator>
157
  bool operator<=(const multiset<Key, Compare, Allocator>& x,
158
  const multiset<Key, Compare, Allocator>& y);
159
 
160
- // specialized algorithms:
161
  template <class Key, class Compare, class Allocator>
162
  void swap(multiset<Key, Compare, Allocator>& x,
163
- multiset<Key,Compare,Allocator>& y);
 
164
  }
165
  ```
166
 
167
  #### `multiset` constructors <a id="multiset.cons">[[multiset.cons]]</a>
168
 
169
  ``` cpp
170
- explicit multiset(const Compare& comp,
171
- const Allocator& = Allocator());
172
  ```
173
 
174
- *Effects:* Constructs an empty set using the specified comparison object
175
- and allocator.
176
 
177
  *Complexity:* Constant.
178
 
179
  ``` cpp
180
  template <class InputIterator>
181
  multiset(InputIterator first, InputIterator last,
182
  const Compare& comp = Compare(), const Allocator& = Allocator());
183
  ```
184
 
185
- *Requires:* If the iterator’s indirection operator returns an lvalue or
186
- a const rvalue, then `Key` shall be `CopyInsertable` into `*this`.
187
-
188
  *Effects:* Constructs an empty `multiset` using the specified comparison
189
  object and allocator, and inserts elements from the range \[`first`,
190
  `last`).
191
 
192
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
@@ -195,14 +228,11 @@ sorted using `comp` and otherwise N log N, where N is `last - first`.
195
  #### `multiset` specialized algorithms <a id="multiset.special">[[multiset.special]]</a>
196
 
197
  ``` cpp
198
  template <class Key, class Compare, class Allocator>
199
  void swap(multiset<Key, Compare, Allocator>& x,
200
- multiset<Key,Compare,Allocator>& y);
 
201
  ```
202
 
203
- *Effects:*
204
-
205
- ``` cpp
206
- x.swap(y);
207
- ```
208
 
 
9
 
10
  A `multiset` satisfies all of the requirements of a container, of a
11
  reversible container ([[container.requirements]]), of an associative
12
  container ([[associative.reqmts]]), and of an allocator-aware container
13
  (Table  [[tab:containers.allocatoraware]]). `multiset` also provides
14
+ most operations described in  [[associative.reqmts]] for duplicate keys.
15
+ This means that a `multiset` supports the `a_eq` operations in 
16
+ [[associative.reqmts]] but not the `a_uniq` operations. For a
17
  `multiset<Key>` both the `key_type` and `value_type` are `Key`.
18
  Descriptions are provided here only for operations on `multiset` that
19
  are not described in one of these tables and for operations where there
20
  is additional semantic information.
21
 
 
24
  template <class Key, class Compare = less<Key>,
25
  class Allocator = allocator<Key>>
26
  class multiset {
27
  public:
28
  // types:
29
+ using key_type = Key;
30
+ using key_compare = Compare;
31
+ using value_type = Key;
32
+ using value_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; // see [container.requirements]
39
+ using difference_type = implementation-defined; // see [container.requirements]
40
+ using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
41
+ using const_iterator = implementation-defined // type of multiset::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;
45
 
46
+ // [multiset.cons], construct/copy/destroy
47
  multiset() : multiset(Compare()) { }
48
+ explicit multiset(const Compare& comp, const Allocator& = Allocator());
 
49
  template <class InputIterator>
50
  multiset(InputIterator first, InputIterator last,
51
+ const Compare& comp = Compare(), const Allocator& = Allocator());
 
52
  multiset(const multiset& x);
53
  multiset(multiset&& x);
54
  explicit multiset(const Allocator&);
55
  multiset(const multiset&, const Allocator&);
56
  multiset(multiset&&, const Allocator&);
57
+ multiset(initializer_list<value_type>, const Compare& = Compare(),
 
58
  const Allocator& = Allocator());
59
  template <class InputIterator>
60
  multiset(InputIterator first, InputIterator last, const Allocator& a)
61
  : multiset(first, last, Compare(), a) { }
62
  multiset(initializer_list<value_type> il, const Allocator& a)
63
  : multiset(il, Compare(), a) { }
64
  ~multiset();
65
  multiset& operator=(const multiset& x);
66
+ multiset& operator=(multiset&& x)
67
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
68
+ is_nothrow_move_assignable_v<Compare>);
69
  multiset& operator=(initializer_list<value_type>);
70
  allocator_type get_allocator() const noexcept;
71
 
72
  // iterators:
73
  iterator begin() noexcept;
 
99
  iterator insert(const_iterator position, value_type&& x);
100
  template <class InputIterator>
101
  void insert(InputIterator first, InputIterator last);
102
  void insert(initializer_list<value_type>);
103
 
104
+ node_type extract(const_iterator position);
105
+ node_type extract(const key_type& x);
106
+ iterator insert(node_type&& nh);
107
+ iterator insert(const_iterator hint, node_type&& nh);
108
+
109
+ iterator erase(iterator position);
110
  iterator erase(const_iterator position);
111
  size_type erase(const key_type& x);
112
  iterator erase(const_iterator first, const_iterator last);
113
+ void swap(multiset&)
114
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
115
+ is_nothrow_swappable_v<Compare>);
116
  void clear() noexcept;
117
 
118
+ template<class C2>
119
+ void merge(multiset<Key, C2, Allocator>& source);
120
+ template<class C2>
121
+ void merge(multiset<Key, C2, Allocator>&& source);
122
+ template<class C2>
123
+ void merge(set<Key, C2, Allocator>& source);
124
+ template<class C2>
125
+ void merge(set<Key, C2, Allocator>&& source);
126
+
127
  // observers:
128
  key_compare key_comp() const;
129
  value_compare value_comp() const;
130
 
131
  // set operations:
 
153
  pair<iterator, iterator> equal_range(const K& x);
154
  template <class K>
155
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
156
  };
157
 
158
+ template<class InputIterator,
159
+ class Compare = less<typename iterator_traits<InputIterator>::value_type>,
160
+ class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
161
+ multiset(InputIterator, InputIterator,
162
+ Compare = Compare(), Allocator = Allocator())
163
+ -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>;
164
+
165
+ template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
166
+ multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
167
+ -> multiset<Key, Compare, Allocator>;
168
+
169
+ template<class InputIterator, class Allocator>
170
+ multiset(InputIterator, InputIterator, Allocator)
171
+ -> multiset<typename iterator_traits<InputIterator>::value_type,
172
+ less<typename iterator_traits<InputIterator>::value_type>, Allocator>;
173
+
174
+ template<class Key, class Allocator>
175
+ multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
176
+
177
  template <class Key, class Compare, class Allocator>
178
  bool operator==(const multiset<Key, Compare, Allocator>& x,
179
  const multiset<Key, Compare, Allocator>& y);
180
  template <class Key, class Compare, class Allocator>
181
  bool operator< (const multiset<Key, Compare, Allocator>& x,
 
191
  const multiset<Key, Compare, Allocator>& y);
192
  template <class Key, class Compare, class Allocator>
193
  bool operator<=(const multiset<Key, Compare, Allocator>& x,
194
  const multiset<Key, Compare, Allocator>& y);
195
 
196
+ // [multiset.special], specialized algorithms
197
  template <class Key, class Compare, class Allocator>
198
  void swap(multiset<Key, Compare, Allocator>& x,
199
+ multiset<Key, Compare, Allocator>& y)
200
+ noexcept(noexcept(x.swap(y)));
201
  }
202
  ```
203
 
204
  #### `multiset` constructors <a id="multiset.cons">[[multiset.cons]]</a>
205
 
206
  ``` cpp
207
+ explicit multiset(const Compare& comp, const Allocator& = Allocator());
 
208
  ```
209
 
210
+ *Effects:* Constructs an empty `multiset` using the specified comparison
211
+ object and allocator.
212
 
213
  *Complexity:* Constant.
214
 
215
  ``` cpp
216
  template <class InputIterator>
217
  multiset(InputIterator first, InputIterator last,
218
  const Compare& comp = Compare(), const Allocator& = Allocator());
219
  ```
220
 
 
 
 
221
  *Effects:* Constructs an empty `multiset` using the specified comparison
222
  object and allocator, and inserts elements from the range \[`first`,
223
  `last`).
224
 
225
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
 
228
  #### `multiset` specialized algorithms <a id="multiset.special">[[multiset.special]]</a>
229
 
230
  ``` cpp
231
  template <class Key, class Compare, class Allocator>
232
  void swap(multiset<Key, Compare, Allocator>& x,
233
+ multiset<Key, Compare, Allocator>& y)
234
+ noexcept(noexcept(x.swap(y)));
235
  ```
236
 
237
+ *Effects:* As if by `x.swap(y)`.
 
 
 
 
238