Warning, /include/c++/v1/unordered_set is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP_UNORDERED_SET
0011 #define _LIBCPP_UNORDERED_SET
0012
0013 // clang-format off
0014
0015 /*
0016
0017 unordered_set synopsis
0018
0019 #include <initializer_list>
0020
0021 namespace std
0022 {
0023
0024 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
0025 class Alloc = allocator<Value>>
0026 class unordered_set
0027 {
0028 public:
0029 // types
0030 typedef Value key_type;
0031 typedef key_type value_type;
0032 typedef Hash hasher;
0033 typedef Pred key_equal;
0034 typedef Alloc allocator_type;
0035 typedef value_type& reference;
0036 typedef const value_type& const_reference;
0037 typedef typename allocator_traits<allocator_type>::pointer pointer;
0038 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0039 typedef typename allocator_traits<allocator_type>::size_type size_type;
0040 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0041
0042 typedef /unspecified/ iterator;
0043 typedef /unspecified/ const_iterator;
0044 typedef /unspecified/ local_iterator;
0045 typedef /unspecified/ const_local_iterator;
0046
0047 typedef unspecified node_type unspecified; // C++17
0048 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
0049
0050 unordered_set()
0051 noexcept(
0052 is_nothrow_default_constructible<hasher>::value &&
0053 is_nothrow_default_constructible<key_equal>::value &&
0054 is_nothrow_default_constructible<allocator_type>::value);
0055 explicit unordered_set(size_type n, const hasher& hf = hasher(),
0056 const key_equal& eql = key_equal(),
0057 const allocator_type& a = allocator_type());
0058 template <class InputIterator>
0059 unordered_set(InputIterator f, InputIterator l,
0060 size_type n = 0, const hasher& hf = hasher(),
0061 const key_equal& eql = key_equal(),
0062 const allocator_type& a = allocator_type());
0063 template<container-compatible-range<value_type> R>
0064 unordered_set(from_range_t, R&& rg, size_type n = see below,
0065 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
0066 const allocator_type& a = allocator_type()); // C++23
0067 explicit unordered_set(const allocator_type&);
0068 unordered_set(const unordered_set&);
0069 unordered_set(const unordered_set&, const Allocator&);
0070 unordered_set(unordered_set&&)
0071 noexcept(
0072 is_nothrow_move_constructible<hasher>::value &&
0073 is_nothrow_move_constructible<key_equal>::value &&
0074 is_nothrow_move_constructible<allocator_type>::value);
0075 unordered_set(unordered_set&&, const Allocator&);
0076 unordered_set(initializer_list<value_type>, size_type n = 0,
0077 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
0078 const allocator_type& a = allocator_type());
0079 unordered_set(size_type n, const allocator_type& a); // C++14
0080 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
0081 template <class InputIterator>
0082 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
0083 template <class InputIterator>
0084 unordered_set(InputIterator f, InputIterator l, size_type n,
0085 const hasher& hf, const allocator_type& a); // C++14
0086 template<container-compatible-range<value_type> R>
0087 unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
0088 : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
0089 template<container-compatible-range<value_type> R>
0090 unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
0091 : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
0092 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
0093 unordered_set(initializer_list<value_type> il, size_type n,
0094 const hasher& hf, const allocator_type& a); // C++14
0095 ~unordered_set();
0096 unordered_set& operator=(const unordered_set&);
0097 unordered_set& operator=(unordered_set&&)
0098 noexcept(
0099 allocator_type::propagate_on_container_move_assignment::value &&
0100 is_nothrow_move_assignable<allocator_type>::value &&
0101 is_nothrow_move_assignable<hasher>::value &&
0102 is_nothrow_move_assignable<key_equal>::value);
0103 unordered_set& operator=(initializer_list<value_type>);
0104
0105 allocator_type get_allocator() const noexcept;
0106
0107 bool empty() const noexcept;
0108 size_type size() const noexcept;
0109 size_type max_size() const noexcept;
0110
0111 iterator begin() noexcept;
0112 iterator end() noexcept;
0113 const_iterator begin() const noexcept;
0114 const_iterator end() const noexcept;
0115 const_iterator cbegin() const noexcept;
0116 const_iterator cend() const noexcept;
0117
0118 template <class... Args>
0119 pair<iterator, bool> emplace(Args&&... args);
0120 template <class... Args>
0121 iterator emplace_hint(const_iterator position, Args&&... args);
0122 pair<iterator, bool> insert(const value_type& obj);
0123 pair<iterator, bool> insert(value_type&& obj);
0124 iterator insert(const_iterator hint, const value_type& obj);
0125 iterator insert(const_iterator hint, value_type&& obj);
0126 template <class InputIterator>
0127 void insert(InputIterator first, InputIterator last);
0128 template<container-compatible-range<value_type> R>
0129 void insert_range(R&& rg); // C++23
0130 void insert(initializer_list<value_type>);
0131
0132 node_type extract(const_iterator position); // C++17
0133 node_type extract(const key_type& x); // C++17
0134 insert_return_type insert(node_type&& nh); // C++17
0135 iterator insert(const_iterator hint, node_type&& nh); // C++17
0136
0137 iterator erase(const_iterator position);
0138 iterator erase(iterator position); // C++14
0139 size_type erase(const key_type& k);
0140 iterator erase(const_iterator first, const_iterator last);
0141 void clear() noexcept;
0142
0143 template<class H2, class P2>
0144 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
0145 template<class H2, class P2>
0146 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
0147 template<class H2, class P2>
0148 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
0149 template<class H2, class P2>
0150 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
0151
0152 void swap(unordered_set&)
0153 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
0154 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
0155 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
0156
0157 hasher hash_function() const;
0158 key_equal key_eq() const;
0159
0160 iterator find(const key_type& k);
0161 const_iterator find(const key_type& k) const;
0162 template<typename K>
0163 iterator find(const K& x); // C++20
0164 template<typename K>
0165 const_iterator find(const K& x) const; // C++20
0166 size_type count(const key_type& k) const;
0167 template<typename K>
0168 size_type count(const K& k) const; // C++20
0169 bool contains(const key_type& k) const; // C++20
0170 template<typename K>
0171 bool contains(const K& k) const; // C++20
0172 pair<iterator, iterator> equal_range(const key_type& k);
0173 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
0174 template<typename K>
0175 pair<iterator, iterator> equal_range(const K& k); // C++20
0176 template<typename K>
0177 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
0178
0179 size_type bucket_count() const noexcept;
0180 size_type max_bucket_count() const noexcept;
0181
0182 size_type bucket_size(size_type n) const;
0183 size_type bucket(const key_type& k) const;
0184
0185 local_iterator begin(size_type n);
0186 local_iterator end(size_type n);
0187 const_local_iterator begin(size_type n) const;
0188 const_local_iterator end(size_type n) const;
0189 const_local_iterator cbegin(size_type n) const;
0190 const_local_iterator cend(size_type n) const;
0191
0192 float load_factor() const noexcept;
0193 float max_load_factor() const noexcept;
0194 void max_load_factor(float z);
0195 void rehash(size_type n);
0196 void reserve(size_type n);
0197 };
0198
0199 template<class InputIterator,
0200 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
0201 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
0202 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0203 unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
0204 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0205 -> unordered_set<typename iterator_traits<InputIterator>::value_type,
0206 Hash, Pred, Allocator>; // C++17
0207
0208 template<ranges::input_range R,
0209 class Hash = hash<ranges::range_value_t<R>>,
0210 class Pred = equal_to<ranges::range_value_t<R>>,
0211 class Allocator = allocator<ranges::range_value_t<R>>>
0212 unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0213 -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
0214
0215 template<class T, class Hash = hash<T>,
0216 class Pred = equal_to<T>, class Allocator = allocator<T>>
0217 unordered_set(initializer_list<T>, typename see below::size_type = see below,
0218 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0219 -> unordered_set<T, Hash, Pred, Allocator>; // C++17
0220
0221 template<class InputIterator, class Allocator>
0222 unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
0223 -> unordered_set<typename iterator_traits<InputIterator>::value_type,
0224 hash<typename iterator_traits<InputIterator>::value_type>,
0225 equal_to<typename iterator_traits<InputIterator>::value_type>,
0226 Allocator>; // C++17
0227
0228 template<class InputIterator, class Hash, class Allocator>
0229 unordered_set(InputIterator, InputIterator, typename see below::size_type,
0230 Hash, Allocator)
0231 -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
0232 equal_to<typename iterator_traits<InputIterator>::value_type>,
0233 Allocator>; // C++17
0234
0235 template<ranges::input_range R, class Allocator>
0236 unordered_set(from_range_t, R&&, typename see below::size_type, Allocator)
0237 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
0238 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
0239
0240 template<ranges::input_range R, class Allocator>
0241 unordered_set(from_range_t, R&&, Allocator)
0242 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
0243 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
0244
0245 template<ranges::input_range R, class Hash, class Allocator>
0246 unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
0247 -> unordered_set<ranges::range_value_t<R>, Hash,
0248 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
0249
0250 template<class T, class Allocator>
0251 unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
0252 -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17
0253
0254 template<class T, class Hash, class Allocator>
0255 unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
0256 -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17
0257
0258 template <class Value, class Hash, class Pred, class Alloc>
0259 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
0260 unordered_set<Value, Hash, Pred, Alloc>& y)
0261 noexcept(noexcept(x.swap(y)));
0262
0263 template <class Value, class Hash, class Pred, class Alloc>
0264 bool
0265 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
0266 const unordered_set<Value, Hash, Pred, Alloc>& y);
0267
0268 template <class Value, class Hash, class Pred, class Alloc>
0269 bool
0270 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
0271 const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20
0272
0273 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
0274 class Alloc = allocator<Value>>
0275 class unordered_multiset
0276 {
0277 public:
0278 // types
0279 typedef Value key_type;
0280 typedef key_type value_type;
0281 typedef Hash hasher;
0282 typedef Pred key_equal;
0283 typedef Alloc allocator_type;
0284 typedef value_type& reference;
0285 typedef const value_type& const_reference;
0286 typedef typename allocator_traits<allocator_type>::pointer pointer;
0287 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0288 typedef typename allocator_traits<allocator_type>::size_type size_type;
0289 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0290
0291 typedef /unspecified/ iterator;
0292 typedef /unspecified/ const_iterator;
0293 typedef /unspecified/ local_iterator;
0294 typedef /unspecified/ const_local_iterator;
0295
0296 typedef unspecified node_type unspecified; // C++17
0297
0298 unordered_multiset()
0299 noexcept(
0300 is_nothrow_default_constructible<hasher>::value &&
0301 is_nothrow_default_constructible<key_equal>::value &&
0302 is_nothrow_default_constructible<allocator_type>::value);
0303 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
0304 const key_equal& eql = key_equal(),
0305 const allocator_type& a = allocator_type());
0306 template <class InputIterator>
0307 unordered_multiset(InputIterator f, InputIterator l,
0308 size_type n = 0, const hasher& hf = hasher(),
0309 const key_equal& eql = key_equal(),
0310 const allocator_type& a = allocator_type());
0311 template<container-compatible-range<value_type> R>
0312 unordered_multiset(from_range_t, R&& rg, size_type n = see below,
0313 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
0314 const allocator_type& a = allocator_type()); // C++23
0315 explicit unordered_multiset(const allocator_type&);
0316 unordered_multiset(const unordered_multiset&);
0317 unordered_multiset(const unordered_multiset&, const Allocator&);
0318 unordered_multiset(unordered_multiset&&)
0319 noexcept(
0320 is_nothrow_move_constructible<hasher>::value &&
0321 is_nothrow_move_constructible<key_equal>::value &&
0322 is_nothrow_move_constructible<allocator_type>::value);
0323 unordered_multiset(unordered_multiset&&, const Allocator&);
0324 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
0325 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
0326 const allocator_type& a = allocator_type());
0327 unordered_multiset(size_type n, const allocator_type& a); // C++14
0328 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
0329 template <class InputIterator>
0330 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
0331 template <class InputIterator>
0332 unordered_multiset(InputIterator f, InputIterator l, size_type n,
0333 const hasher& hf, const allocator_type& a); // C++14
0334 template<container-compatible-range<value_type> R>
0335 unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
0336 : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
0337 template<container-compatible-range<value_type> R>
0338 unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
0339 : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
0340 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
0341 unordered_multiset(initializer_list<value_type> il, size_type n,
0342 const hasher& hf, const allocator_type& a); // C++14
0343 ~unordered_multiset();
0344 unordered_multiset& operator=(const unordered_multiset&);
0345 unordered_multiset& operator=(unordered_multiset&&)
0346 noexcept(
0347 allocator_type::propagate_on_container_move_assignment::value &&
0348 is_nothrow_move_assignable<allocator_type>::value &&
0349 is_nothrow_move_assignable<hasher>::value &&
0350 is_nothrow_move_assignable<key_equal>::value);
0351 unordered_multiset& operator=(initializer_list<value_type>);
0352
0353 allocator_type get_allocator() const noexcept;
0354
0355 bool empty() const noexcept;
0356 size_type size() const noexcept;
0357 size_type max_size() const noexcept;
0358
0359 iterator begin() noexcept;
0360 iterator end() noexcept;
0361 const_iterator begin() const noexcept;
0362 const_iterator end() const noexcept;
0363 const_iterator cbegin() const noexcept;
0364 const_iterator cend() const noexcept;
0365
0366 template <class... Args>
0367 iterator emplace(Args&&... args);
0368 template <class... Args>
0369 iterator emplace_hint(const_iterator position, Args&&... args);
0370 iterator insert(const value_type& obj);
0371 iterator insert(value_type&& obj);
0372 iterator insert(const_iterator hint, const value_type& obj);
0373 iterator insert(const_iterator hint, value_type&& obj);
0374 template <class InputIterator>
0375 void insert(InputIterator first, InputIterator last);
0376 template<container-compatible-range<value_type> R>
0377 void insert_range(R&& rg); // C++23
0378 void insert(initializer_list<value_type>);
0379
0380 node_type extract(const_iterator position); // C++17
0381 node_type extract(const key_type& x); // C++17
0382 iterator insert(node_type&& nh); // C++17
0383 iterator insert(const_iterator hint, node_type&& nh); // C++17
0384
0385 iterator erase(const_iterator position);
0386 iterator erase(iterator position); // C++14
0387 size_type erase(const key_type& k);
0388 iterator erase(const_iterator first, const_iterator last);
0389 void clear() noexcept;
0390
0391 template<class H2, class P2>
0392 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
0393 template<class H2, class P2>
0394 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
0395 template<class H2, class P2>
0396 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
0397 template<class H2, class P2>
0398 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
0399
0400 void swap(unordered_multiset&)
0401 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
0402 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
0403 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
0404
0405 hasher hash_function() const;
0406 key_equal key_eq() const;
0407
0408 iterator find(const key_type& k);
0409 const_iterator find(const key_type& k) const;
0410 template<typename K>
0411 iterator find(const K& x); // C++20
0412 template<typename K>
0413 const_iterator find(const K& x) const; // C++20
0414 size_type count(const key_type& k) const;
0415 template<typename K>
0416 size_type count(const K& k) const; // C++20
0417 bool contains(const key_type& k) const; // C++20
0418 template<typename K>
0419 bool contains(const K& k) const; // C++20
0420 pair<iterator, iterator> equal_range(const key_type& k);
0421 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
0422 template<typename K>
0423 pair<iterator, iterator> equal_range(const K& k); // C++20
0424 template<typename K>
0425 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
0426
0427 size_type bucket_count() const noexcept;
0428 size_type max_bucket_count() const noexcept;
0429
0430 size_type bucket_size(size_type n) const;
0431 size_type bucket(const key_type& k) const;
0432
0433 local_iterator begin(size_type n);
0434 local_iterator end(size_type n);
0435 const_local_iterator begin(size_type n) const;
0436 const_local_iterator end(size_type n) const;
0437 const_local_iterator cbegin(size_type n) const;
0438 const_local_iterator cend(size_type n) const;
0439
0440 float load_factor() const noexcept;
0441 float max_load_factor() const noexcept;
0442 void max_load_factor(float z);
0443 void rehash(size_type n);
0444 void reserve(size_type n);
0445 };
0446
0447 template<class InputIterator,
0448 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
0449 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
0450 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0451 unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
0452 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0453 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
0454 Hash, Pred, Allocator>; // C++17
0455
0456 template<ranges::input_range R,
0457 class Hash = hash<ranges::range_value_t<R>>,
0458 class Pred = equal_to<ranges::range_value_t<R>>,
0459 class Allocator = allocator<ranges::range_value_t<R>>>
0460 unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0461 -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
0462
0463 template<class T, class Hash = hash<T>,
0464 class Pred = equal_to<T>, class Allocator = allocator<T>>
0465 unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
0466 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0467 -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17
0468
0469 template<class InputIterator, class Allocator>
0470 unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
0471 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
0472 hash<typename iterator_traits<InputIterator>::value_type>,
0473 equal_to<typename iterator_traits<InputIterator>::value_type>,
0474 Allocator>; // C++17
0475
0476 template<class InputIterator, class Hash, class Allocator>
0477 unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
0478 Hash, Allocator)
0479 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
0480 equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
0481
0482 template<ranges::input_range R, class Allocator>
0483 unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator)
0484 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
0485 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
0486
0487 template<ranges::input_range R, class Allocator>
0488 unordered_multiset(from_range_t, R&&, Allocator)
0489 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
0490 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
0491
0492 template<ranges::input_range R, class Hash, class Allocator>
0493 unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
0494 -> unordered_multiset<ranges::range_value_t<R>, Hash,
0495 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
0496
0497 template<class T, class Allocator>
0498 unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
0499 -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17
0500
0501 template<class T, class Hash, class Allocator>
0502 unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
0503 -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17
0504
0505 template <class Value, class Hash, class Pred, class Alloc>
0506 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
0507 unordered_multiset<Value, Hash, Pred, Alloc>& y)
0508 noexcept(noexcept(x.swap(y)));
0509
0510 template <class K, class T, class H, class P, class A, class Predicate>
0511 typename unordered_set<K, T, H, P, A>::size_type
0512 erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20
0513
0514 template <class K, class T, class H, class P, class A, class Predicate>
0515 typename unordered_multiset<K, T, H, P, A>::size_type
0516 erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20
0517
0518
0519 template <class Value, class Hash, class Pred, class Alloc>
0520 bool
0521 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
0522 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
0523
0524 template <class Value, class Hash, class Pred, class Alloc>
0525 bool
0526 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
0527 const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20
0528 } // std
0529
0530 */
0531
0532 // clang-format on
0533
0534 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0535 # include <__cxx03/unordered_set>
0536 #else
0537 # include <__algorithm/is_permutation.h>
0538 # include <__assert>
0539 # include <__config>
0540 # include <__functional/hash.h>
0541 # include <__functional/is_transparent.h>
0542 # include <__functional/operations.h>
0543 # include <__hash_table>
0544 # include <__iterator/distance.h>
0545 # include <__iterator/erase_if_container.h>
0546 # include <__iterator/iterator_traits.h>
0547 # include <__iterator/ranges_iterator_traits.h>
0548 # include <__memory/addressof.h>
0549 # include <__memory/allocator.h>
0550 # include <__memory/allocator_traits.h>
0551 # include <__memory_resource/polymorphic_allocator.h>
0552 # include <__node_handle>
0553 # include <__ranges/concepts.h>
0554 # include <__ranges/container_compatible_range.h>
0555 # include <__ranges/from_range.h>
0556 # include <__type_traits/container_traits.h>
0557 # include <__type_traits/enable_if.h>
0558 # include <__type_traits/invoke.h>
0559 # include <__type_traits/is_allocator.h>
0560 # include <__type_traits/is_integral.h>
0561 # include <__type_traits/is_nothrow_assignable.h>
0562 # include <__type_traits/is_nothrow_constructible.h>
0563 # include <__type_traits/is_same.h>
0564 # include <__type_traits/is_swappable.h>
0565 # include <__type_traits/type_identity.h>
0566 # include <__utility/forward.h>
0567 # include <__utility/move.h>
0568 # include <__utility/pair.h>
0569 # include <version>
0570
0571 // standard-mandated includes
0572
0573 // [iterator.range]
0574 # include <__iterator/access.h>
0575 # include <__iterator/data.h>
0576 # include <__iterator/empty.h>
0577 # include <__iterator/reverse_access.h>
0578 # include <__iterator/size.h>
0579
0580 // [unord.set.syn]
0581 # include <compare>
0582 # include <initializer_list>
0583
0584 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0585 # pragma GCC system_header
0586 # endif
0587
0588 _LIBCPP_PUSH_MACROS
0589 # include <__undef_macros>
0590
0591 _LIBCPP_BEGIN_NAMESPACE_STD
0592
0593 template <class _Value, class _Hash, class _Pred, class _Alloc>
0594 class unordered_multiset;
0595
0596 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
0597 class _LIBCPP_TEMPLATE_VIS unordered_set {
0598 public:
0599 // types
0600 typedef _Value key_type;
0601 typedef key_type value_type;
0602 typedef __type_identity_t<_Hash> hasher;
0603 typedef __type_identity_t<_Pred> key_equal;
0604 typedef __type_identity_t<_Alloc> allocator_type;
0605 typedef value_type& reference;
0606 typedef const value_type& const_reference;
0607 static_assert(__check_valid_allocator<allocator_type>::value, "");
0608 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
0609 "Allocator::value_type must be same type as value_type");
0610
0611 private:
0612 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
0613
0614 __table __table_;
0615
0616 public:
0617 typedef typename __table::pointer pointer;
0618 typedef typename __table::const_pointer const_pointer;
0619 typedef typename __table::size_type size_type;
0620 typedef typename __table::difference_type difference_type;
0621
0622 typedef typename __table::const_iterator iterator;
0623 typedef typename __table::const_iterator const_iterator;
0624 typedef typename __table::const_local_iterator local_iterator;
0625 typedef typename __table::const_local_iterator const_local_iterator;
0626
0627 # if _LIBCPP_STD_VER >= 17
0628 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
0629 typedef __insert_return_type<iterator, node_type> insert_return_type;
0630 # endif
0631
0632 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
0633 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
0634 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
0635 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
0636
0637 _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
0638 explicit _LIBCPP_HIDE_FROM_ABI
0639 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0640 # if _LIBCPP_STD_VER >= 14
0641 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)
0642 : unordered_set(__n, hasher(), key_equal(), __a) {}
0643 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
0644 : unordered_set(__n, __hf, key_equal(), __a) {}
0645 # endif
0646 _LIBCPP_HIDE_FROM_ABI
0647 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0648 template <class _InputIterator>
0649 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
0650 template <class _InputIterator>
0651 _LIBCPP_HIDE_FROM_ABI
0652 unordered_set(_InputIterator __first,
0653 _InputIterator __last,
0654 size_type __n,
0655 const hasher& __hf = hasher(),
0656 const key_equal& __eql = key_equal());
0657 template <class _InputIterator>
0658 _LIBCPP_HIDE_FROM_ABI unordered_set(
0659 _InputIterator __first,
0660 _InputIterator __last,
0661 size_type __n,
0662 const hasher& __hf,
0663 const key_equal& __eql,
0664 const allocator_type& __a);
0665
0666 # if _LIBCPP_STD_VER >= 23
0667 template <_ContainerCompatibleRange<value_type> _Range>
0668 _LIBCPP_HIDE_FROM_ABI unordered_set(
0669 from_range_t,
0670 _Range&& __range,
0671 size_type __n = /*implementation-defined*/ 0,
0672 const hasher& __hf = hasher(),
0673 const key_equal& __eql = key_equal(),
0674 const allocator_type& __a = allocator_type())
0675 : __table_(__hf, __eql, __a) {
0676 if (__n > 0) {
0677 __table_.__rehash_unique(__n);
0678 }
0679 insert_range(std::forward<_Range>(__range));
0680 }
0681 # endif
0682
0683 # if _LIBCPP_STD_VER >= 14
0684 template <class _InputIterator>
0685 inline _LIBCPP_HIDE_FROM_ABI
0686 unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
0687 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
0688 template <class _InputIterator>
0689 _LIBCPP_HIDE_FROM_ABI unordered_set(
0690 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
0691 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
0692 # endif
0693
0694 # if _LIBCPP_STD_VER >= 23
0695 template <_ContainerCompatibleRange<value_type> _Range>
0696 _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
0697 : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
0698
0699 template <_ContainerCompatibleRange<value_type> _Range>
0700 _LIBCPP_HIDE_FROM_ABI
0701 unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
0702 : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
0703 # endif
0704
0705 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
0706 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
0707 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
0708 # ifndef _LIBCPP_CXX03_LANG
0709 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
0710 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);
0711 _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);
0712 _LIBCPP_HIDE_FROM_ABI
0713 unordered_set(initializer_list<value_type> __il,
0714 size_type __n,
0715 const hasher& __hf = hasher(),
0716 const key_equal& __eql = key_equal());
0717 _LIBCPP_HIDE_FROM_ABI unordered_set(
0718 initializer_list<value_type> __il,
0719 size_type __n,
0720 const hasher& __hf,
0721 const key_equal& __eql,
0722 const allocator_type& __a);
0723 # if _LIBCPP_STD_VER >= 14
0724 inline _LIBCPP_HIDE_FROM_ABI
0725 unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
0726 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
0727 inline _LIBCPP_HIDE_FROM_ABI
0728 unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
0729 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
0730 # endif
0731 # endif // _LIBCPP_CXX03_LANG
0732 _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
0733 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
0734 }
0735
0736 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
0737 __table_ = __u.__table_;
0738 return *this;
0739 }
0740 # ifndef _LIBCPP_CXX03_LANG
0741 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u)
0742 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
0743 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);
0744 # endif // _LIBCPP_CXX03_LANG
0745
0746 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
0747 return allocator_type(__table_.__node_alloc());
0748 }
0749
0750 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
0751 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
0752 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
0753
0754 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
0755 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
0756 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
0757 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
0758 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
0759 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
0760
0761 # ifndef _LIBCPP_CXX03_LANG
0762 template <class... _Args>
0763 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
0764 return __table_.__emplace_unique(std::forward<_Args>(__args)...);
0765 }
0766 template <class... _Args>
0767 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
0768 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
0769 }
0770
0771 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
0772 return __table_.__insert_unique(std::move(__x));
0773 }
0774 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }
0775
0776 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
0777 # endif // _LIBCPP_CXX03_LANG
0778 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
0779
0780 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
0781 template <class _InputIterator>
0782 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0783
0784 # if _LIBCPP_STD_VER >= 23
0785 template <_ContainerCompatibleRange<value_type> _Range>
0786 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
0787 for (auto&& __element : __range) {
0788 __table_.__insert_unique(std::forward<decltype(__element)>(__element));
0789 }
0790 }
0791 # endif
0792
0793 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
0794 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
0795 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
0796 return __table_.erase(__first, __last);
0797 }
0798 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
0799
0800 # if _LIBCPP_STD_VER >= 17
0801 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
0802 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0803 "node_type with incompatible allocator passed to unordered_set::insert()");
0804 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
0805 }
0806 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {
0807 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0808 "node_type with incompatible allocator passed to unordered_set::insert()");
0809 return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));
0810 }
0811 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
0812 return __table_.template __node_handle_extract<node_type>(__key);
0813 }
0814 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
0815 return __table_.template __node_handle_extract<node_type>(__it);
0816 }
0817
0818 template <class _H2, class _P2>
0819 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
0820 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0821 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0822 __table_.__node_handle_merge_unique(__source.__table_);
0823 }
0824 template <class _H2, class _P2>
0825 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
0826 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0827 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0828 __table_.__node_handle_merge_unique(__source.__table_);
0829 }
0830 template <class _H2, class _P2>
0831 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
0832 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0833 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0834 __table_.__node_handle_merge_unique(__source.__table_);
0835 }
0836 template <class _H2, class _P2>
0837 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
0838 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0839 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0840 __table_.__node_handle_merge_unique(__source.__table_);
0841 }
0842 # endif
0843
0844 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
0845 __table_.swap(__u.__table_);
0846 }
0847
0848 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
0849 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
0850
0851 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0852 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0853 # if _LIBCPP_STD_VER >= 20
0854 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0855 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
0856 return __table_.find(__k);
0857 }
0858 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0859 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
0860 return __table_.find(__k);
0861 }
0862 # endif // _LIBCPP_STD_VER >= 20
0863
0864 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
0865 # if _LIBCPP_STD_VER >= 20
0866 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0867 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
0868 return __table_.__count_unique(__k);
0869 }
0870 # endif // _LIBCPP_STD_VER >= 20
0871
0872 # if _LIBCPP_STD_VER >= 20
0873 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
0874
0875 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0876 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
0877 return find(__k) != end();
0878 }
0879 # endif // _LIBCPP_STD_VER >= 20
0880
0881 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
0882 return __table_.__equal_range_unique(__k);
0883 }
0884 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0885 return __table_.__equal_range_unique(__k);
0886 }
0887 # if _LIBCPP_STD_VER >= 20
0888 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0889 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
0890 return __table_.__equal_range_unique(__k);
0891 }
0892 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0893 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
0894 return __table_.__equal_range_unique(__k);
0895 }
0896 # endif // _LIBCPP_STD_VER >= 20
0897
0898 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
0899 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
0900
0901 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
0902 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
0903
0904 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
0905 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
0906 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
0907 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
0908 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
0909 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
0910
0911 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
0912 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
0913 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
0914 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
0915 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
0916 };
0917
0918 # if _LIBCPP_STD_VER >= 17
0919 template <class _InputIterator,
0920 class _Hash = hash<__iter_value_type<_InputIterator>>,
0921 class _Pred = equal_to<__iter_value_type<_InputIterator>>,
0922 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
0923 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0924 class = enable_if_t<!__is_allocator<_Hash>::value>,
0925 class = enable_if_t<!is_integral<_Hash>::value>,
0926 class = enable_if_t<!__is_allocator<_Pred>::value>,
0927 class = enable_if_t<__is_allocator<_Allocator>::value>>
0928 unordered_set(_InputIterator,
0929 _InputIterator,
0930 typename allocator_traits<_Allocator>::size_type = 0,
0931 _Hash = _Hash(),
0932 _Pred = _Pred(),
0933 _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
0934
0935 # if _LIBCPP_STD_VER >= 23
0936 template <ranges::input_range _Range,
0937 class _Hash = hash<ranges::range_value_t<_Range>>,
0938 class _Pred = equal_to<ranges::range_value_t<_Range>>,
0939 class _Allocator = allocator<ranges::range_value_t<_Range>>,
0940 class = enable_if_t<!__is_allocator<_Hash>::value>,
0941 class = enable_if_t<!is_integral<_Hash>::value>,
0942 class = enable_if_t<!__is_allocator<_Pred>::value>,
0943 class = enable_if_t<__is_allocator<_Allocator>::value>>
0944 unordered_set(
0945 from_range_t,
0946 _Range&&,
0947 typename allocator_traits<_Allocator>::size_type = 0,
0948 _Hash = _Hash(),
0949 _Pred = _Pred(),
0950 _Allocator = _Allocator()) -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
0951 # endif
0952
0953 template <class _Tp,
0954 class _Hash = hash<_Tp>,
0955 class _Pred = equal_to<_Tp>,
0956 class _Allocator = allocator<_Tp>,
0957 class = enable_if_t<!__is_allocator<_Hash>::value>,
0958 class = enable_if_t<!is_integral<_Hash>::value>,
0959 class = enable_if_t<!__is_allocator<_Pred>::value>,
0960 class = enable_if_t<__is_allocator<_Allocator>::value>>
0961 unordered_set(initializer_list<_Tp>,
0962 typename allocator_traits<_Allocator>::size_type = 0,
0963 _Hash = _Hash(),
0964 _Pred = _Pred(),
0965 _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
0966
0967 template <class _InputIterator,
0968 class _Allocator,
0969 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0970 class = enable_if_t<__is_allocator<_Allocator>::value>>
0971 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
0972 -> unordered_set<__iter_value_type<_InputIterator>,
0973 hash<__iter_value_type<_InputIterator>>,
0974 equal_to<__iter_value_type<_InputIterator>>,
0975 _Allocator>;
0976
0977 template <class _InputIterator,
0978 class _Hash,
0979 class _Allocator,
0980 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0981 class = enable_if_t<!__is_allocator<_Hash>::value>,
0982 class = enable_if_t<!is_integral<_Hash>::value>,
0983 class = enable_if_t<__is_allocator<_Allocator>::value>>
0984 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
0985 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>;
0986
0987 # if _LIBCPP_STD_VER >= 23
0988
0989 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
0990 unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
0991 -> unordered_set<ranges::range_value_t<_Range>,
0992 hash<ranges::range_value_t<_Range>>,
0993 equal_to<ranges::range_value_t<_Range>>,
0994 _Allocator>;
0995
0996 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
0997 unordered_set(from_range_t, _Range&&, _Allocator)
0998 -> unordered_set<ranges::range_value_t<_Range>,
0999 hash<ranges::range_value_t<_Range>>,
1000 equal_to<ranges::range_value_t<_Range>>,
1001 _Allocator>;
1002
1003 template <ranges::input_range _Range,
1004 class _Hash,
1005 class _Allocator,
1006 class = enable_if_t<!__is_allocator<_Hash>::value>,
1007 class = enable_if_t<!is_integral<_Hash>::value>,
1008 class = enable_if_t<__is_allocator<_Allocator>::value>>
1009 unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1010 -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
1011
1012 # endif
1013
1014 template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1015 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1016 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1017
1018 template <class _Tp,
1019 class _Hash,
1020 class _Allocator,
1021 class = enable_if_t<!__is_allocator<_Hash>::value>,
1022 class = enable_if_t<!is_integral<_Hash>::value>,
1023 class = enable_if_t<__is_allocator<_Allocator>::value>>
1024 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1025 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1026 # endif
1027
1028 template <class _Value, class _Hash, class _Pred, class _Alloc>
1029 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)
1030 : __table_(__hf, __eql) {
1031 __table_.__rehash_unique(__n);
1032 }
1033
1034 template <class _Value, class _Hash, class _Pred, class _Alloc>
1035 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1036 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1037 : __table_(__hf, __eql, __a) {
1038 __table_.__rehash_unique(__n);
1039 }
1040
1041 template <class _Value, class _Hash, class _Pred, class _Alloc>
1042 template <class _InputIterator>
1043 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {
1044 insert(__first, __last);
1045 }
1046
1047 template <class _Value, class _Hash, class _Pred, class _Alloc>
1048 template <class _InputIterator>
1049 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1050 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1051 : __table_(__hf, __eql) {
1052 __table_.__rehash_unique(__n);
1053 insert(__first, __last);
1054 }
1055
1056 template <class _Value, class _Hash, class _Pred, class _Alloc>
1057 template <class _InputIterator>
1058 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1059 _InputIterator __first,
1060 _InputIterator __last,
1061 size_type __n,
1062 const hasher& __hf,
1063 const key_equal& __eql,
1064 const allocator_type& __a)
1065 : __table_(__hf, __eql, __a) {
1066 __table_.__rehash_unique(__n);
1067 insert(__first, __last);
1068 }
1069
1070 template <class _Value, class _Hash, class _Pred, class _Alloc>
1071 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}
1072
1073 template <class _Value, class _Hash, class _Pred, class _Alloc>
1074 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {
1075 __table_.__rehash_unique(__u.bucket_count());
1076 insert(__u.begin(), __u.end());
1077 }
1078
1079 template <class _Value, class _Hash, class _Pred, class _Alloc>
1080 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)
1081 : __table_(__u.__table_, __a) {
1082 __table_.__rehash_unique(__u.bucket_count());
1083 insert(__u.begin(), __u.end());
1084 }
1085
1086 # ifndef _LIBCPP_CXX03_LANG
1087
1088 template <class _Value, class _Hash, class _Pred, class _Alloc>
1089 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u)
1090 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1091 : __table_(std::move(__u.__table_)) {}
1092
1093 template <class _Value, class _Hash, class _Pred, class _Alloc>
1094 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a)
1095 : __table_(std::move(__u.__table_), __a) {
1096 if (__a != __u.get_allocator()) {
1097 iterator __i = __u.begin();
1098 while (__u.size() != 0)
1099 __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value()));
1100 }
1101 }
1102
1103 template <class _Value, class _Hash, class _Pred, class _Alloc>
1104 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) {
1105 insert(__il.begin(), __il.end());
1106 }
1107
1108 template <class _Value, class _Hash, class _Pred, class _Alloc>
1109 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1110 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1111 : __table_(__hf, __eql) {
1112 __table_.__rehash_unique(__n);
1113 insert(__il.begin(), __il.end());
1114 }
1115
1116 template <class _Value, class _Hash, class _Pred, class _Alloc>
1117 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1118 initializer_list<value_type> __il,
1119 size_type __n,
1120 const hasher& __hf,
1121 const key_equal& __eql,
1122 const allocator_type& __a)
1123 : __table_(__hf, __eql, __a) {
1124 __table_.__rehash_unique(__n);
1125 insert(__il.begin(), __il.end());
1126 }
1127
1128 template <class _Value, class _Hash, class _Pred, class _Alloc>
1129 inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1130 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
1131 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1132 __table_ = std::move(__u.__table_);
1133 return *this;
1134 }
1135
1136 template <class _Value, class _Hash, class _Pred, class _Alloc>
1137 inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1138 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1139 __table_.__assign_unique(__il.begin(), __il.end());
1140 return *this;
1141 }
1142
1143 # endif // _LIBCPP_CXX03_LANG
1144
1145 template <class _Value, class _Hash, class _Pred, class _Alloc>
1146 template <class _InputIterator>
1147 inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1148 for (; __first != __last; ++__first)
1149 __table_.__insert_unique(*__first);
1150 }
1151
1152 template <class _Value, class _Hash, class _Pred, class _Alloc>
1153 inline _LIBCPP_HIDE_FROM_ABI void
1154 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1155 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1156 __x.swap(__y);
1157 }
1158
1159 # if _LIBCPP_STD_VER >= 20
1160 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1161 inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type
1162 erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1163 return std::__libcpp_erase_if_container(__c, __pred);
1164 }
1165 # endif
1166
1167 template <class _Value, class _Hash, class _Pred, class _Alloc>
1168 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1169 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1170 if (__x.size() != __y.size())
1171 return false;
1172 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1173 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1174 const_iterator __j = __y.find(*__i);
1175 if (__j == __ey || !(*__i == *__j))
1176 return false;
1177 }
1178 return true;
1179 }
1180
1181 # if _LIBCPP_STD_VER <= 17
1182
1183 template <class _Value, class _Hash, class _Pred, class _Alloc>
1184 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1185 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1186 return !(__x == __y);
1187 }
1188
1189 # endif
1190
1191 template <class _Value, class _Hash, class _Pred, class _Alloc>
1192 struct __container_traits<unordered_set<_Value, _Hash, _Pred, _Alloc> > {
1193 // http://eel.is/c++draft/unord.req.except#2
1194 // For unordered associative containers, if an exception is thrown by any operation
1195 // other than the container's hash function from within an insert or emplace function
1196 // inserting a single element, the insertion has no effect.
1197 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =
1198 __is_nothrow_invocable_v<_Hash, const _Value&>;
1199 };
1200
1201 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
1202 class _LIBCPP_TEMPLATE_VIS unordered_multiset {
1203 public:
1204 // types
1205 typedef _Value key_type;
1206 typedef key_type value_type;
1207 typedef __type_identity_t<_Hash> hasher;
1208 typedef __type_identity_t<_Pred> key_equal;
1209 typedef __type_identity_t<_Alloc> allocator_type;
1210 typedef value_type& reference;
1211 typedef const value_type& const_reference;
1212 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1213 "Allocator::value_type must be same type as value_type");
1214
1215 private:
1216 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1217
1218 __table __table_;
1219
1220 public:
1221 typedef typename __table::pointer pointer;
1222 typedef typename __table::const_pointer const_pointer;
1223 typedef typename __table::size_type size_type;
1224 typedef typename __table::difference_type difference_type;
1225
1226 typedef typename __table::const_iterator iterator;
1227 typedef typename __table::const_iterator const_iterator;
1228 typedef typename __table::const_local_iterator local_iterator;
1229 typedef typename __table::const_local_iterator const_local_iterator;
1230
1231 # if _LIBCPP_STD_VER >= 17
1232 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1233 # endif
1234
1235 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1236 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1237 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1238 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1239
1240 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1241 explicit _LIBCPP_HIDE_FROM_ABI
1242 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1243 _LIBCPP_HIDE_FROM_ABI
1244 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1245 # if _LIBCPP_STD_VER >= 14
1246 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a)
1247 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1248 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1249 : unordered_multiset(__n, __hf, key_equal(), __a) {}
1250 # endif
1251 template <class _InputIterator>
1252 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);
1253 template <class _InputIterator>
1254 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1255 _InputIterator __first,
1256 _InputIterator __last,
1257 size_type __n,
1258 const hasher& __hf = hasher(),
1259 const key_equal& __eql = key_equal());
1260 template <class _InputIterator>
1261 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1262 _InputIterator __first,
1263 _InputIterator __last,
1264 size_type __n,
1265 const hasher& __hf,
1266 const key_equal& __eql,
1267 const allocator_type& __a);
1268
1269 # if _LIBCPP_STD_VER >= 23
1270 template <_ContainerCompatibleRange<value_type> _Range>
1271 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1272 from_range_t,
1273 _Range&& __range,
1274 size_type __n = /*implementation-defined*/ 0,
1275 const hasher& __hf = hasher(),
1276 const key_equal& __eql = key_equal(),
1277 const allocator_type& __a = allocator_type())
1278 : __table_(__hf, __eql, __a) {
1279 if (__n > 0) {
1280 __table_.__rehash_multi(__n);
1281 }
1282 insert_range(std::forward<_Range>(__range));
1283 }
1284 # endif
1285
1286 # if _LIBCPP_STD_VER >= 14
1287 template <class _InputIterator>
1288 inline _LIBCPP_HIDE_FROM_ABI
1289 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1290 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1291 template <class _InputIterator>
1292 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1293 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1294 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1295 # endif
1296
1297 # if _LIBCPP_STD_VER >= 23
1298 template <_ContainerCompatibleRange<value_type> _Range>
1299 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1300 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1301
1302 template <_ContainerCompatibleRange<value_type> _Range>
1303 _LIBCPP_HIDE_FROM_ABI
1304 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1305 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1306 # endif
1307
1308 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);
1309 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);
1310 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1311 # ifndef _LIBCPP_CXX03_LANG
1312 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u)
1313 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1314 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1315 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il);
1316 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1317 initializer_list<value_type> __il,
1318 size_type __n,
1319 const hasher& __hf = hasher(),
1320 const key_equal& __eql = key_equal());
1321 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1322 initializer_list<value_type> __il,
1323 size_type __n,
1324 const hasher& __hf,
1325 const key_equal& __eql,
1326 const allocator_type& __a);
1327 # if _LIBCPP_STD_VER >= 14
1328 inline _LIBCPP_HIDE_FROM_ABI
1329 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1330 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1331 inline _LIBCPP_HIDE_FROM_ABI
1332 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1333 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1334 # endif
1335 # endif // _LIBCPP_CXX03_LANG
1336 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {
1337 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
1338 }
1339
1340 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {
1341 __table_ = __u.__table_;
1342 return *this;
1343 }
1344 # ifndef _LIBCPP_CXX03_LANG
1345 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u)
1346 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1347 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il);
1348 # endif // _LIBCPP_CXX03_LANG
1349
1350 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1351 return allocator_type(__table_.__node_alloc());
1352 }
1353
1354 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1355 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1356 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1357
1358 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1359 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1360 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1361 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1362 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1363 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1364
1365 # ifndef _LIBCPP_CXX03_LANG
1366 template <class... _Args>
1367 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1368 return __table_.__emplace_multi(std::forward<_Args>(__args)...);
1369 }
1370 template <class... _Args>
1371 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1372 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1373 }
1374
1375 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
1376 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
1377 return __table_.__insert_multi(__p, std::move(__x));
1378 }
1379 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1380 # endif // _LIBCPP_CXX03_LANG
1381
1382 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
1383
1384 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1385 return __table_.__insert_multi(__p, __x);
1386 }
1387
1388 template <class _InputIterator>
1389 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1390
1391 # if _LIBCPP_STD_VER >= 23
1392 template <_ContainerCompatibleRange<value_type> _Range>
1393 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1394 for (auto&& __element : __range) {
1395 __table_.__insert_multi(std::forward<decltype(__element)>(__element));
1396 }
1397 }
1398 # endif
1399
1400 # if _LIBCPP_STD_VER >= 17
1401 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1402 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1403 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1404 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1405 }
1406 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1407 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1408 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1409 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1410 }
1411 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) {
1412 return __table_.template __node_handle_extract<node_type>(__position);
1413 }
1414 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1415 return __table_.template __node_handle_extract<node_type>(__key);
1416 }
1417
1418 template <class _H2, class _P2>
1419 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
1420 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1421 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1422 return __table_.__node_handle_merge_multi(__source.__table_);
1423 }
1424 template <class _H2, class _P2>
1425 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
1426 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1427 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1428 return __table_.__node_handle_merge_multi(__source.__table_);
1429 }
1430 template <class _H2, class _P2>
1431 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
1432 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1433 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1434 return __table_.__node_handle_merge_multi(__source.__table_);
1435 }
1436 template <class _H2, class _P2>
1437 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
1438 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1439 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1440 return __table_.__node_handle_merge_multi(__source.__table_);
1441 }
1442 # endif
1443
1444 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
1445 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1446 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1447 return __table_.erase(__first, __last);
1448 }
1449 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1450
1451 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1452 __table_.swap(__u.__table_);
1453 }
1454
1455 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
1456 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
1457
1458 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1459 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1460 # if _LIBCPP_STD_VER >= 20
1461 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1462 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1463 return __table_.find(__k);
1464 }
1465 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1466 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1467 return __table_.find(__k);
1468 }
1469 # endif // _LIBCPP_STD_VER >= 20
1470
1471 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
1472 # if _LIBCPP_STD_VER >= 20
1473 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1474 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1475 return __table_.__count_multi(__k);
1476 }
1477 # endif // _LIBCPP_STD_VER >= 20
1478
1479 # if _LIBCPP_STD_VER >= 20
1480 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1481
1482 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1483 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1484 return find(__k) != end();
1485 }
1486 # endif // _LIBCPP_STD_VER >= 20
1487
1488 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1489 return __table_.__equal_range_multi(__k);
1490 }
1491 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1492 return __table_.__equal_range_multi(__k);
1493 }
1494 # if _LIBCPP_STD_VER >= 20
1495 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1496 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1497 return __table_.__equal_range_multi(__k);
1498 }
1499 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1500 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1501 return __table_.__equal_range_multi(__k);
1502 }
1503 # endif // _LIBCPP_STD_VER >= 20
1504
1505 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1506 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1507
1508 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1509 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1510
1511 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1512 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1513 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1514 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1515 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1516 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1517
1518 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1519 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1520 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1521 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
1522 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
1523 };
1524
1525 # if _LIBCPP_STD_VER >= 17
1526 template <class _InputIterator,
1527 class _Hash = hash<__iter_value_type<_InputIterator>>,
1528 class _Pred = equal_to<__iter_value_type<_InputIterator>>,
1529 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1530 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1531 class = enable_if_t<!__is_allocator<_Hash>::value>,
1532 class = enable_if_t<!is_integral<_Hash>::value>,
1533 class = enable_if_t<!__is_allocator<_Pred>::value>,
1534 class = enable_if_t<__is_allocator<_Allocator>::value>>
1535 unordered_multiset(
1536 _InputIterator,
1537 _InputIterator,
1538 typename allocator_traits<_Allocator>::size_type = 0,
1539 _Hash = _Hash(),
1540 _Pred = _Pred(),
1541 _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1542
1543 # if _LIBCPP_STD_VER >= 23
1544 template <ranges::input_range _Range,
1545 class _Hash = hash<ranges::range_value_t<_Range>>,
1546 class _Pred = equal_to<ranges::range_value_t<_Range>>,
1547 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1548 class = enable_if_t<!__is_allocator<_Hash>::value>,
1549 class = enable_if_t<!is_integral<_Hash>::value>,
1550 class = enable_if_t<!__is_allocator<_Pred>::value>,
1551 class = enable_if_t<__is_allocator<_Allocator>::value>>
1552 unordered_multiset(
1553 from_range_t,
1554 _Range&&,
1555 typename allocator_traits<_Allocator>::size_type = 0,
1556 _Hash = _Hash(),
1557 _Pred = _Pred(),
1558 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
1559 # endif
1560
1561 template <class _Tp,
1562 class _Hash = hash<_Tp>,
1563 class _Pred = equal_to<_Tp>,
1564 class _Allocator = allocator<_Tp>,
1565 class = enable_if_t<!__is_allocator<_Hash>::value>,
1566 class = enable_if_t<!is_integral<_Hash>::value>,
1567 class = enable_if_t<!__is_allocator<_Pred>::value>,
1568 class = enable_if_t<__is_allocator<_Allocator>::value>>
1569 unordered_multiset(initializer_list<_Tp>,
1570 typename allocator_traits<_Allocator>::size_type = 0,
1571 _Hash = _Hash(),
1572 _Pred = _Pred(),
1573 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1574
1575 template <class _InputIterator,
1576 class _Allocator,
1577 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1578 class = enable_if_t<__is_allocator<_Allocator>::value>>
1579 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1580 -> unordered_multiset<__iter_value_type<_InputIterator>,
1581 hash<__iter_value_type<_InputIterator>>,
1582 equal_to<__iter_value_type<_InputIterator>>,
1583 _Allocator>;
1584
1585 template <class _InputIterator,
1586 class _Hash,
1587 class _Allocator,
1588 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1589 class = enable_if_t<!__is_allocator<_Hash>::value>,
1590 class = enable_if_t<!is_integral<_Hash>::value>,
1591 class = enable_if_t<__is_allocator<_Allocator>::value>>
1592 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1593 -> unordered_multiset<__iter_value_type<_InputIterator>,
1594 _Hash,
1595 equal_to<__iter_value_type<_InputIterator>>,
1596 _Allocator>;
1597
1598 # if _LIBCPP_STD_VER >= 23
1599
1600 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1601 unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1602 -> unordered_multiset<ranges::range_value_t<_Range>,
1603 hash<ranges::range_value_t<_Range>>,
1604 equal_to<ranges::range_value_t<_Range>>,
1605 _Allocator>;
1606
1607 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1608 unordered_multiset(from_range_t, _Range&&, _Allocator)
1609 -> unordered_multiset<ranges::range_value_t<_Range>,
1610 hash<ranges::range_value_t<_Range>>,
1611 equal_to<ranges::range_value_t<_Range>>,
1612 _Allocator>;
1613
1614 template <ranges::input_range _Range,
1615 class _Hash,
1616 class _Allocator,
1617 class = enable_if_t<!__is_allocator<_Hash>::value>,
1618 class = enable_if_t<!is_integral<_Hash>::value>,
1619 class = enable_if_t<__is_allocator<_Allocator>::value>>
1620 unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1621 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
1622
1623 # endif
1624
1625 template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1626 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1627 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1628
1629 template <class _Tp,
1630 class _Hash,
1631 class _Allocator,
1632 class = enable_if_t<!__is_allocator<_Hash>::value>,
1633 class = enable_if_t<!is_integral<_Hash>::value>,
1634 class = enable_if_t<__is_allocator<_Allocator>::value>>
1635 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1636 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1637 # endif
1638
1639 template <class _Value, class _Hash, class _Pred, class _Alloc>
1640 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1641 size_type __n, const hasher& __hf, const key_equal& __eql)
1642 : __table_(__hf, __eql) {
1643 __table_.__rehash_multi(__n);
1644 }
1645
1646 template <class _Value, class _Hash, class _Pred, class _Alloc>
1647 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1648 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1649 : __table_(__hf, __eql, __a) {
1650 __table_.__rehash_multi(__n);
1651 }
1652
1653 template <class _Value, class _Hash, class _Pred, class _Alloc>
1654 template <class _InputIterator>
1655 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {
1656 insert(__first, __last);
1657 }
1658
1659 template <class _Value, class _Hash, class _Pred, class _Alloc>
1660 template <class _InputIterator>
1661 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1662 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1663 : __table_(__hf, __eql) {
1664 __table_.__rehash_multi(__n);
1665 insert(__first, __last);
1666 }
1667
1668 template <class _Value, class _Hash, class _Pred, class _Alloc>
1669 template <class _InputIterator>
1670 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1671 _InputIterator __first,
1672 _InputIterator __last,
1673 size_type __n,
1674 const hasher& __hf,
1675 const key_equal& __eql,
1676 const allocator_type& __a)
1677 : __table_(__hf, __eql, __a) {
1678 __table_.__rehash_multi(__n);
1679 insert(__first, __last);
1680 }
1681
1682 template <class _Value, class _Hash, class _Pred, class _Alloc>
1683 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)
1684 : __table_(__a) {}
1685
1686 template <class _Value, class _Hash, class _Pred, class _Alloc>
1687 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)
1688 : __table_(__u.__table_) {
1689 __table_.__rehash_multi(__u.bucket_count());
1690 insert(__u.begin(), __u.end());
1691 }
1692
1693 template <class _Value, class _Hash, class _Pred, class _Alloc>
1694 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1695 const unordered_multiset& __u, const allocator_type& __a)
1696 : __table_(__u.__table_, __a) {
1697 __table_.__rehash_multi(__u.bucket_count());
1698 insert(__u.begin(), __u.end());
1699 }
1700
1701 # ifndef _LIBCPP_CXX03_LANG
1702
1703 template <class _Value, class _Hash, class _Pred, class _Alloc>
1704 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u)
1705 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1706 : __table_(std::move(__u.__table_)) {}
1707
1708 template <class _Value, class _Hash, class _Pred, class _Alloc>
1709 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1710 unordered_multiset&& __u, const allocator_type& __a)
1711 : __table_(std::move(__u.__table_), __a) {
1712 if (__a != __u.get_allocator()) {
1713 iterator __i = __u.begin();
1714 while (__u.size() != 0)
1715 __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value()));
1716 }
1717 }
1718
1719 template <class _Value, class _Hash, class _Pred, class _Alloc>
1720 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) {
1721 insert(__il.begin(), __il.end());
1722 }
1723
1724 template <class _Value, class _Hash, class _Pred, class _Alloc>
1725 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1726 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1727 : __table_(__hf, __eql) {
1728 __table_.__rehash_multi(__n);
1729 insert(__il.begin(), __il.end());
1730 }
1731
1732 template <class _Value, class _Hash, class _Pred, class _Alloc>
1733 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1734 initializer_list<value_type> __il,
1735 size_type __n,
1736 const hasher& __hf,
1737 const key_equal& __eql,
1738 const allocator_type& __a)
1739 : __table_(__hf, __eql, __a) {
1740 __table_.__rehash_multi(__n);
1741 insert(__il.begin(), __il.end());
1742 }
1743
1744 template <class _Value, class _Hash, class _Pred, class _Alloc>
1745 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1746 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u)
1747 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1748 __table_ = std::move(__u.__table_);
1749 return *this;
1750 }
1751
1752 template <class _Value, class _Hash, class _Pred, class _Alloc>
1753 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1754 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1755 __table_.__assign_multi(__il.begin(), __il.end());
1756 return *this;
1757 }
1758
1759 # endif // _LIBCPP_CXX03_LANG
1760
1761 template <class _Value, class _Hash, class _Pred, class _Alloc>
1762 template <class _InputIterator>
1763 inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1764 for (; __first != __last; ++__first)
1765 __table_.__insert_multi(*__first);
1766 }
1767
1768 template <class _Value, class _Hash, class _Pred, class _Alloc>
1769 inline _LIBCPP_HIDE_FROM_ABI void
1770 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1771 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1772 __x.swap(__y);
1773 }
1774
1775 # if _LIBCPP_STD_VER >= 20
1776 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1777 inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type
1778 erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1779 return std::__libcpp_erase_if_container(__c, __pred);
1780 }
1781 # endif
1782
1783 template <class _Value, class _Hash, class _Pred, class _Alloc>
1784 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1785 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1786 if (__x.size() != __y.size())
1787 return false;
1788 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1789 typedef pair<const_iterator, const_iterator> _EqRng;
1790 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
1791 _EqRng __xeq = __x.equal_range(*__i);
1792 _EqRng __yeq = __y.equal_range(*__i);
1793 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
1794 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1795 return false;
1796 __i = __xeq.second;
1797 }
1798 return true;
1799 }
1800
1801 # if _LIBCPP_STD_VER <= 17
1802
1803 template <class _Value, class _Hash, class _Pred, class _Alloc>
1804 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1805 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1806 return !(__x == __y);
1807 }
1808
1809 # endif
1810
1811 template <class _Value, class _Hash, class _Pred, class _Alloc>
1812 struct __container_traits<unordered_multiset<_Value, _Hash, _Pred, _Alloc> > {
1813 // http://eel.is/c++draft/unord.req.except#2
1814 // For unordered associative containers, if an exception is thrown by any operation
1815 // other than the container's hash function from within an insert or emplace function
1816 // inserting a single element, the insertion has no effect.
1817 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =
1818 __is_nothrow_invocable_v<_Hash, const _Value&>;
1819 };
1820
1821 _LIBCPP_END_NAMESPACE_STD
1822
1823 # if _LIBCPP_STD_VER >= 17
1824 _LIBCPP_BEGIN_NAMESPACE_STD
1825 namespace pmr {
1826 template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1827 using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1828
1829 template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1830 using unordered_multiset _LIBCPP_AVAILABILITY_PMR =
1831 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1832 } // namespace pmr
1833 _LIBCPP_END_NAMESPACE_STD
1834 # endif
1835
1836 _LIBCPP_POP_MACROS
1837
1838 # if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1839 # include <cmath>
1840 # include <concepts>
1841 # include <cstdlib>
1842 # include <functional>
1843 # include <iterator>
1844 # include <stdexcept>
1845 # include <type_traits>
1846 # endif
1847 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
1848
1849 #endif // _LIBCPP_UNORDERED_SET
