llvm-project

1
// -*- C++ -*-
2
//===----------------------------------------------------------------------===//
3
//
4
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5
// See https://llvm.org/LICENSE.txt for license information.
6
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7
//
8
//===----------------------------------------------------------------------===//
9

10
#ifndef _LIBCPP_UNORDERED_SET
11
#define _LIBCPP_UNORDERED_SET
12

13
// clang-format off
14

15
/*
16

17
    unordered_set synopsis
18

19
#include <initializer_list>
20

21
namespace std
22
{
23

24
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
25
          class Alloc = allocator<Value>>
26
class unordered_set
27
{
28
public:
29
    // types
30
    typedef Value                                                      key_type;
31
    typedef key_type                                                   value_type;
32
    typedef Hash                                                       hasher;
33
    typedef Pred                                                       key_equal;
34
    typedef Alloc                                                      allocator_type;
35
    typedef value_type&                                                reference;
36
    typedef const value_type&                                          const_reference;
37
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
38
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
39
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
40
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41

42
    typedef /unspecified/ iterator;
43
    typedef /unspecified/ const_iterator;
44
    typedef /unspecified/ local_iterator;
45
    typedef /unspecified/ const_local_iterator;
46

47
    typedef unspecified node_type unspecified;                            // C++17
48
    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
49

50
    unordered_set()
51
        noexcept(
52
            is_nothrow_default_constructible<hasher>::value &&
53
            is_nothrow_default_constructible<key_equal>::value &&
54
            is_nothrow_default_constructible<allocator_type>::value);
55
    explicit unordered_set(size_type n, const hasher& hf = hasher(),
56
                           const key_equal& eql = key_equal(),
57
                           const allocator_type& a = allocator_type());
58
    template <class InputIterator>
59
        unordered_set(InputIterator f, InputIterator l,
60
                      size_type n = 0, const hasher& hf = hasher(),
61
                      const key_equal& eql = key_equal(),
62
                      const allocator_type& a = allocator_type());
63
    template<container-compatible-range<value_type> R>
64
      unordered_set(from_range_t, R&& rg, size_type n = see below,
65
        const hasher& hf = hasher(), const key_equal& eql = key_equal(),
66
        const allocator_type& a = allocator_type()); // C++23
67
    explicit unordered_set(const allocator_type&);
68
    unordered_set(const unordered_set&);
69
    unordered_set(const unordered_set&, const Allocator&);
70
    unordered_set(unordered_set&&)
71
        noexcept(
72
            is_nothrow_move_constructible<hasher>::value &&
73
            is_nothrow_move_constructible<key_equal>::value &&
74
            is_nothrow_move_constructible<allocator_type>::value);
75
    unordered_set(unordered_set&&, const Allocator&);
76
    unordered_set(initializer_list<value_type>, size_type n = 0,
77
                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
78
                  const allocator_type& a = allocator_type());
79
    unordered_set(size_type n, const allocator_type& a); // C++14
80
    unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
81
    template <class InputIterator>
82
      unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
83
    template <class InputIterator>
84
      unordered_set(InputIterator f, InputIterator l, size_type n,
85
                    const hasher& hf,  const allocator_type& a); // C++14
86
    template<container-compatible-range<value_type> R>
87
      unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
88
        : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
89
    template<container-compatible-range<value_type> R>
90
      unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
91
        : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
92
    unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
93
    unordered_set(initializer_list<value_type> il, size_type n,
94
                  const hasher& hf,  const allocator_type& a); // C++14
95
    ~unordered_set();
96
    unordered_set& operator=(const unordered_set&);
97
    unordered_set& operator=(unordered_set&&)
98
        noexcept(
99
            allocator_type::propagate_on_container_move_assignment::value &&
100
            is_nothrow_move_assignable<allocator_type>::value &&
101
            is_nothrow_move_assignable<hasher>::value &&
102
            is_nothrow_move_assignable<key_equal>::value);
103
    unordered_set& operator=(initializer_list<value_type>);
104

105
    allocator_type get_allocator() const noexcept;
106

107
    bool      empty() const noexcept;
108
    size_type size() const noexcept;
109
    size_type max_size() const noexcept;
110

111
    iterator       begin() noexcept;
112
    iterator       end() noexcept;
113
    const_iterator begin()  const noexcept;
114
    const_iterator end()    const noexcept;
115
    const_iterator cbegin() const noexcept;
116
    const_iterator cend()   const noexcept;
117

118
    template <class... Args>
119
        pair<iterator, bool> emplace(Args&&... args);
120
    template <class... Args>
121
        iterator emplace_hint(const_iterator position, Args&&... args);
122
    pair<iterator, bool> insert(const value_type& obj);
123
    pair<iterator, bool> insert(value_type&& obj);
124
    iterator insert(const_iterator hint, const value_type& obj);
125
    iterator insert(const_iterator hint, value_type&& obj);
126
    template <class InputIterator>
127
        void insert(InputIterator first, InputIterator last);
128
    template<container-compatible-range<value_type> R>
129
      void insert_range(R&& rg);                                      // C++23
130
    void insert(initializer_list<value_type>);
131

132
    node_type extract(const_iterator position);                       // C++17
133
    node_type extract(const key_type& x);                             // C++17
134
    insert_return_type insert(node_type&& nh);                        // C++17
135
    iterator           insert(const_iterator hint, node_type&& nh);   // C++17
136

137
    iterator erase(const_iterator position);
138
    iterator erase(iterator position);  // C++14
139
    size_type erase(const key_type& k);
140
    iterator erase(const_iterator first, const_iterator last);
141
    void clear() noexcept;
142

143
    template<class H2, class P2>
144
      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
145
    template<class H2, class P2>
146
      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
147
    template<class H2, class P2>
148
      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
149
    template<class H2, class P2>
150
      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
151

152
    void swap(unordered_set&)
153
       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
154
                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
155
                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
156

157
    hasher hash_function() const;
158
    key_equal key_eq() const;
159

160
    iterator       find(const key_type& k);
161
    const_iterator find(const key_type& k) const;
162
    template<typename K>
163
        iterator find(const K& x);              // C++20
164
    template<typename K>
165
        const_iterator find(const K& x) const;  // C++20
166
    size_type count(const key_type& k) const;
167
    template<typename K>
168
        size_type count(const K& k) const; // C++20
169
    bool contains(const key_type& k) const; // C++20
170
    template<typename K>
171
        bool contains(const K& k) const; // C++20
172
    pair<iterator, iterator>             equal_range(const key_type& k);
173
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
174
    template<typename K>
175
        pair<iterator, iterator>             equal_range(const K& k); // C++20
176
    template<typename K>
177
        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
178

179
    size_type bucket_count() const noexcept;
180
    size_type max_bucket_count() const noexcept;
181

182
    size_type bucket_size(size_type n) const;
183
    size_type bucket(const key_type& k) const;
184

185
    local_iterator       begin(size_type n);
186
    local_iterator       end(size_type n);
187
    const_local_iterator begin(size_type n) const;
188
    const_local_iterator end(size_type n) const;
189
    const_local_iterator cbegin(size_type n) const;
190
    const_local_iterator cend(size_type n) const;
191

192
    float load_factor() const noexcept;
193
    float max_load_factor() const noexcept;
194
    void max_load_factor(float z);
195
    void rehash(size_type n);
196
    void reserve(size_type n);
197
};
198

199
template<class InputIterator,
200
    class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
201
    class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
202
    class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
203
unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
204
    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
205
  -> unordered_set<typename iterator_traits<InputIterator>::value_type,
206
        Hash, Pred, Allocator>; // C++17
207

208
template<ranges::input_range R,
209
         class Hash = hash<ranges::range_value_t<R>>,
210
         class Pred = equal_to<ranges::range_value_t<R>>,
211
         class Allocator = allocator<ranges::range_value_t<R>>>
212
  unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
213
    -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
214

215
template<class T, class Hash = hash<T>,
216
          class Pred = equal_to<T>, class Allocator = allocator<T>>
217
unordered_set(initializer_list<T>, typename see below::size_type = see below,
218
    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
219
  -> unordered_set<T, Hash, Pred, Allocator>; // C++17
220

221
template<class InputIterator,  class Allocator>
222
unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
223
  -> unordered_set<typename iterator_traits<InputIterator>::value_type,
224
        hash<typename iterator_traits<InputIterator>::value_type>,
225
        equal_to<typename iterator_traits<InputIterator>::value_type>,
226
        Allocator>; // C++17
227

228
template<class InputIterator, class Hash, class Allocator>
229
unordered_set(InputIterator, InputIterator, typename see below::size_type,
230
    Hash, Allocator)
231
  -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
232
        equal_to<typename iterator_traits<InputIterator>::value_type>,
233
        Allocator>; // C++17
234

235
template<ranges::input_range R, class Allocator>
236
  unordered_set(from_range_t, R&&, typename see below::size_type, Allocator)
237
    -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
238
                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
239

240
template<ranges::input_range R, class Allocator>
241
  unordered_set(from_range_t, R&&, Allocator)
242
    -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
243
                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
244

245
template<ranges::input_range R, class Hash, class Allocator>
246
  unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
247
    -> unordered_set<ranges::range_value_t<R>, Hash,
248
                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
249

250
template<class T, class Allocator>
251
unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
252
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17
253

254
template<class T, class Hash, class Allocator>
255
unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
256
  -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17
257

258
template <class Value, class Hash, class Pred, class Alloc>
259
    void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
260
              unordered_set<Value, Hash, Pred, Alloc>& y)
261
              noexcept(noexcept(x.swap(y)));
262

263
template <class Value, class Hash, class Pred, class Alloc>
264
    bool
265
    operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
266
               const unordered_set<Value, Hash, Pred, Alloc>& y);
267

268
template <class Value, class Hash, class Pred, class Alloc>
269
    bool
270
    operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
271
               const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20
272

273
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
274
          class Alloc = allocator<Value>>
275
class unordered_multiset
276
{
277
public:
278
    // types
279
    typedef Value                                                      key_type;
280
    typedef key_type                                                   value_type;
281
    typedef Hash                                                       hasher;
282
    typedef Pred                                                       key_equal;
283
    typedef Alloc                                                      allocator_type;
284
    typedef value_type&                                                reference;
285
    typedef const value_type&                                          const_reference;
286
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
287
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
288
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
289
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
290

291
    typedef /unspecified/ iterator;
292
    typedef /unspecified/ const_iterator;
293
    typedef /unspecified/ local_iterator;
294
    typedef /unspecified/ const_local_iterator;
295

296
    typedef unspecified node_type unspecified;   // C++17
297

298
    unordered_multiset()
299
        noexcept(
300
            is_nothrow_default_constructible<hasher>::value &&
301
            is_nothrow_default_constructible<key_equal>::value &&
302
            is_nothrow_default_constructible<allocator_type>::value);
303
    explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
304
                           const key_equal& eql = key_equal(),
305
                           const allocator_type& a = allocator_type());
306
    template <class InputIterator>
307
        unordered_multiset(InputIterator f, InputIterator l,
308
                      size_type n = 0, const hasher& hf = hasher(),
309
                      const key_equal& eql = key_equal(),
310
                      const allocator_type& a = allocator_type());
311
    template<container-compatible-range<value_type> R>
312
      unordered_multiset(from_range_t, R&& rg, size_type n = see below,
313
        const hasher& hf = hasher(), const key_equal& eql = key_equal(),
314
        const allocator_type& a = allocator_type()); // C++23
315
    explicit unordered_multiset(const allocator_type&);
316
    unordered_multiset(const unordered_multiset&);
317
    unordered_multiset(const unordered_multiset&, const Allocator&);
318
    unordered_multiset(unordered_multiset&&)
319
        noexcept(
320
            is_nothrow_move_constructible<hasher>::value &&
321
            is_nothrow_move_constructible<key_equal>::value &&
322
            is_nothrow_move_constructible<allocator_type>::value);
323
    unordered_multiset(unordered_multiset&&, const Allocator&);
324
    unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
325
                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
326
                  const allocator_type& a = allocator_type());
327
    unordered_multiset(size_type n, const allocator_type& a); // C++14
328
    unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
329
    template <class InputIterator>
330
      unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
331
    template <class InputIterator>
332
      unordered_multiset(InputIterator f, InputIterator l, size_type n,
333
                         const hasher& hf, const allocator_type& a); // C++14
334
    template<container-compatible-range<value_type> R>
335
      unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
336
        : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
337
    template<container-compatible-range<value_type> R>
338
      unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
339
        : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
340
    unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
341
    unordered_multiset(initializer_list<value_type> il, size_type n,
342
                       const hasher& hf,  const allocator_type& a); // C++14
343
    ~unordered_multiset();
344
    unordered_multiset& operator=(const unordered_multiset&);
345
    unordered_multiset& operator=(unordered_multiset&&)
346
        noexcept(
347
            allocator_type::propagate_on_container_move_assignment::value &&
348
            is_nothrow_move_assignable<allocator_type>::value &&
349
            is_nothrow_move_assignable<hasher>::value &&
350
            is_nothrow_move_assignable<key_equal>::value);
351
    unordered_multiset& operator=(initializer_list<value_type>);
352

353
    allocator_type get_allocator() const noexcept;
354

355
    bool      empty() const noexcept;
356
    size_type size() const noexcept;
357
    size_type max_size() const noexcept;
358

359
    iterator       begin() noexcept;
360
    iterator       end() noexcept;
361
    const_iterator begin()  const noexcept;
362
    const_iterator end()    const noexcept;
363
    const_iterator cbegin() const noexcept;
364
    const_iterator cend()   const noexcept;
365

366
    template <class... Args>
367
        iterator emplace(Args&&... args);
368
    template <class... Args>
369
        iterator emplace_hint(const_iterator position, Args&&... args);
370
    iterator insert(const value_type& obj);
371
    iterator insert(value_type&& obj);
372
    iterator insert(const_iterator hint, const value_type& obj);
373
    iterator insert(const_iterator hint, value_type&& obj);
374
    template <class InputIterator>
375
        void insert(InputIterator first, InputIterator last);
376
    template<container-compatible-range<value_type> R>
377
      void insert_range(R&& rg);                            // C++23
378
    void insert(initializer_list<value_type>);
379

380
    node_type extract(const_iterator position);             // C++17
381
    node_type extract(const key_type& x);                   // C++17
382
    iterator insert(node_type&& nh);                        // C++17
383
    iterator insert(const_iterator hint, node_type&& nh);   // C++17
384

385
    iterator erase(const_iterator position);
386
    iterator erase(iterator position);  // C++14
387
    size_type erase(const key_type& k);
388
    iterator erase(const_iterator first, const_iterator last);
389
    void clear() noexcept;
390

391
    template<class H2, class P2>
392
      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
393
    template<class H2, class P2>
394
      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
395
    template<class H2, class P2>
396
      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
397
    template<class H2, class P2>
398
      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
399

400
    void swap(unordered_multiset&)
401
       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
402
                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
403
                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
404

405
    hasher hash_function() const;
406
    key_equal key_eq() const;
407

408
    iterator       find(const key_type& k);
409
    const_iterator find(const key_type& k) const;
410
    template<typename K>
411
        iterator find(const K& x);              // C++20
412
    template<typename K>
413
        const_iterator find(const K& x) const;  // C++20
414
    size_type count(const key_type& k) const;
415
    template<typename K>
416
        size_type count(const K& k) const; // C++20
417
    bool contains(const key_type& k) const; // C++20
418
    template<typename K>
419
        bool contains(const K& k) const; // C++20
420
    pair<iterator, iterator>             equal_range(const key_type& k);
421
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
422
    template<typename K>
423
        pair<iterator, iterator>             equal_range(const K& k); // C++20
424
    template<typename K>
425
        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
426

427
    size_type bucket_count() const noexcept;
428
    size_type max_bucket_count() const noexcept;
429

430
    size_type bucket_size(size_type n) const;
431
    size_type bucket(const key_type& k) const;
432

433
    local_iterator       begin(size_type n);
434
    local_iterator       end(size_type n);
435
    const_local_iterator begin(size_type n) const;
436
    const_local_iterator end(size_type n) const;
437
    const_local_iterator cbegin(size_type n) const;
438
    const_local_iterator cend(size_type n) const;
439

440
    float load_factor() const noexcept;
441
    float max_load_factor() const noexcept;
442
    void max_load_factor(float z);
443
    void rehash(size_type n);
444
    void reserve(size_type n);
445
};
446

447
template<class InputIterator,
448
    class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
449
    class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
450
    class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
451
unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
452
    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
453
  -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
454
        Hash, Pred, Allocator>; // C++17
455

456
template<ranges::input_range R,
457
         class Hash = hash<ranges::range_value_t<R>>,
458
         class Pred = equal_to<ranges::range_value_t<R>>,
459
         class Allocator = allocator<ranges::range_value_t<R>>>
460
  unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
461
    -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
462

463
template<class T, class Hash = hash<T>,
464
          class Pred = equal_to<T>, class Allocator = allocator<T>>
465
unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
466
    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
467
  -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17
468

469
template<class InputIterator,  class Allocator>
470
unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
471
  -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
472
        hash<typename iterator_traits<InputIterator>::value_type>,
473
        equal_to<typename iterator_traits<InputIterator>::value_type>,
474
        Allocator>; // C++17
475

476
template<class InputIterator,  class Hash, class Allocator>
477
unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
478
    Hash, Allocator)
479
  -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
480
        equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
481

482
template<ranges::input_range R, class Allocator>
483
  unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator)
484
    -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
485
                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
486

487
template<ranges::input_range R, class Allocator>
488
  unordered_multiset(from_range_t, R&&, Allocator)
489
    -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
490
                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
491

492
template<ranges::input_range R, class Hash, class Allocator>
493
  unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
494
    -> unordered_multiset<ranges::range_value_t<R>, Hash,
495
                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
496

497
template<class T, class Allocator>
498
unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
499
  -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17
500

501
template<class T, class Hash, class Allocator>
502
unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
503
  -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17
504

505
template <class Value, class Hash, class Pred, class Alloc>
506
    void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
507
              unordered_multiset<Value, Hash, Pred, Alloc>& y)
508
              noexcept(noexcept(x.swap(y)));
509

510
template <class K, class T, class H, class P, class A, class Predicate>
511
    typename unordered_set<K, T, H, P, A>::size_type
512
    erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred);       // C++20
513

514
template <class K, class T, class H, class P, class A, class Predicate>
515
    typename unordered_multiset<K, T, H, P, A>::size_type
516
    erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred);  // C++20
517

518

519
template <class Value, class Hash, class Pred, class Alloc>
520
    bool
521
    operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
522
               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
523

524
template <class Value, class Hash, class Pred, class Alloc>
525
    bool
526
    operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
527
               const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20
528
}  // std
529

530
*/
531

