Warning, /include/c++/v1/__cxx03/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___CXX03_UNORDERED_SET
0011 #define _LIBCPP___CXX03_UNORDERED_SET
0012
0013 // clang-format off
0014
0015 /*
0016
0017 unordered_set synopsis
0018
0019 #include <__cxx03/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 #include <__cxx03/__algorithm/is_permutation.h>
0535 #include <__cxx03/__assert>
0536 #include <__cxx03/__config>
0537 #include <__cxx03/__functional/is_transparent.h>
0538 #include <__cxx03/__functional/operations.h>
0539 #include <__cxx03/__hash_table>
0540 #include <__cxx03/__iterator/distance.h>
0541 #include <__cxx03/__iterator/erase_if_container.h>
0542 #include <__cxx03/__iterator/iterator_traits.h>
0543 #include <__cxx03/__iterator/ranges_iterator_traits.h>
0544 #include <__cxx03/__memory/addressof.h>
0545 #include <__cxx03/__memory/allocator.h>
0546 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
0547 #include <__cxx03/__node_handle>
0548 #include <__cxx03/__ranges/concepts.h>
0549 #include <__cxx03/__ranges/container_compatible_range.h>
0550 #include <__cxx03/__ranges/from_range.h>
0551 #include <__cxx03/__type_traits/is_allocator.h>
0552 #include <__cxx03/__utility/forward.h>
0553 #include <__cxx03/version>
0554
0555 // standard-mandated includes
0556
0557 // [iterator.range]
0558 #include <__cxx03/__iterator/access.h>
0559 #include <__cxx03/__iterator/data.h>
0560 #include <__cxx03/__iterator/empty.h>
0561 #include <__cxx03/__iterator/reverse_access.h>
0562 #include <__cxx03/__iterator/size.h>
0563
0564 // [unord.set.syn]
0565 #include <__cxx03/compare>
0566 #include <__cxx03/initializer_list>
0567
0568 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0569 # pragma GCC system_header
0570 #endif
0571
0572 _LIBCPP_PUSH_MACROS
0573 #include <__cxx03/__undef_macros>
0574
0575 _LIBCPP_BEGIN_NAMESPACE_STD
0576
0577 template <class _Value, class _Hash, class _Pred, class _Alloc>
0578 class unordered_multiset;
0579
0580 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
0581 class _LIBCPP_TEMPLATE_VIS unordered_set {
0582 public:
0583 // types
0584 typedef _Value key_type;
0585 typedef key_type value_type;
0586 typedef __type_identity_t<_Hash> hasher;
0587 typedef __type_identity_t<_Pred> key_equal;
0588 typedef __type_identity_t<_Alloc> allocator_type;
0589 typedef value_type& reference;
0590 typedef const value_type& const_reference;
0591 static_assert(__check_valid_allocator<allocator_type>::value, "");
0592 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
0593 "Allocator::value_type must be same type as value_type");
0594
0595 private:
0596 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
0597
0598 __table __table_;
0599
0600 public:
0601 typedef typename __table::pointer pointer;
0602 typedef typename __table::const_pointer const_pointer;
0603 typedef typename __table::size_type size_type;
0604 typedef typename __table::difference_type difference_type;
0605
0606 typedef typename __table::const_iterator iterator;
0607 typedef typename __table::const_iterator const_iterator;
0608 typedef typename __table::const_local_iterator local_iterator;
0609 typedef typename __table::const_local_iterator const_local_iterator;
0610
0611 #if _LIBCPP_STD_VER >= 17
0612 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
0613 typedef __insert_return_type<iterator, node_type> insert_return_type;
0614 #endif
0615
0616 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
0617 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
0618 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
0619 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
0620
0621 _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
0622 explicit _LIBCPP_HIDE_FROM_ABI
0623 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0624 #if _LIBCPP_STD_VER >= 14
0625 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)
0626 : unordered_set(__n, hasher(), key_equal(), __a) {}
0627 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
0628 : unordered_set(__n, __hf, key_equal(), __a) {}
0629 #endif
0630 _LIBCPP_HIDE_FROM_ABI
0631 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0632 template <class _InputIterator>
0633 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
0634 template <class _InputIterator>
0635 _LIBCPP_HIDE_FROM_ABI
0636 unordered_set(_InputIterator __first,
0637 _InputIterator __last,
0638 size_type __n,
0639 const hasher& __hf = hasher(),
0640 const key_equal& __eql = key_equal());
0641 template <class _InputIterator>
0642 _LIBCPP_HIDE_FROM_ABI unordered_set(
0643 _InputIterator __first,
0644 _InputIterator __last,
0645 size_type __n,
0646 const hasher& __hf,
0647 const key_equal& __eql,
0648 const allocator_type& __a);
0649
0650 #if _LIBCPP_STD_VER >= 23
0651 template <_ContainerCompatibleRange<value_type> _Range>
0652 _LIBCPP_HIDE_FROM_ABI unordered_set(
0653 from_range_t,
0654 _Range&& __range,
0655 size_type __n = /*implementation-defined*/ 0,
0656 const hasher& __hf = hasher(),
0657 const key_equal& __eql = key_equal(),
0658 const allocator_type& __a = allocator_type())
0659 : __table_(__hf, __eql, __a) {
0660 if (__n > 0) {
0661 __table_.__rehash_unique(__n);
0662 }
0663 insert_range(std::forward<_Range>(__range));
0664 }
0665 #endif
0666
0667 #if _LIBCPP_STD_VER >= 14
0668 template <class _InputIterator>
0669 inline _LIBCPP_HIDE_FROM_ABI
0670 unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
0671 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
0672 template <class _InputIterator>
0673 _LIBCPP_HIDE_FROM_ABI unordered_set(
0674 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
0675 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
0676 #endif
0677
0678 #if _LIBCPP_STD_VER >= 23
0679 template <_ContainerCompatibleRange<value_type> _Range>
0680 _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
0681 : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
0682
0683 template <_ContainerCompatibleRange<value_type> _Range>
0684 _LIBCPP_HIDE_FROM_ABI
0685 unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
0686 : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
0687 #endif
0688
0689 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
0690 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
0691 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
0692 #ifndef _LIBCPP_CXX03_LANG
0693 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
0694 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);
0695 _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);
0696 _LIBCPP_HIDE_FROM_ABI
0697 unordered_set(initializer_list<value_type> __il,
0698 size_type __n,
0699 const hasher& __hf = hasher(),
0700 const key_equal& __eql = key_equal());
0701 _LIBCPP_HIDE_FROM_ABI unordered_set(
0702 initializer_list<value_type> __il,
0703 size_type __n,
0704 const hasher& __hf,
0705 const key_equal& __eql,
0706 const allocator_type& __a);
0707 # if _LIBCPP_STD_VER >= 14
0708 inline _LIBCPP_HIDE_FROM_ABI
0709 unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
0710 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
0711 inline _LIBCPP_HIDE_FROM_ABI
0712 unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
0713 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
0714 # endif
0715 #endif // _LIBCPP_CXX03_LANG
0716 _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
0717 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
0718 }
0719
0720 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
0721 __table_ = __u.__table_;
0722 return *this;
0723 }
0724 #ifndef _LIBCPP_CXX03_LANG
0725 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u)
0726 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
0727 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);
0728 #endif // _LIBCPP_CXX03_LANG
0729
0730 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
0731 return allocator_type(__table_.__node_alloc());
0732 }
0733
0734 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
0735 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
0736 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
0737
0738 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
0739 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
0740 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
0741 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
0742 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
0743 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
0744
0745 #ifndef _LIBCPP_CXX03_LANG
0746 template <class... _Args>
0747 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
0748 return __table_.__emplace_unique(std::forward<_Args>(__args)...);
0749 }
0750 template <class... _Args>
0751 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
0752 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
0753 }
0754
0755 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
0756 return __table_.__insert_unique(std::move(__x));
0757 }
0758 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }
0759
0760 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
0761 #endif // _LIBCPP_CXX03_LANG
0762 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
0763
0764 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
0765 template <class _InputIterator>
0766 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0767
0768 #if _LIBCPP_STD_VER >= 23
0769 template <_ContainerCompatibleRange<value_type> _Range>
0770 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
0771 for (auto&& __element : __range) {
0772 __table_.__insert_unique(std::forward<decltype(__element)>(__element));
0773 }
0774 }
0775 #endif
0776
0777 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
0778 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
0779 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
0780 return __table_.erase(__first, __last);
0781 }
0782 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
0783
0784 #if _LIBCPP_STD_VER >= 17
0785 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
0786 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0787 "node_type with incompatible allocator passed to unordered_set::insert()");
0788 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
0789 }
0790 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {
0791 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0792 "node_type with incompatible allocator passed to unordered_set::insert()");
0793 return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));
0794 }
0795 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
0796 return __table_.template __node_handle_extract<node_type>(__key);
0797 }
0798 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
0799 return __table_.template __node_handle_extract<node_type>(__it);
0800 }
0801
0802 template <class _H2, class _P2>
0803 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
0804 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0805 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0806 __table_.__node_handle_merge_unique(__source.__table_);
0807 }
0808 template <class _H2, class _P2>
0809 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
0810 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0811 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0812 __table_.__node_handle_merge_unique(__source.__table_);
0813 }
0814 template <class _H2, class _P2>
0815 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
0816 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0817 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0818 __table_.__node_handle_merge_unique(__source.__table_);
0819 }
0820 template <class _H2, class _P2>
0821 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
0822 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0823 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0824 __table_.__node_handle_merge_unique(__source.__table_);
0825 }
0826 #endif
0827
0828 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
0829 __table_.swap(__u.__table_);
0830 }
0831
0832 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
0833 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
0834
0835 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0836 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0837 #if _LIBCPP_STD_VER >= 20
0838 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0839 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
0840 return __table_.find(__k);
0841 }
0842 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0843 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
0844 return __table_.find(__k);
0845 }
0846 #endif // _LIBCPP_STD_VER >= 20
0847
0848 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
0849 #if _LIBCPP_STD_VER >= 20
0850 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0851 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
0852 return __table_.__count_unique(__k);
0853 }
0854 #endif // _LIBCPP_STD_VER >= 20
0855
0856 #if _LIBCPP_STD_VER >= 20
0857 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
0858
0859 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0860 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
0861 return find(__k) != end();
0862 }
0863 #endif // _LIBCPP_STD_VER >= 20
0864
0865 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
0866 return __table_.__equal_range_unique(__k);
0867 }
0868 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0869 return __table_.__equal_range_unique(__k);
0870 }
0871 #if _LIBCPP_STD_VER >= 20
0872 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0873 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
0874 return __table_.__equal_range_unique(__k);
0875 }
0876 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
0877 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
0878 return __table_.__equal_range_unique(__k);
0879 }
0880 #endif // _LIBCPP_STD_VER >= 20
0881
0882 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
0883 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
0884
0885 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
0886 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
0887
0888 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
0889 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
0890 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
0891 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
0892 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
0893 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
0894
0895 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
0896 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
0897 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
0898 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
0899 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
0900 };
0901
0902 #if _LIBCPP_STD_VER >= 17
0903 template <class _InputIterator,
0904 class _Hash = hash<__iter_value_type<_InputIterator>>,
0905 class _Pred = equal_to<__iter_value_type<_InputIterator>>,
0906 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
0907 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0908 class = enable_if_t<!__is_allocator<_Hash>::value>,
0909 class = enable_if_t<!is_integral<_Hash>::value>,
0910 class = enable_if_t<!__is_allocator<_Pred>::value>,
0911 class = enable_if_t<__is_allocator<_Allocator>::value>>
0912 unordered_set(_InputIterator,
0913 _InputIterator,
0914 typename allocator_traits<_Allocator>::size_type = 0,
0915 _Hash = _Hash(),
0916 _Pred = _Pred(),
0917 _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
0918
0919 # if _LIBCPP_STD_VER >= 23
0920 template <ranges::input_range _Range,
0921 class _Hash = hash<ranges::range_value_t<_Range>>,
0922 class _Pred = equal_to<ranges::range_value_t<_Range>>,
0923 class _Allocator = allocator<ranges::range_value_t<_Range>>,
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(
0929 from_range_t,
0930 _Range&&,
0931 typename allocator_traits<_Allocator>::size_type = 0,
0932 _Hash = _Hash(),
0933 _Pred = _Pred(),
0934 _Allocator = _Allocator()) -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
0935 # endif
0936
0937 template <class _Tp,
0938 class _Hash = hash<_Tp>,
0939 class _Pred = equal_to<_Tp>,
0940 class _Allocator = allocator<_Tp>,
0941 class = enable_if_t<!__is_allocator<_Hash>::value>,
0942 class = enable_if_t<!is_integral<_Hash>::value>,
0943 class = enable_if_t<!__is_allocator<_Pred>::value>,
0944 class = enable_if_t<__is_allocator<_Allocator>::value>>
0945 unordered_set(initializer_list<_Tp>,
0946 typename allocator_traits<_Allocator>::size_type = 0,
0947 _Hash = _Hash(),
0948 _Pred = _Pred(),
0949 _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
0950
0951 template <class _InputIterator,
0952 class _Allocator,
0953 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0954 class = enable_if_t<__is_allocator<_Allocator>::value>>
0955 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
0956 -> unordered_set<__iter_value_type<_InputIterator>,
0957 hash<__iter_value_type<_InputIterator>>,
0958 equal_to<__iter_value_type<_InputIterator>>,
0959 _Allocator>;
0960
0961 template <class _InputIterator,
0962 class _Hash,
0963 class _Allocator,
0964 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0965 class = enable_if_t<!__is_allocator<_Hash>::value>,
0966 class = enable_if_t<!is_integral<_Hash>::value>,
0967 class = enable_if_t<__is_allocator<_Allocator>::value>>
0968 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
0969 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>;
0970
0971 # if _LIBCPP_STD_VER >= 23
0972
0973 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
0974 unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
0975 -> unordered_set<ranges::range_value_t<_Range>,
0976 hash<ranges::range_value_t<_Range>>,
0977 equal_to<ranges::range_value_t<_Range>>,
0978 _Allocator>;
0979
0980 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
0981 unordered_set(from_range_t, _Range&&, _Allocator)
0982 -> unordered_set<ranges::range_value_t<_Range>,
0983 hash<ranges::range_value_t<_Range>>,
0984 equal_to<ranges::range_value_t<_Range>>,
0985 _Allocator>;
0986
0987 template <ranges::input_range _Range,
0988 class _Hash,
0989 class _Allocator,
0990 class = enable_if_t<!__is_allocator<_Hash>::value>,
0991 class = enable_if_t<!is_integral<_Hash>::value>,
0992 class = enable_if_t<__is_allocator<_Allocator>::value>>
0993 unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
0994 -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
0995
0996 # endif
0997
0998 template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
0999 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1000 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1001
1002 template <class _Tp,
1003 class _Hash,
1004 class _Allocator,
1005 class = enable_if_t<!__is_allocator<_Hash>::value>,
1006 class = enable_if_t<!is_integral<_Hash>::value>,
1007 class = enable_if_t<__is_allocator<_Allocator>::value>>
1008 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1009 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1010 #endif
1011
1012 template <class _Value, class _Hash, class _Pred, class _Alloc>
1013 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)
1014 : __table_(__hf, __eql) {
1015 __table_.__rehash_unique(__n);
1016 }
1017
1018 template <class _Value, class _Hash, class _Pred, class _Alloc>
1019 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1020 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1021 : __table_(__hf, __eql, __a) {
1022 __table_.__rehash_unique(__n);
1023 }
1024
1025 template <class _Value, class _Hash, class _Pred, class _Alloc>
1026 template <class _InputIterator>
1027 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {
1028 insert(__first, __last);
1029 }
1030
1031 template <class _Value, class _Hash, class _Pred, class _Alloc>
1032 template <class _InputIterator>
1033 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1034 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1035 : __table_(__hf, __eql) {
1036 __table_.__rehash_unique(__n);
1037 insert(__first, __last);
1038 }
1039
1040 template <class _Value, class _Hash, class _Pred, class _Alloc>
1041 template <class _InputIterator>
1042 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1043 _InputIterator __first,
1044 _InputIterator __last,
1045 size_type __n,
1046 const hasher& __hf,
1047 const key_equal& __eql,
1048 const allocator_type& __a)
1049 : __table_(__hf, __eql, __a) {
1050 __table_.__rehash_unique(__n);
1051 insert(__first, __last);
1052 }
1053
1054 template <class _Value, class _Hash, class _Pred, class _Alloc>
1055 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}
1056
1057 template <class _Value, class _Hash, class _Pred, class _Alloc>
1058 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {
1059 __table_.__rehash_unique(__u.bucket_count());
1060 insert(__u.begin(), __u.end());
1061 }
1062
1063 template <class _Value, class _Hash, class _Pred, class _Alloc>
1064 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)
1065 : __table_(__u.__table_, __a) {
1066 __table_.__rehash_unique(__u.bucket_count());
1067 insert(__u.begin(), __u.end());
1068 }
1069
1070 #ifndef _LIBCPP_CXX03_LANG
1071
1072 template <class _Value, class _Hash, class _Pred, class _Alloc>
1073 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u)
1074 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1075 : __table_(std::move(__u.__table_)) {}
1076
1077 template <class _Value, class _Hash, class _Pred, class _Alloc>
1078 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a)
1079 : __table_(std::move(__u.__table_), __a) {
1080 if (__a != __u.get_allocator()) {
1081 iterator __i = __u.begin();
1082 while (__u.size() != 0)
1083 __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value()));
1084 }
1085 }
1086
1087 template <class _Value, class _Hash, class _Pred, class _Alloc>
1088 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) {
1089 insert(__il.begin(), __il.end());
1090 }
1091
1092 template <class _Value, class _Hash, class _Pred, class _Alloc>
1093 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1094 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1095 : __table_(__hf, __eql) {
1096 __table_.__rehash_unique(__n);
1097 insert(__il.begin(), __il.end());
1098 }
1099
1100 template <class _Value, class _Hash, class _Pred, class _Alloc>
1101 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1102 initializer_list<value_type> __il,
1103 size_type __n,
1104 const hasher& __hf,
1105 const key_equal& __eql,
1106 const allocator_type& __a)
1107 : __table_(__hf, __eql, __a) {
1108 __table_.__rehash_unique(__n);
1109 insert(__il.begin(), __il.end());
1110 }
1111
1112 template <class _Value, class _Hash, class _Pred, class _Alloc>
1113 inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1114 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
1115 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1116 __table_ = std::move(__u.__table_);
1117 return *this;
1118 }
1119
1120 template <class _Value, class _Hash, class _Pred, class _Alloc>
1121 inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1122 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1123 __table_.__assign_unique(__il.begin(), __il.end());
1124 return *this;
1125 }
1126
1127 #endif // _LIBCPP_CXX03_LANG
1128
1129 template <class _Value, class _Hash, class _Pred, class _Alloc>
1130 template <class _InputIterator>
1131 inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1132 for (; __first != __last; ++__first)
1133 __table_.__insert_unique(*__first);
1134 }
1135
1136 template <class _Value, class _Hash, class _Pred, class _Alloc>
1137 inline _LIBCPP_HIDE_FROM_ABI void
1138 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1139 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1140 __x.swap(__y);
1141 }
1142
1143 #if _LIBCPP_STD_VER >= 20
1144 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1145 inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type
1146 erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1147 return std::__libcpp_erase_if_container(__c, __pred);
1148 }
1149 #endif
1150
1151 template <class _Value, class _Hash, class _Pred, class _Alloc>
1152 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1153 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1154 if (__x.size() != __y.size())
1155 return false;
1156 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1157 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1158 const_iterator __j = __y.find(*__i);
1159 if (__j == __ey || !(*__i == *__j))
1160 return false;
1161 }
1162 return true;
1163 }
1164
1165 #if _LIBCPP_STD_VER <= 17
1166
1167 template <class _Value, class _Hash, class _Pred, class _Alloc>
1168 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1169 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1170 return !(__x == __y);
1171 }
1172
1173 #endif
1174
1175 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
1176 class _LIBCPP_TEMPLATE_VIS unordered_multiset {
1177 public:
1178 // types
1179 typedef _Value key_type;
1180 typedef key_type value_type;
1181 typedef __type_identity_t<_Hash> hasher;
1182 typedef __type_identity_t<_Pred> key_equal;
1183 typedef __type_identity_t<_Alloc> allocator_type;
1184 typedef value_type& reference;
1185 typedef const value_type& const_reference;
1186 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1187 "Allocator::value_type must be same type as value_type");
1188
1189 private:
1190 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1191
1192 __table __table_;
1193
1194 public:
1195 typedef typename __table::pointer pointer;
1196 typedef typename __table::const_pointer const_pointer;
1197 typedef typename __table::size_type size_type;
1198 typedef typename __table::difference_type difference_type;
1199
1200 typedef typename __table::const_iterator iterator;
1201 typedef typename __table::const_iterator const_iterator;
1202 typedef typename __table::const_local_iterator local_iterator;
1203 typedef typename __table::const_local_iterator const_local_iterator;
1204
1205 #if _LIBCPP_STD_VER >= 17
1206 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1207 #endif
1208
1209 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1210 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1211 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1212 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1213
1214 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1215 explicit _LIBCPP_HIDE_FROM_ABI
1216 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1217 _LIBCPP_HIDE_FROM_ABI
1218 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1219 #if _LIBCPP_STD_VER >= 14
1220 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a)
1221 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1222 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1223 : unordered_multiset(__n, __hf, key_equal(), __a) {}
1224 #endif
1225 template <class _InputIterator>
1226 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);
1227 template <class _InputIterator>
1228 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1229 _InputIterator __first,
1230 _InputIterator __last,
1231 size_type __n,
1232 const hasher& __hf = hasher(),
1233 const key_equal& __eql = key_equal());
1234 template <class _InputIterator>
1235 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1236 _InputIterator __first,
1237 _InputIterator __last,
1238 size_type __n,
1239 const hasher& __hf,
1240 const key_equal& __eql,
1241 const allocator_type& __a);
1242
1243 #if _LIBCPP_STD_VER >= 23
1244 template <_ContainerCompatibleRange<value_type> _Range>
1245 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1246 from_range_t,
1247 _Range&& __range,
1248 size_type __n = /*implementation-defined*/ 0,
1249 const hasher& __hf = hasher(),
1250 const key_equal& __eql = key_equal(),
1251 const allocator_type& __a = allocator_type())
1252 : __table_(__hf, __eql, __a) {
1253 if (__n > 0) {
1254 __table_.__rehash_multi(__n);
1255 }
1256 insert_range(std::forward<_Range>(__range));
1257 }
1258 #endif
1259
1260 #if _LIBCPP_STD_VER >= 14
1261 template <class _InputIterator>
1262 inline _LIBCPP_HIDE_FROM_ABI
1263 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1264 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1265 template <class _InputIterator>
1266 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1267 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1268 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1269 #endif
1270
1271 #if _LIBCPP_STD_VER >= 23
1272 template <_ContainerCompatibleRange<value_type> _Range>
1273 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1274 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1275
1276 template <_ContainerCompatibleRange<value_type> _Range>
1277 _LIBCPP_HIDE_FROM_ABI
1278 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1279 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1280 #endif
1281
1282 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);
1283 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);
1284 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1285 #ifndef _LIBCPP_CXX03_LANG
1286 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u)
1287 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1288 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1289 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il);
1290 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1291 initializer_list<value_type> __il,
1292 size_type __n,
1293 const hasher& __hf = hasher(),
1294 const key_equal& __eql = key_equal());
1295 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1296 initializer_list<value_type> __il,
1297 size_type __n,
1298 const hasher& __hf,
1299 const key_equal& __eql,
1300 const allocator_type& __a);
1301 # if _LIBCPP_STD_VER >= 14
1302 inline _LIBCPP_HIDE_FROM_ABI
1303 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1304 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1305 inline _LIBCPP_HIDE_FROM_ABI
1306 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1307 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1308 # endif
1309 #endif // _LIBCPP_CXX03_LANG
1310 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {
1311 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
1312 }
1313
1314 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {
1315 __table_ = __u.__table_;
1316 return *this;
1317 }
1318 #ifndef _LIBCPP_CXX03_LANG
1319 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u)
1320 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1321 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il);
1322 #endif // _LIBCPP_CXX03_LANG
1323
1324 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1325 return allocator_type(__table_.__node_alloc());
1326 }
1327
1328 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1329 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1330 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1331
1332 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1333 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1334 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1335 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1336 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1337 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1338
1339 #ifndef _LIBCPP_CXX03_LANG
1340 template <class... _Args>
1341 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1342 return __table_.__emplace_multi(std::forward<_Args>(__args)...);
1343 }
1344 template <class... _Args>
1345 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1346 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1347 }
1348
1349 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
1350 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
1351 return __table_.__insert_multi(__p, std::move(__x));
1352 }
1353 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1354 #endif // _LIBCPP_CXX03_LANG
1355
1356 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
1357
1358 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1359 return __table_.__insert_multi(__p, __x);
1360 }
1361
1362 template <class _InputIterator>
1363 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1364
1365 #if _LIBCPP_STD_VER >= 23
1366 template <_ContainerCompatibleRange<value_type> _Range>
1367 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1368 for (auto&& __element : __range) {
1369 __table_.__insert_multi(std::forward<decltype(__element)>(__element));
1370 }
1371 }
1372 #endif
1373
1374 #if _LIBCPP_STD_VER >= 17
1375 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1376 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1377 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1378 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1379 }
1380 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1381 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1382 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1383 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1384 }
1385 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) {
1386 return __table_.template __node_handle_extract<node_type>(__position);
1387 }
1388 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1389 return __table_.template __node_handle_extract<node_type>(__key);
1390 }
1391
1392 template <class _H2, class _P2>
1393 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
1394 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1395 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1396 return __table_.__node_handle_merge_multi(__source.__table_);
1397 }
1398 template <class _H2, class _P2>
1399 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
1400 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1401 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1402 return __table_.__node_handle_merge_multi(__source.__table_);
1403 }
1404 template <class _H2, class _P2>
1405 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
1406 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1407 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1408 return __table_.__node_handle_merge_multi(__source.__table_);
1409 }
1410 template <class _H2, class _P2>
1411 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
1412 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1413 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1414 return __table_.__node_handle_merge_multi(__source.__table_);
1415 }
1416 #endif
1417
1418 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
1419 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1420 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1421 return __table_.erase(__first, __last);
1422 }
1423 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1424
1425 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1426 __table_.swap(__u.__table_);
1427 }
1428
1429 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
1430 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
1431
1432 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1433 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1434 #if _LIBCPP_STD_VER >= 20
1435 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1436 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1437 return __table_.find(__k);
1438 }
1439 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1440 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1441 return __table_.find(__k);
1442 }
1443 #endif // _LIBCPP_STD_VER >= 20
1444
1445 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
1446 #if _LIBCPP_STD_VER >= 20
1447 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1448 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1449 return __table_.__count_multi(__k);
1450 }
1451 #endif // _LIBCPP_STD_VER >= 20
1452
1453 #if _LIBCPP_STD_VER >= 20
1454 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1455
1456 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1457 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1458 return find(__k) != end();
1459 }
1460 #endif // _LIBCPP_STD_VER >= 20
1461
1462 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1463 return __table_.__equal_range_multi(__k);
1464 }
1465 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1466 return __table_.__equal_range_multi(__k);
1467 }
1468 #if _LIBCPP_STD_VER >= 20
1469 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1470 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1471 return __table_.__equal_range_multi(__k);
1472 }
1473 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1474 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1475 return __table_.__equal_range_multi(__k);
1476 }
1477 #endif // _LIBCPP_STD_VER >= 20
1478
1479 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1480 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1481
1482 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1483 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1484
1485 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1486 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1487 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1488 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1489 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1490 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1491
1492 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1493 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1494 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1495 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
1496 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
1497 };
1498
1499 #if _LIBCPP_STD_VER >= 17
1500 template <class _InputIterator,
1501 class _Hash = hash<__iter_value_type<_InputIterator>>,
1502 class _Pred = equal_to<__iter_value_type<_InputIterator>>,
1503 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1504 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1505 class = enable_if_t<!__is_allocator<_Hash>::value>,
1506 class = enable_if_t<!is_integral<_Hash>::value>,
1507 class = enable_if_t<!__is_allocator<_Pred>::value>,
1508 class = enable_if_t<__is_allocator<_Allocator>::value>>
1509 unordered_multiset(
1510 _InputIterator,
1511 _InputIterator,
1512 typename allocator_traits<_Allocator>::size_type = 0,
1513 _Hash = _Hash(),
1514 _Pred = _Pred(),
1515 _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1516
1517 # if _LIBCPP_STD_VER >= 23
1518 template <ranges::input_range _Range,
1519 class _Hash = hash<ranges::range_value_t<_Range>>,
1520 class _Pred = equal_to<ranges::range_value_t<_Range>>,
1521 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1522 class = enable_if_t<!__is_allocator<_Hash>::value>,
1523 class = enable_if_t<!is_integral<_Hash>::value>,
1524 class = enable_if_t<!__is_allocator<_Pred>::value>,
1525 class = enable_if_t<__is_allocator<_Allocator>::value>>
1526 unordered_multiset(
1527 from_range_t,
1528 _Range&&,
1529 typename allocator_traits<_Allocator>::size_type = 0,
1530 _Hash = _Hash(),
1531 _Pred = _Pred(),
1532 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
1533 # endif
1534
1535 template <class _Tp,
1536 class _Hash = hash<_Tp>,
1537 class _Pred = equal_to<_Tp>,
1538 class _Allocator = allocator<_Tp>,
1539 class = enable_if_t<!__is_allocator<_Hash>::value>,
1540 class = enable_if_t<!is_integral<_Hash>::value>,
1541 class = enable_if_t<!__is_allocator<_Pred>::value>,
1542 class = enable_if_t<__is_allocator<_Allocator>::value>>
1543 unordered_multiset(initializer_list<_Tp>,
1544 typename allocator_traits<_Allocator>::size_type = 0,
1545 _Hash = _Hash(),
1546 _Pred = _Pred(),
1547 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1548
1549 template <class _InputIterator,
1550 class _Allocator,
1551 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1552 class = enable_if_t<__is_allocator<_Allocator>::value>>
1553 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1554 -> unordered_multiset<__iter_value_type<_InputIterator>,
1555 hash<__iter_value_type<_InputIterator>>,
1556 equal_to<__iter_value_type<_InputIterator>>,
1557 _Allocator>;
1558
1559 template <class _InputIterator,
1560 class _Hash,
1561 class _Allocator,
1562 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1563 class = enable_if_t<!__is_allocator<_Hash>::value>,
1564 class = enable_if_t<!is_integral<_Hash>::value>,
1565 class = enable_if_t<__is_allocator<_Allocator>::value>>
1566 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1567 -> unordered_multiset<__iter_value_type<_InputIterator>,
1568 _Hash,
1569 equal_to<__iter_value_type<_InputIterator>>,
1570 _Allocator>;
1571
1572 # if _LIBCPP_STD_VER >= 23
1573
1574 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1575 unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1576 -> unordered_multiset<ranges::range_value_t<_Range>,
1577 hash<ranges::range_value_t<_Range>>,
1578 equal_to<ranges::range_value_t<_Range>>,
1579 _Allocator>;
1580
1581 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1582 unordered_multiset(from_range_t, _Range&&, _Allocator)
1583 -> unordered_multiset<ranges::range_value_t<_Range>,
1584 hash<ranges::range_value_t<_Range>>,
1585 equal_to<ranges::range_value_t<_Range>>,
1586 _Allocator>;
1587
1588 template <ranges::input_range _Range,
1589 class _Hash,
1590 class _Allocator,
1591 class = enable_if_t<!__is_allocator<_Hash>::value>,
1592 class = enable_if_t<!is_integral<_Hash>::value>,
1593 class = enable_if_t<__is_allocator<_Allocator>::value>>
1594 unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1595 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
1596
1597 # endif
1598
1599 template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1600 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1601 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1602
1603 template <class _Tp,
1604 class _Hash,
1605 class _Allocator,
1606 class = enable_if_t<!__is_allocator<_Hash>::value>,
1607 class = enable_if_t<!is_integral<_Hash>::value>,
1608 class = enable_if_t<__is_allocator<_Allocator>::value>>
1609 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1610 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1611 #endif
1612
1613 template <class _Value, class _Hash, class _Pred, class _Alloc>
1614 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1615 size_type __n, const hasher& __hf, const key_equal& __eql)
1616 : __table_(__hf, __eql) {
1617 __table_.__rehash_multi(__n);
1618 }
1619
1620 template <class _Value, class _Hash, class _Pred, class _Alloc>
1621 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1622 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1623 : __table_(__hf, __eql, __a) {
1624 __table_.__rehash_multi(__n);
1625 }
1626
1627 template <class _Value, class _Hash, class _Pred, class _Alloc>
1628 template <class _InputIterator>
1629 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {
1630 insert(__first, __last);
1631 }
1632
1633 template <class _Value, class _Hash, class _Pred, class _Alloc>
1634 template <class _InputIterator>
1635 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1636 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1637 : __table_(__hf, __eql) {
1638 __table_.__rehash_multi(__n);
1639 insert(__first, __last);
1640 }
1641
1642 template <class _Value, class _Hash, class _Pred, class _Alloc>
1643 template <class _InputIterator>
1644 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1645 _InputIterator __first,
1646 _InputIterator __last,
1647 size_type __n,
1648 const hasher& __hf,
1649 const key_equal& __eql,
1650 const allocator_type& __a)
1651 : __table_(__hf, __eql, __a) {
1652 __table_.__rehash_multi(__n);
1653 insert(__first, __last);
1654 }
1655
1656 template <class _Value, class _Hash, class _Pred, class _Alloc>
1657 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)
1658 : __table_(__a) {}
1659
1660 template <class _Value, class _Hash, class _Pred, class _Alloc>
1661 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)
1662 : __table_(__u.__table_) {
1663 __table_.__rehash_multi(__u.bucket_count());
1664 insert(__u.begin(), __u.end());
1665 }
1666
1667 template <class _Value, class _Hash, class _Pred, class _Alloc>
1668 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1669 const unordered_multiset& __u, const allocator_type& __a)
1670 : __table_(__u.__table_, __a) {
1671 __table_.__rehash_multi(__u.bucket_count());
1672 insert(__u.begin(), __u.end());
1673 }
1674
1675 #ifndef _LIBCPP_CXX03_LANG
1676
1677 template <class _Value, class _Hash, class _Pred, class _Alloc>
1678 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u)
1679 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1680 : __table_(std::move(__u.__table_)) {}
1681
1682 template <class _Value, class _Hash, class _Pred, class _Alloc>
1683 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1684 unordered_multiset&& __u, const allocator_type& __a)
1685 : __table_(std::move(__u.__table_), __a) {
1686 if (__a != __u.get_allocator()) {
1687 iterator __i = __u.begin();
1688 while (__u.size() != 0)
1689 __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value()));
1690 }
1691 }
1692
1693 template <class _Value, class _Hash, class _Pred, class _Alloc>
1694 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) {
1695 insert(__il.begin(), __il.end());
1696 }
1697
1698 template <class _Value, class _Hash, class _Pred, class _Alloc>
1699 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1700 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1701 : __table_(__hf, __eql) {
1702 __table_.__rehash_multi(__n);
1703 insert(__il.begin(), __il.end());
1704 }
1705
1706 template <class _Value, class _Hash, class _Pred, class _Alloc>
1707 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1708 initializer_list<value_type> __il,
1709 size_type __n,
1710 const hasher& __hf,
1711 const key_equal& __eql,
1712 const allocator_type& __a)
1713 : __table_(__hf, __eql, __a) {
1714 __table_.__rehash_multi(__n);
1715 insert(__il.begin(), __il.end());
1716 }
1717
1718 template <class _Value, class _Hash, class _Pred, class _Alloc>
1719 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1720 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u)
1721 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1722 __table_ = std::move(__u.__table_);
1723 return *this;
1724 }
1725
1726 template <class _Value, class _Hash, class _Pred, class _Alloc>
1727 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1728 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1729 __table_.__assign_multi(__il.begin(), __il.end());
1730 return *this;
1731 }
1732
1733 #endif // _LIBCPP_CXX03_LANG
1734
1735 template <class _Value, class _Hash, class _Pred, class _Alloc>
1736 template <class _InputIterator>
1737 inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1738 for (; __first != __last; ++__first)
1739 __table_.__insert_multi(*__first);
1740 }
1741
1742 template <class _Value, class _Hash, class _Pred, class _Alloc>
1743 inline _LIBCPP_HIDE_FROM_ABI void
1744 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1745 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1746 __x.swap(__y);
1747 }
1748
1749 #if _LIBCPP_STD_VER >= 20
1750 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1751 inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type
1752 erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1753 return std::__libcpp_erase_if_container(__c, __pred);
1754 }
1755 #endif
1756
1757 template <class _Value, class _Hash, class _Pred, class _Alloc>
1758 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1759 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1760 if (__x.size() != __y.size())
1761 return false;
1762 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1763 typedef pair<const_iterator, const_iterator> _EqRng;
1764 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
1765 _EqRng __xeq = __x.equal_range(*__i);
1766 _EqRng __yeq = __y.equal_range(*__i);
1767 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
1768 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1769 return false;
1770 __i = __xeq.second;
1771 }
1772 return true;
1773 }
1774
1775 #if _LIBCPP_STD_VER <= 17
1776
1777 template <class _Value, class _Hash, class _Pred, class _Alloc>
1778 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1779 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1780 return !(__x == __y);
1781 }
1782
1783 #endif
1784
1785 _LIBCPP_END_NAMESPACE_STD
1786
1787 #if _LIBCPP_STD_VER >= 17
1788 _LIBCPP_BEGIN_NAMESPACE_STD
1789 namespace pmr {
1790 template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1791 using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1792
1793 template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1794 using unordered_multiset _LIBCPP_AVAILABILITY_PMR =
1795 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1796 } // namespace pmr
1797 _LIBCPP_END_NAMESPACE_STD
1798 #endif
1799
1800 _LIBCPP_POP_MACROS
1801
1802 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1803 # include <__cxx03/concepts>
1804 # include <__cxx03/cstdlib>
1805 # include <__cxx03/functional>
1806 # include <__cxx03/iterator>
1807 # include <__cxx03/stdexcept>
1808 # include <__cxx03/type_traits>
1809 #endif
1810
1811 #endif // _LIBCPP___CXX03_UNORDERED_SET
