From Jason Turner

[unord.set.overview]

C++23 → Trunk 16.2 KB 212 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/tmp8ymc90jb/{from.md → to.md} +105 -101
tmp/tmp8ymc90jb/{from.md → to.md} RENAMED
@@ -5,11 +5,11 @@ unique keys (an `unordered_set` contains at most one of each key value)
5
  and in which the elements’ keys are the elements themselves. The
6
  `unordered_set` class supports forward iterators.
7
 
8
  An `unordered_set` meets all of the requirements of a container
9
  [[container.reqmts]], of an allocator-aware container
10
- [[container.alloc.reqmts]], of an unordered associative container
11
  [[unord.req]]. It provides the operations described in the preceding
12
  requirements table for unique keys; that is, an `unordered_set` supports
13
  the `a_uniq` operations in that table, not the `a_eq` operations. For an
14
  `unordered_set<Key>` the `key_type` and the `value_type` are both `Key`.
15
  The `iterator` and `const_iterator` types are both constant iterator
@@ -17,10 +17,13 @@ types. It is unspecified whether they are the same type.
17
 
18
  Subclause  [[unord.set]] only describes operations on `unordered_set`
19
  that are not described in one of the requirement tables, or for which
20
  there is additional semantic information.
21
 
 
 
 
22
  ``` cpp
23
  namespace std {
24
  template<class Key,
25
  class Hash = hash<Key>,
26
  class Pred = equal_to<Key>,
@@ -31,12 +34,12 @@ namespace std {
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 // type of unordered_set::size_type; // see [container.requirements]
41
  using difference_type = implementation-defined // type of unordered_set::difference_type; // see [container.requirements]
42
 
@@ -46,162 +49,163 @@ namespace std {
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());
56
  template<class InputIterator>
57
- unordered_set(InputIterator f, InputIterator l,
58
- size_type n = see below,
59
- const hasher& hf = hasher(),
60
  const key_equal& eql = key_equal(),
61
  const allocator_type& a = allocator_type());
62
  template<container-compatible-range<value_type> R>
63
- unordered_set(from_range_t, R&& rg,
64
- size_type n = see below,
65
- const hasher& hf = hasher(),
66
  const key_equal& eql = key_equal(),
67
  const allocator_type& a = allocator_type());
68
- unordered_set(const unordered_set&);
69
- unordered_set(unordered_set&&);
70
- explicit unordered_set(const Allocator&);
71
- unordered_set(const unordered_set&, const type_identity_t<Allocator>&);
72
- unordered_set(unordered_set&&, const type_identity_t<Allocator>&);
73
- unordered_set(initializer_list<value_type> il,
74
- size_type n = see below,
75
- const hasher& hf = hasher(),
76
  const key_equal& eql = key_equal(),
77
  const allocator_type& a = allocator_type());
78
- unordered_set(size_type n, const allocator_type& a)
79
  : unordered_set(n, hasher(), key_equal(), a) { }
80
- unordered_set(size_type n, const hasher& hf, const allocator_type& a)
81
  : unordered_set(n, hf, key_equal(), a) { }
82
  template<class InputIterator>
83
- unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
 
84
  : unordered_set(f, l, n, hasher(), key_equal(), a) { }
85
  template<class InputIterator>
86
- unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf,
87
  const allocator_type& a)
88
  : unordered_set(f, l, n, hf, key_equal(), a) { }
89
- unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a)
 
90
  : unordered_set(il, n, hasher(), key_equal(), a) { }
91
  template<container-compatible-range<value_type> R>
92
- unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
93
  : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { }
94
  template<container-compatible-range<value_type> R>
95
- unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
 
96
  : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
97
- unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
98
  const allocator_type& a)
99
  : unordered_set(il, n, hf, key_equal(), a) { }
100
- ~unordered_set();
101
- unordered_set& operator=(const unordered_set&);
102
- unordered_set& operator=(unordered_set&&)
103
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
104
- is_nothrow_move_assignable_v<Hash> &&
105
- is_nothrow_move_assignable_v<Pred>);
106
- unordered_set& operator=(initializer_list<value_type>);
107
- allocator_type get_allocator() const noexcept;
108
 
109
  // iterators
110
- iterator begin() noexcept;
111
- const_iterator begin() const noexcept;
112
- iterator end() noexcept;
113
- const_iterator end() const noexcept;
114
- const_iterator cbegin() const noexcept;
115
- const_iterator cend() const noexcept;
116
 
117
  // capacity
118
- [[nodiscard]] bool empty() const noexcept;
119
- size_type size() const noexcept;
120
- size_type max_size() const noexcept;
121
 
122
- // modifiers
123
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
124
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
125
- pair<iterator, bool> insert(const value_type& obj);
126
- pair<iterator, bool> insert(value_type&& obj);
127
- iterator insert(const_iterator hint, const value_type& obj);
128
- iterator insert(const_iterator hint, value_type&& obj);
129
- template<class InputIterator> void insert(InputIterator first, InputIterator last);
 
 
 
130
  template<container-compatible-range<value_type> R>
131
- void insert_range(R&& rg);
132
- void insert(initializer_list<value_type>);
133
 
134
- node_type extract(const_iterator position);
135
- node_type extract(const key_type& x);
136
- template<class K> node_type extract(K&& x);
137
- insert_return_type insert(node_type&& nh);
138
- iterator insert(const_iterator hint, node_type&& nh);
139
 
140
- iterator erase(iterator position)
141
  requires (!same_as<iterator, const_iterator>);
142
- iterator erase(const_iterator position);
143
- size_type erase(const key_type& k);
144
- template<class K> size_type erase(K&& x);
145
- iterator erase(const_iterator first, const_iterator last);
146
- void swap(unordered_set&)
147
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
148
- is_nothrow_swappable_v<Hash> &&
149
- is_nothrow_swappable_v<Pred>);
150
- void clear() noexcept;
151
 
152
  template<class H2, class P2>
153
- void merge(unordered_set<Key, H2, P2, Allocator>& source);
154
  template<class H2, class P2>
155
- void merge(unordered_set<Key, H2, P2, Allocator>&& source);
156
  template<class H2, class P2>
157
- void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
158
  template<class H2, class P2>
159
- void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
160
 
161
  // observers
162
- hasher hash_function() const;
163
- key_equal key_eq() const;
164
 
165
  // set operations
166
- iterator find(const key_type& k);
167
- const_iterator find(const key_type& k) const;
168
  template<class K>
169
- iterator find(const K& k);
170
  template<class K>
171
- const_iterator find(const K& k) const;
172
- size_type count(const key_type& k) const;
173
  template<class K>
174
- size_type count(const K& k) const;
175
- bool contains(const key_type& k) const;
176
  template<class K>
177
- bool contains(const K& k) const;
178
- pair<iterator, iterator> equal_range(const key_type& k);
179
- pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
180
  template<class K>
181
- pair<iterator, iterator> equal_range(const K& k);
182
  template<class K>
183
- pair<const_iterator, const_iterator> equal_range(const K& k) const;
184
 
185
  // bucket interface
186
- size_type bucket_count() const noexcept;
187
- size_type max_bucket_count() const noexcept;
188
- size_type bucket_size(size_type n) const;
189
- size_type bucket(const key_type& k) const;
190
- local_iterator begin(size_type n);
191
- const_local_iterator begin(size_type n) const;
192
- local_iterator end(size_type n);
193
- const_local_iterator end(size_type n) const;
194
- const_local_iterator cbegin(size_type n) const;
195
- const_local_iterator cend(size_type n) const;
 
196
 
197
  // hash policy
198
- float load_factor() const noexcept;
199
- float max_load_factor() const noexcept;
200
- void max_load_factor(float z);
201
- void rehash(size_type n);
202
- void reserve(size_type n);
203
  };
204
 
205
  template<class InputIterator,
206
  class Hash = hash<iter-value-type<InputIterator>>,
207
  class Pred = equal_to<iter-value-type<InputIterator>>,
 
5
  and in which the elements’ keys are the elements themselves. The
6
  `unordered_set` class supports forward iterators.
7
 
8
  An `unordered_set` meets all of the requirements of a container
9
  [[container.reqmts]], of an allocator-aware container
10
+ [[container.alloc.reqmts]], and of an unordered associative container
11
  [[unord.req]]. It provides the operations described in the preceding
12
  requirements table for unique keys; that is, an `unordered_set` supports
13
  the `a_uniq` operations in that table, not the `a_eq` operations. For an
14
  `unordered_set<Key>` the `key_type` and the `value_type` are both `Key`.
15
  The `iterator` and `const_iterator` types are both constant iterator
 
17
 
18
  Subclause  [[unord.set]] only describes operations on `unordered_set`
19
  that are not described in one of the requirement tables, or for which
20
  there is additional semantic information.
21
 
22
+ The types `iterator` and `const_iterator` meet the constexpr iterator
23
+ requirements [[iterator.requirements.general]].
24
+
25
  ``` cpp