532
// clang-format on
533

534
#include <__algorithm/is_permutation.h>
535
#include <__assert>
536
#include <__config>
537
#include <__functional/is_transparent.h>
538
#include <__functional/operations.h>
539
#include <__hash_table>
540
#include <__iterator/distance.h>
541
#include <__iterator/erase_if_container.h>
542
#include <__iterator/iterator_traits.h>
543
#include <__iterator/ranges_iterator_traits.h>
544
#include <__memory/addressof.h>
545
#include <__memory/allocator.h>
546
#include <__memory_resource/polymorphic_allocator.h>
547
#include <__node_handle>
548
#include <__ranges/concepts.h>
549
#include <__ranges/container_compatible_range.h>
550
#include <__ranges/from_range.h>
551
#include <__type_traits/is_allocator.h>
552
#include <__utility/forward.h>
553
#include <version>
554

555
// standard-mandated includes
556

557
// [iterator.range]
558
#include <__iterator/access.h>
559
#include <__iterator/data.h>
560
#include <__iterator/empty.h>
561
#include <__iterator/reverse_access.h>
562
#include <__iterator/size.h>
563

564
// [unord.set.syn]
565
#include <compare>
566
#include <initializer_list>
567

568
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
569
#  pragma GCC system_header
570
#endif
571

