From Jason Turner

[unord.set.overview]

C++14 → C++17 12.0 KB 154 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/tmp_a2hdeev/{from.md → to.md} +106 -42
tmp/tmp_a2hdeev/{from.md → to.md} RENAMED
@@ -10,45 +10,46 @@ an unordered associative container, and of an allocator-aware container
10
  (Table  [[tab:containers.allocatoraware]]). It provides the operations
11
  described in the preceding requirements table for unique keys; that is,
12
  an `unordered_set` supports the `a_uniq` operations in that table, not
13
  the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
14
  the value type are both `Key`. The `iterator` and `const_iterator` types
15
- are both const iterator types. It is unspecified whether they are the
16
  same type.
17
 
18
  This section only describes operations on `unordered_set` that are not
19
  described in one of the requirement tables, or for which there is
20
  additional semantic information.
21
 
22
  ``` cpp
23
  namespace std {
24
  template <class Key,
25
  class Hash = hash<Key>,
26
- class Pred = std::equal_to<Key>,
27
- class Allocator = std::allocator<Key> >
28
- class unordered_set
29
- {
30
  public:
31
- // types
32
- typedef Key key_type;
33
- typedef Key value_type;
34
- typedef Hash hasher;
35
- typedef Pred key_equal;
36
- typedef Allocator allocator_type;
37
- typedef typename allocator_traits<Allocator>::pointer pointer;
38
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
39
- typedef value_type& reference;
40
- typedef const value_type& const_reference;
41
- typedef implementation-defined size_type;
42
- typedef implementation-defined difference_type;
43
 
44
- typedef implementation-defined iterator;
45
- typedef implementation-defined const_iterator;
46
- typedef implementation-defined local_iterator;
47
- typedef implementation-defined const_local_iterator;
 
 
48
 
49
- // construct/destroy/copy
50
  unordered_set();
51
  explicit unordered_set(size_type n,
52
  const hasher& hf = hasher(),
53
  const key_equal& eql = key_equal(),
54
  const allocator_type& a = allocator_type());
@@ -61,12 +62,12 @@ namespace std {
61
  unordered_set(const unordered_set&);
62
  unordered_set(unordered_set&&);
63
  explicit unordered_set(const Allocator&);
64
  unordered_set(const unordered_set&, const Allocator&);
65
  unordered_set(unordered_set&&, const Allocator&);
66
- unordered_set(initializer_list<value_type>,
67
- size_type = see below,
68
  const hasher& hf = hasher(),
69
  const key_equal& eql = key_equal(),
70
  const allocator_type& a = allocator_type());
71
  unordered_set(size_type n, const allocator_type& a)
72
  : unordered_set(n, hasher(), key_equal(), a) { }
@@ -84,56 +85,76 @@ namespace std {
84
  unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
85
  const allocator_type& a)
86
  : unordered_set(il, n, hf, key_equal(), a) { }
87
  ~unordered_set();
88
  unordered_set& operator=(const unordered_set&);
89
- unordered_set& operator=(unordered_set&&);
 
 
 
90
  unordered_set& operator=(initializer_list<value_type>);
91
  allocator_type get_allocator() const noexcept;
92
 
93
- // size and capacity
94
- bool empty() const noexcept;
95
- size_type size() const noexcept;
96
- size_type max_size() const noexcept;
97
-
98
- // iterators
99
  iterator begin() noexcept;
100
  const_iterator begin() const noexcept;
101
  iterator end() noexcept;
102
  const_iterator end() const noexcept;
103
  const_iterator cbegin() const noexcept;
104
  const_iterator cend() const noexcept;
105
 
106
- // modifiers
 
 
 
 
 
107
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
108
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
109
  pair<iterator, bool> insert(const value_type& obj);
110
  pair<iterator, bool> insert(value_type&& obj);
111
  iterator insert(const_iterator hint, const value_type& obj);
112
  iterator insert(const_iterator hint, value_type&& obj);
113
  template <class InputIterator> 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& k);
118
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
119
  void clear() noexcept;
120
 
121
- void swap(unordered_set&);
 
 
 
 
 
 
 
122
 
123
- // observers
124
  hasher hash_function() const;
125
  key_equal key_eq() const;
126
 
127
- // lookup
128
  iterator find(const key_type& k);
129
  const_iterator find(const key_type& k) const;
130
  size_type count(const key_type& k) const;
131
- std::pair<iterator, iterator> equal_range(const key_type& k);
132
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
133
 
134
- // bucket interface
135
  size_type bucket_count() const noexcept;
136
  size_type max_bucket_count() const noexcept;
137
  size_type bucket_size(size_type n) const;
138
  size_type bucket(const key_type& k) const;
139
  local_iterator begin(size_type n);
@@ -141,26 +162,69 @@ namespace std {
141
  local_iterator end(size_type n);
142
  const_local_iterator end(size_type n) const;
143
  const_local_iterator cbegin(size_type n) const;
144
  const_local_iterator cend(size_type n) const;
145
 
146
- // hash policy
147
  float load_factor() const noexcept;
148
  float max_load_factor() const noexcept;
149
  void max_load_factor(float z);
150
  void rehash(size_type n);
151
  void reserve(size_type n);
152
  };
153
 
154
- template <class Key, class Hash, class Pred, class Alloc>
155
- void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
156
- unordered_set<Key, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
157
 
158
  template <class Key, class Hash, class Pred, class Alloc>
159
  bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
160
  const unordered_set<Key, Hash, Pred, Alloc>& b);
161
  template <class Key, class Hash, class Pred, class Alloc>
162
  bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
163
  const unordered_set<Key, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
164
  }
165
  ```
