blob: fd378fa071457764cf27c88d6cccf30648901d21 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_set -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UNORDERED_SET
12#define _LIBCPP_UNORDERED_SET
13
14/*
15
16 unordered_set synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
24 class Alloc = allocator<Value>>
25class unordered_set
26{
27public:
28 // types
29 typedef Value key_type;
30 typedef key_type value_type;
31 typedef Hash hasher;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef value_type& reference;
35 typedef const value_type& const_reference;
36 typedef typename allocator_traits<allocator_type>::pointer pointer;
37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
38 typedef typename allocator_traits<allocator_type>::size_type size_type;
39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
40
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
45
Howard Hinnant04dae1d2011-06-04 20:18:37 +000046 unordered_set()
47 noexcept(
48 is_nothrow_default_constructible<hasher>::value &&
49 is_nothrow_default_constructible<key_equal>::value &&
50 is_nothrow_default_constructible<allocator_type>::value);
51 explicit unordered_set(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000052 const key_equal& eql = key_equal(),
53 const allocator_type& a = allocator_type());
54 template <class InputIterator>
55 unordered_set(InputIterator f, InputIterator l,
56 size_type n = 0, const hasher& hf = hasher(),
57 const key_equal& eql = key_equal(),
58 const allocator_type& a = allocator_type());
59 explicit unordered_set(const allocator_type&);
60 unordered_set(const unordered_set&);
61 unordered_set(const unordered_set&, const Allocator&);
Howard Hinnant04dae1d2011-06-04 20:18:37 +000062 unordered_set(unordered_set&&)
63 noexcept(
64 is_nothrow_move_constructible<hasher>::value &&
65 is_nothrow_move_constructible<key_equal>::value &&
66 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000067 unordered_set(unordered_set&&, const Allocator&);
68 unordered_set(initializer_list<value_type>, size_type n = 0,
69 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
70 const allocator_type& a = allocator_type());
Marshall Clowbd444af2013-09-30 21:33:51 +000071 unordered_set(size_type n, const allocator_type& a); // C++14
72 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
73 template <class InputIterator>
74 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
75 template <class InputIterator>
76 unordered_set(InputIterator f, InputIterator l, size_type n,
77 const hasher& hf, const allocator_type& a); // C++14
78 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
79 unordered_set(initializer_list<value_type> il, size_type n,
80 const hasher& hf, const allocator_type& a); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000081 ~unordered_set();
82 unordered_set& operator=(const unordered_set&);
Howard Hinnant04dae1d2011-06-04 20:18:37 +000083 unordered_set& operator=(unordered_set&&)
84 noexcept(
85 allocator_type::propagate_on_container_move_assignment::value &&
86 is_nothrow_move_assignable<allocator_type>::value &&
87 is_nothrow_move_assignable<hasher>::value &&
88 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000089 unordered_set& operator=(initializer_list<value_type>);
90
Howard Hinnant04dae1d2011-06-04 20:18:37 +000091 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000092
Howard Hinnant04dae1d2011-06-04 20:18:37 +000093 bool empty() const noexcept;
94 size_type size() const noexcept;
95 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000096
Howard Hinnant04dae1d2011-06-04 20:18:37 +000097 iterator begin() noexcept;
98 iterator end() noexcept;
99 const_iterator begin() const noexcept;
100 const_iterator end() const noexcept;
101 const_iterator cbegin() const noexcept;
102 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000103
104 template <class... Args>
105 pair<iterator, bool> emplace(Args&&... args);
106 template <class... Args>
107 iterator emplace_hint(const_iterator position, Args&&... args);
108 pair<iterator, bool> insert(const value_type& obj);
109 pair<iterator, bool> insert(value_type&& obj);
110 iterator insert(const_iterator hint, const value_type& obj);
111 iterator insert(const_iterator hint, value_type&& obj);
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& k);
118 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000119 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000121 void swap(unordered_set&)
122 noexcept(
123 (!allocator_type::propagate_on_container_swap::value ||
124 __is_nothrow_swappable<allocator_type>::value) &&
125 __is_nothrow_swappable<hasher>::value &&
126 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000127
128 hasher hash_function() const;
129 key_equal key_eq() const;
130
131 iterator find(const key_type& k);
132 const_iterator find(const key_type& k) const;
133 size_type count(const key_type& k) const;
134 pair<iterator, iterator> equal_range(const key_type& k);
135 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
136
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000137 size_type bucket_count() const noexcept;
138 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000139
140 size_type bucket_size(size_type n) const;
141 size_type bucket(const key_type& k) const;
142
143 local_iterator begin(size_type n);
144 local_iterator end(size_type n);
145 const_local_iterator begin(size_type n) const;
146 const_local_iterator end(size_type n) const;
147 const_local_iterator cbegin(size_type n) const;
148 const_local_iterator cend(size_type n) const;
149
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000150 float load_factor() const noexcept;
151 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000152 void max_load_factor(float z);
153 void rehash(size_type n);
154 void reserve(size_type n);
155};
156
157template <class Value, class Hash, class Pred, class Alloc>
158 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000159 unordered_set<Value, Hash, Pred, Alloc>& y)
160 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000161
162template <class Value, class Hash, class Pred, class Alloc>
163 bool
164 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
165 const unordered_set<Value, Hash, Pred, Alloc>& y);
166
167template <class Value, class Hash, class Pred, class Alloc>
168 bool
169 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
170 const unordered_set<Value, Hash, Pred, Alloc>& y);
171
172template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
173 class Alloc = allocator<Value>>
174class unordered_multiset
175{
176public:
177 // types
178 typedef Value key_type;
179 typedef key_type value_type;
180 typedef Hash hasher;
181 typedef Pred key_equal;
182 typedef Alloc allocator_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
194
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000195 unordered_multiset()
196 noexcept(
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multiset(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multiset(const allocator_type&);
209 unordered_multiset(const unordered_multiset&);
210 unordered_multiset(const unordered_multiset&, const Allocator&);
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000211 unordered_multiset(unordered_multiset&&)
212 noexcept(
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216 unordered_multiset(unordered_multiset&&, const Allocator&);
217 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
Marshall Clowbd444af2013-09-30 21:33:51 +0000220 unordered_multiset(size_type n, const allocator_type& a); // C++14
221 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
222 template <class InputIterator>
223 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
224 template <class InputIterator>
225 unordered_multiset(InputIterator f, InputIterator l, size_type n,
226 const hasher& hf, const allocator_type& a); // C++14
227 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
228 unordered_multiset(initializer_list<value_type> il, size_type n,
229 const hasher& hf, const allocator_type& a); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000230 ~unordered_multiset();
231 unordered_multiset& operator=(const unordered_multiset&);
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000232 unordered_multiset& operator=(unordered_multiset&&)
233 noexcept(
234 allocator_type::propagate_on_container_move_assignment::value &&
235 is_nothrow_move_assignable<allocator_type>::value &&
236 is_nothrow_move_assignable<hasher>::value &&
237 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000238 unordered_multiset& operator=(initializer_list<value_type>);
239
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000240 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000241
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000242 bool empty() const noexcept;
243 size_type size() const noexcept;
244 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000245
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000246 iterator begin() noexcept;
247 iterator end() noexcept;
248 const_iterator begin() const noexcept;
249 const_iterator end() const noexcept;
250 const_iterator cbegin() const noexcept;
251 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000252
253 template <class... Args>
254 iterator emplace(Args&&... args);
255 template <class... Args>
256 iterator emplace_hint(const_iterator position, Args&&... args);
257 iterator insert(const value_type& obj);
258 iterator insert(value_type&& obj);
259 iterator insert(const_iterator hint, const value_type& obj);
260 iterator insert(const_iterator hint, value_type&& obj);
261 template <class InputIterator>
262 void insert(InputIterator first, InputIterator last);
263 void insert(initializer_list<value_type>);
264
265 iterator erase(const_iterator position);
266 size_type erase(const key_type& k);
267 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000268 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000269
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000270 void swap(unordered_multiset&)
271 noexcept(
272 (!allocator_type::propagate_on_container_swap::value ||
273 __is_nothrow_swappable<allocator_type>::value) &&
274 __is_nothrow_swappable<hasher>::value &&
275 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000276
277 hasher hash_function() const;
278 key_equal key_eq() const;
279
280 iterator find(const key_type& k);
281 const_iterator find(const key_type& k) const;
282 size_type count(const key_type& k) const;
283 pair<iterator, iterator> equal_range(const key_type& k);
284 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
285
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000286 size_type bucket_count() const noexcept;
287 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000288
289 size_type bucket_size(size_type n) const;
290 size_type bucket(const key_type& k) const;
291
292 local_iterator begin(size_type n);
293 local_iterator end(size_type n);
294 const_local_iterator begin(size_type n) const;
295 const_local_iterator end(size_type n) const;
296 const_local_iterator cbegin(size_type n) const;
297 const_local_iterator cend(size_type n) const;
298
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000299 float load_factor() const noexcept;
300 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000301 void max_load_factor(float z);
302 void rehash(size_type n);
303 void reserve(size_type n);
304};
305
306template <class Value, class Hash, class Pred, class Alloc>
307 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000308 unordered_multiset<Value, Hash, Pred, Alloc>& y)
309 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000310
311template <class Value, class Hash, class Pred, class Alloc>
312 bool
313 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
314 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
315
316template <class Value, class Hash, class Pred, class Alloc>
317 bool
318 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
319 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
320} // std
321
322*/
323
324#include <__config>
325#include <__hash_table>
326#include <functional>
327
Howard Hinnant08e17472011-10-17 20:05:10 +0000328#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000329#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000330#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000331
332_LIBCPP_BEGIN_NAMESPACE_STD
333
334template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
335 class _Alloc = allocator<_Value> >
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000336class _LIBCPP_TYPE_VIS_ONLY unordered_set
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000337{
338public:
339 // types
340 typedef _Value key_type;
341 typedef key_type value_type;
342 typedef _Hash hasher;
343 typedef _Pred key_equal;
344 typedef _Alloc allocator_type;
345 typedef value_type& reference;
346 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +0000347 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
348 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000349
350private:
351 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
352
353 __table __table_;
354
355public:
356 typedef typename __table::pointer pointer;
357 typedef typename __table::const_pointer const_pointer;
358 typedef typename __table::size_type size_type;
359 typedef typename __table::difference_type difference_type;
360
361 typedef typename __table::const_iterator iterator;
362 typedef typename __table::const_iterator const_iterator;
363 typedef typename __table::const_local_iterator local_iterator;
364 typedef typename __table::const_local_iterator const_local_iterator;
365
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000366 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000367 unordered_set()
368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +0000369 {
370#if _LIBCPP_DEBUG_LEVEL >= 2
371 __get_db()->__insert_c(this);
372#endif
373 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000374 explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
375 const key_equal& __eql = key_equal());
Marshall Clowbd444af2013-09-30 21:33:51 +0000376#if _LIBCPP_STD_VER > 11
377 inline _LIBCPP_INLINE_VISIBILITY
378 unordered_set(size_type __n, const allocator_type& __a)
379 : unordered_set(__n, hasher(), key_equal(), __a) {}
380 inline _LIBCPP_INLINE_VISIBILITY
381 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
382 : unordered_set(__n, __hf, key_equal(), __a) {}
383#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000384 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
385 const allocator_type& __a);
386 template <class _InputIterator>
387 unordered_set(_InputIterator __first, _InputIterator __last);
388 template <class _InputIterator>
389 unordered_set(_InputIterator __first, _InputIterator __last,
390 size_type __n, const hasher& __hf = hasher(),
391 const key_equal& __eql = key_equal());
392 template <class _InputIterator>
393 unordered_set(_InputIterator __first, _InputIterator __last,
394 size_type __n, const hasher& __hf, const key_equal& __eql,
395 const allocator_type& __a);
Marshall Clowbd444af2013-09-30 21:33:51 +0000396#if _LIBCPP_STD_VER > 11
397 template <class _InputIterator>
398 inline _LIBCPP_INLINE_VISIBILITY
399 unordered_set(_InputIterator __first, _InputIterator __last,
400 size_type __n, const allocator_type& __a)
401 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
402 template <class _InputIterator>
403 unordered_set(_InputIterator __first, _InputIterator __last,
404 size_type __n, const hasher& __hf, const allocator_type& __a)
405 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
406#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000407 explicit unordered_set(const allocator_type& __a);
408 unordered_set(const unordered_set& __u);
409 unordered_set(const unordered_set& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000410#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000411 unordered_set(unordered_set&& __u)
412 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000413 unordered_set(unordered_set&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000414#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000415#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000416 unordered_set(initializer_list<value_type> __il);
417 unordered_set(initializer_list<value_type> __il, size_type __n,
418 const hasher& __hf = hasher(),
419 const key_equal& __eql = key_equal());
420 unordered_set(initializer_list<value_type> __il, size_type __n,
421 const hasher& __hf, const key_equal& __eql,
422 const allocator_type& __a);
Marshall Clowbd444af2013-09-30 21:33:51 +0000423#if _LIBCPP_STD_VER > 11
424 inline _LIBCPP_INLINE_VISIBILITY
425 unordered_set(initializer_list<value_type> __il, size_type __n,
426 const allocator_type& __a)
427 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
428 inline _LIBCPP_INLINE_VISIBILITY
429 unordered_set(initializer_list<value_type> __il, size_type __n,
430 const hasher& __hf, const allocator_type& __a)
431 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
432#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000433#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000434 // ~unordered_set() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000435 _LIBCPP_INLINE_VISIBILITY
436 unordered_set& operator=(const unordered_set& __u)
437 {
438 __table_ = __u.__table_;
439 return *this;
440 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000441#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000442 unordered_set& operator=(unordered_set&& __u)
443 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000444#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000445#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000446 unordered_set& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000447#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000448
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000449 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000450 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000451 {return allocator_type(__table_.__node_alloc());}
452
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000453 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000454 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000456 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000458 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000459
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000461 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000462 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000463 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000464 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000465 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000467 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000468 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000469 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000470 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000471 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000472
Howard Hinnant73d21a42010-09-04 23:28:19 +0000473#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000474 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000475 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000476 pair<iterator, bool> emplace(_Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000477 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000478 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000479 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000480#if _LIBCPP_DEBUG_LEVEL >= 2
481 iterator emplace_hint(const_iterator __p, _Args&&... __args)
482 {
483 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
484 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
485 " referring to this unordered_set");
486 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
487 }
488#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489 iterator emplace_hint(const_iterator, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000490 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant39213642013-07-23 22:01:58 +0000491#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000492#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000493 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000494 pair<iterator, bool> insert(const value_type& __x)
495 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000496#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000497 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000498 pair<iterator, bool> insert(value_type&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000499 {return __table_.__insert_unique(_VSTD::move(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000500#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000501 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000502#if _LIBCPP_DEBUG_LEVEL >= 2
503 iterator insert(const_iterator __p, const value_type& __x)
504 {
505 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
506 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
507 " referring to this unordered_set");
508 return insert(__x).first;
509 }
510#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000511 iterator insert(const_iterator, const value_type& __x)
512 {return insert(__x).first;}
Howard Hinnant39213642013-07-23 22:01:58 +0000513#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000514#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000515 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant39213642013-07-23 22:01:58 +0000516#if _LIBCPP_DEBUG_LEVEL >= 2
517 iterator insert(const_iterator __p, value_type&& __x)
518 {
519 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
520 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
521 " referring to this unordered_set");
522 return insert(_VSTD::move(__x)).first;
523 }
524#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525 iterator insert(const_iterator, value_type&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000526 {return insert(_VSTD::move(__x)).first;}
Howard Hinnant39213642013-07-23 22:01:58 +0000527#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000528#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000529 template <class _InputIterator>
530 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000531#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000532 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000533 void insert(initializer_list<value_type> __il)
534 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000535#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000536
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000537 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000538 iterator erase(const_iterator __p) {return __table_.erase(__p);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000539 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000540 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000541 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000542 iterator erase(const_iterator __first, const_iterator __last)
543 {return __table_.erase(__first, __last);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000544 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000545 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000546
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000547 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000548 void swap(unordered_set& __u)
549 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
550 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000551
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000552 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000553 hasher hash_function() const {return __table_.hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000555 key_equal key_eq() const {return __table_.key_eq();}
556
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000557 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000558 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000559 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000560 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000561 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000562 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000563 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000564 pair<iterator, iterator> equal_range(const key_type& __k)
565 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000566 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000567 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
568 {return __table_.__equal_range_unique(__k);}
569
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000571 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000573 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000574
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000576 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000578 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
579
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000581 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000585 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000586 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000587 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000588 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000589 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000590 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000591 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
592
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000594 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000595 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000596 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000598 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000599 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000600 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000601 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000602 void reserve(size_type __n) {__table_.reserve(__n);}
Howard Hinnant39213642013-07-23 22:01:58 +0000603
604#if _LIBCPP_DEBUG_LEVEL >= 2
605
606 bool __dereferenceable(const const_iterator* __i) const
607 {return __table_.__dereferenceable(__i);}
608 bool __decrementable(const const_iterator* __i) const
609 {return __table_.__decrementable(__i);}
610 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
611 {return __table_.__addable(__i, __n);}
612 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
613 {return __table_.__addable(__i, __n);}
614
615#endif // _LIBCPP_DEBUG_LEVEL >= 2
616
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000617};
618
619template <class _Value, class _Hash, class _Pred, class _Alloc>
620unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
621 const hasher& __hf, const key_equal& __eql)
622 : __table_(__hf, __eql)
623{
Howard Hinnant39213642013-07-23 22:01:58 +0000624#if _LIBCPP_DEBUG_LEVEL >= 2
625 __get_db()->__insert_c(this);
626#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000627 __table_.rehash(__n);
628}
629
630template <class _Value, class _Hash, class _Pred, class _Alloc>
631unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
632 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
633 : __table_(__hf, __eql, __a)
634{
Howard Hinnant39213642013-07-23 22:01:58 +0000635#if _LIBCPP_DEBUG_LEVEL >= 2
636 __get_db()->__insert_c(this);
637#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000638 __table_.rehash(__n);
639}
640
641template <class _Value, class _Hash, class _Pred, class _Alloc>
642template <class _InputIterator>
643unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
644 _InputIterator __first, _InputIterator __last)
645{
Howard Hinnant39213642013-07-23 22:01:58 +0000646#if _LIBCPP_DEBUG_LEVEL >= 2
647 __get_db()->__insert_c(this);
648#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000649 insert(__first, __last);
650}
651
652template <class _Value, class _Hash, class _Pred, class _Alloc>
653template <class _InputIterator>
654unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
655 _InputIterator __first, _InputIterator __last, size_type __n,
656 const hasher& __hf, const key_equal& __eql)
657 : __table_(__hf, __eql)
658{
Howard Hinnant39213642013-07-23 22:01:58 +0000659#if _LIBCPP_DEBUG_LEVEL >= 2
660 __get_db()->__insert_c(this);
661#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000662 __table_.rehash(__n);
663 insert(__first, __last);
664}
665
666template <class _Value, class _Hash, class _Pred, class _Alloc>
667template <class _InputIterator>
668unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
669 _InputIterator __first, _InputIterator __last, size_type __n,
670 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
671 : __table_(__hf, __eql, __a)
672{
Howard Hinnant39213642013-07-23 22:01:58 +0000673#if _LIBCPP_DEBUG_LEVEL >= 2
674 __get_db()->__insert_c(this);
675#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000676 __table_.rehash(__n);
677 insert(__first, __last);
678}
679
680template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000681inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000682unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
683 const allocator_type& __a)
684 : __table_(__a)
685{
Howard Hinnant39213642013-07-23 22:01:58 +0000686#if _LIBCPP_DEBUG_LEVEL >= 2
687 __get_db()->__insert_c(this);
688#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000689}
690
691template <class _Value, class _Hash, class _Pred, class _Alloc>
692unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
693 const unordered_set& __u)
694 : __table_(__u.__table_)
695{
Howard Hinnant39213642013-07-23 22:01:58 +0000696#if _LIBCPP_DEBUG_LEVEL >= 2
697 __get_db()->__insert_c(this);
698#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000699 __table_.rehash(__u.bucket_count());
700 insert(__u.begin(), __u.end());
701}
702
703template <class _Value, class _Hash, class _Pred, class _Alloc>
704unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
705 const unordered_set& __u, const allocator_type& __a)
706 : __table_(__u.__table_, __a)
707{
Howard Hinnant39213642013-07-23 22:01:58 +0000708#if _LIBCPP_DEBUG_LEVEL >= 2
709 __get_db()->__insert_c(this);
710#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000711 __table_.rehash(__u.bucket_count());
712 insert(__u.begin(), __u.end());
713}
714
Howard Hinnant73d21a42010-09-04 23:28:19 +0000715#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000716
717template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000718inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000719unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
720 unordered_set&& __u)
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000721 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000722 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000723{
Howard Hinnant39213642013-07-23 22:01:58 +0000724#if _LIBCPP_DEBUG_LEVEL >= 2
725 __get_db()->__insert_c(this);
726 __get_db()->swap(this, &__u);
727#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000728}
729
730template <class _Value, class _Hash, class _Pred, class _Alloc>
731unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
732 unordered_set&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000733 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000734{
Howard Hinnant39213642013-07-23 22:01:58 +0000735#if _LIBCPP_DEBUG_LEVEL >= 2
736 __get_db()->__insert_c(this);
737#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000738 if (__a != __u.get_allocator())
739 {
740 iterator __i = __u.begin();
741 while (__u.size() != 0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000742 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000743 }
Howard Hinnant39213642013-07-23 22:01:58 +0000744#if _LIBCPP_DEBUG_LEVEL >= 2
745 else
746 __get_db()->swap(this, &__u);
747#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000748}
749
Howard Hinnant73d21a42010-09-04 23:28:19 +0000750#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000751
Howard Hinnante3e32912011-08-12 21:56:02 +0000752#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
753
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000754template <class _Value, class _Hash, class _Pred, class _Alloc>
755unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
756 initializer_list<value_type> __il)
757{
Howard Hinnant39213642013-07-23 22:01:58 +0000758#if _LIBCPP_DEBUG_LEVEL >= 2
759 __get_db()->__insert_c(this);
760#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000761 insert(__il.begin(), __il.end());
762}
763
764template <class _Value, class _Hash, class _Pred, class _Alloc>
765unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
766 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
767 const key_equal& __eql)
768 : __table_(__hf, __eql)
769{
Howard Hinnant39213642013-07-23 22:01:58 +0000770#if _LIBCPP_DEBUG_LEVEL >= 2
771 __get_db()->__insert_c(this);
772#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000773 __table_.rehash(__n);
774 insert(__il.begin(), __il.end());
775}
776
777template <class _Value, class _Hash, class _Pred, class _Alloc>
778unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
779 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
780 const key_equal& __eql, const allocator_type& __a)
781 : __table_(__hf, __eql, __a)
782{
Howard Hinnant39213642013-07-23 22:01:58 +0000783#if _LIBCPP_DEBUG_LEVEL >= 2
784 __get_db()->__insert_c(this);
785#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000786 __table_.rehash(__n);
787 insert(__il.begin(), __il.end());
788}
789
Howard Hinnante3e32912011-08-12 21:56:02 +0000790#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
791
Howard Hinnant73d21a42010-09-04 23:28:19 +0000792#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000793
794template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000795inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000796unordered_set<_Value, _Hash, _Pred, _Alloc>&
797unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000798 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000799{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000800 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000801 return *this;
802}
803
Howard Hinnant73d21a42010-09-04 23:28:19 +0000804#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000805
Howard Hinnante3e32912011-08-12 21:56:02 +0000806#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
807
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000808template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000809inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000810unordered_set<_Value, _Hash, _Pred, _Alloc>&
811unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
812 initializer_list<value_type> __il)
813{
814 __table_.__assign_unique(__il.begin(), __il.end());
815 return *this;
816}
817
Howard Hinnante3e32912011-08-12 21:56:02 +0000818#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
819
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000820template <class _Value, class _Hash, class _Pred, class _Alloc>
821template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000822inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000823void
824unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
825 _InputIterator __last)
826{
827 for (; __first != __last; ++__first)
828 __table_.__insert_unique(*__first);
829}
830
831template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000832inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000833void
834swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
835 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000836 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000837{
838 __x.swap(__y);
839}
840
841template <class _Value, class _Hash, class _Pred, class _Alloc>
842bool
843operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
844 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
845{
846 if (__x.size() != __y.size())
847 return false;
848 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
849 const_iterator;
850 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
851 __i != __ex; ++__i)
852 {
853 const_iterator __j = __y.find(*__i);
854 if (__j == __ey || !(*__i == *__j))
855 return false;
856 }
857 return true;
858}
859
860template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000861inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862bool
863operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
864 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
865{
866 return !(__x == __y);
867}
868
869template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
870 class _Alloc = allocator<_Value> >
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000871class _LIBCPP_TYPE_VIS_ONLY unordered_multiset
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000872{
873public:
874 // types
875 typedef _Value key_type;
876 typedef key_type value_type;
877 typedef _Hash hasher;
878 typedef _Pred key_equal;
879 typedef _Alloc allocator_type;
880 typedef value_type& reference;
881 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +0000882 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
883 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000884
885private:
886 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
887
888 __table __table_;
889
890public:
891 typedef typename __table::pointer pointer;
892 typedef typename __table::const_pointer const_pointer;
893 typedef typename __table::size_type size_type;
894 typedef typename __table::difference_type difference_type;
895
896 typedef typename __table::const_iterator iterator;
897 typedef typename __table::const_iterator const_iterator;
898 typedef typename __table::const_local_iterator local_iterator;
899 typedef typename __table::const_local_iterator const_local_iterator;
900
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000902 unordered_multiset()
903 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +0000904 {
905#if _LIBCPP_DEBUG_LEVEL >= 2
906 __get_db()->__insert_c(this);
907#endif
908 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000909 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
910 const key_equal& __eql = key_equal());
911 unordered_multiset(size_type __n, const hasher& __hf,
912 const key_equal& __eql, const allocator_type& __a);
Marshall Clowbd444af2013-09-30 21:33:51 +0000913#if _LIBCPP_STD_VER > 11
914 inline _LIBCPP_INLINE_VISIBILITY
915 unordered_multiset(size_type __n, const allocator_type& __a)
916 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
917 inline _LIBCPP_INLINE_VISIBILITY
918 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
919 : unordered_multiset(__n, __hf, key_equal(), __a) {}
920#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000921 template <class _InputIterator>
922 unordered_multiset(_InputIterator __first, _InputIterator __last);
923 template <class _InputIterator>
924 unordered_multiset(_InputIterator __first, _InputIterator __last,
925 size_type __n, const hasher& __hf = hasher(),
926 const key_equal& __eql = key_equal());
927 template <class _InputIterator>
928 unordered_multiset(_InputIterator __first, _InputIterator __last,
929 size_type __n , const hasher& __hf,
930 const key_equal& __eql, const allocator_type& __a);
Marshall Clowbd444af2013-09-30 21:33:51 +0000931#if _LIBCPP_STD_VER > 11
932 template <class _InputIterator>
933 inline _LIBCPP_INLINE_VISIBILITY
934 unordered_multiset(_InputIterator __first, _InputIterator __last,
935 size_type __n, const allocator_type& __a)
936 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
937 template <class _InputIterator>
938 inline _LIBCPP_INLINE_VISIBILITY
939 unordered_multiset(_InputIterator __first, _InputIterator __last,
940 size_type __n, const hasher& __hf, const allocator_type& __a)
941 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
942#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000943 explicit unordered_multiset(const allocator_type& __a);
944 unordered_multiset(const unordered_multiset& __u);
945 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000946#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000947 unordered_multiset(unordered_multiset&& __u)
948 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000949 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000950#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000951#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000952 unordered_multiset(initializer_list<value_type> __il);
953 unordered_multiset(initializer_list<value_type> __il, size_type __n,
954 const hasher& __hf = hasher(),
955 const key_equal& __eql = key_equal());
956 unordered_multiset(initializer_list<value_type> __il, size_type __n,
957 const hasher& __hf, const key_equal& __eql,
958 const allocator_type& __a);
Marshall Clowbd444af2013-09-30 21:33:51 +0000959#if _LIBCPP_STD_VER > 11
960 inline _LIBCPP_INLINE_VISIBILITY
961 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
962 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
963 inline _LIBCPP_INLINE_VISIBILITY
964 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
965 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
966#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000967#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000968 // ~unordered_multiset() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000969 _LIBCPP_INLINE_VISIBILITY
970 unordered_multiset& operator=(const unordered_multiset& __u)
971 {
972 __table_ = __u.__table_;
973 return *this;
974 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000975#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000976 unordered_multiset& operator=(unordered_multiset&& __u)
977 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000978#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000979#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000980 unordered_multiset& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000981#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000982
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000983 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000984 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000985 {return allocator_type(__table_.__node_alloc());}
986
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000988 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000989 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000990 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000991 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000992 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000993
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000995 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000996 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000997 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000998 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +0000999 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001000 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001001 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001002 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001003 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001004 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001005 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001006
Howard Hinnant73d21a42010-09-04 23:28:19 +00001007#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001008 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001009 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001010 iterator emplace(_Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001011 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001012 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001013 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001014 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001015 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001016#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001017 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001018 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001019#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001020 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0949eed2011-06-30 21:18:19 +00001021 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001022#endif
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001023 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001024 iterator insert(const_iterator __p, const value_type& __x)
1025 {return __table_.__insert_multi(__p, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001026#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001027 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001028 iterator insert(const_iterator __p, value_type&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001029 {return __table_.__insert_multi(__p, _VSTD::move(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001030#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001031 template <class _InputIterator>
1032 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001033#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001034 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001035 void insert(initializer_list<value_type> __il)
1036 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001037#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001038
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001039 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001040 iterator erase(const_iterator __p) {return __table_.erase(__p);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001041 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001042 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001043 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001044 iterator erase(const_iterator __first, const_iterator __last)
1045 {return __table_.erase(__first, __last);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001046 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001047 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001048
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001049 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001050 void swap(unordered_multiset& __u)
1051 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1052 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001053
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001054 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001055 hasher hash_function() const {return __table_.hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001056 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001057 key_equal key_eq() const {return __table_.key_eq();}
1058
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001059 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001060 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001061 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001062 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001063 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001064 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001065 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001066 pair<iterator, iterator> equal_range(const key_type& __k)
1067 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001068 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001069 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1070 {return __table_.__equal_range_multi(__k);}
1071
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001072 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001073 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001074 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001075 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001076
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001077 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001078 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001079 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001080 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1081
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001082 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001083 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001084 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001085 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001086 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001087 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001088 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001089 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001090 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001091 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001092 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001093 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1094
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001095 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001096 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001097 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001098 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001099 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001100 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001101 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001102 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001103 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001104 void reserve(size_type __n) {__table_.reserve(__n);}
Howard Hinnant39213642013-07-23 22:01:58 +00001105
1106#if _LIBCPP_DEBUG_LEVEL >= 2
1107
1108 bool __dereferenceable(const const_iterator* __i) const
1109 {return __table_.__dereferenceable(__i);}
1110 bool __decrementable(const const_iterator* __i) const
1111 {return __table_.__decrementable(__i);}
1112 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1113 {return __table_.__addable(__i, __n);}
1114 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1115 {return __table_.__addable(__i, __n);}
1116
1117#endif // _LIBCPP_DEBUG_LEVEL >= 2
1118
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001119};
1120
1121template <class _Value, class _Hash, class _Pred, class _Alloc>
1122unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1123 size_type __n, const hasher& __hf, const key_equal& __eql)
1124 : __table_(__hf, __eql)
1125{
Howard Hinnant39213642013-07-23 22:01:58 +00001126#if _LIBCPP_DEBUG_LEVEL >= 2
1127 __get_db()->__insert_c(this);
1128#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001129 __table_.rehash(__n);
1130}
1131
1132template <class _Value, class _Hash, class _Pred, class _Alloc>
1133unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1134 size_type __n, const hasher& __hf, const key_equal& __eql,
1135 const allocator_type& __a)
1136 : __table_(__hf, __eql, __a)
1137{
Howard Hinnant39213642013-07-23 22:01:58 +00001138#if _LIBCPP_DEBUG_LEVEL >= 2
1139 __get_db()->__insert_c(this);
1140#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001141 __table_.rehash(__n);
1142}
1143
1144template <class _Value, class _Hash, class _Pred, class _Alloc>
1145template <class _InputIterator>
1146unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1147 _InputIterator __first, _InputIterator __last)
1148{
Howard Hinnant39213642013-07-23 22:01:58 +00001149#if _LIBCPP_DEBUG_LEVEL >= 2
1150 __get_db()->__insert_c(this);
1151#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001152 insert(__first, __last);
1153}
1154
1155template <class _Value, class _Hash, class _Pred, class _Alloc>
1156template <class _InputIterator>
1157unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1158 _InputIterator __first, _InputIterator __last, size_type __n,
1159 const hasher& __hf, const key_equal& __eql)
1160 : __table_(__hf, __eql)
1161{
Howard Hinnant39213642013-07-23 22:01:58 +00001162#if _LIBCPP_DEBUG_LEVEL >= 2
1163 __get_db()->__insert_c(this);
1164#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001165 __table_.rehash(__n);
1166 insert(__first, __last);
1167}
1168
1169template <class _Value, class _Hash, class _Pred, class _Alloc>
1170template <class _InputIterator>
1171unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1172 _InputIterator __first, _InputIterator __last, size_type __n,
1173 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1174 : __table_(__hf, __eql, __a)
1175{
Howard Hinnant39213642013-07-23 22:01:58 +00001176#if _LIBCPP_DEBUG_LEVEL >= 2
1177 __get_db()->__insert_c(this);
1178#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001179 __table_.rehash(__n);
1180 insert(__first, __last);
1181}
1182
1183template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001184inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001185unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1186 const allocator_type& __a)
1187 : __table_(__a)
1188{
Howard Hinnant39213642013-07-23 22:01:58 +00001189#if _LIBCPP_DEBUG_LEVEL >= 2
1190 __get_db()->__insert_c(this);
1191#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001192}
1193
1194template <class _Value, class _Hash, class _Pred, class _Alloc>
1195unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1196 const unordered_multiset& __u)
1197 : __table_(__u.__table_)
1198{
Howard Hinnant39213642013-07-23 22:01:58 +00001199#if _LIBCPP_DEBUG_LEVEL >= 2
1200 __get_db()->__insert_c(this);
1201#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001202 __table_.rehash(__u.bucket_count());
1203 insert(__u.begin(), __u.end());
1204}
1205
1206template <class _Value, class _Hash, class _Pred, class _Alloc>
1207unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1208 const unordered_multiset& __u, const allocator_type& __a)
1209 : __table_(__u.__table_, __a)
1210{
Howard Hinnant39213642013-07-23 22:01:58 +00001211#if _LIBCPP_DEBUG_LEVEL >= 2
1212 __get_db()->__insert_c(this);
1213#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001214 __table_.rehash(__u.bucket_count());
1215 insert(__u.begin(), __u.end());
1216}
1217
Howard Hinnant73d21a42010-09-04 23:28:19 +00001218#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001219
1220template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001221inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001222unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1223 unordered_multiset&& __u)
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001224 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001225 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001226{
Howard Hinnant39213642013-07-23 22:01:58 +00001227#if _LIBCPP_DEBUG_LEVEL >= 2
1228 __get_db()->__insert_c(this);
1229 __get_db()->swap(this, &__u);
1230#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001231}
1232
1233template <class _Value, class _Hash, class _Pred, class _Alloc>
1234unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1235 unordered_multiset&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001236 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001237{
Howard Hinnant39213642013-07-23 22:01:58 +00001238#if _LIBCPP_DEBUG_LEVEL >= 2
1239 __get_db()->__insert_c(this);
1240#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001241 if (__a != __u.get_allocator())
1242 {
1243 iterator __i = __u.begin();
1244 while (__u.size() != 0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001245 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001246 }
Howard Hinnant39213642013-07-23 22:01:58 +00001247#if _LIBCPP_DEBUG_LEVEL >= 2
1248 else
1249 __get_db()->swap(this, &__u);
1250#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001251}
1252
Howard Hinnant73d21a42010-09-04 23:28:19 +00001253#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001254
Howard Hinnante3e32912011-08-12 21:56:02 +00001255#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1256
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001257template <class _Value, class _Hash, class _Pred, class _Alloc>
1258unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1259 initializer_list<value_type> __il)
1260{
Howard Hinnant39213642013-07-23 22:01:58 +00001261#if _LIBCPP_DEBUG_LEVEL >= 2
1262 __get_db()->__insert_c(this);
1263#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001264 insert(__il.begin(), __il.end());
1265}
1266
1267template <class _Value, class _Hash, class _Pred, class _Alloc>
1268unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1269 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1270 const key_equal& __eql)
1271 : __table_(__hf, __eql)
1272{
Howard Hinnant39213642013-07-23 22:01:58 +00001273#if _LIBCPP_DEBUG_LEVEL >= 2
1274 __get_db()->__insert_c(this);
1275#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001276 __table_.rehash(__n);
1277 insert(__il.begin(), __il.end());
1278}
1279
1280template <class _Value, class _Hash, class _Pred, class _Alloc>
1281unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1282 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1283 const key_equal& __eql, const allocator_type& __a)
1284 : __table_(__hf, __eql, __a)
1285{
Howard Hinnant39213642013-07-23 22:01:58 +00001286#if _LIBCPP_DEBUG_LEVEL >= 2
1287 __get_db()->__insert_c(this);
1288#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001289 __table_.rehash(__n);
1290 insert(__il.begin(), __il.end());
1291}
1292
Howard Hinnante3e32912011-08-12 21:56:02 +00001293#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1294
Howard Hinnant73d21a42010-09-04 23:28:19 +00001295#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001296
1297template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001298inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001299unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1300unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1301 unordered_multiset&& __u)
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001302 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001303{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001304 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001305 return *this;
1306}
1307
Howard Hinnant73d21a42010-09-04 23:28:19 +00001308#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001309
Howard Hinnante3e32912011-08-12 21:56:02 +00001310#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1311
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001312template <class _Value, class _Hash, class _Pred, class _Alloc>
1313inline
1314unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1315unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1316 initializer_list<value_type> __il)
1317{
1318 __table_.__assign_multi(__il.begin(), __il.end());
1319 return *this;
1320}
1321
Howard Hinnante3e32912011-08-12 21:56:02 +00001322#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1323
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001324template <class _Value, class _Hash, class _Pred, class _Alloc>
1325template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001326inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001327void
1328unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1329 _InputIterator __last)
1330{
1331 for (; __first != __last; ++__first)
1332 __table_.__insert_multi(*__first);
1333}
1334
1335template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001336inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001337void
1338swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1339 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant04dae1d2011-06-04 20:18:37 +00001340 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001341{
1342 __x.swap(__y);
1343}
1344
1345template <class _Value, class _Hash, class _Pred, class _Alloc>
1346bool
1347operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1348 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1349{
1350 if (__x.size() != __y.size())
1351 return false;
1352 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1353 const_iterator;
1354 typedef pair<const_iterator, const_iterator> _EqRng;
1355 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1356 {
1357 _EqRng __xeq = __x.equal_range(*__i);
1358 _EqRng __yeq = __y.equal_range(*__i);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001359 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1360 _VSTD::distance(__yeq.first, __yeq.second) ||
1361 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001362 return false;
1363 __i = __xeq.second;
1364 }
1365 return true;
1366}
1367
1368template <class _Value, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001369inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001370bool
1371operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1372 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1373{
1374 return !(__x == __y);
1375}
1376
1377_LIBCPP_END_NAMESPACE_STD
1378
1379#endif // _LIBCPP_UNORDERED_SET