572
_LIBCPP_PUSH_MACROS
573
#include <__undef_macros>
574

575
_LIBCPP_BEGIN_NAMESPACE_STD
576

577
template <class _Value, class _Hash, class _Pred, class _Alloc>
578
class unordered_multiset;
579

580
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
581
class _LIBCPP_TEMPLATE_VIS unordered_set {
582
public:
583
  // types
584
  typedef _Value key_type;
585
  typedef key_type value_type;
586
  typedef __type_identity_t<_Hash> hasher;
587
  typedef __type_identity_t<_Pred> key_equal;
588
  typedef __type_identity_t<_Alloc> allocator_type;
589
  typedef value_type& reference;
590
  typedef const value_type& const_reference;
591
  static_assert(__check_valid_allocator<allocator_type>::value, "");
592
  static_assert(is_same<value_type, typename allocator_type::value_type>::value,
593
                "Allocator::value_type must be same type as value_type");
594

595
private:
596
  typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
597

598
  __table __table_;
599

600
public:
601
  typedef typename __table::pointer pointer;
602
  typedef typename __table::const_pointer const_pointer;
603
  typedef typename __table::size_type size_type;
604
  typedef typename __table::difference_type difference_type;
605

606
  typedef typename __table::const_iterator iterator;
607
  typedef typename __table::const_iterator const_iterator;
608
  typedef typename __table::const_local_iterator local_iterator;
609
  typedef typename __table::const_local_iterator const_local_iterator;
610

611
#if _LIBCPP_STD_VER >= 17
612
  typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
613
  typedef __insert_return_type<iterator, node_type> insert_return_type;
614
#endif
615

616
  template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
617
  friend class _LIBCPP_TEMPLATE_VIS unordered_set;
618
  template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
619
  friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
620

621
  _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
622
  explicit _LIBCPP_HIDE_FROM_ABI
623
  unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
624
#if _LIBCPP_STD_VER >= 14
625
  inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)
