1046 lines · plain
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_UNORDERED_SET11#define _LIBCPP___CXX03_UNORDERED_SET12 13// clang-format off14 15/*16 17 unordered_set synopsis18 19#include <__cxx03/initializer_list>20 21namespace std22{23 24template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,25 class Alloc = allocator<Value>>26class unordered_set27{28public:29 // types30 typedef Value key_type;31 typedef key_type value_type;32 typedef Hash hasher;33 typedef Pred key_equal;34 typedef Alloc allocator_type;35 typedef value_type& reference;36 typedef const value_type& const_reference;37 typedef typename allocator_traits<allocator_type>::pointer pointer;38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;39 typedef typename allocator_traits<allocator_type>::size_type size_type;40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;41 42 typedef /unspecified/ iterator;43 typedef /unspecified/ const_iterator;44 typedef /unspecified/ local_iterator;45 typedef /unspecified/ const_local_iterator;46 47 typedef unspecified node_type unspecified; // C++1748 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++1749 50 unordered_set()51 noexcept(52 is_nothrow_default_constructible<hasher>::value &&53 is_nothrow_default_constructible<key_equal>::value &&54 is_nothrow_default_constructible<allocator_type>::value);55 explicit unordered_set(size_type n, const hasher& hf = hasher(),56 const key_equal& eql = key_equal(),57 const allocator_type& a = allocator_type());58 template <class InputIterator>59 unordered_set(InputIterator f, InputIterator l,60 size_type n = 0, const hasher& hf = hasher(),61 const key_equal& eql = key_equal(),62 const allocator_type& a = allocator_type());63 template<container-compatible-range<value_type> R>64 unordered_set(from_range_t, R&& rg, size_type n = see below,65 const hasher& hf = hasher(), const key_equal& eql = key_equal(),66 const allocator_type& a = allocator_type()); // C++2367 explicit unordered_set(const allocator_type&);68 unordered_set(const unordered_set&);69 unordered_set(const unordered_set&, const Allocator&);70 unordered_set(unordered_set&&)71 noexcept(72 is_nothrow_move_constructible<hasher>::value &&73 is_nothrow_move_constructible<key_equal>::value &&74 is_nothrow_move_constructible<allocator_type>::value);75 unordered_set(unordered_set&&, const Allocator&);76 unordered_set(initializer_list<value_type>, size_type n = 0,77 const hasher& hf = hasher(), const key_equal& eql = key_equal(),78 const allocator_type& a = allocator_type());79 unordered_set(size_type n, const allocator_type& a); // C++1480 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++1481 template <class InputIterator>82 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++1483 template <class InputIterator>84 unordered_set(InputIterator f, InputIterator l, size_type n,85 const hasher& hf, const allocator_type& a); // C++1486 template<container-compatible-range<value_type> R>87 unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)88 : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++2389 template<container-compatible-range<value_type> R>90 unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)91 : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++2392 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++1493 unordered_set(initializer_list<value_type> il, size_type n,94 const hasher& hf, const allocator_type& a); // C++1495 ~unordered_set();96 unordered_set& operator=(const unordered_set&);97 unordered_set& operator=(unordered_set&&)98 noexcept(99 allocator_type::propagate_on_container_move_assignment::value &&100 is_nothrow_move_assignable<allocator_type>::value &&101 is_nothrow_move_assignable<hasher>::value &&102 is_nothrow_move_assignable<key_equal>::value);103 unordered_set& operator=(initializer_list<value_type>);104 105 allocator_type get_allocator() const noexcept;106 107 bool empty() const noexcept;108 size_type size() const noexcept;109 size_type max_size() const noexcept;110 111 iterator begin() noexcept;112 iterator end() noexcept;113 const_iterator begin() const noexcept;114 const_iterator end() const noexcept;115 const_iterator cbegin() const noexcept;116 const_iterator cend() const noexcept;117 118 template <class... Args>119 pair<iterator, bool> emplace(Args&&... args);120 template <class... Args>121 iterator emplace_hint(const_iterator position, Args&&... args);122 pair<iterator, bool> insert(const value_type& obj);123 pair<iterator, bool> insert(value_type&& obj);124 iterator insert(const_iterator hint, const value_type& obj);125 iterator insert(const_iterator hint, value_type&& obj);126 template <class InputIterator>127 void insert(InputIterator first, InputIterator last);128 template<container-compatible-range<value_type> R>129 void insert_range(R&& rg); // C++23130 void insert(initializer_list<value_type>);131 132 node_type extract(const_iterator position); // C++17133 node_type extract(const key_type& x); // C++17134 insert_return_type insert(node_type&& nh); // C++17135 iterator insert(const_iterator hint, node_type&& nh); // C++17136 137 iterator erase(const_iterator position);138 iterator erase(iterator position); // C++14139 size_type erase(const key_type& k);140 iterator erase(const_iterator first, const_iterator last);141 void clear() noexcept;142 143 template<class H2, class P2>144 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17145 template<class H2, class P2>146 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17147 template<class H2, class P2>148 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17149 template<class H2, class P2>150 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17151 152 void swap(unordered_set&)153 noexcept(allocator_traits<Allocator>::is_always_equal::value &&154 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&155 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17156 157 hasher hash_function() const;158 key_equal key_eq() const;159 160 iterator find(const key_type& k);161 const_iterator find(const key_type& k) const;162 template<typename K>163 iterator find(const K& x); // C++20164 template<typename K>165 const_iterator find(const K& x) const; // C++20166 size_type count(const key_type& k) const;167 template<typename K>168 size_type count(const K& k) const; // C++20169 bool contains(const key_type& k) const; // C++20170 template<typename K>171 bool contains(const K& k) const; // C++20172 pair<iterator, iterator> equal_range(const key_type& k);173 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;174 template<typename K>175 pair<iterator, iterator> equal_range(const K& k); // C++20176 template<typename K>177 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20178 179 size_type bucket_count() const noexcept;180 size_type max_bucket_count() const noexcept;181 182 size_type bucket_size(size_type n) const;183 size_type bucket(const key_type& k) const;184 185 local_iterator begin(size_type n);186 local_iterator end(size_type n);187 const_local_iterator begin(size_type n) const;188 const_local_iterator end(size_type n) const;189 const_local_iterator cbegin(size_type n) const;190 const_local_iterator cend(size_type n) const;191 192 float load_factor() const noexcept;193 float max_load_factor() const noexcept;194 void max_load_factor(float z);195 void rehash(size_type n);196 void reserve(size_type n);197};198 199template<class InputIterator,200 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,201 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,202 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>203unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,204 Hash = Hash(), Pred = Pred(), Allocator = Allocator())205 -> unordered_set<typename iterator_traits<InputIterator>::value_type,206 Hash, Pred, Allocator>; // C++17207 208template<ranges::input_range R,209 class Hash = hash<ranges::range_value_t<R>>,210 class Pred = equal_to<ranges::range_value_t<R>>,211 class Allocator = allocator<ranges::range_value_t<R>>>212 unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())213 -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23214 215template<class T, class Hash = hash<T>,216 class Pred = equal_to<T>, class Allocator = allocator<T>>217unordered_set(initializer_list<T>, typename see below::size_type = see below,218 Hash = Hash(), Pred = Pred(), Allocator = Allocator())219 -> unordered_set<T, Hash, Pred, Allocator>; // C++17220 221template<class InputIterator, class Allocator>222unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)223 -> unordered_set<typename iterator_traits<InputIterator>::value_type,224 hash<typename iterator_traits<InputIterator>::value_type>,225 equal_to<typename iterator_traits<InputIterator>::value_type>,226 Allocator>; // C++17227 228template<class InputIterator, class Hash, class Allocator>229unordered_set(InputIterator, InputIterator, typename see below::size_type,230 Hash, Allocator)231 -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,232 equal_to<typename iterator_traits<InputIterator>::value_type>,233 Allocator>; // C++17234 235template<ranges::input_range R, class Allocator>236 unordered_set(from_range_t, R&&, typename see below::size_type, Allocator)237 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,238 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23239 240template<ranges::input_range R, class Allocator>241 unordered_set(from_range_t, R&&, Allocator)242 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,243 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23244 245template<ranges::input_range R, class Hash, class Allocator>246 unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator)247 -> unordered_set<ranges::range_value_t<R>, Hash,248 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23249 250template<class T, class Allocator>251unordered_set(initializer_list<T>, typename see below::size_type, Allocator)252 -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17253 254template<class T, class Hash, class Allocator>255unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)256 -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17257 258template <class Value, class Hash, class Pred, class Alloc>259 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,260 unordered_set<Value, Hash, Pred, Alloc>& y)261 noexcept(noexcept(x.swap(y)));262 263template <class Value, class Hash, class Pred, class Alloc>264 bool265 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,266 const unordered_set<Value, Hash, Pred, Alloc>& y);267 268template <class Value, class Hash, class Pred, class Alloc>269 bool270 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,271 const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20272 273template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,274 class Alloc = allocator<Value>>275class unordered_multiset276{277public:278 // types279 typedef Value key_type;280 typedef key_type value_type;281 typedef Hash hasher;282 typedef Pred key_equal;283 typedef Alloc allocator_type;284 typedef value_type& reference;285 typedef const value_type& const_reference;286 typedef typename allocator_traits<allocator_type>::pointer pointer;287 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;288 typedef typename allocator_traits<allocator_type>::size_type size_type;289 typedef typename allocator_traits<allocator_type>::difference_type difference_type;290 291 typedef /unspecified/ iterator;292 typedef /unspecified/ const_iterator;293 typedef /unspecified/ local_iterator;294 typedef /unspecified/ const_local_iterator;295 296 typedef unspecified node_type unspecified; // C++17297 298 unordered_multiset()299 noexcept(300 is_nothrow_default_constructible<hasher>::value &&301 is_nothrow_default_constructible<key_equal>::value &&302 is_nothrow_default_constructible<allocator_type>::value);303 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),304 const key_equal& eql = key_equal(),305 const allocator_type& a = allocator_type());306 template <class InputIterator>307 unordered_multiset(InputIterator f, InputIterator l,308 size_type n = 0, const hasher& hf = hasher(),309 const key_equal& eql = key_equal(),310 const allocator_type& a = allocator_type());311 template<container-compatible-range<value_type> R>312 unordered_multiset(from_range_t, R&& rg, size_type n = see below,313 const hasher& hf = hasher(), const key_equal& eql = key_equal(),314 const allocator_type& a = allocator_type()); // C++23315 explicit unordered_multiset(const allocator_type&);316 unordered_multiset(const unordered_multiset&);317 unordered_multiset(const unordered_multiset&, const Allocator&);318 unordered_multiset(unordered_multiset&&)319 noexcept(320 is_nothrow_move_constructible<hasher>::value &&321 is_nothrow_move_constructible<key_equal>::value &&322 is_nothrow_move_constructible<allocator_type>::value);323 unordered_multiset(unordered_multiset&&, const Allocator&);324 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,325 const hasher& hf = hasher(), const key_equal& eql = key_equal(),326 const allocator_type& a = allocator_type());327 unordered_multiset(size_type n, const allocator_type& a); // C++14328 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14329 template <class InputIterator>330 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14331 template <class InputIterator>332 unordered_multiset(InputIterator f, InputIterator l, size_type n,333 const hasher& hf, const allocator_type& a); // C++14334 template<container-compatible-range<value_type> R>335 unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)336 : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23337 template<container-compatible-range<value_type> R>338 unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)339 : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23340 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14341 unordered_multiset(initializer_list<value_type> il, size_type n,342 const hasher& hf, const allocator_type& a); // C++14343 ~unordered_multiset();344 unordered_multiset& operator=(const unordered_multiset&);345 unordered_multiset& operator=(unordered_multiset&&)346 noexcept(347 allocator_type::propagate_on_container_move_assignment::value &&348 is_nothrow_move_assignable<allocator_type>::value &&349 is_nothrow_move_assignable<hasher>::value &&350 is_nothrow_move_assignable<key_equal>::value);351 unordered_multiset& operator=(initializer_list<value_type>);352 353 allocator_type get_allocator() const noexcept;354 355 bool empty() const noexcept;356 size_type size() const noexcept;357 size_type max_size() const noexcept;358 359 iterator begin() noexcept;360 iterator end() noexcept;361 const_iterator begin() const noexcept;362 const_iterator end() const noexcept;363 const_iterator cbegin() const noexcept;364 const_iterator cend() const noexcept;365 366 template <class... Args>367 iterator emplace(Args&&... args);368 template <class... Args>369 iterator emplace_hint(const_iterator position, Args&&... args);370 iterator insert(const value_type& obj);371 iterator insert(value_type&& obj);372 iterator insert(const_iterator hint, const value_type& obj);373 iterator insert(const_iterator hint, value_type&& obj);374 template <class InputIterator>375 void insert(InputIterator first, InputIterator last);376 template<container-compatible-range<value_type> R>377 void insert_range(R&& rg); // C++23378 void insert(initializer_list<value_type>);379 380 node_type extract(const_iterator position); // C++17381 node_type extract(const key_type& x); // C++17382 iterator insert(node_type&& nh); // C++17383 iterator insert(const_iterator hint, node_type&& nh); // C++17384 385 iterator erase(const_iterator position);386 iterator erase(iterator position); // C++14387 size_type erase(const key_type& k);388 iterator erase(const_iterator first, const_iterator last);389 void clear() noexcept;390 391 template<class H2, class P2>392 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17393 template<class H2, class P2>394 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17395 template<class H2, class P2>396 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17397 template<class H2, class P2>398 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17399 400 void swap(unordered_multiset&)401 noexcept(allocator_traits<Allocator>::is_always_equal::value &&402 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&403 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17404 405 hasher hash_function() const;406 key_equal key_eq() const;407 408 iterator find(const key_type& k);409 const_iterator find(const key_type& k) const;410 template<typename K>411 iterator find(const K& x); // C++20412 template<typename K>413 const_iterator find(const K& x) const; // C++20414 size_type count(const key_type& k) const;415 template<typename K>416 size_type count(const K& k) const; // C++20417 bool contains(const key_type& k) const; // C++20418 template<typename K>419 bool contains(const K& k) const; // C++20420 pair<iterator, iterator> equal_range(const key_type& k);421 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;422 template<typename K>423 pair<iterator, iterator> equal_range(const K& k); // C++20424 template<typename K>425 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20426 427 size_type bucket_count() const noexcept;428 size_type max_bucket_count() const noexcept;429 430 size_type bucket_size(size_type n) const;431 size_type bucket(const key_type& k) const;432 433 local_iterator begin(size_type n);434 local_iterator end(size_type n);435 const_local_iterator begin(size_type n) const;436 const_local_iterator end(size_type n) const;437 const_local_iterator cbegin(size_type n) const;438 const_local_iterator cend(size_type n) const;439 440 float load_factor() const noexcept;441 float max_load_factor() const noexcept;442 void max_load_factor(float z);443 void rehash(size_type n);444 void reserve(size_type n);445};446 447template<class InputIterator,448 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,449 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,450 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>451unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,452 Hash = Hash(), Pred = Pred(), Allocator = Allocator())453 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,454 Hash, Pred, Allocator>; // C++17455 456template<ranges::input_range R,457 class Hash = hash<ranges::range_value_t<R>>,458 class Pred = equal_to<ranges::range_value_t<R>>,459 class Allocator = allocator<ranges::range_value_t<R>>>460 unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())461 -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23462 463template<class T, class Hash = hash<T>,464 class Pred = equal_to<T>, class Allocator = allocator<T>>465unordered_multiset(initializer_list<T>, typename see below::size_type = see below,466 Hash = Hash(), Pred = Pred(), Allocator = Allocator())467 -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17468 469template<class InputIterator, class Allocator>470unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)471 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,472 hash<typename iterator_traits<InputIterator>::value_type>,473 equal_to<typename iterator_traits<InputIterator>::value_type>,474 Allocator>; // C++17475 476template<class InputIterator, class Hash, class Allocator>477unordered_multiset(InputIterator, InputIterator, typename see below::size_type,478 Hash, Allocator)479 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,480 equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17481 482template<ranges::input_range R, class Allocator>483 unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator)484 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,485 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23486 487template<ranges::input_range R, class Allocator>488 unordered_multiset(from_range_t, R&&, Allocator)489 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,490 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23491 492template<ranges::input_range R, class Hash, class Allocator>493 unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator)494 -> unordered_multiset<ranges::range_value_t<R>, Hash,495 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23496 497template<class T, class Allocator>498unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)499 -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17500 501template<class T, class Hash, class Allocator>502unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)503 -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17504 505template <class Value, class Hash, class Pred, class Alloc>506 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,507 unordered_multiset<Value, Hash, Pred, Alloc>& y)508 noexcept(noexcept(x.swap(y)));509 510template <class K, class T, class H, class P, class A, class Predicate>511 typename unordered_set<K, T, H, P, A>::size_type512 erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20513 514template <class K, class T, class H, class P, class A, class Predicate>515 typename unordered_multiset<K, T, H, P, A>::size_type516 erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20517 518 519template <class Value, class Hash, class Pred, class Alloc>520 bool521 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,522 const unordered_multiset<Value, Hash, Pred, Alloc>& y);523 524template <class Value, class Hash, class Pred, class Alloc>525 bool526 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,527 const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20528} // std529 530*/531 532// clang-format on533 534#include <__cxx03/__algorithm/is_permutation.h>535#include <__cxx03/__assert>536#include <__cxx03/__config>537#include <__cxx03/__functional/operations.h>538#include <__cxx03/__hash_table>539#include <__cxx03/__iterator/distance.h>540#include <__cxx03/__iterator/erase_if_container.h>541#include <__cxx03/__iterator/iterator_traits.h>542#include <__cxx03/__memory/addressof.h>543#include <__cxx03/__memory/allocator.h>544#include <__cxx03/__type_traits/is_allocator.h>545#include <__cxx03/__utility/forward.h>546#include <__cxx03/version>547 548// standard-mandated includes549 550// [iterator.range]551#include <__cxx03/__iterator/access.h>552 553#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)554# pragma GCC system_header555#endif556 557_LIBCPP_PUSH_MACROS558#include <__cxx03/__undef_macros>559 560_LIBCPP_BEGIN_NAMESPACE_STD561 562template <class _Value, class _Hash, class _Pred, class _Alloc>563class unordered_multiset;564 565template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >566class _LIBCPP_TEMPLATE_VIS unordered_set {567public:568 // types569 typedef _Value key_type;570 typedef key_type value_type;571 typedef __type_identity_t<_Hash> hasher;572 typedef __type_identity_t<_Pred> key_equal;573 typedef __type_identity_t<_Alloc> allocator_type;574 typedef value_type& reference;575 typedef const value_type& const_reference;576 static_assert(__check_valid_allocator<allocator_type>::value, "");577 static_assert(is_same<value_type, typename allocator_type::value_type>::value,578 "Allocator::value_type must be same type as value_type");579 580private:581 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;582 583 __table __table_;584 585public:586 typedef typename __table::pointer pointer;587 typedef typename __table::const_pointer const_pointer;588 typedef typename __table::size_type size_type;589 typedef typename __table::difference_type difference_type;590 591 typedef typename __table::const_iterator iterator;592 typedef typename __table::const_iterator const_iterator;593 typedef typename __table::const_local_iterator local_iterator;594 typedef typename __table::const_local_iterator const_local_iterator;595 596 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>597 friend class _LIBCPP_TEMPLATE_VIS unordered_set;598 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>599 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;600 601 _LIBCPP_HIDE_FROM_ABI unordered_set() {}602 explicit _LIBCPP_HIDE_FROM_ABI603 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());604 605 _LIBCPP_HIDE_FROM_ABI606 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);607 template <class _InputIterator>608 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);609 template <class _InputIterator>610 _LIBCPP_HIDE_FROM_ABI611 unordered_set(_InputIterator __first,612 _InputIterator __last,613 size_type __n,614 const hasher& __hf = hasher(),615 const key_equal& __eql = key_equal());616 template <class _InputIterator>617 _LIBCPP_HIDE_FROM_ABI unordered_set(618 _InputIterator __first,619 _InputIterator __last,620 size_type __n,621 const hasher& __hf,622 const key_equal& __eql,623 const allocator_type& __a);624 625 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);626 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);627 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);628 629 _LIBCPP_HIDE_FROM_ABI ~unordered_set() {630 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");631 }632 633 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {634 __table_ = __u.__table_;635 return *this;636 }637 638 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {639 return allocator_type(__table_.__node_alloc());640 }641 642 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }643 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }644 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }645 646 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }647 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }648 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }649 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }650 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }651 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }652 653 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }654 655 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }656 template <class _InputIterator>657 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);658 659 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }660 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }661 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {662 return __table_.erase(__first, __last);663 }664 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }665 666 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) { __table_.swap(__u.__table_); }667 668 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }669 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }670 671 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }672 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }673 674 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }675 676 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {677 return __table_.__equal_range_unique(__k);678 }679 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {680 return __table_.__equal_range_unique(__k);681 }682 683 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }684 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }685 686 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }687 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }688 689 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }690 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }691 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }692 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }693 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }694 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }695 696 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }697 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }698 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }699 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }700 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }701};702 703template <class _Value, class _Hash, class _Pred, class _Alloc>704unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)705 : __table_(__hf, __eql) {706 __table_.__rehash_unique(__n);707}708 709template <class _Value, class _Hash, class _Pred, class _Alloc>710unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(711 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)712 : __table_(__hf, __eql, __a) {713 __table_.__rehash_unique(__n);714}715 716template <class _Value, class _Hash, class _Pred, class _Alloc>717template <class _InputIterator>718unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {719 insert(__first, __last);720}721 722template <class _Value, class _Hash, class _Pred, class _Alloc>723template <class _InputIterator>724unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(725 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)726 : __table_(__hf, __eql) {727 __table_.__rehash_unique(__n);728 insert(__first, __last);729}730 731template <class _Value, class _Hash, class _Pred, class _Alloc>732template <class _InputIterator>733unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(734 _InputIterator __first,735 _InputIterator __last,736 size_type __n,737 const hasher& __hf,738 const key_equal& __eql,739 const allocator_type& __a)740 : __table_(__hf, __eql, __a) {741 __table_.__rehash_unique(__n);742 insert(__first, __last);743}744 745template <class _Value, class _Hash, class _Pred, class _Alloc>746inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}747 748template <class _Value, class _Hash, class _Pred, class _Alloc>749unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {750 __table_.__rehash_unique(__u.bucket_count());751 insert(__u.begin(), __u.end());752}753 754template <class _Value, class _Hash, class _Pred, class _Alloc>755unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)756 : __table_(__u.__table_, __a) {757 __table_.__rehash_unique(__u.bucket_count());758 insert(__u.begin(), __u.end());759}760 761template <class _Value, class _Hash, class _Pred, class _Alloc>762template <class _InputIterator>763inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {764 for (; __first != __last; ++__first)765 __table_.__insert_unique(*__first);766}767 768template <class _Value, class _Hash, class _Pred, class _Alloc>769inline _LIBCPP_HIDE_FROM_ABI void770swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {771 __x.swap(__y);772}773 774template <class _Value, class _Hash, class _Pred, class _Alloc>775_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,776 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {777 if (__x.size() != __y.size())778 return false;779 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;780 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {781 const_iterator __j = __y.find(*__i);782 if (__j == __ey || !(*__i == *__j))783 return false;784 }785 return true;786}787 788template <class _Value, class _Hash, class _Pred, class _Alloc>789inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,790 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {791 return !(__x == __y);792}793 794template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >795class _LIBCPP_TEMPLATE_VIS unordered_multiset {796public:797 // types798 typedef _Value key_type;799 typedef key_type value_type;800 typedef __type_identity_t<_Hash> hasher;801 typedef __type_identity_t<_Pred> key_equal;802 typedef __type_identity_t<_Alloc> allocator_type;803 typedef value_type& reference;804 typedef const value_type& const_reference;805 static_assert(is_same<value_type, typename allocator_type::value_type>::value,806 "Allocator::value_type must be same type as value_type");807 808private:809 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;810 811 __table __table_;812 813public:814 typedef typename __table::pointer pointer;815 typedef typename __table::const_pointer const_pointer;816 typedef typename __table::size_type size_type;817 typedef typename __table::difference_type difference_type;818 819 typedef typename __table::const_iterator iterator;820 typedef typename __table::const_iterator const_iterator;821 typedef typename __table::const_local_iterator local_iterator;822 typedef typename __table::const_local_iterator const_local_iterator;823 824 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>825 friend class _LIBCPP_TEMPLATE_VIS unordered_set;826 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>827 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;828 829 _LIBCPP_HIDE_FROM_ABI unordered_multiset() {}830 explicit _LIBCPP_HIDE_FROM_ABI831 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());832 _LIBCPP_HIDE_FROM_ABI833 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);834 835 template <class _InputIterator>836 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);837 template <class _InputIterator>838 _LIBCPP_HIDE_FROM_ABI unordered_multiset(839 _InputIterator __first,840 _InputIterator __last,841 size_type __n,842 const hasher& __hf = hasher(),843 const key_equal& __eql = key_equal());844 template <class _InputIterator>845 _LIBCPP_HIDE_FROM_ABI unordered_multiset(846 _InputIterator __first,847 _InputIterator __last,848 size_type __n,849 const hasher& __hf,850 const key_equal& __eql,851 const allocator_type& __a);852 853 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);854 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);855 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);856 857 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {858 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");859 }860 861 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {862 __table_ = __u.__table_;863 return *this;864 }865 866 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {867 return allocator_type(__table_.__node_alloc());868 }869 870 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }871 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }872 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }873 874 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }875 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }876 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }877 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }878 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }879 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }880 881 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }882 883 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {884 return __table_.__insert_multi(__p, __x);885 }886 887 template <class _InputIterator>888 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);889 890 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }891 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }892 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {893 return __table_.erase(__first, __last);894 }895 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }896 897 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) { __table_.swap(__u.__table_); }898 899 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }900 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }901 902 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }903 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }904 905 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }906 907 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {908 return __table_.__equal_range_multi(__k);909 }910 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {911 return __table_.__equal_range_multi(__k);912 }913 914 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }915 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }916 917 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }918 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }919 920 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }921 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }922 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }923 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }924 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }925 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }926 927 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }928 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }929 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }930 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }931 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }932};933 934template <class _Value, class _Hash, class _Pred, class _Alloc>935unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(936 size_type __n, const hasher& __hf, const key_equal& __eql)937 : __table_(__hf, __eql) {938 __table_.__rehash_multi(__n);939}940 941template <class _Value, class _Hash, class _Pred, class _Alloc>942unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(943 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)944 : __table_(__hf, __eql, __a) {945 __table_.__rehash_multi(__n);946}947 948template <class _Value, class _Hash, class _Pred, class _Alloc>949template <class _InputIterator>950unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {951 insert(__first, __last);952}953 954template <class _Value, class _Hash, class _Pred, class _Alloc>955template <class _InputIterator>956unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(957 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)958 : __table_(__hf, __eql) {959 __table_.__rehash_multi(__n);960 insert(__first, __last);961}962 963template <class _Value, class _Hash, class _Pred, class _Alloc>964template <class _InputIterator>965unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(966 _InputIterator __first,967 _InputIterator __last,968 size_type __n,969 const hasher& __hf,970 const key_equal& __eql,971 const allocator_type& __a)972 : __table_(__hf, __eql, __a) {973 __table_.__rehash_multi(__n);974 insert(__first, __last);975}976 977template <class _Value, class _Hash, class _Pred, class _Alloc>978inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)979 : __table_(__a) {}980 981template <class _Value, class _Hash, class _Pred, class _Alloc>982unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)983 : __table_(__u.__table_) {984 __table_.__rehash_multi(__u.bucket_count());985 insert(__u.begin(), __u.end());986}987 988template <class _Value, class _Hash, class _Pred, class _Alloc>989unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(990 const unordered_multiset& __u, const allocator_type& __a)991 : __table_(__u.__table_, __a) {992 __table_.__rehash_multi(__u.bucket_count());993 insert(__u.begin(), __u.end());994}995 996template <class _Value, class _Hash, class _Pred, class _Alloc>997template <class _InputIterator>998inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {999 for (; __first != __last; ++__first)1000 __table_.__insert_multi(*__first);1001}1002 1003template <class _Value, class _Hash, class _Pred, class _Alloc>1004inline _LIBCPP_HIDE_FROM_ABI void1005swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {1006 __x.swap(__y);1007}1008 1009template <class _Value, class _Hash, class _Pred, class _Alloc>1010_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,1011 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {1012 if (__x.size() != __y.size())1013 return false;1014 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;1015 typedef pair<const_iterator, const_iterator> _EqRng;1016 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {1017 _EqRng __xeq = __x.equal_range(*__i);1018 _EqRng __yeq = __y.equal_range(*__i);1019 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||1020 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))1021 return false;1022 __i = __xeq.second;1023 }1024 return true;1025}1026 1027template <class _Value, class _Hash, class _Pred, class _Alloc>1028inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,1029 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {1030 return !(__x == __y);1031}1032 1033_LIBCPP_END_NAMESPACE_STD1034 1035_LIBCPP_POP_MACROS1036 1037#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)1038# include <__cxx03/cstdlib>1039# include <__cxx03/functional>1040# include <__cxx03/iterator>1041# include <__cxx03/stdexcept>1042# include <__cxx03/type_traits>1043#endif1044 1045#endif // _LIBCPP___CXX03_UNORDERED_SET1046