26
  namespace std {
27
  template<class Key,
28
  class Hash = hash<Key>,
29
  class Pred = equal_to<Key>,
 
34
  using key_type = Key;
35
  using value_type = Key;
36
  using hasher = Hash;
37
  using key_equal = Pred;
38
  using allocator_type = Allocator;
39
+ using pointer = allocator_traits<Allocator>::pointer;
40
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
41
  using reference = value_type&;
42
  using const_reference = const value_type&;
43
  using size_type = implementation-defined // type of unordered_set::size_type; // see [container.requirements]
44
  using difference_type = implementation-defined // type of unordered_set::difference_type; // see [container.requirements]
45
 
 
49
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
50
  using node_type = unspecified;
51
  using insert_return_type = insert-return-type<iterator, node_type>;
52
 
53
  // [unord.set.cnstr], construct/copy/destroy
54
+ constexpr unordered_set();
55
+ constexpr explicit unordered_set(size_type n, const hasher& hf = hasher(),
 
56
  const key_equal& eql = key_equal(),
57
  const allocator_type& a = allocator_type());
58
  template<class InputIterator>
59
+ constexpr unordered_set(InputIterator f, InputIterator l,
60
+ size_type n = see below, const hasher& hf = hasher(),
 
61
  const key_equal& eql = key_equal(),
62
  const allocator_type& a = allocator_type());
63
  template<container-compatible-range<value_type> R>
64
+ constexpr unordered_set(from_range_t, R&& rg,
65
+ size_type n = see below, const hasher& hf = hasher(),
 
66
  const key_equal& eql = key_equal(),
67
  const allocator_type& a = allocator_type());
68
+ constexpr unordered_set(const unordered_set&);
69
+ constexpr unordered_set(unordered_set&&);
70
+ constexpr explicit unordered_set(const Allocator&);
71
+ constexpr unordered_set(const unordered_set&, const type_identity_t<Allocator>&);
72
+ constexpr unordered_set(unordered_set&&, const type_identity_t<Allocator>&);
73
+ constexpr unordered_set(initializer_list<value_type> il,
74
+ size_type n = see below, const hasher& hf = hasher(),
 
75
  const key_equal& eql = key_equal(),
76
  const allocator_type& a = allocator_type());
77
+ constexpr unordered_set(size_type n, const allocator_type& a)
78
  : unordered_set(n, hasher(), key_equal(), a) { }
79
+ constexpr unordered_set(size_type n, const hasher& hf, const allocator_type& a)
80
  : unordered_set(n, hf, key_equal(), a) { }
81
  template<class InputIterator>
82
+ constexpr unordered_set(InputIterator f, InputIterator l, size_type n,
83
+ const allocator_type& a)
84
  : unordered_set(f, l, n, hasher(), key_equal(), a) { }
85
  template<class InputIterator>
86
+ constexpr unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf,
87
  const allocator_type& a)