626
      : unordered_set(__n, hasher(), key_equal(), __a) {}
627
  inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
628
      : unordered_set(__n, __hf, key_equal(), __a) {}
629
#endif
630
  _LIBCPP_HIDE_FROM_ABI
631
  unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
632
  template <class _InputIterator>
633
  _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
634
  template <class _InputIterator>
635
  _LIBCPP_HIDE_FROM_ABI
636
  unordered_set(_InputIterator __first,
637
                _InputIterator __last,
638
                size_type __n,
639
                const hasher& __hf     = hasher(),
640
                const key_equal& __eql = key_equal());
641
  template <class _InputIterator>
642
  _LIBCPP_HIDE_FROM_ABI unordered_set(
643
      _InputIterator __first,
644
      _InputIterator __last,
645
      size_type __n,
646
      const hasher& __hf,
647
      const key_equal& __eql,
648
      const allocator_type& __a);
649

650
#if _LIBCPP_STD_VER >= 23
651
  template <_ContainerCompatibleRange<value_type> _Range>
652
  _LIBCPP_HIDE_FROM_ABI unordered_set(
653
      from_range_t,
654
      _Range&& __range,
655
      size_type __n             = /*implementation-defined*/ 0,
656
      const hasher& __hf        = hasher(),
657
      const key_equal& __eql    = key_equal(),
658
      const allocator_type& __a = allocator_type())