166
 
 
 
 
 
 
10
  (Table  [[tab:containers.allocatoraware]]). It provides the operations
11
  described in the preceding requirements table for unique keys; that is,
12
  an `unordered_set` supports the `a_uniq` operations in that table, not
13
  the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
14
  the value type are both `Key`. The `iterator` and `const_iterator` types
15
+ are both constant iterator types. It is unspecified whether they are the
16
  same type.
17
 
18
  This section only describes operations on `unordered_set` that are not
19
  described in one of the requirement tables, or for which there is
20
  additional semantic information.
21
 
22
  ``` cpp
23
  namespace std {
24
  template <class Key,
25
  class Hash = hash<Key>,
26
+ class Pred = equal_to<Key>,
27
+ class Allocator = allocator<Key>>
28
+ class unordered_set {
 
29
  public:
30
+ // types:
31
+ using key_type = Key;
32
+ using value_type = Key;
33
+ using hasher = Hash;
34
+ using key_equal = Pred;
35
+ using allocator_type = Allocator;
36
+ using pointer = typename allocator_traits<Allocator>::pointer;
37
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
38
+ using reference = value_type&;
39
+ using const_reference = const value_type&;
40
+ using size_type = implementation-defined; // see [container.requirements]
41
+ using difference_type = implementation-defined; // see [container.requirements]
42
 
43
+ using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
44
+ using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
45
+ using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
46
+ using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
47
+ using node_type = unspecified;
48
+ using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
49
 
50
+ // [unord.set.cnstr], construct/copy/destroy
51
  unordered_set();
52
  explicit unordered_set(size_type n,
53
  const hasher& hf = hasher(),
54
  const key_equal& eql = key_equal(),
55
  const allocator_type& a = allocator_type());
 
62
  unordered_set(const unordered_set&);
63
  unordered_set(unordered_set&&);
64
  explicit unordered_set(const Allocator&);
65
  unordered_set(const unordered_set&, const Allocator&);
66
  unordered_set(unordered_set&&, const Allocator&);
67
+ unordered_set(initializer_list<value_type> il,
68
+ size_type n = see below,
69
  const hasher& hf = hasher(),
70
  const key_equal& eql = key_equal(),
71
  const allocator_type& a = allocator_type());
72
  unordered_set(size_type n, const allocator_type& a)
73
  : unordered_set(n, hasher(), key_equal(), a) { }
 
85
  unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
86
  const allocator_type& a)
87
  : unordered_set(il, n, hf, key_equal(), a) { }
88
  ~unordered_set();
89
  unordered_set& operator=(const unordered_set&);
90
+ unordered_set& operator=(unordered_set&&)
91
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
92
+ is_nothrow_move_assignable_v<Hash> &&
93
+ is_nothrow_move_assignable_v<Pred>);
94
  unordered_set& operator=(initializer_list<value_type>);
95
  allocator_type get_allocator() const noexcept;
96
 
97
+ // iterators:
 
 
 
 
 
98
  iterator begin() noexcept;
99
  const_iterator begin() const noexcept;
100
  iterator end() noexcept;
101
  const_iterator end() const noexcept;
102
  const_iterator cbegin() const noexcept;
103
  const_iterator cend() const noexcept;
104
 
105
+ // capacity:
106
+ bool empty() const noexcept;
107
+ size_type size() const noexcept;
108
+ size_type max_size() const noexcept;
109
+
110
+ // 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& obj);
114
  pair<iterator, bool> insert(value_type&& obj);
115
  iterator insert(const_iterator hint, const value_type& obj);
116
  iterator insert(const_iterator hint, value_type&& obj);
117
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
118
  void insert(initializer_list<value_type>);
119
 
120
+ node_type extract(const_iterator position);
121
+ node_type extract(const key_type& x);
122
+ insert_return_type insert(node_type&& nh);
123
+ iterator insert(const_iterator hint, node_type&& nh);
124
+
125
+ iterator erase(iterator position);
126
  iterator erase(const_iterator position);
127
  size_type erase(const key_type& k);
128
  iterator erase(const_iterator first, const_iterator last);
129
+ void swap(unordered_set&)
130
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
131
+ is_nothrow_swappable_v<Hash> &&
132
+ is_nothrow_swappable_v<Pred>);
133
  void clear() noexcept;
134
 
135
+ template<class H2, class P2>
136
+ void merge(unordered_set<Key, H2, P2, Allocator>& source);
137
+ template<class H2, class P2>
138
+ void merge(unordered_set<Key, H2, P2, Allocator>&& source);
139
+ template<class H2, class P2>
140
+ void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
141
+ template<class H2, class P2>
142
+ void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
143
 
144
+ // observers:
145
  hasher hash_function() const;
146
  key_equal key_eq() const;
147
 
148
+ // set operations:
149
  iterator find(const key_type& k);
150
  const_iterator find(const key_type& k) const;
151
  size_type count(const key_type& k) const;
152
+ pair<iterator, iterator> equal_range(const key_type& k);
153
+ pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
154
 
155
+ // bucket interface:
156
  size_type bucket_count() const noexcept;
157
  size_type max_bucket_count() const noexcept;
158
  size_type bucket_size(size_type n) const;
159
  size_type bucket(const key_type& k) const;
160
  local_iterator begin(size_type n);
 
162
  local_iterator end(size_type n);
163
  const_local_iterator end(size_type n) const;
164
  const_local_iterator cbegin(size_type n) const;
165
  const_local_iterator cend(size_type n) const;
166
 
167
+ // hash policy:
168
  float load_factor() const noexcept;
169
  float max_load_factor() const noexcept;
170
  void max_load_factor(float z);
171
  void rehash(size_type n);
172
  void reserve(size_type n);
173
  };
174
 
175
+ template<class InputIterator,
176
+ class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
177
+ class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
178
+ class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
179
+ unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
180
+ Hash = Hash(), Pred = Pred(), Allocator = Allocator())
181
+ -> unordered_set<typename iterator_traits<InputIterator>::value_type,
182
+ Hash, Pred, Allocator>;
183
+
184
+ template<class T, class Hash = hash<T>,
185
+ class Pred = equal_to<T>, class Allocator = allocator<T>>
186
+ unordered_set(initializer_list<T>, typename see below::size_type = see below,
187
+ Hash = Hash(), Pred = Pred(), Allocator = Allocator())
188
+ -> unordered_set<T, Hash, Pred, Allocator>;
189
+
190
+ template<class InputIterator, class Allocator>
191
+ unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
192
+ -> unordered_set<typename iterator_traits<InputIterator>::value_type,
193
+ hash<typename iterator_traits<InputIterator>::value_type>,
194
+ equal_to<typename iterator_traits<InputIterator>::value_type>,
195
+ Allocator>;
196
+
197
+ template<class InputIterator, class Hash, class Allocator>
198
+ unordered_set(InputIterator, InputIterator, typename see below::size_type,
199
+ Hash, Allocator)
200
+ -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
201
+ equal_to<typename iterator_traits<InputIterator>::value_type>,
202
+ Allocator>;
203
+
204
+ template<class T, class Allocator>
205
+ unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
206
+ -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
207
+
208
+ template<class T, class Hash, class Allocator>
209
+ unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
210
+ -> unordered_set<T, Hash, equal_to<T>, Allocator>;
211
 
212
  template <class Key, class Hash, class Pred, class Alloc>
213
  bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
214
  const unordered_set<Key, Hash, Pred, Alloc>& b);
215
  template <class Key, class Hash, class Pred, class Alloc>
216
  bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
217
  const unordered_set<Key, Hash, Pred, Alloc>& b);
218
+
219
+ // [unord.set.swap], swap
220
+ template <class Key, class Hash, class Pred, class Alloc>
221
+ void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
222
+ unordered_set<Key, Hash, Pred, Alloc>& y)
223
+ noexcept(noexcept(x.swap(y)));
224
  }
225
  ```
226
 
227
+ A `size_type` parameter type in an `unordered_set` deduction guide
228
+ refers to the `size_type` member type of the primary `unordered_set`
229
+ template.
230
+