1807 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_UNORDERED_SET11#define _LIBCPP_UNORDERED_SET12 13// clang-format off14 15/*16 17 unordered_set synopsis18 19#include <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#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)535# include <__cxx03/unordered_set>536#else537# include <__algorithm/is_permutation.h>538# include <__assert>539# include <__config>540# include <__functional/hash.h>541# include <__functional/is_transparent.h>542# include <__functional/operations.h>543# include <__hash_table>544# include <__iterator/distance.h>545# include <__iterator/erase_if_container.h>546# include <__iterator/iterator_traits.h>547# include <__memory/allocator.h>548# include <__memory/allocator_traits.h>549# include <__memory_resource/polymorphic_allocator.h>550# include <__node_handle>551# include <__ranges/concepts.h>552# include <__ranges/container_compatible_range.h>553# include <__ranges/from_range.h>554# include <__type_traits/container_traits.h>555# include <__type_traits/enable_if.h>556# include <__type_traits/invoke.h>557# include <__type_traits/is_allocator.h>558# include <__type_traits/is_integral.h>559# include <__type_traits/is_nothrow_constructible.h>560# include <__type_traits/is_same.h>561# include <__type_traits/is_swappable.h>562# include <__type_traits/type_identity.h>563# include <__utility/forward.h>564# include <__utility/move.h>565# include <__utility/pair.h>566# include <version>567 568// standard-mandated includes569 570// [iterator.range]571# include <__iterator/access.h>572# include <__iterator/data.h>573# include <__iterator/empty.h>574# include <__iterator/reverse_access.h>575# include <__iterator/size.h>576 577// [unord.set.syn]578# include <compare>579# include <initializer_list>580 581# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)582# pragma GCC system_header583# endif584 585_LIBCPP_PUSH_MACROS586# include <__undef_macros>587 588_LIBCPP_BEGIN_NAMESPACE_STD589 590template <class _Value, class _Hash, class _Pred, class _Alloc>591class unordered_multiset;592 593template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >594class unordered_set {595public:596 // types597 typedef _Value key_type;598 typedef key_type value_type;599 typedef __type_identity_t<_Hash> hasher;600 typedef __type_identity_t<_Pred> key_equal;601 typedef __type_identity_t<_Alloc> allocator_type;602 typedef value_type& reference;603 typedef const value_type& const_reference;604 static_assert(__check_valid_allocator<allocator_type>::value, "");605 static_assert(is_same<value_type, typename allocator_type::value_type>::value,606 "Allocator::value_type must be same type as value_type");607 608private:609 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;610 611 __table __table_;612 613public:614 typedef typename __table::pointer pointer;615 typedef typename __table::const_pointer const_pointer;616 typedef typename __table::size_type size_type;617 typedef typename __table::difference_type difference_type;618 619 typedef typename __table::const_iterator iterator;620 typedef typename __table::const_iterator const_iterator;621 typedef typename __table::const_local_iterator local_iterator;622 typedef typename __table::const_local_iterator const_local_iterator;623 624# if _LIBCPP_STD_VER >= 17625 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;626 typedef __insert_return_type<iterator, node_type> insert_return_type;627# endif628 629 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>630 friend class unordered_set;631 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>632 friend class unordered_multiset;633 634 _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}635 explicit _LIBCPP_HIDE_FROM_ABI636 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());637# if _LIBCPP_STD_VER >= 14638 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)639 : unordered_set(__n, hasher(), key_equal(), __a) {}640 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)641 : unordered_set(__n, __hf, key_equal(), __a) {}642# endif643 _LIBCPP_HIDE_FROM_ABI644 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);645 template <class _InputIterator>646 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);647 template <class _InputIterator>648 _LIBCPP_HIDE_FROM_ABI649 unordered_set(_InputIterator __first,650 _InputIterator __last,651 size_type __n,652 const hasher& __hf = hasher(),653 const key_equal& __eql = key_equal());654 template <class _InputIterator>655 _LIBCPP_HIDE_FROM_ABI unordered_set(656 _InputIterator __first,657 _InputIterator __last,658 size_type __n,659 const hasher& __hf,660 const key_equal& __eql,661 const allocator_type& __a);662 663# if _LIBCPP_STD_VER >= 23664 template <_ContainerCompatibleRange<value_type> _Range>665 _LIBCPP_HIDE_FROM_ABI unordered_set(666 from_range_t,667 _Range&& __range,668 size_type __n = /*implementation-defined*/ 0,669 const hasher& __hf = hasher(),670 const key_equal& __eql = key_equal(),671 const allocator_type& __a = allocator_type())672 : __table_(__hf, __eql, __a) {673 if (__n > 0) {674 __table_.__rehash_unique(__n);675 }676 insert_range(std::forward<_Range>(__range));677 }678# endif679 680# if _LIBCPP_STD_VER >= 14681 template <class _InputIterator>682 inline _LIBCPP_HIDE_FROM_ABI683 unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)684 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}685 template <class _InputIterator>686 _LIBCPP_HIDE_FROM_ABI unordered_set(687 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)688 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}689# endif690 691# if _LIBCPP_STD_VER >= 23692 template <_ContainerCompatibleRange<value_type> _Range>693 _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)694 : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}695 696 template <_ContainerCompatibleRange<value_type> _Range>697 _LIBCPP_HIDE_FROM_ABI698 unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)699 : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}700# endif701 702 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);703 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u) = default;704 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);705# ifndef _LIBCPP_CXX03_LANG706 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) = default;707 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);708 _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);709 _LIBCPP_HIDE_FROM_ABI710 unordered_set(initializer_list<value_type> __il,711 size_type __n,712 const hasher& __hf = hasher(),713 const key_equal& __eql = key_equal());714 _LIBCPP_HIDE_FROM_ABI unordered_set(715 initializer_list<value_type> __il,716 size_type __n,717 const hasher& __hf,718 const key_equal& __eql,719 const allocator_type& __a);720# if _LIBCPP_STD_VER >= 14721 inline _LIBCPP_HIDE_FROM_ABI722 unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)723 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}724 inline _LIBCPP_HIDE_FROM_ABI725 unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)726 : unordered_set(__il, __n, __hf, key_equal(), __a) {}727# endif728# endif // _LIBCPP_CXX03_LANG729 _LIBCPP_HIDE_FROM_ABI ~unordered_set() {730 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");731 }732 733 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) = default;734# ifndef _LIBCPP_CXX03_LANG735 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u) = default;736 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);737# endif // _LIBCPP_CXX03_LANG738 739 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {740 return allocator_type(__table_.__node_alloc());741 }742 743 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }744 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }745 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }746 747 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }748 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }749 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }750 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }751 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }752 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }753 754# ifndef _LIBCPP_CXX03_LANG755 template <class... _Args>756 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {757 return __table_.__emplace_unique(std::forward<_Args>(__args)...);758 }759 template <class... _Args>760 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {761 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;762 }763 764 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {765 return __table_.__emplace_unique(std::move(__x));766 }767 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }768 769 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }770# endif // _LIBCPP_CXX03_LANG771 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__emplace_unique(__x); }772 773 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }774 template <class _InputIterator>775 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);776 777# if _LIBCPP_STD_VER >= 23778 template <_ContainerCompatibleRange<value_type> _Range>779 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {780 for (auto&& __element : __range) {781 __table_.__emplace_unique(std::forward<decltype(__element)>(__element));782 }783 }784# endif785 786 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }787 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }788 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {789 return __table_.erase(__first, __last);790 }791 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }792 793# if _LIBCPP_STD_VER >= 17794 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {795 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),796 "node_type with incompatible allocator passed to unordered_set::insert()");797 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));798 }799 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {800 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),801 "node_type with incompatible allocator passed to unordered_set::insert()");802 return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));803 }804 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {805 return __table_.template __node_handle_extract<node_type>(__key);806 }807 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {808 return __table_.template __node_handle_extract<node_type>(__it);809 }810 811 template <class _H2, class _P2>812 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {813 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(814 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");815 __table_.__node_handle_merge_unique(__source.__table_);816 }817 template <class _H2, class _P2>818 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {819 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(820 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");821 __table_.__node_handle_merge_unique(__source.__table_);822 }823 template <class _H2, class _P2>824 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {825 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(826 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");827 __table_.__node_handle_merge_unique(__source.__table_);828 }829 template <class _H2, class _P2>830 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {831 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(832 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");833 __table_.__node_handle_merge_unique(__source.__table_);834 }835# endif836 837 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {838 __table_.swap(__u.__table_);839 }840 841 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }842 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }843 844 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }845 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }846# if _LIBCPP_STD_VER >= 20847 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>848 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {849 return __table_.find(__k);850 }851 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>852 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {853 return __table_.find(__k);854 }855# endif // _LIBCPP_STD_VER >= 20856 857 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }858# if _LIBCPP_STD_VER >= 20859 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>860 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {861 return __table_.__count_unique(__k);862 }863# endif // _LIBCPP_STD_VER >= 20864 865# if _LIBCPP_STD_VER >= 20866 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }867 868 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>869 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {870 return find(__k) != end();871 }872# endif // _LIBCPP_STD_VER >= 20873 874 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {875 return __table_.__equal_range_unique(__k);876 }877 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {878 return __table_.__equal_range_unique(__k);879 }880# if _LIBCPP_STD_VER >= 20881 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>882 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {883 return __table_.__equal_range_unique(__k);884 }885 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>886 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {887 return __table_.__equal_range_unique(__k);888 }889# endif // _LIBCPP_STD_VER >= 20890 891 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }892 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }893 894 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }895 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }896 897 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }898 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }899 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }900 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }901 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }902 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }903 904 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }905 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }906 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }907 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }908 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }909};910 911# if _LIBCPP_STD_VER >= 17912template <class _InputIterator,913 class _Hash = hash<__iterator_value_type<_InputIterator>>,914 class _Pred = equal_to<__iterator_value_type<_InputIterator>>,915 class _Allocator = allocator<__iterator_value_type<_InputIterator>>,916 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,917 class = enable_if_t<!__is_allocator_v<_Hash>>,918 class = enable_if_t<!is_integral<_Hash>::value>,919 class = enable_if_t<!__is_allocator_v<_Pred>>,920 class = enable_if_t<__is_allocator_v<_Allocator>>>921unordered_set(_InputIterator,922 _InputIterator,923 typename allocator_traits<_Allocator>::size_type = 0,924 _Hash = _Hash(),925 _Pred = _Pred(),926 _Allocator = _Allocator())927 -> unordered_set<__iterator_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;928 929# if _LIBCPP_STD_VER >= 23930template <ranges::input_range _Range,931 class _Hash = hash<ranges::range_value_t<_Range>>,932 class _Pred = equal_to<ranges::range_value_t<_Range>>,933 class _Allocator = allocator<ranges::range_value_t<_Range>>,934 class = enable_if_t<!__is_allocator_v<_Hash>>,935 class = enable_if_t<!is_integral<_Hash>::value>,936 class = enable_if_t<!__is_allocator_v<_Pred>>,937 class = enable_if_t<__is_allocator_v<_Allocator>>>938unordered_set(from_range_t,939 _Range&&,940 typename allocator_traits<_Allocator>::size_type = 0,941 _Hash = _Hash(),942 _Pred = _Pred(),943 _Allocator = _Allocator())944 -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23945# endif946 947template <class _Tp,948 class _Hash = hash<_Tp>,949 class _Pred = equal_to<_Tp>,950 class _Allocator = allocator<_Tp>,951 class = enable_if_t<!__is_allocator_v<_Hash>>,952 class = enable_if_t<!is_integral<_Hash>::value>,953 class = enable_if_t<!__is_allocator_v<_Pred>>,954 class = enable_if_t<__is_allocator_v<_Allocator>>>955unordered_set(initializer_list<_Tp>,956 typename allocator_traits<_Allocator>::size_type = 0,957 _Hash = _Hash(),958 _Pred = _Pred(),959 _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;960 961template <class _InputIterator,962 class _Allocator,963 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,964 class = enable_if_t<__is_allocator_v<_Allocator>>>965unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)966 -> unordered_set<__iterator_value_type<_InputIterator>,967 hash<__iterator_value_type<_InputIterator>>,968 equal_to<__iterator_value_type<_InputIterator>>,969 _Allocator>;970 971template <class _InputIterator,972 class _Hash,973 class _Allocator,974 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,975 class = enable_if_t<!__is_allocator_v<_Hash>>,976 class = enable_if_t<!is_integral<_Hash>::value>,977 class = enable_if_t<__is_allocator_v<_Allocator>>>978unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)979 -> unordered_set<__iterator_value_type<_InputIterator>,980 _Hash,981 equal_to<__iterator_value_type<_InputIterator>>,982 _Allocator>;983 984# if _LIBCPP_STD_VER >= 23985 986template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>987unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)988 -> unordered_set<ranges::range_value_t<_Range>,989 hash<ranges::range_value_t<_Range>>,990 equal_to<ranges::range_value_t<_Range>>,991 _Allocator>;992 993template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>994unordered_set(from_range_t, _Range&&, _Allocator)995 -> unordered_set<ranges::range_value_t<_Range>,996 hash<ranges::range_value_t<_Range>>,997 equal_to<ranges::range_value_t<_Range>>,998 _Allocator>;999 1000template <ranges::input_range _Range,1001 class _Hash,1002 class _Allocator,1003 class = enable_if_t<!__is_allocator_v<_Hash>>,1004 class = enable_if_t<!is_integral<_Hash>::value>,1005 class = enable_if_t<__is_allocator_v<_Allocator>>>1006unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1007 -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;1008 1009# endif1010 1011template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1012unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)1013 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;1014 1015template <class _Tp,1016 class _Hash,1017 class _Allocator,1018 class = enable_if_t<!__is_allocator_v<_Hash>>,1019 class = enable_if_t<!is_integral<_Hash>::value>,1020 class = enable_if_t<__is_allocator_v<_Allocator>>>1021unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1022 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;1023# endif1024 1025template <class _Value, class _Hash, class _Pred, class _Alloc>1026unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)1027 : __table_(__hf, __eql) {1028 __table_.__rehash_unique(__n);1029}1030 1031template <class _Value, class _Hash, class _Pred, class _Alloc>1032unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(1033 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)1034 : __table_(__hf, __eql, __a) {1035 __table_.__rehash_unique(__n);1036}1037 1038template <class _Value, class _Hash, class _Pred, class _Alloc>1039template <class _InputIterator>1040unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {1041 insert(__first, __last);1042}1043 1044template <class _Value, class _Hash, class _Pred, class _Alloc>1045template <class _InputIterator>1046unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(1047 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)1048 : __table_(__hf, __eql) {1049 __table_.__rehash_unique(__n);1050 insert(__first, __last);1051}1052 1053template <class _Value, class _Hash, class _Pred, class _Alloc>1054template <class _InputIterator>1055unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(1056 _InputIterator __first,1057 _InputIterator __last,1058 size_type __n,1059 const hasher& __hf,1060 const key_equal& __eql,1061 const allocator_type& __a)1062 : __table_(__hf, __eql, __a) {1063 __table_.__rehash_unique(__n);1064 insert(__first, __last);1065}1066 1067template <class _Value, class _Hash, class _Pred, class _Alloc>1068inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}1069 1070template <class _Value, class _Hash, class _Pred, class _Alloc>1071unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)1072 : __table_(__u.__table_, __a) {1073 __table_.__rehash_unique(__u.bucket_count());1074 insert(__u.begin(), __u.end());1075}1076 1077# ifndef _LIBCPP_CXX03_LANG1078 1079template <class _Value, class _Hash, class _Pred, class _Alloc>1080unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a)1081 : __table_(std::move(__u.__table_), __a) {1082 if (__a != __u.get_allocator()) {1083 iterator __i = __u.begin();1084 while (__u.size() != 0)1085 __table_.__emplace_unique(std::move(__u.__table_.remove(__i++)->__get_value()));1086 }1087}1088 1089template <class _Value, class _Hash, class _Pred, class _Alloc>1090unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) {1091 insert(__il.begin(), __il.end());1092}1093 1094template <class _Value, class _Hash, class _Pred, class _Alloc>1095unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(1096 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)1097 : __table_(__hf, __eql) {1098 __table_.__rehash_unique(__n);1099 insert(__il.begin(), __il.end());1100}1101 1102template <class _Value, class _Hash, class _Pred, class _Alloc>1103unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(1104 initializer_list<value_type> __il,1105 size_type __n,1106 const hasher& __hf,1107 const key_equal& __eql,1108 const allocator_type& __a)1109 : __table_(__hf, __eql, __a) {1110 __table_.__rehash_unique(__n);1111 insert(__il.begin(), __il.end());1112}1113 1114template <class _Value, class _Hash, class _Pred, class _Alloc>1115inline unordered_set<_Value, _Hash, _Pred, _Alloc>&1116unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {1117 __table_.__assign_unique(__il.begin(), __il.end());1118 return *this;1119}1120 1121# endif // _LIBCPP_CXX03_LANG1122 1123template <class _Value, class _Hash, class _Pred, class _Alloc>1124template <class _InputIterator>1125inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {1126 for (; __first != __last; ++__first)1127 __table_.__emplace_unique(*__first);1128}1129 1130template <class _Value, class _Hash, class _Pred, class _Alloc>1131inline _LIBCPP_HIDE_FROM_ABI void1132swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)1133 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {1134 __x.swap(__y);1135}1136 1137# if _LIBCPP_STD_VER >= 201138template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>1139inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type1140erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {1141 return std::__libcpp_erase_if_container(__c, __pred);1142}1143# endif1144 1145template <class _Value, class _Hash, class _Pred, class _Alloc>1146_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,1147 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {1148 if (__x.size() != __y.size())1149 return false;1150 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;1151 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {1152 const_iterator __j = __y.find(*__i);1153 if (__j == __ey || !(*__i == *__j))1154 return false;1155 }1156 return true;1157}1158 1159# if _LIBCPP_STD_VER <= 171160 1161template <class _Value, class _Hash, class _Pred, class _Alloc>1162inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,1163 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {1164 return !(__x == __y);1165}1166 1167# endif1168 1169template <class _Value, class _Hash, class _Pred, class _Alloc>1170struct __container_traits<unordered_set<_Value, _Hash, _Pred, _Alloc> > {1171 // http://eel.is/c++draft/unord.req.except#21172 // For unordered associative containers, if an exception is thrown by any operation1173 // other than the container's hash function from within an insert or emplace function1174 // inserting a single element, the insertion has no effect.1175 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =1176 __is_nothrow_invocable_v<_Hash, const _Value&>;1177 1178 static _LIBCPP_CONSTEXPR const bool __reservable = true;1179};1180 1181template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >1182class unordered_multiset {1183public:1184 // types1185 typedef _Value key_type;1186 typedef key_type value_type;1187 typedef __type_identity_t<_Hash> hasher;1188 typedef __type_identity_t<_Pred> key_equal;1189 typedef __type_identity_t<_Alloc> allocator_type;1190 typedef value_type& reference;1191 typedef const value_type& const_reference;1192 static_assert(is_same<value_type, typename allocator_type::value_type>::value,1193 "Allocator::value_type must be same type as value_type");1194 1195private:1196 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;1197 1198 __table __table_;1199 1200public:1201 typedef typename __table::pointer pointer;1202 typedef typename __table::const_pointer const_pointer;1203 typedef typename __table::size_type size_type;1204 typedef typename __table::difference_type difference_type;1205 1206 typedef typename __table::const_iterator iterator;1207 typedef typename __table::const_iterator const_iterator;1208 typedef typename __table::const_local_iterator local_iterator;1209 typedef typename __table::const_local_iterator const_local_iterator;1210 1211# if _LIBCPP_STD_VER >= 171212 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;1213# endif1214 1215 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>1216 friend class unordered_set;1217 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>1218 friend class unordered_multiset;1219 1220 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}1221 explicit _LIBCPP_HIDE_FROM_ABI1222 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());1223 _LIBCPP_HIDE_FROM_ABI1224 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);1225# if _LIBCPP_STD_VER >= 141226 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a)1227 : unordered_multiset(__n, hasher(), key_equal(), __a) {}1228 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)1229 : unordered_multiset(__n, __hf, key_equal(), __a) {}1230# endif1231 template <class _InputIterator>1232 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);1233 template <class _InputIterator>1234 _LIBCPP_HIDE_FROM_ABI unordered_multiset(1235 _InputIterator __first,1236 _InputIterator __last,1237 size_type __n,1238 const hasher& __hf = hasher(),1239 const key_equal& __eql = key_equal());1240 template <class _InputIterator>1241 _LIBCPP_HIDE_FROM_ABI unordered_multiset(1242 _InputIterator __first,1243 _InputIterator __last,1244 size_type __n,1245 const hasher& __hf,1246 const key_equal& __eql,1247 const allocator_type& __a);1248 1249# if _LIBCPP_STD_VER >= 231250 template <_ContainerCompatibleRange<value_type> _Range>1251 _LIBCPP_HIDE_FROM_ABI unordered_multiset(1252 from_range_t,1253 _Range&& __range,1254 size_type __n = /*implementation-defined*/ 0,1255 const hasher& __hf = hasher(),1256 const key_equal& __eql = key_equal(),1257 const allocator_type& __a = allocator_type())1258 : __table_(__hf, __eql, __a) {1259 if (__n > 0) {1260 __table_.__rehash_multi(__n);1261 }1262 insert_range(std::forward<_Range>(__range));1263 }1264# endif1265 1266# if _LIBCPP_STD_VER >= 141267 template <class _InputIterator>1268 inline _LIBCPP_HIDE_FROM_ABI1269 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)1270 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}1271 template <class _InputIterator>1272 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(1273 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)1274 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}1275# endif1276 1277# if _LIBCPP_STD_VER >= 231278 template <_ContainerCompatibleRange<value_type> _Range>1279 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)1280 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}1281 1282 template <_ContainerCompatibleRange<value_type> _Range>1283 _LIBCPP_HIDE_FROM_ABI1284 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)1285 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}1286# endif1287 1288 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);1289 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u) = default;1290 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);1291# ifndef _LIBCPP_CXX03_LANG1292 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u) = default;1293 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);1294 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il);1295 _LIBCPP_HIDE_FROM_ABI unordered_multiset(1296 initializer_list<value_type> __il,1297 size_type __n,1298 const hasher& __hf = hasher(),1299 const key_equal& __eql = key_equal());1300 _LIBCPP_HIDE_FROM_ABI unordered_multiset(1301 initializer_list<value_type> __il,1302 size_type __n,1303 const hasher& __hf,1304 const key_equal& __eql,1305 const allocator_type& __a);1306# if _LIBCPP_STD_VER >= 141307 inline _LIBCPP_HIDE_FROM_ABI1308 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)1309 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}1310 inline _LIBCPP_HIDE_FROM_ABI1311 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)1312 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}1313# endif1314# endif // _LIBCPP_CXX03_LANG1315 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {1316 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");1317 }1318 1319 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) = default;1320# ifndef _LIBCPP_CXX03_LANG1321 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u) = default;1322 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il);1323# endif // _LIBCPP_CXX03_LANG1324 1325 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {1326 return allocator_type(__table_.__node_alloc());1327 }1328 1329 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }1330 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }1331 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }1332 1333 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }1334 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }1335 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }1336 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }1337 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }1338 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }1339 1340# ifndef _LIBCPP_CXX03_LANG1341 template <class... _Args>1342 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {1343 return __table_.__emplace_multi(std::forward<_Args>(__args)...);1344 }1345 template <class... _Args>1346 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {1347 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);1348 }1349 1350 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__emplace_multi(std::move(__x)); }1351 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {1352 return __table_.__emplace_hint_multi(__p, std::move(__x));1353 }1354 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }1355# endif // _LIBCPP_CXX03_LANG1356 1357 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); }1358 1359 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {1360 return __table_.__emplace_hint_multi(__p, __x);1361 }1362 1363 template <class _InputIterator>1364 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);1365 1366# if _LIBCPP_STD_VER >= 231367 template <_ContainerCompatibleRange<value_type> _Range>1368 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {1369 for (auto&& __element : __range) {1370 __table_.__emplace_multi(std::forward<decltype(__element)>(__element));1371 }1372 }1373# endif1374 1375# if _LIBCPP_STD_VER >= 171376 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {1377 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1378 "node_type with incompatible allocator passed to unordered_multiset::insert()");1379 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));1380 }1381 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {1382 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1383 "node_type with incompatible allocator passed to unordered_multiset::insert()");1384 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));1385 }1386 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) {1387 return __table_.template __node_handle_extract<node_type>(__position);1388 }1389 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {1390 return __table_.template __node_handle_extract<node_type>(__key);1391 }1392 1393 template <class _H2, class _P2>1394 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {1395 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1396 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1397 return __table_.__node_handle_merge_multi(__source.__table_);1398 }1399 template <class _H2, class _P2>1400 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {1401 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1402 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1403 return __table_.__node_handle_merge_multi(__source.__table_);1404 }1405 template <class _H2, class _P2>1406 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {1407 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1408 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1409 return __table_.__node_handle_merge_multi(__source.__table_);1410 }1411 template <class _H2, class _P2>1412 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {1413 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1414 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1415 return __table_.__node_handle_merge_multi(__source.__table_);1416 }1417# endif1418 1419 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }1420 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }1421 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {1422 return __table_.erase(__first, __last);1423 }1424 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }1425 1426 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {1427 __table_.swap(__u.__table_);1428 }1429 1430 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }1431 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }1432 1433 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }1434 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }1435# if _LIBCPP_STD_VER >= 201436 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1437 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {1438 return __table_.find(__k);1439 }1440 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1441 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {1442 return __table_.find(__k);1443 }1444# endif // _LIBCPP_STD_VER >= 201445 1446 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }1447# if _LIBCPP_STD_VER >= 201448 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1449 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {1450 return __table_.__count_multi(__k);1451 }1452# endif // _LIBCPP_STD_VER >= 201453 1454# if _LIBCPP_STD_VER >= 201455 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }1456 1457 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1458 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {1459 return find(__k) != end();1460 }1461# endif // _LIBCPP_STD_VER >= 201462 1463 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1464 return __table_.__equal_range_multi(__k);1465 }1466 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1467 return __table_.__equal_range_multi(__k);1468 }1469# if _LIBCPP_STD_VER >= 201470 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1471 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {1472 return __table_.__equal_range_multi(__k);1473 }1474 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1475 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {1476 return __table_.__equal_range_multi(__k);1477 }1478# endif // _LIBCPP_STD_VER >= 201479 1480 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }1481 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }1482 1483 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }1484 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }1485 1486 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }1487 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }1488 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }1489 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }1490 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }1491 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }1492 1493 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }1494 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }1495 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }1496 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }1497 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }1498};1499 1500# if _LIBCPP_STD_VER >= 171501template <class _InputIterator,1502 class _Hash = hash<__iterator_value_type<_InputIterator>>,1503 class _Pred = equal_to<__iterator_value_type<_InputIterator>>,1504 class _Allocator = allocator<__iterator_value_type<_InputIterator>>,1505 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1506 class = enable_if_t<!__is_allocator_v<_Hash>>,1507 class = enable_if_t<!is_integral<_Hash>::value>,1508 class = enable_if_t<!__is_allocator_v<_Pred>>,1509 class = enable_if_t<__is_allocator_v<_Allocator>>>1510unordered_multiset(1511 _InputIterator,1512 _InputIterator,1513 typename allocator_traits<_Allocator>::size_type = 0,1514 _Hash = _Hash(),1515 _Pred = _Pred(),1516 _Allocator = _Allocator()) -> unordered_multiset<__iterator_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;1517 1518# if _LIBCPP_STD_VER >= 231519template <ranges::input_range _Range,1520 class _Hash = hash<ranges::range_value_t<_Range>>,1521 class _Pred = equal_to<ranges::range_value_t<_Range>>,1522 class _Allocator = allocator<ranges::range_value_t<_Range>>,1523 class = enable_if_t<!__is_allocator_v<_Hash>>,1524 class = enable_if_t<!is_integral<_Hash>::value>,1525 class = enable_if_t<!__is_allocator_v<_Pred>>,1526 class = enable_if_t<__is_allocator_v<_Allocator>>>1527unordered_multiset(1528 from_range_t,1529 _Range&&,1530 typename allocator_traits<_Allocator>::size_type = 0,1531 _Hash = _Hash(),1532 _Pred = _Pred(),1533 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++231534# endif1535 1536template <class _Tp,1537 class _Hash = hash<_Tp>,1538 class _Pred = equal_to<_Tp>,1539 class _Allocator = allocator<_Tp>,1540 class = enable_if_t<!__is_allocator_v<_Hash>>,1541 class = enable_if_t<!is_integral<_Hash>::value>,1542 class = enable_if_t<!__is_allocator_v<_Pred>>,1543 class = enable_if_t<__is_allocator_v<_Allocator>>>1544unordered_multiset(initializer_list<_Tp>,1545 typename allocator_traits<_Allocator>::size_type = 0,1546 _Hash = _Hash(),1547 _Pred = _Pred(),1548 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;1549 1550template <class _InputIterator,1551 class _Allocator,1552 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1553 class = enable_if_t<__is_allocator_v<_Allocator>>>1554unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)1555 -> unordered_multiset<__iterator_value_type<_InputIterator>,1556 hash<__iterator_value_type<_InputIterator>>,1557 equal_to<__iterator_value_type<_InputIterator>>,1558 _Allocator>;1559 1560template <class _InputIterator,1561 class _Hash,1562 class _Allocator,1563 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1564 class = enable_if_t<!__is_allocator_v<_Hash>>,1565 class = enable_if_t<!is_integral<_Hash>::value>,1566 class = enable_if_t<__is_allocator_v<_Allocator>>>1567unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1568 -> unordered_multiset<__iterator_value_type<_InputIterator>,1569 _Hash,1570 equal_to<__iterator_value_type<_InputIterator>>,1571 _Allocator>;1572 1573# if _LIBCPP_STD_VER >= 231574 1575template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1576unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)1577 -> unordered_multiset<ranges::range_value_t<_Range>,1578 hash<ranges::range_value_t<_Range>>,1579 equal_to<ranges::range_value_t<_Range>>,1580 _Allocator>;1581 1582template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1583unordered_multiset(from_range_t, _Range&&, _Allocator)1584 -> unordered_multiset<ranges::range_value_t<_Range>,1585 hash<ranges::range_value_t<_Range>>,1586 equal_to<ranges::range_value_t<_Range>>,1587 _Allocator>;1588 1589template <ranges::input_range _Range,1590 class _Hash,1591 class _Allocator,1592 class = enable_if_t<!__is_allocator_v<_Hash>>,1593 class = enable_if_t<!is_integral<_Hash>::value>,1594 class = enable_if_t<__is_allocator_v<_Allocator>>>1595unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1596 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;1597 1598# endif1599 1600template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1601unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)1602 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;1603 1604template <class _Tp,1605 class _Hash,1606 class _Allocator,1607 class = enable_if_t<!__is_allocator_v<_Hash>>,1608 class = enable_if_t<!is_integral<_Hash>::value>,1609 class = enable_if_t<__is_allocator_v<_Allocator>>>1610unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1611 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;1612# endif1613 1614template <class _Value, class _Hash, class _Pred, class _Alloc>1615unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1616 size_type __n, const hasher& __hf, const key_equal& __eql)1617 : __table_(__hf, __eql) {1618 __table_.__rehash_multi(__n);1619}1620 1621template <class _Value, class _Hash, class _Pred, class _Alloc>1622unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1623 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)1624 : __table_(__hf, __eql, __a) {1625 __table_.__rehash_multi(__n);1626}1627 1628template <class _Value, class _Hash, class _Pred, class _Alloc>1629template <class _InputIterator>1630unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {1631 insert(__first, __last);1632}1633 1634template <class _Value, class _Hash, class _Pred, class _Alloc>1635template <class _InputIterator>1636unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1637 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)1638 : __table_(__hf, __eql) {1639 __table_.__rehash_multi(__n);1640 insert(__first, __last);1641}1642 1643template <class _Value, class _Hash, class _Pred, class _Alloc>1644template <class _InputIterator>1645unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1646 _InputIterator __first,1647 _InputIterator __last,1648 size_type __n,1649 const hasher& __hf,1650 const key_equal& __eql,1651 const allocator_type& __a)1652 : __table_(__hf, __eql, __a) {1653 __table_.__rehash_multi(__n);1654 insert(__first, __last);1655}1656 1657template <class _Value, class _Hash, class _Pred, class _Alloc>1658inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)1659 : __table_(__a) {}1660 1661template <class _Value, class _Hash, class _Pred, class _Alloc>1662unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1663 const unordered_multiset& __u, const allocator_type& __a)1664 : __table_(__u.__table_, __a) {1665 __table_.__rehash_multi(__u.bucket_count());1666 insert(__u.begin(), __u.end());1667}1668 1669# ifndef _LIBCPP_CXX03_LANG1670 1671template <class _Value, class _Hash, class _Pred, class _Alloc>1672unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1673 unordered_multiset&& __u, const allocator_type& __a)1674 : __table_(std::move(__u.__table_), __a) {1675 if (__a != __u.get_allocator()) {1676 iterator __i = __u.begin();1677 while (__u.size() != 0)1678 __table_.__emplace_multi(std::move(__u.__table_.remove(__i++)->__get_value()));1679 }1680}1681 1682template <class _Value, class _Hash, class _Pred, class _Alloc>1683unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) {1684 insert(__il.begin(), __il.end());1685}1686 1687template <class _Value, class _Hash, class _Pred, class _Alloc>1688unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1689 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)1690 : __table_(__hf, __eql) {1691 __table_.__rehash_multi(__n);1692 insert(__il.begin(), __il.end());1693}1694 1695template <class _Value, class _Hash, class _Pred, class _Alloc>1696unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(1697 initializer_list<value_type> __il,1698 size_type __n,1699 const hasher& __hf,1700 const key_equal& __eql,1701 const allocator_type& __a)1702 : __table_(__hf, __eql, __a) {1703 __table_.__rehash_multi(__n);1704 insert(__il.begin(), __il.end());1705}1706 1707template <class _Value, class _Hash, class _Pred, class _Alloc>1708inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&1709unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {1710 __table_.__assign_multi(__il.begin(), __il.end());1711 return *this;1712}1713 1714# endif // _LIBCPP_CXX03_LANG1715 1716template <class _Value, class _Hash, class _Pred, class _Alloc>1717template <class _InputIterator>1718inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {1719 for (; __first != __last; ++__first)1720 __table_.__emplace_multi(*__first);1721}1722 1723template <class _Value, class _Hash, class _Pred, class _Alloc>1724inline _LIBCPP_HIDE_FROM_ABI void1725swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)1726 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {1727 __x.swap(__y);1728}1729 1730# if _LIBCPP_STD_VER >= 201731template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>1732inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type1733erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {1734 return std::__libcpp_erase_if_container(__c, __pred);1735}1736# endif1737 1738template <class _Value, class _Hash, class _Pred, class _Alloc>1739_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,1740 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {1741 if (__x.size() != __y.size())1742 return false;1743 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;1744 typedef pair<const_iterator, const_iterator> _EqRng;1745 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {1746 _EqRng __xeq = __x.equal_range(*__i);1747 _EqRng __yeq = __y.equal_range(*__i);1748 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||1749 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))1750 return false;1751 __i = __xeq.second;1752 }1753 return true;1754}1755 1756# if _LIBCPP_STD_VER <= 171757 1758template <class _Value, class _Hash, class _Pred, class _Alloc>1759inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,1760 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {1761 return !(__x == __y);1762}1763 1764# endif1765 1766template <class _Value, class _Hash, class _Pred, class _Alloc>1767struct __container_traits<unordered_multiset<_Value, _Hash, _Pred, _Alloc> > {1768 // http://eel.is/c++draft/unord.req.except#21769 // For unordered associative containers, if an exception is thrown by any operation1770 // other than the container's hash function from within an insert or emplace function1771 // inserting a single element, the insertion has no effect.1772 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =1773 __is_nothrow_invocable_v<_Hash, const _Value&>;1774 1775 static _LIBCPP_CONSTEXPR const bool __reservable = true;1776};1777 1778_LIBCPP_END_NAMESPACE_STD1779 1780# if _LIBCPP_STD_VER >= 171781_LIBCPP_BEGIN_NAMESPACE_STD1782namespace pmr {1783template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>1784using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;1785 1786template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>1787using unordered_multiset _LIBCPP_AVAILABILITY_PMR =1788 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;1789} // namespace pmr1790_LIBCPP_END_NAMESPACE_STD1791# endif1792 1793_LIBCPP_POP_MACROS1794 1795# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 201796# include <cmath>1797# include <concepts>1798# include <cstdlib>1799# include <functional>1800# include <iterator>1801# include <stdexcept>1802# include <type_traits>1803# endif1804#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)1805 1806#endif // _LIBCPP_UNORDERED_SET1807