659
      : __table_(__hf, __eql, __a) {
660
    if (__n > 0) {
661
      __table_.__rehash_unique(__n);
662
    }
663
    insert_range(std::forward<_Range>(__range));
664
  }
665
#endif
666

667
#if _LIBCPP_STD_VER >= 14
668
  template <class _InputIterator>
669
  inline _LIBCPP_HIDE_FROM_ABI
670
  unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
671
      : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
672
  template <class _InputIterator>
673
  _LIBCPP_HIDE_FROM_ABI unordered_set(
674
      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
675
      : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
676
#endif
677

678
#if _LIBCPP_STD_VER >= 23
679
  template <_ContainerCompatibleRange<value_type> _Range>
680
  _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
681
      : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
682

683
  template <_ContainerCompatibleRange<value_type> _Range>
684
  _LIBCPP_HIDE_FROM_ABI
685
  unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
686
      : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
687
#endif
688

689
  _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
690
  _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
691
  _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
692
#ifndef _LIBCPP_CXX03_LANG
693
  _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
694
  _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);
695
  _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);
696
  _LIBCPP_HIDE_FROM_ABI
697
  unordered_set(initializer_list<value_type> __il,
698
                size_type __n,
699
                const hasher& __hf     = hasher(),
700
                const key_equal& __eql = key_equal());