88
  : unordered_set(f, l, n, hf, key_equal(), a) { }
89
+ constexpr unordered_set(initializer_list<value_type> il, size_type n,
90
+ const allocator_type& a)
91
  : unordered_set(il, n, hasher(), key_equal(), a) { }
92
  template<container-compatible-range<value_type> R>
93
+ constexpr unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
94
  : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { }
95
  template<container-compatible-range<value_type> R>
96
+ constexpr unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf,
97
+ const allocator_type& a)
98
  : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
99
+ constexpr unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
100
  const allocator_type& a)
101
  : unordered_set(il, n, hf, key_equal(), a) { }
102
+ constexpr ~unordered_set();
103
+ constexpr unordered_set& operator=(const unordered_set&);
104
+ constexpr unordered_set& operator=(unordered_set&&)
105
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
106
+ is_nothrow_move_assignable_v<Hash> && is_nothrow_move_assignable_v<Pred>);
107
+ constexpr unordered_set& operator=(initializer_list<value_type>);
108
+ constexpr allocator_type get_allocator() const noexcept;
 
109
 
110
  // iterators
111
+ constexpr iterator begin() noexcept;
112
+ constexpr const_iterator begin() const noexcept;
113
+ constexpr iterator end() noexcept;
114
+ constexpr const_iterator end() const noexcept;
115
+ constexpr const_iterator cbegin() const noexcept;
116
+ constexpr const_iterator cend() const noexcept;
117
 
