2 //===-------------------------- unordered_set -----------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_UNORDERED_SET
12 #define _LIBCPP_UNORDERED_SET
16 unordered_set synopsis
18 #include <initializer_list>
23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
24 class Alloc = allocator<Value>>
29 typedef Value key_type;
30 typedef key_type value_type;
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;
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
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(),
52 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&);
62 unordered_set(unordered_set&&)
64 is_nothrow_move_constructible<hasher>::value &&
65 is_nothrow_move_constructible<key_equal>::value &&
66 is_nothrow_move_constructible<allocator_type>::value);
67 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());
72 unordered_set& operator=(const unordered_set&);
73 unordered_set& operator=(unordered_set&&)
75 allocator_type::propagate_on_container_move_assignment::value &&
76 is_nothrow_move_assignable<allocator_type>::value &&
77 is_nothrow_move_assignable<hasher>::value &&
78 is_nothrow_move_assignable<key_equal>::value);
79 unordered_set& operator=(initializer_list<value_type>);
81 allocator_type get_allocator() const noexcept;
83 bool empty() const noexcept;
84 size_type size() const noexcept;
85 size_type max_size() const noexcept;
87 iterator begin() noexcept;
88 iterator end() noexcept;
89 const_iterator begin() const noexcept;
90 const_iterator end() const noexcept;
91 const_iterator cbegin() const noexcept;
92 const_iterator cend() const noexcept;
94 template <class... Args>
95 pair<iterator, bool> emplace(Args&&... args);
96 template <class... Args>
97 iterator emplace_hint(const_iterator position, Args&&... args);
98 pair<iterator, bool> insert(const value_type& obj);
99 pair<iterator, bool> insert(value_type&& obj);
100 iterator insert(const_iterator hint, const value_type& obj);
101 iterator insert(const_iterator hint, value_type&& obj);
102 template <class InputIterator>
103 void insert(InputIterator first, InputIterator last);
104 void insert(initializer_list<value_type>);
106 iterator erase(const_iterator position);
107 size_type erase(const key_type& k);
108 iterator erase(const_iterator first, const_iterator last);
109 void clear() noexcept;
111 void swap(unordered_set&)
113 (!allocator_type::propagate_on_container_swap::value ||
114 __is_nothrow_swappable<allocator_type>::value) &&
115 __is_nothrow_swappable<hasher>::value &&
116 __is_nothrow_swappable<key_equal>::value);
118 hasher hash_function() const;
119 key_equal key_eq() const;
121 iterator find(const key_type& k);
122 const_iterator find(const key_type& k) const;
123 size_type count(const key_type& k) const;
124 pair<iterator, iterator> equal_range(const key_type& k);
125 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
127 size_type bucket_count() const noexcept;
128 size_type max_bucket_count() const noexcept;
130 size_type bucket_size(size_type n) const;
131 size_type bucket(const key_type& k) const;
133 local_iterator begin(size_type n);
134 local_iterator end(size_type n);
135 const_local_iterator begin(size_type n) const;
136 const_local_iterator end(size_type n) const;
137 const_local_iterator cbegin(size_type n) const;
138 const_local_iterator cend(size_type n) const;
140 float load_factor() const noexcept;
141 float max_load_factor() const noexcept;
142 void max_load_factor(float z);
143 void rehash(size_type n);
144 void reserve(size_type n);
147 template <class Value, class Hash, class Pred, class Alloc>
148 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
149 unordered_set<Value, Hash, Pred, Alloc>& y)
150 noexcept(noexcept(x.swap(y)));
152 template <class Value, class Hash, class Pred, class Alloc>
154 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
155 const unordered_set<Value, Hash, Pred, Alloc>& y);
157 template <class Value, class Hash, class Pred, class Alloc>
159 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
160 const unordered_set<Value, Hash, Pred, Alloc>& y);
162 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
163 class Alloc = allocator<Value>>
164 class unordered_multiset
168 typedef Value key_type;
169 typedef key_type value_type;
171 typedef Pred key_equal;
172 typedef Alloc allocator_type;
173 typedef value_type& reference;
174 typedef const value_type& const_reference;
175 typedef typename allocator_traits<allocator_type>::pointer pointer;
176 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
177 typedef typename allocator_traits<allocator_type>::size_type size_type;
178 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
180 typedef /unspecified/ iterator;
181 typedef /unspecified/ const_iterator;
182 typedef /unspecified/ local_iterator;
183 typedef /unspecified/ const_local_iterator;
187 is_nothrow_default_constructible<hasher>::value &&
188 is_nothrow_default_constructible<key_equal>::value &&
189 is_nothrow_default_constructible<allocator_type>::value);
190 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
191 const key_equal& eql = key_equal(),
192 const allocator_type& a = allocator_type());
193 template <class InputIterator>
194 unordered_multiset(InputIterator f, InputIterator l,
195 size_type n = 0, const hasher& hf = hasher(),
196 const key_equal& eql = key_equal(),
197 const allocator_type& a = allocator_type());
198 explicit unordered_multiset(const allocator_type&);
199 unordered_multiset(const unordered_multiset&);
200 unordered_multiset(const unordered_multiset&, const Allocator&);
201 unordered_multiset(unordered_multiset&&)
203 is_nothrow_move_constructible<hasher>::value &&
204 is_nothrow_move_constructible<key_equal>::value &&
205 is_nothrow_move_constructible<allocator_type>::value);
206 unordered_multiset(unordered_multiset&&, const Allocator&);
207 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
208 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
209 const allocator_type& a = allocator_type());
210 ~unordered_multiset();
211 unordered_multiset& operator=(const unordered_multiset&);
212 unordered_multiset& operator=(unordered_multiset&&)
214 allocator_type::propagate_on_container_move_assignment::value &&
215 is_nothrow_move_assignable<allocator_type>::value &&
216 is_nothrow_move_assignable<hasher>::value &&
217 is_nothrow_move_assignable<key_equal>::value);
218 unordered_multiset& operator=(initializer_list<value_type>);
220 allocator_type get_allocator() const noexcept;
222 bool empty() const noexcept;
223 size_type size() const noexcept;
224 size_type max_size() const noexcept;
226 iterator begin() noexcept;
227 iterator end() noexcept;
228 const_iterator begin() const noexcept;
229 const_iterator end() const noexcept;
230 const_iterator cbegin() const noexcept;
231 const_iterator cend() const noexcept;
233 template <class... Args>
234 iterator emplace(Args&&... args);
235 template <class... Args>
236 iterator emplace_hint(const_iterator position, Args&&... args);
237 iterator insert(const value_type& obj);
238 iterator insert(value_type&& obj);
239 iterator insert(const_iterator hint, const value_type& obj);
240 iterator insert(const_iterator hint, value_type&& obj);
241 template <class InputIterator>
242 void insert(InputIterator first, InputIterator last);
243 void insert(initializer_list<value_type>);
245 iterator erase(const_iterator position);
246 size_type erase(const key_type& k);
247 iterator erase(const_iterator first, const_iterator last);
248 void clear() noexcept;
250 void swap(unordered_multiset&)
252 (!allocator_type::propagate_on_container_swap::value ||
253 __is_nothrow_swappable<allocator_type>::value) &&
254 __is_nothrow_swappable<hasher>::value &&
255 __is_nothrow_swappable<key_equal>::value);
257 hasher hash_function() const;
258 key_equal key_eq() const;
260 iterator find(const key_type& k);
261 const_iterator find(const key_type& k) const;
262 size_type count(const key_type& k) const;
263 pair<iterator, iterator> equal_range(const key_type& k);
264 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
266 size_type bucket_count() const noexcept;
267 size_type max_bucket_count() const noexcept;
269 size_type bucket_size(size_type n) const;
270 size_type bucket(const key_type& k) const;
272 local_iterator begin(size_type n);
273 local_iterator end(size_type n);
274 const_local_iterator begin(size_type n) const;
275 const_local_iterator end(size_type n) const;
276 const_local_iterator cbegin(size_type n) const;
277 const_local_iterator cend(size_type n) const;
279 float load_factor() const noexcept;
280 float max_load_factor() const noexcept;
281 void max_load_factor(float z);
282 void rehash(size_type n);
283 void reserve(size_type n);
286 template <class Value, class Hash, class Pred, class Alloc>
287 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
288 unordered_multiset<Value, Hash, Pred, Alloc>& y)
289 noexcept(noexcept(x.swap(y)));
291 template <class Value, class Hash, class Pred, class Alloc>
293 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
294 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
296 template <class Value, class Hash, class Pred, class Alloc>
298 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
299 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
305 #include <__hash_table>
306 #include <functional>
308 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
309 #pragma GCC system_header
312 _LIBCPP_BEGIN_NAMESPACE_STD
314 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
315 class _Alloc = allocator<_Value> >
316 class _LIBCPP_TYPE_VIS unordered_set
320 typedef _Value key_type;
321 typedef key_type value_type;
322 typedef _Hash hasher;
323 typedef _Pred key_equal;
324 typedef _Alloc allocator_type;
325 typedef value_type& reference;
326 typedef const value_type& const_reference;
329 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
334 typedef typename __table::pointer pointer;
335 typedef typename __table::const_pointer const_pointer;
336 typedef typename __table::size_type size_type;
337 typedef typename __table::difference_type difference_type;
339 typedef typename __table::const_iterator iterator;
340 typedef typename __table::const_iterator const_iterator;
341 typedef typename __table::const_local_iterator local_iterator;
342 typedef typename __table::const_local_iterator const_local_iterator;
344 _LIBCPP_INLINE_VISIBILITY
346 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
348 explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
349 const key_equal& __eql = key_equal());
350 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
351 const allocator_type& __a);
352 template <class _InputIterator>
353 unordered_set(_InputIterator __first, _InputIterator __last);
354 template <class _InputIterator>
355 unordered_set(_InputIterator __first, _InputIterator __last,
356 size_type __n, const hasher& __hf = hasher(),
357 const key_equal& __eql = key_equal());
358 template <class _InputIterator>
359 unordered_set(_InputIterator __first, _InputIterator __last,
360 size_type __n, const hasher& __hf, const key_equal& __eql,
361 const allocator_type& __a);
362 explicit unordered_set(const allocator_type& __a);
363 unordered_set(const unordered_set& __u);
364 unordered_set(const unordered_set& __u, const allocator_type& __a);
365 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
366 unordered_set(unordered_set&& __u)
367 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
368 unordered_set(unordered_set&& __u, const allocator_type& __a);
369 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
370 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
371 unordered_set(initializer_list<value_type> __il);
372 unordered_set(initializer_list<value_type> __il, size_type __n,
373 const hasher& __hf = hasher(),
374 const key_equal& __eql = key_equal());
375 unordered_set(initializer_list<value_type> __il, size_type __n,
376 const hasher& __hf, const key_equal& __eql,
377 const allocator_type& __a);
378 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
379 // ~unordered_set() = default;
380 _LIBCPP_INLINE_VISIBILITY
381 unordered_set& operator=(const unordered_set& __u)
383 __table_ = __u.__table_;
386 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
387 unordered_set& operator=(unordered_set&& __u)
388 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
390 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
391 unordered_set& operator=(initializer_list<value_type> __il);
392 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
394 _LIBCPP_INLINE_VISIBILITY
395 allocator_type get_allocator() const _NOEXCEPT
396 {return allocator_type(__table_.__node_alloc());}
398 _LIBCPP_INLINE_VISIBILITY
399 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
400 _LIBCPP_INLINE_VISIBILITY
401 size_type size() const _NOEXCEPT {return __table_.size();}
402 _LIBCPP_INLINE_VISIBILITY
403 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
405 _LIBCPP_INLINE_VISIBILITY
406 iterator begin() _NOEXCEPT {return __table_.begin();}
407 _LIBCPP_INLINE_VISIBILITY
408 iterator end() _NOEXCEPT {return __table_.end();}
409 _LIBCPP_INLINE_VISIBILITY
410 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
411 _LIBCPP_INLINE_VISIBILITY
412 const_iterator end() const _NOEXCEPT {return __table_.end();}
413 _LIBCPP_INLINE_VISIBILITY
414 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
415 _LIBCPP_INLINE_VISIBILITY
416 const_iterator cend() const _NOEXCEPT {return __table_.end();}
418 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
419 template <class... _Args>
420 _LIBCPP_INLINE_VISIBILITY
421 pair<iterator, bool> emplace(_Args&&... __args)
422 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
423 template <class... _Args>
424 _LIBCPP_INLINE_VISIBILITY
425 iterator emplace_hint(const_iterator, _Args&&... __args)
426 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
427 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
428 _LIBCPP_INLINE_VISIBILITY
429 pair<iterator, bool> insert(const value_type& __x)
430 {return __table_.__insert_unique(__x);}
431 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
432 _LIBCPP_INLINE_VISIBILITY
433 pair<iterator, bool> insert(value_type&& __x)
434 {return __table_.__insert_unique(_VSTD::move(__x));}
435 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
436 _LIBCPP_INLINE_VISIBILITY
437 iterator insert(const_iterator, const value_type& __x)
438 {return insert(__x).first;}
439 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
440 _LIBCPP_INLINE_VISIBILITY
441 iterator insert(const_iterator, value_type&& __x)
442 {return insert(_VSTD::move(__x)).first;}
443 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
444 template <class _InputIterator>
445 void insert(_InputIterator __first, _InputIterator __last);
446 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
447 _LIBCPP_INLINE_VISIBILITY
448 void insert(initializer_list<value_type> __il)
449 {insert(__il.begin(), __il.end());}
450 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
452 _LIBCPP_INLINE_VISIBILITY
453 iterator erase(const_iterator __p) {return __table_.erase(__p);}
454 _LIBCPP_INLINE_VISIBILITY
455 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
456 _LIBCPP_INLINE_VISIBILITY
457 iterator erase(const_iterator __first, const_iterator __last)
458 {return __table_.erase(__first, __last);}
459 _LIBCPP_INLINE_VISIBILITY
460 void clear() _NOEXCEPT {__table_.clear();}
462 _LIBCPP_INLINE_VISIBILITY
463 void swap(unordered_set& __u)
464 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
465 {__table_.swap(__u.__table_);}
467 _LIBCPP_INLINE_VISIBILITY
468 hasher hash_function() const {return __table_.hash_function();}
469 _LIBCPP_INLINE_VISIBILITY
470 key_equal key_eq() const {return __table_.key_eq();}
472 _LIBCPP_INLINE_VISIBILITY
473 iterator find(const key_type& __k) {return __table_.find(__k);}
474 _LIBCPP_INLINE_VISIBILITY
475 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
476 _LIBCPP_INLINE_VISIBILITY
477 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
478 _LIBCPP_INLINE_VISIBILITY
479 pair<iterator, iterator> equal_range(const key_type& __k)
480 {return __table_.__equal_range_unique(__k);}
481 _LIBCPP_INLINE_VISIBILITY
482 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
483 {return __table_.__equal_range_unique(__k);}
485 _LIBCPP_INLINE_VISIBILITY
486 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
487 _LIBCPP_INLINE_VISIBILITY
488 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
490 _LIBCPP_INLINE_VISIBILITY
491 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
492 _LIBCPP_INLINE_VISIBILITY
493 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
495 _LIBCPP_INLINE_VISIBILITY
496 local_iterator begin(size_type __n) {return __table_.begin(__n);}
497 _LIBCPP_INLINE_VISIBILITY
498 local_iterator end(size_type __n) {return __table_.end(__n);}
499 _LIBCPP_INLINE_VISIBILITY
500 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
501 _LIBCPP_INLINE_VISIBILITY
502 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
503 _LIBCPP_INLINE_VISIBILITY
504 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
505 _LIBCPP_INLINE_VISIBILITY
506 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
508 _LIBCPP_INLINE_VISIBILITY
509 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
510 _LIBCPP_INLINE_VISIBILITY
511 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
512 _LIBCPP_INLINE_VISIBILITY
513 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
514 _LIBCPP_INLINE_VISIBILITY
515 void rehash(size_type __n) {__table_.rehash(__n);}
516 _LIBCPP_INLINE_VISIBILITY
517 void reserve(size_type __n) {__table_.reserve(__n);}
520 template <class _Value, class _Hash, class _Pred, class _Alloc>
521 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
522 const hasher& __hf, const key_equal& __eql)
523 : __table_(__hf, __eql)
525 __table_.rehash(__n);
528 template <class _Value, class _Hash, class _Pred, class _Alloc>
529 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
530 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
531 : __table_(__hf, __eql, __a)
533 __table_.rehash(__n);
536 template <class _Value, class _Hash, class _Pred, class _Alloc>
537 template <class _InputIterator>
538 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
539 _InputIterator __first, _InputIterator __last)
541 insert(__first, __last);
544 template <class _Value, class _Hash, class _Pred, class _Alloc>
545 template <class _InputIterator>
546 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
547 _InputIterator __first, _InputIterator __last, size_type __n,
548 const hasher& __hf, const key_equal& __eql)
549 : __table_(__hf, __eql)
551 __table_.rehash(__n);
552 insert(__first, __last);
555 template <class _Value, class _Hash, class _Pred, class _Alloc>
556 template <class _InputIterator>
557 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
558 _InputIterator __first, _InputIterator __last, size_type __n,
559 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
560 : __table_(__hf, __eql, __a)
562 __table_.rehash(__n);
563 insert(__first, __last);
566 template <class _Value, class _Hash, class _Pred, class _Alloc>
567 inline _LIBCPP_INLINE_VISIBILITY
568 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
569 const allocator_type& __a)
574 template <class _Value, class _Hash, class _Pred, class _Alloc>
575 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
576 const unordered_set& __u)
577 : __table_(__u.__table_)
579 __table_.rehash(__u.bucket_count());
580 insert(__u.begin(), __u.end());
583 template <class _Value, class _Hash, class _Pred, class _Alloc>
584 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
585 const unordered_set& __u, const allocator_type& __a)
586 : __table_(__u.__table_, __a)
588 __table_.rehash(__u.bucket_count());
589 insert(__u.begin(), __u.end());
592 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
594 template <class _Value, class _Hash, class _Pred, class _Alloc>
595 inline _LIBCPP_INLINE_VISIBILITY
596 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
598 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
599 : __table_(_VSTD::move(__u.__table_))
603 template <class _Value, class _Hash, class _Pred, class _Alloc>
604 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
605 unordered_set&& __u, const allocator_type& __a)
606 : __table_(_VSTD::move(__u.__table_), __a)
608 if (__a != __u.get_allocator())
610 iterator __i = __u.begin();
611 while (__u.size() != 0)
612 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
616 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
618 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
620 template <class _Value, class _Hash, class _Pred, class _Alloc>
621 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
622 initializer_list<value_type> __il)
624 insert(__il.begin(), __il.end());
627 template <class _Value, class _Hash, class _Pred, class _Alloc>
628 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
629 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
630 const key_equal& __eql)
631 : __table_(__hf, __eql)
633 __table_.rehash(__n);
634 insert(__il.begin(), __il.end());
637 template <class _Value, class _Hash, class _Pred, class _Alloc>
638 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
639 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
640 const key_equal& __eql, const allocator_type& __a)
641 : __table_(__hf, __eql, __a)
643 __table_.rehash(__n);
644 insert(__il.begin(), __il.end());
647 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
649 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
651 template <class _Value, class _Hash, class _Pred, class _Alloc>
652 inline _LIBCPP_INLINE_VISIBILITY
653 unordered_set<_Value, _Hash, _Pred, _Alloc>&
654 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
655 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
657 __table_ = _VSTD::move(__u.__table_);
661 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
663 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
665 template <class _Value, class _Hash, class _Pred, class _Alloc>
666 inline _LIBCPP_INLINE_VISIBILITY
667 unordered_set<_Value, _Hash, _Pred, _Alloc>&
668 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
669 initializer_list<value_type> __il)
671 __table_.__assign_unique(__il.begin(), __il.end());
675 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
677 template <class _Value, class _Hash, class _Pred, class _Alloc>
678 template <class _InputIterator>
679 inline _LIBCPP_INLINE_VISIBILITY
681 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
682 _InputIterator __last)
684 for (; __first != __last; ++__first)
685 __table_.__insert_unique(*__first);
688 template <class _Value, class _Hash, class _Pred, class _Alloc>
689 inline _LIBCPP_INLINE_VISIBILITY
691 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
692 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
693 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
698 template <class _Value, class _Hash, class _Pred, class _Alloc>
700 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
701 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
703 if (__x.size() != __y.size())
705 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
707 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
710 const_iterator __j = __y.find(*__i);
711 if (__j == __ey || !(*__i == *__j))
717 template <class _Value, class _Hash, class _Pred, class _Alloc>
718 inline _LIBCPP_INLINE_VISIBILITY
720 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
721 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
723 return !(__x == __y);
726 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
727 class _Alloc = allocator<_Value> >
728 class _LIBCPP_TYPE_VIS unordered_multiset
732 typedef _Value key_type;
733 typedef key_type value_type;
734 typedef _Hash hasher;
735 typedef _Pred key_equal;
736 typedef _Alloc allocator_type;
737 typedef value_type& reference;
738 typedef const value_type& const_reference;
741 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
746 typedef typename __table::pointer pointer;
747 typedef typename __table::const_pointer const_pointer;
748 typedef typename __table::size_type size_type;
749 typedef typename __table::difference_type difference_type;
751 typedef typename __table::const_iterator iterator;
752 typedef typename __table::const_iterator const_iterator;
753 typedef typename __table::const_local_iterator local_iterator;
754 typedef typename __table::const_local_iterator const_local_iterator;
756 _LIBCPP_INLINE_VISIBILITY
758 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
760 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
761 const key_equal& __eql = key_equal());
762 unordered_multiset(size_type __n, const hasher& __hf,
763 const key_equal& __eql, const allocator_type& __a);
764 template <class _InputIterator>
765 unordered_multiset(_InputIterator __first, _InputIterator __last);
766 template <class _InputIterator>
767 unordered_multiset(_InputIterator __first, _InputIterator __last,
768 size_type __n, const hasher& __hf = hasher(),
769 const key_equal& __eql = key_equal());
770 template <class _InputIterator>
771 unordered_multiset(_InputIterator __first, _InputIterator __last,
772 size_type __n , const hasher& __hf,
773 const key_equal& __eql, const allocator_type& __a);
774 explicit unordered_multiset(const allocator_type& __a);
775 unordered_multiset(const unordered_multiset& __u);
776 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
777 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
778 unordered_multiset(unordered_multiset&& __u)
779 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
780 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
781 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
782 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
783 unordered_multiset(initializer_list<value_type> __il);
784 unordered_multiset(initializer_list<value_type> __il, size_type __n,
785 const hasher& __hf = hasher(),
786 const key_equal& __eql = key_equal());
787 unordered_multiset(initializer_list<value_type> __il, size_type __n,
788 const hasher& __hf, const key_equal& __eql,
789 const allocator_type& __a);
790 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
791 // ~unordered_multiset() = default;
792 _LIBCPP_INLINE_VISIBILITY
793 unordered_multiset& operator=(const unordered_multiset& __u)
795 __table_ = __u.__table_;
798 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
799 unordered_multiset& operator=(unordered_multiset&& __u)
800 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
802 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
803 unordered_multiset& operator=(initializer_list<value_type> __il);
804 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
806 _LIBCPP_INLINE_VISIBILITY
807 allocator_type get_allocator() const _NOEXCEPT
808 {return allocator_type(__table_.__node_alloc());}
810 _LIBCPP_INLINE_VISIBILITY
811 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
812 _LIBCPP_INLINE_VISIBILITY
813 size_type size() const _NOEXCEPT {return __table_.size();}
814 _LIBCPP_INLINE_VISIBILITY
815 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
817 _LIBCPP_INLINE_VISIBILITY
818 iterator begin() _NOEXCEPT {return __table_.begin();}
819 _LIBCPP_INLINE_VISIBILITY
820 iterator end() _NOEXCEPT {return __table_.end();}
821 _LIBCPP_INLINE_VISIBILITY
822 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
823 _LIBCPP_INLINE_VISIBILITY
824 const_iterator end() const _NOEXCEPT {return __table_.end();}
825 _LIBCPP_INLINE_VISIBILITY
826 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
827 _LIBCPP_INLINE_VISIBILITY
828 const_iterator cend() const _NOEXCEPT {return __table_.end();}
830 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
831 template <class... _Args>
832 _LIBCPP_INLINE_VISIBILITY
833 iterator emplace(_Args&&... __args)
834 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
835 template <class... _Args>
836 _LIBCPP_INLINE_VISIBILITY
837 iterator emplace_hint(const_iterator __p, _Args&&... __args)
838 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
839 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
840 _LIBCPP_INLINE_VISIBILITY
841 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
842 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
843 _LIBCPP_INLINE_VISIBILITY
844 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
846 _LIBCPP_INLINE_VISIBILITY
847 iterator insert(const_iterator __p, const value_type& __x)
848 {return __table_.__insert_multi(__p, __x);}
849 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
850 _LIBCPP_INLINE_VISIBILITY
851 iterator insert(const_iterator __p, value_type&& __x)
852 {return __table_.__insert_multi(__p, _VSTD::move(__x));}
853 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
854 template <class _InputIterator>
855 void insert(_InputIterator __first, _InputIterator __last);
856 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
857 _LIBCPP_INLINE_VISIBILITY
858 void insert(initializer_list<value_type> __il)
859 {insert(__il.begin(), __il.end());}
860 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
862 _LIBCPP_INLINE_VISIBILITY
863 iterator erase(const_iterator __p) {return __table_.erase(__p);}
864 _LIBCPP_INLINE_VISIBILITY
865 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
866 _LIBCPP_INLINE_VISIBILITY
867 iterator erase(const_iterator __first, const_iterator __last)
868 {return __table_.erase(__first, __last);}
869 _LIBCPP_INLINE_VISIBILITY
870 void clear() _NOEXCEPT {__table_.clear();}
872 _LIBCPP_INLINE_VISIBILITY
873 void swap(unordered_multiset& __u)
874 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
875 {__table_.swap(__u.__table_);}
877 _LIBCPP_INLINE_VISIBILITY
878 hasher hash_function() const {return __table_.hash_function();}
879 _LIBCPP_INLINE_VISIBILITY
880 key_equal key_eq() const {return __table_.key_eq();}
882 _LIBCPP_INLINE_VISIBILITY
883 iterator find(const key_type& __k) {return __table_.find(__k);}
884 _LIBCPP_INLINE_VISIBILITY
885 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
886 _LIBCPP_INLINE_VISIBILITY
887 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
888 _LIBCPP_INLINE_VISIBILITY
889 pair<iterator, iterator> equal_range(const key_type& __k)
890 {return __table_.__equal_range_multi(__k);}
891 _LIBCPP_INLINE_VISIBILITY
892 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
893 {return __table_.__equal_range_multi(__k);}
895 _LIBCPP_INLINE_VISIBILITY
896 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
897 _LIBCPP_INLINE_VISIBILITY
898 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
900 _LIBCPP_INLINE_VISIBILITY
901 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
902 _LIBCPP_INLINE_VISIBILITY
903 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
905 _LIBCPP_INLINE_VISIBILITY
906 local_iterator begin(size_type __n) {return __table_.begin(__n);}
907 _LIBCPP_INLINE_VISIBILITY
908 local_iterator end(size_type __n) {return __table_.end(__n);}
909 _LIBCPP_INLINE_VISIBILITY
910 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
911 _LIBCPP_INLINE_VISIBILITY
912 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
913 _LIBCPP_INLINE_VISIBILITY
914 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
915 _LIBCPP_INLINE_VISIBILITY
916 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
918 _LIBCPP_INLINE_VISIBILITY
919 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
920 _LIBCPP_INLINE_VISIBILITY
921 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
922 _LIBCPP_INLINE_VISIBILITY
923 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
924 _LIBCPP_INLINE_VISIBILITY
925 void rehash(size_type __n) {__table_.rehash(__n);}
926 _LIBCPP_INLINE_VISIBILITY
927 void reserve(size_type __n) {__table_.reserve(__n);}
930 template <class _Value, class _Hash, class _Pred, class _Alloc>
931 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
932 size_type __n, const hasher& __hf, const key_equal& __eql)
933 : __table_(__hf, __eql)
935 __table_.rehash(__n);
938 template <class _Value, class _Hash, class _Pred, class _Alloc>
939 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
940 size_type __n, const hasher& __hf, const key_equal& __eql,
941 const allocator_type& __a)
942 : __table_(__hf, __eql, __a)
944 __table_.rehash(__n);
947 template <class _Value, class _Hash, class _Pred, class _Alloc>
948 template <class _InputIterator>
949 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
950 _InputIterator __first, _InputIterator __last)
952 insert(__first, __last);
955 template <class _Value, class _Hash, class _Pred, class _Alloc>
956 template <class _InputIterator>
957 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
958 _InputIterator __first, _InputIterator __last, size_type __n,
959 const hasher& __hf, const key_equal& __eql)
960 : __table_(__hf, __eql)
962 __table_.rehash(__n);
963 insert(__first, __last);
966 template <class _Value, class _Hash, class _Pred, class _Alloc>
967 template <class _InputIterator>
968 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
969 _InputIterator __first, _InputIterator __last, size_type __n,
970 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
971 : __table_(__hf, __eql, __a)
973 __table_.rehash(__n);
974 insert(__first, __last);
977 template <class _Value, class _Hash, class _Pred, class _Alloc>
978 inline _LIBCPP_INLINE_VISIBILITY
979 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
980 const allocator_type& __a)
985 template <class _Value, class _Hash, class _Pred, class _Alloc>
986 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
987 const unordered_multiset& __u)
988 : __table_(__u.__table_)
990 __table_.rehash(__u.bucket_count());
991 insert(__u.begin(), __u.end());
994 template <class _Value, class _Hash, class _Pred, class _Alloc>
995 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
996 const unordered_multiset& __u, const allocator_type& __a)
997 : __table_(__u.__table_, __a)
999 __table_.rehash(__u.bucket_count());
1000 insert(__u.begin(), __u.end());
1003 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1005 template <class _Value, class _Hash, class _Pred, class _Alloc>
1006 inline _LIBCPP_INLINE_VISIBILITY
1007 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1008 unordered_multiset&& __u)
1009 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1010 : __table_(_VSTD::move(__u.__table_))
1014 template <class _Value, class _Hash, class _Pred, class _Alloc>
1015 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1016 unordered_multiset&& __u, const allocator_type& __a)
1017 : __table_(_VSTD::move(__u.__table_), __a)
1019 if (__a != __u.get_allocator())
1021 iterator __i = __u.begin();
1022 while (__u.size() != 0)
1023 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1027 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1029 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1031 template <class _Value, class _Hash, class _Pred, class _Alloc>
1032 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1033 initializer_list<value_type> __il)
1035 insert(__il.begin(), __il.end());
1038 template <class _Value, class _Hash, class _Pred, class _Alloc>
1039 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1040 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1041 const key_equal& __eql)
1042 : __table_(__hf, __eql)
1044 __table_.rehash(__n);
1045 insert(__il.begin(), __il.end());
1048 template <class _Value, class _Hash, class _Pred, class _Alloc>
1049 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1050 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1051 const key_equal& __eql, const allocator_type& __a)
1052 : __table_(__hf, __eql, __a)
1054 __table_.rehash(__n);
1055 insert(__il.begin(), __il.end());
1058 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1060 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1062 template <class _Value, class _Hash, class _Pred, class _Alloc>
1063 inline _LIBCPP_INLINE_VISIBILITY
1064 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1065 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1066 unordered_multiset&& __u)
1067 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1069 __table_ = _VSTD::move(__u.__table_);
1073 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1075 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1077 template <class _Value, class _Hash, class _Pred, class _Alloc>
1079 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1080 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1081 initializer_list<value_type> __il)
1083 __table_.__assign_multi(__il.begin(), __il.end());
1087 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1089 template <class _Value, class _Hash, class _Pred, class _Alloc>
1090 template <class _InputIterator>
1091 inline _LIBCPP_INLINE_VISIBILITY
1093 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1094 _InputIterator __last)
1096 for (; __first != __last; ++__first)
1097 __table_.__insert_multi(*__first);
1100 template <class _Value, class _Hash, class _Pred, class _Alloc>
1101 inline _LIBCPP_INLINE_VISIBILITY
1103 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1104 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1105 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1110 template <class _Value, class _Hash, class _Pred, class _Alloc>
1112 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1113 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1115 if (__x.size() != __y.size())
1117 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1119 typedef pair<const_iterator, const_iterator> _EqRng;
1120 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1122 _EqRng __xeq = __x.equal_range(*__i);
1123 _EqRng __yeq = __y.equal_range(*__i);
1124 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1125 _VSTD::distance(__yeq.first, __yeq.second) ||
1126 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1133 template <class _Value, class _Hash, class _Pred, class _Alloc>
1134 inline _LIBCPP_INLINE_VISIBILITY
1136 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1137 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1139 return !(__x == __y);
1142 _LIBCPP_END_NAMESPACE_STD
1144 #endif // _LIBCPP_UNORDERED_SET