701
  _LIBCPP_HIDE_FROM_ABI unordered_set(
702
      initializer_list<value_type> __il,
703
      size_type __n,
704
      const hasher& __hf,
705
      const key_equal& __eql,
706
      const allocator_type& __a);
707
#  if _LIBCPP_STD_VER >= 14
708
  inline _LIBCPP_HIDE_FROM_ABI
709
  unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
710
      : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
711
  inline _LIBCPP_HIDE_FROM_ABI
712
  unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
713
      : unordered_set(__il, __n, __hf, key_equal(), __a) {}
714
#  endif
715
#endif // _LIBCPP_CXX03_LANG
716
  _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
717
    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
718
  }
719

720
  _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
721
    __table_ = __u.__table_;
722
    return *this;
723
  }
724
#ifndef _LIBCPP_CXX03_LANG
725
  _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u)
726
      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
727
  _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);
728
#endif // _LIBCPP_CXX03_LANG
729

730
  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
731
    return allocator_type(__table_.__node_alloc());
732
  }
733

734
  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
735
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
736
  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
737

738
  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
739
  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
740
  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
741
  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
742
  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
743
  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
744

745
#ifndef _LIBCPP_CXX03_LANG
746
  template <class... _Args>
747
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
748
    return __table_.__emplace_unique(std::forward<_Args>(__args)...);