118
  // capacity
119
+ constexpr bool empty() const noexcept;
120
+ constexpr size_type size() const noexcept;
121
+ constexpr size_type max_size() const noexcept;
122
 
123
+ // [unord.set.modifiers], modifiers
124
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
125
+ template<class... Args>
126
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
127
+ constexpr pair<iterator, bool> insert(const value_type& obj);
128
+ constexpr pair<iterator, bool> insert(value_type&& obj);
129
+ template<class K> constexpr pair<iterator, bool> insert(K&& obj);
130
+ constexpr iterator insert(const_iterator hint, const value_type& obj);
131
+ constexpr iterator insert(const_iterator hint, value_type&& obj);
132
+ template<class K> constexpr iterator insert(const_iterator hint, K&& obj);
133
+ template<class InputIterator> 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
+ constexpr iterator erase(iterator position)
145
  requires (!same_as<iterator, const_iterator>);
146
+ constexpr iterator erase(const_iterator position);
147
+ constexpr size_type erase(const key_type& k);
148
+ template<class K> constexpr size_type erase(K&& x);
149
+ constexpr iterator erase(const_iterator first, const_iterator last);
150
+ constexpr void swap(unordered_set&)
151
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
152
+ is_nothrow_swappable_v<Hash> && is_nothrow_swappable_v<Pred>);
153
+ constexpr void clear() noexcept;
 
154
 
155
  template<class H2, class P2>
156
+ constexpr void merge(unordered_set<Key, H2, P2, Allocator>& source);
157
  template<class H2, class P2>
158
+ constexpr void merge(unordered_set<Key, H2, P2, Allocator>&& source);
159
  template<class H2, class P2>
160
+ constexpr void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
161
  template<class H2, class P2>
162
+ constexpr void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
163
 
164
  // observers
165
+ constexpr hasher hash_function() const;
166
+ constexpr key_equal key_eq() const;
167
 
168
  // set operations
169
+ constexpr iterator find(const key_type& k);
170
+ constexpr const_iterator find(const key_type& k) const;
171
  template<class K>
172
+ constexpr iterator find(const K& k);
173
  template<class K>
174
+ constexpr const_iterator find(const K& k) const;
175
+ constexpr size_type count(const key_type& k) const;
176
  template<class K>
177
+ constexpr size_type count(const K& k) const;
178
+ constexpr bool contains(const key_type& k) const;
179
  template<class K>
180
+ constexpr bool contains(const K& k) const;
181
+ constexpr pair<iterator, iterator> equal_range(const key_type& k);
182
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
183
  template<class K>
184
+ constexpr pair<iterator, iterator> equal_range(const K& k);
185
  template<class K>
186
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& k) const;
187
 
188
  // bucket interface
189
+ constexpr size_type bucket_count() const noexcept;
190
+ constexpr size_type max_bucket_count() const noexcept;
191
+ constexpr size_type bucket_size(size_type n) const;
192
+ constexpr size_type bucket(const key_type& k) const;
193
+ template<class K> constexpr size_type bucket(const K& k) const;
194
+ constexpr local_iterator begin(size_type n);
195
+ constexpr const_local_iterator begin(size_type n) const;
196
+ constexpr local_iterator end(size_type n);
197
+ constexpr const_local_iterator end(size_type n) const;
198
+ constexpr const_local_iterator cbegin(size_type n) const;
199
+ constexpr const_local_iterator cend(size_type n) const;
200
 
201
  // hash policy
202
+ constexpr float load_factor() const noexcept;
203
+ constexpr float max_load_factor() const noexcept;
204
+ constexpr void max_load_factor(float z);
205
+ constexpr void rehash(size_type n);
206
+ constexpr void reserve(size_type n);
207
  };
208
 
209
  template<class InputIterator,
210
  class Hash = hash<iter-value-type<InputIterator>>,
211
  class Pred = equal_to<iter-value-type<InputIterator>>,