749
  }
750
  template <class... _Args>
751
  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
752
    return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
753
  }
754

755
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
756
    return __table_.__insert_unique(std::move(__x));
757
  }
758
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }
759

760
  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
761
#endif // _LIBCPP_CXX03_LANG
762
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
763

764
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
765
  template <class _InputIterator>
766
  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
767

768
#if _LIBCPP_STD_VER >= 23
769
  template <_ContainerCompatibleRange<value_type> _Range>
770
  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
771
    for (auto&& __element : __range) {
772
      __table_.__insert_unique(std::forward<decltype(__element)>(__element));
773
    }
774
  }
775
#endif
776

777
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
778
  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
779
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
780
    return __table_.erase(__first, __last);
781
  }
782
  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
783

784
#if _LIBCPP_STD_VER >= 17
785
  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
786
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
787
                                        "node_type with incompatible allocator passed to unordered_set::insert()");
788
    return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
789
  }
790
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {
791
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
792
                                        "node_type with incompatible allocator passed to unordered_set::insert()");
793
    return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));
794
  }
795
  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
796
    return __table_.template __node_handle_extract<node_type>(__key);
797
  }
798
  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
799
    return __table_.template __node_handle_extract<node_type>(__it);
800
  }
801

802
  template <class _H2, class _P2>
803
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
804
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
805
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
806
    __table_.__node_handle_merge_unique(__source.__table_);
807
  }
808
  template <class _H2, class _P2>
809
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
810
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
811
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
812
    __table_.__node_handle_merge_unique(__source.__table_);
813
  }
814
  template <class _H2, class _P2>
815
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
816
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
817
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
818
    __table_.__node_handle_merge_unique(__source.__table_);
819
  }
820
  template <class _H2, class _P2>
821
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
822
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
823
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
824
    __table_.__node_handle_merge_unique(__source.__table_);
825
  }
826
#endif
827

828
  _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
829
    __table_.swap(__u.__table_);
830
  }
831

832
  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
833
  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
834

835
  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
836
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
837
#if _LIBCPP_STD_VER >= 20
838
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
839
  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
840
    return __table_.find(__k);
841
  }
842
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
843
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
844
    return __table_.find(__k);
845
  }
846
#endif // _LIBCPP_STD_VER >= 20
847

848
  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
849
#if _LIBCPP_STD_VER >= 20
850
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
851
  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
852
    return __table_.__count_unique(__k);
853
  }
854
#endif // _LIBCPP_STD_VER >= 20
855

856
#if _LIBCPP_STD_VER >= 20
857
  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
858

859
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
860
  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
861
    return find(__k) != end();
862
  }
863
#endif // _LIBCPP_STD_VER >= 20
864

865
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
866
    return __table_.__equal_range_unique(__k);
867
  }
868
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
869
    return __table_.__equal_range_unique(__k);
870
  }
871
#if _LIBCPP_STD_VER >= 20
872
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
873
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
874
    return __table_.__equal_range_unique(__k);
875
  }
876
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
877
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
878
    return __table_.__equal_range_unique(__k);
879
  }
880
#endif // _LIBCPP_STD_VER >= 20
881

882
  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
883
  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
884

885
  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
886
  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
887

888
  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
889
  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
890
  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
891
  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
892
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
893
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
894

895
  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
896
  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
897
  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
898
  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
899
  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
900
};
901

902
#if _LIBCPP_STD_VER >= 17
903
template <class _InputIterator,
904
          class _Hash      = hash<__iter_value_type<_InputIterator>>,
905
          class _Pred      = equal_to<__iter_value_type<_InputIterator>>,
906
          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
907
          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
908
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
909
          class            = enable_if_t<!is_integral<_Hash>::value>,
910
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
911
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
912
unordered_set(_InputIterator,
913
              _InputIterator,
914
              typename allocator_traits<_Allocator>::size_type = 0,
915
              _Hash                                            = _Hash(),
916
              _Pred                                            = _Pred(),
917
              _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
918

919
#  if _LIBCPP_STD_VER >= 23
920
template <ranges::input_range _Range,
921
          class _Hash      = hash<ranges::range_value_t<_Range>>,
922
          class _Pred      = equal_to<ranges::range_value_t<_Range>>,
923
          class _Allocator = allocator<ranges::range_value_t<_Range>>,
924
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
925
          class            = enable_if_t<!is_integral<_Hash>::value>,
926
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
927
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
928
unordered_set(
929
    from_range_t,
930
    _Range&&,
931
    typename allocator_traits<_Allocator>::size_type = 0,
932
    _Hash                                            = _Hash(),
933
    _Pred                                            = _Pred(),
934
    _Allocator = _Allocator()) -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
935
#  endif
936

937
template <class _Tp,
938
          class _Hash      = hash<_Tp>,
939
          class _Pred      = equal_to<_Tp>,
940
          class _Allocator = allocator<_Tp>,
941
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
942
          class            = enable_if_t<!is_integral<_Hash>::value>,
943
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
944
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
945
unordered_set(initializer_list<_Tp>,
946
              typename allocator_traits<_Allocator>::size_type = 0,
947
              _Hash                                            = _Hash(),
948
              _Pred                                            = _Pred(),
949
              _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
950

951
template <class _InputIterator,
952
          class _Allocator,
953
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
954
          class = enable_if_t<__is_allocator<_Allocator>::value>>
955
unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
956
    -> unordered_set<__iter_value_type<_InputIterator>,
957
                     hash<__iter_value_type<_InputIterator>>,
958
                     equal_to<__iter_value_type<_InputIterator>>,
959
                     _Allocator>;
960

961
template <class _InputIterator,
962
          class _Hash,
963
          class _Allocator,
964
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
965
          class = enable_if_t<!__is_allocator<_Hash>::value>,
966
          class = enable_if_t<!is_integral<_Hash>::value>,
967
          class = enable_if_t<__is_allocator<_Allocator>::value>>
968
unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
969
    -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>;
970

971
#  if _LIBCPP_STD_VER >= 23
972

973
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
974
unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
975
    -> unordered_set<ranges::range_value_t<_Range>,
976
                     hash<ranges::range_value_t<_Range>>,
977
                     equal_to<ranges::range_value_t<_Range>>,
978
                     _Allocator>;
979

980
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
981
unordered_set(from_range_t, _Range&&, _Allocator)
982
    -> unordered_set<ranges::range_value_t<_Range>,
983
                     hash<ranges::range_value_t<_Range>>,
984
                     equal_to<ranges::range_value_t<_Range>>,
985
                     _Allocator>;
986

987
template <ranges::input_range _Range,
988
          class _Hash,
989
          class _Allocator,
990
          class = enable_if_t<!__is_allocator<_Hash>::value>,
991
          class = enable_if_t<!is_integral<_Hash>::value>,
992
          class = enable_if_t<__is_allocator<_Allocator>::value>>
993
unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
994
    -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
995

996
#  endif
997

998
template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
999
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 <concepts>
1804
#  include <cstdlib>
1805
#  include <functional>
1806
#  include <iterator>
1807
#  include <stdexcept>
1808
#  include <type_traits>
1809
#endif
1810

1811
#endif // _LIBCPP_UNORDERED_SET
1812