← Back to branch summary

~ubuntu-branches/ubuntu/saucy/emscripten/saucy-proposed

« back to all changes in this revision

Viewing changes to system/include/libcxx/unordered_set

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
system/include/libcxx/unordered_set
 
1
// -*- C++ -*-
 
2
//===-------------------------- unordered_set -----------------------------===//
 
3
//
 
4
//                     The LLVM Compiler Infrastructure
 
5
//
 
6
// This file is dual licensed under the MIT and the University of Illinois Open
 
7
// Source Licenses. See LICENSE.TXT for details.
 
8
//
 
9
//===----------------------------------------------------------------------===//
 
10
 
 
11
#ifndef _LIBCPP_UNORDERED_SET
 
12
#define _LIBCPP_UNORDERED_SET
 
13
 
 
14
/*
 
15
 
 
16
    unordered_set synopsis
 
17
 
 
18
#include <initializer_list>
 
19
 
 
20
namespace std
 
21
{
 
22
 
 
23
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 
24
          class Alloc = allocator<Value>>
 
25
class unordered_set
 
26
{
 
27
public:
 
28
    // types
 
29
    typedef Value                                                      key_type;
 
30
    typedef key_type                                                   value_type;
 
31
    typedef Hash                                                       hasher;
 
32
    typedef Pred                                                       key_equal;
 
33
    typedef Alloc                                                      allocator_type;
 
34
    typedef value_type&                                                reference;
 
35
    typedef const value_type&                                          const_reference;
 
36
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
 
37
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 
38
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
 
39
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
40
 
 
41
    typedef /unspecified/ iterator;
 
42
    typedef /unspecified/ const_iterator;
 
43
    typedef /unspecified/ local_iterator;
 
44
    typedef /unspecified/ const_local_iterator;
 
45
 
 
46
    unordered_set()
 
47
        noexcept(
 
48
            is_nothrow_default_constructible<hasher>::value &&
 
49
            is_nothrow_default_constructible<key_equal>::value &&
 
50
            is_nothrow_default_constructible<allocator_type>::value);
 
51
    explicit unordered_set(size_type n, const hasher& hf = hasher(),
 
52
                           const key_equal& eql = key_equal(),
 
53
                           const allocator_type& a = allocator_type());
 
54
    template <class InputIterator>
 
55
        unordered_set(InputIterator f, InputIterator l,
 
56
                      size_type n = 0, const hasher& hf = hasher(),
 
57
                      const key_equal& eql = key_equal(),
 
58
                      const allocator_type& a = allocator_type());
 
59
    explicit unordered_set(const allocator_type&);
 
60
    unordered_set(const unordered_set&);
 
61
    unordered_set(const unordered_set&, const Allocator&);
 
62
    unordered_set(unordered_set&&)
 
63
        noexcept(
 
64
            is_nothrow_move_constructible<hasher>::value &&
 
65
            is_nothrow_move_constructible<key_equal>::value &&
 
66
            is_nothrow_move_constructible<allocator_type>::value);
 
67
    unordered_set(unordered_set&&, const Allocator&);
 
68
    unordered_set(initializer_list<value_type>, size_type n = 0,
 
69
                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 
70
                  const allocator_type& a = allocator_type());
 
71
    ~unordered_set();
 
72
    unordered_set& operator=(const unordered_set&);
 
73
    unordered_set& operator=(unordered_set&&)
 
74
        noexcept(
 
75
            allocator_type::propagate_on_container_move_assignment::value &&
 
76
            is_nothrow_move_assignable<allocator_type>::value &&
 
77
            is_nothrow_move_assignable<hasher>::value &&
 
78
            is_nothrow_move_assignable<key_equal>::value);
 
79
    unordered_set& operator=(initializer_list<value_type>);
 
80
 
 
81
    allocator_type get_allocator() const noexcept;
 
82
 
 
83
    bool      empty() const noexcept;
 
84
    size_type size() const noexcept;
 
85
    size_type max_size() const noexcept;
 
86
 
 
87
    iterator       begin() noexcept;
 
88
    iterator       end() noexcept;
 
89
    const_iterator begin()  const noexcept;
 
90
    const_iterator end()    const noexcept;
 
91
    const_iterator cbegin() const noexcept;
 
92
    const_iterator cend()   const noexcept;
 
93
 
 
94
    template <class... Args>
 
95
        pair<iterator, bool> emplace(Args&&... args);
 
96
    template <class... Args>
 
97
        iterator emplace_hint(const_iterator position, Args&&... args);
 
98
    pair<iterator, bool> insert(const value_type& obj);
 
99
    pair<iterator, bool> insert(value_type&& obj);
 
100
    iterator insert(const_iterator hint, const value_type& obj);
 
101
    iterator insert(const_iterator hint, value_type&& obj);
 
102
    template <class InputIterator>
 
103
        void insert(InputIterator first, InputIterator last);
 
104
    void insert(initializer_list<value_type>);
 
105
 
 
106
    iterator erase(const_iterator position);
 
107
    size_type erase(const key_type& k);
 
108
    iterator erase(const_iterator first, const_iterator last);
 
109
    void clear() noexcept;
 
110
 
 
111
    void swap(unordered_set&)
 
112
        noexcept(
 
113
            (!allocator_type::propagate_on_container_swap::value ||
 
114
             __is_nothrow_swappable<allocator_type>::value) &&
 
115
            __is_nothrow_swappable<hasher>::value &&
 
116
            __is_nothrow_swappable<key_equal>::value);
 
117
 
 
118
    hasher hash_function() const;
 
119
    key_equal key_eq() const;
 
120
 
 
121
    iterator       find(const key_type& k);
 
122
    const_iterator find(const key_type& k) const;
 
123
    size_type count(const key_type& k) const;
 
124
    pair<iterator, iterator>             equal_range(const key_type& k);
 
125
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
126
 
 
127
    size_type bucket_count() const noexcept;
 
128
    size_type max_bucket_count() const noexcept;
 
129
 
 
130
    size_type bucket_size(size_type n) const;
 
131
    size_type bucket(const key_type& k) const;
 
132
 
 
133
    local_iterator       begin(size_type n);
 
134
    local_iterator       end(size_type n);
 
135
    const_local_iterator begin(size_type n) const;
 
136
    const_local_iterator end(size_type n) const;
 
137
    const_local_iterator cbegin(size_type n) const;
 
138
    const_local_iterator cend(size_type n) const;
 
139
 
 
140
    float load_factor() const noexcept;
 
141
    float max_load_factor() const noexcept;
 
142
    void max_load_factor(float z);
 
143
    void rehash(size_type n);
 
144
    void reserve(size_type n);
 
145
};
 
146
 
 
147
template <class Value, class Hash, class Pred, class Alloc>
 
148
    void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
 
149
              unordered_set<Value, Hash, Pred, Alloc>& y)
 
150
              noexcept(noexcept(x.swap(y)));
 
151
 
 
152
template <class Value, class Hash, class Pred, class Alloc>
 
153
    bool
 
154
    operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
 
155
               const unordered_set<Value, Hash, Pred, Alloc>& y);
 
156
 
 
157
template <class Value, class Hash, class Pred, class Alloc>
 
158
    bool
 
159
    operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
 
160
               const unordered_set<Value, Hash, Pred, Alloc>& y);
 
161
 
 
162
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 
163
          class Alloc = allocator<Value>>
 
164
class unordered_multiset
 
165
{
 
166
public:
 
167
    // types
 
168
    typedef Value                                                      key_type;
 
169
    typedef key_type                                                   value_type;
 
170
    typedef Hash                                                       hasher;
 
171
    typedef Pred                                                       key_equal;
 
172
    typedef Alloc                                                      allocator_type;
 
173
    typedef value_type&                                                reference;
 
174
    typedef const value_type&                                          const_reference;
 
175
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
 
176
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 
177
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
 
178
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
179
 
 
180
    typedef /unspecified/ iterator;
 
181
    typedef /unspecified/ const_iterator;
 
182
    typedef /unspecified/ local_iterator;
 
183
    typedef /unspecified/ const_local_iterator;
 
184
 
 
185
    unordered_multiset()
 
186
        noexcept(
 
187
            is_nothrow_default_constructible<hasher>::value &&
 
188
            is_nothrow_default_constructible<key_equal>::value &&
 
189
            is_nothrow_default_constructible<allocator_type>::value);
 
190
    explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
 
191
                           const key_equal& eql = key_equal(),
 
192
                           const allocator_type& a = allocator_type());
 
193
    template <class InputIterator>
 
194
        unordered_multiset(InputIterator f, InputIterator l,
 
195
                      size_type n = 0, const hasher& hf = hasher(),
 
196
                      const key_equal& eql = key_equal(),
 
197
                      const allocator_type& a = allocator_type());
 
198
    explicit unordered_multiset(const allocator_type&);
 
199
    unordered_multiset(const unordered_multiset&);
 
200
    unordered_multiset(const unordered_multiset&, const Allocator&);
 
201
    unordered_multiset(unordered_multiset&&)
 
202
        noexcept(
 
203
            is_nothrow_move_constructible<hasher>::value &&
 
204
            is_nothrow_move_constructible<key_equal>::value &&
 
205
            is_nothrow_move_constructible<allocator_type>::value);
 
206
    unordered_multiset(unordered_multiset&&, const Allocator&);
 
207
    unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
 
208
                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 
209
                  const allocator_type& a = allocator_type());
 
210
    ~unordered_multiset();
 
211
    unordered_multiset& operator=(const unordered_multiset&);
 
212
    unordered_multiset& operator=(unordered_multiset&&)
 
213
        noexcept(
 
214
            allocator_type::propagate_on_container_move_assignment::value &&
 
215
            is_nothrow_move_assignable<allocator_type>::value &&
 
216
            is_nothrow_move_assignable<hasher>::value &&
 
217
            is_nothrow_move_assignable<key_equal>::value);
 
218
    unordered_multiset& operator=(initializer_list<value_type>);
 
219
 
 
220
    allocator_type get_allocator() const noexcept;
 
221
 
 
222
    bool      empty() const noexcept;
 
223
    size_type size() const noexcept;
 
224
    size_type max_size() const noexcept;
 
225
 
 
226
    iterator       begin() noexcept;
 
227
    iterator       end() noexcept;
 
228
    const_iterator begin()  const noexcept;
 
229
    const_iterator end()    const noexcept;
 
230
    const_iterator cbegin() const noexcept;
 
231
    const_iterator cend()   const noexcept;
 
232
 
 
233
    template <class... Args>
 
234
        iterator emplace(Args&&... args);
 
235
    template <class... Args>
 
236
        iterator emplace_hint(const_iterator position, Args&&... args);
 
237
    iterator insert(const value_type& obj);
 
238
    iterator insert(value_type&& obj);
 
239
    iterator insert(const_iterator hint, const value_type& obj);
 
240
    iterator insert(const_iterator hint, value_type&& obj);
 
241
    template <class InputIterator>
 
242
        void insert(InputIterator first, InputIterator last);
 
243
    void insert(initializer_list<value_type>);
 
244
 
 
245
    iterator erase(const_iterator position);
 
246
    size_type erase(const key_type& k);
 
247
    iterator erase(const_iterator first, const_iterator last);
 
248
    void clear() noexcept;
 
249
 
 
250
    void swap(unordered_multiset&)
 
251
        noexcept(
 
252
            (!allocator_type::propagate_on_container_swap::value ||
 
253
             __is_nothrow_swappable<allocator_type>::value) &&
 
254
            __is_nothrow_swappable<hasher>::value &&
 
255
            __is_nothrow_swappable<key_equal>::value);
 
256
 
 
257
    hasher hash_function() const;
 
258
    key_equal key_eq() const;
 
259
 
 
260
    iterator       find(const key_type& k);
 
261
    const_iterator find(const key_type& k) const;
 
262
    size_type count(const key_type& k) const;
 
263
    pair<iterator, iterator>             equal_range(const key_type& k);
 
264
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
265
 
 
266
    size_type bucket_count() const noexcept;
 
267
    size_type max_bucket_count() const noexcept;
 
268
 
 
269
    size_type bucket_size(size_type n) const;
 
270
    size_type bucket(const key_type& k) const;
 
271
 
 
272
    local_iterator       begin(size_type n);
 
273
    local_iterator       end(size_type n);
 
274
    const_local_iterator begin(size_type n) const;
 
275
    const_local_iterator end(size_type n) const;
 
276
    const_local_iterator cbegin(size_type n) const;
 
277
    const_local_iterator cend(size_type n) const;
 
278
 
 
279
    float load_factor() const noexcept;
 
280
    float max_load_factor() const noexcept;
 
281
    void max_load_factor(float z);
 
282
    void rehash(size_type n);
 
283
    void reserve(size_type n);
 
284
};
 
285
 
 
286
template <class Value, class Hash, class Pred, class Alloc>
 
287
    void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
 
288
              unordered_multiset<Value, Hash, Pred, Alloc>& y)
 
289
              noexcept(noexcept(x.swap(y)));
 
290
 
 
291
template <class Value, class Hash, class Pred, class Alloc>
 
292
    bool
 
293
    operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 
294
               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 
295
 
 
296
template <class Value, class Hash, class Pred, class Alloc>
 
297
    bool
 
298
    operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 
299
               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 
300
}  // std
 
301
 
 
302
*/
 
303
 
 
304
#include <__config>
 
305
#include <__hash_table>
 
306
#include <functional>
 
307
 
 
308
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 
309
#pragma GCC system_header
 
310
#endif
 
311
 
 
312
_LIBCPP_BEGIN_NAMESPACE_STD
 
313
 
 
314
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 
315
          class _Alloc = allocator<_Value> >
 
316
class _LIBCPP_TYPE_VIS unordered_set
 
317
{
 
318
public:
 
319
    // types
 
320
    typedef _Value                                                     key_type;
 
321
    typedef key_type                                                   value_type;
 
322
    typedef _Hash                                                      hasher;
 
323
    typedef _Pred                                                      key_equal;
 
324
    typedef _Alloc                                                     allocator_type;
 
325
    typedef value_type&                                                reference;
 
326
    typedef const value_type&                                          const_reference;
 
327
 
 
328
private:
 
329
    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 
330
 
 
331
    __table __table_;
 
332
 
 
333
public:
 
334
    typedef typename __table::pointer         pointer;
 
335
    typedef typename __table::const_pointer   const_pointer;
 
336
    typedef typename __table::size_type       size_type;
 
337
    typedef typename __table::difference_type difference_type;
 
338
 
 
339
    typedef typename __table::const_iterator       iterator;
 
340
    typedef typename __table::const_iterator       const_iterator;
 
341
    typedef typename __table::const_local_iterator local_iterator;
 
342
    typedef typename __table::const_local_iterator const_local_iterator;
 
343
 
 
344
    _LIBCPP_INLINE_VISIBILITY
 
345
    unordered_set()
 
346
        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 
347
        {} // = default;
 
348
    explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
 
349
                           const key_equal& __eql = key_equal());
 
350
    unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 
351
                  const allocator_type& __a);
 
352
    template <class _InputIterator>
 
353
        unordered_set(_InputIterator __first, _InputIterator __last);
 
354
    template <class _InputIterator>
 
355
        unordered_set(_InputIterator __first, _InputIterator __last,
 
356
                      size_type __n, const hasher& __hf = hasher(),
 
357
                      const key_equal& __eql = key_equal());
 
358
    template <class _InputIterator>
 
359
        unordered_set(_InputIterator __first, _InputIterator __last,
 
360
                      size_type __n, const hasher& __hf, const key_equal& __eql,
 
361
                      const allocator_type& __a);
 
362
    explicit unordered_set(const allocator_type& __a);
 
363
    unordered_set(const unordered_set& __u);
 
364
    unordered_set(const unordered_set& __u, const allocator_type& __a);
 
365
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
366
    unordered_set(unordered_set&& __u)
 
367
        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 
368
    unordered_set(unordered_set&& __u, const allocator_type& __a);
 
369
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
370
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
371
    unordered_set(initializer_list<value_type> __il);
 
372
    unordered_set(initializer_list<value_type> __il, size_type __n,
 
373
                  const hasher& __hf = hasher(),
 
374
                  const key_equal& __eql = key_equal());
 
375
    unordered_set(initializer_list<value_type> __il, size_type __n,
 
376
                  const hasher& __hf, const key_equal& __eql,
 
377
                  const allocator_type& __a);
 
378
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
379
    // ~unordered_set() = default;
 
380
    _LIBCPP_INLINE_VISIBILITY
 
381
    unordered_set& operator=(const unordered_set& __u)
 
382
    {
 
383
        __table_ = __u.__table_;
 
384
        return *this;
 
385
    }
 
386
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
387
    unordered_set& operator=(unordered_set&& __u)
 
388
        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 
389
#endif
 
390
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
391
    unordered_set& operator=(initializer_list<value_type> __il);
 
392
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
393
 
 
394
    _LIBCPP_INLINE_VISIBILITY
 
395
    allocator_type get_allocator() const _NOEXCEPT
 
396
        {return allocator_type(__table_.__node_alloc());}
 
397
 
 
398
    _LIBCPP_INLINE_VISIBILITY
 
399
    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 
400
    _LIBCPP_INLINE_VISIBILITY
 
401
    size_type size() const _NOEXCEPT  {return __table_.size();}
 
402
    _LIBCPP_INLINE_VISIBILITY
 
403
    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 
404
 
 
405
    _LIBCPP_INLINE_VISIBILITY
 
406
    iterator       begin() _NOEXCEPT        {return __table_.begin();}
 
407
    _LIBCPP_INLINE_VISIBILITY
 
408
    iterator       end() _NOEXCEPT          {return __table_.end();}
 
409
    _LIBCPP_INLINE_VISIBILITY
 
410
    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 
411
    _LIBCPP_INLINE_VISIBILITY
 
412
    const_iterator end()    const _NOEXCEPT {return __table_.end();}
 
413
    _LIBCPP_INLINE_VISIBILITY
 
414
    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 
415
    _LIBCPP_INLINE_VISIBILITY
 
416
    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 
417
 
 
418
#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 
419
    template <class... _Args>
 
420
        _LIBCPP_INLINE_VISIBILITY
 
421
        pair<iterator, bool> emplace(_Args&&... __args)
 
422
            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 
423
    template <class... _Args>
 
424
        _LIBCPP_INLINE_VISIBILITY
 
425
        iterator emplace_hint(const_iterator, _Args&&... __args)
 
426
            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
 
427
#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 
428
    _LIBCPP_INLINE_VISIBILITY
 
429
    pair<iterator, bool> insert(const value_type& __x)
 
430
        {return __table_.__insert_unique(__x);}
 
431
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
432
    _LIBCPP_INLINE_VISIBILITY
 
433
    pair<iterator, bool> insert(value_type&& __x)
 
434
        {return __table_.__insert_unique(_VSTD::move(__x));}
 
435
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
436
    _LIBCPP_INLINE_VISIBILITY
 
437
    iterator insert(const_iterator, const value_type& __x)
 
438
        {return insert(__x).first;}
 
439
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
440
    _LIBCPP_INLINE_VISIBILITY
 
441
    iterator insert(const_iterator, value_type&& __x)
 
442
        {return insert(_VSTD::move(__x)).first;}
 
443
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
444
    template <class _InputIterator>
 
445
        void insert(_InputIterator __first, _InputIterator __last);
 
446
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
447
    _LIBCPP_INLINE_VISIBILITY
 
448
    void insert(initializer_list<value_type> __il)
 
449
        {insert(__il.begin(), __il.end());}
 
450
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
451
 
 
452
    _LIBCPP_INLINE_VISIBILITY
 
453
    iterator erase(const_iterator __p) {return __table_.erase(__p);}
 
454
    _LIBCPP_INLINE_VISIBILITY
 
455
    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 
456
    _LIBCPP_INLINE_VISIBILITY
 
457
    iterator erase(const_iterator __first, const_iterator __last)
 
458
        {return __table_.erase(__first, __last);}
 
459
    _LIBCPP_INLINE_VISIBILITY
 
460
    void clear() _NOEXCEPT {__table_.clear();}
 
461
 
 
462
    _LIBCPP_INLINE_VISIBILITY
 
463
    void swap(unordered_set& __u)
 
464
        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 
465
        {__table_.swap(__u.__table_);}
 
466
 
 
467
    _LIBCPP_INLINE_VISIBILITY
 
468
    hasher hash_function() const {return __table_.hash_function();}
 
469
    _LIBCPP_INLINE_VISIBILITY
 
470
    key_equal key_eq() const {return __table_.key_eq();}
 
471
 
 
472
    _LIBCPP_INLINE_VISIBILITY
 
473
    iterator       find(const key_type& __k)       {return __table_.find(__k);}
 
474
    _LIBCPP_INLINE_VISIBILITY
 
475
    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 
476
    _LIBCPP_INLINE_VISIBILITY
 
477
    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 
478
    _LIBCPP_INLINE_VISIBILITY
 
479
    pair<iterator, iterator>             equal_range(const key_type& __k)
 
480
        {return __table_.__equal_range_unique(__k);}
 
481
    _LIBCPP_INLINE_VISIBILITY
 
482
    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 
483
        {return __table_.__equal_range_unique(__k);}
 
484
 
 
485
    _LIBCPP_INLINE_VISIBILITY
 
486
    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 
487
    _LIBCPP_INLINE_VISIBILITY
 
488
    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
489
 
 
490
    _LIBCPP_INLINE_VISIBILITY
 
491
    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 
492
    _LIBCPP_INLINE_VISIBILITY
 
493
    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 
494
 
 
495
    _LIBCPP_INLINE_VISIBILITY
 
496
    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 
497
    _LIBCPP_INLINE_VISIBILITY
 
498
    local_iterator       end(size_type __n)          {return __table_.end(__n);}
 
499
    _LIBCPP_INLINE_VISIBILITY
 
500
    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 
501
    _LIBCPP_INLINE_VISIBILITY
 
502
    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 
503
    _LIBCPP_INLINE_VISIBILITY
 
504
    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 
505
    _LIBCPP_INLINE_VISIBILITY
 
506
    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 
507
 
 
508
    _LIBCPP_INLINE_VISIBILITY
 
509
    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 
510
    _LIBCPP_INLINE_VISIBILITY
 
511
    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 
512
    _LIBCPP_INLINE_VISIBILITY
 
513
    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 
514
    _LIBCPP_INLINE_VISIBILITY
 
515
    void rehash(size_type __n) {__table_.rehash(__n);}
 
516
    _LIBCPP_INLINE_VISIBILITY
 
517
    void reserve(size_type __n) {__table_.reserve(__n);}
 
518
};
 
519
 
 
520
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
521
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 
522
        const hasher& __hf, const key_equal& __eql)
 
523
    : __table_(__hf, __eql)
 
524
{
 
525
    __table_.rehash(__n);
 
526
}
 
527
 
 
528
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
529
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 
530
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
531
    : __table_(__hf, __eql, __a)
 
532
{
 
533
    __table_.rehash(__n);
 
534
}
 
535
 
 
536
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
537
template <class _InputIterator>
 
538
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
539
        _InputIterator __first, _InputIterator __last)
 
540
{
 
541
    insert(__first, __last);
 
542
}
 
543
 
 
544
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
545
template <class _InputIterator>
 
546
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
547
        _InputIterator __first, _InputIterator __last, size_type __n,
 
548
        const hasher& __hf, const key_equal& __eql)
 
549
    : __table_(__hf, __eql)
 
550
{
 
551
    __table_.rehash(__n);
 
552
    insert(__first, __last);
 
553
}
 
554
 
 
555
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
556
template <class _InputIterator>
 
557
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
558
        _InputIterator __first, _InputIterator __last, size_type __n,
 
559
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
560
    : __table_(__hf, __eql, __a)
 
561
{
 
562
    __table_.rehash(__n);
 
563
    insert(__first, __last);
 
564
}
 
565
 
 
566
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
567
inline _LIBCPP_INLINE_VISIBILITY
 
568
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
569
        const allocator_type& __a)
 
570
    : __table_(__a)
 
571
{
 
572
}
 
573
 
 
574
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
575
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
576
        const unordered_set& __u)
 
577
    : __table_(__u.__table_)
 
578
{
 
579
    __table_.rehash(__u.bucket_count());
 
580
    insert(__u.begin(), __u.end());
 
581
}
 
582
 
 
583
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
584
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
585
        const unordered_set& __u, const allocator_type& __a)
 
586
    : __table_(__u.__table_, __a)
 
587
{
 
588
    __table_.rehash(__u.bucket_count());
 
589
    insert(__u.begin(), __u.end());
 
590
}
 
591
 
 
592
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
593
 
 
594
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
595
inline _LIBCPP_INLINE_VISIBILITY
 
596
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
597
        unordered_set&& __u)
 
598
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 
599
    : __table_(_VSTD::move(__u.__table_))
 
600
{
 
601
}
 
602
 
 
603
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
604
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
605
        unordered_set&& __u, const allocator_type& __a)
 
606
    : __table_(_VSTD::move(__u.__table_), __a)
 
607
{
 
608
    if (__a != __u.get_allocator())
 
609
    {
 
610
        iterator __i = __u.begin();
 
611
        while (__u.size() != 0)
 
612
            __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
 
613
    }
 
614
}
 
615
 
 
616
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
617
 
 
618
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
619
 
 
620
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
621
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
622
        initializer_list<value_type> __il)
 
623
{
 
624
    insert(__il.begin(), __il.end());
 
625
}
 
626
 
 
627
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
628
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
629
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
630
        const key_equal& __eql)
 
631
    : __table_(__hf, __eql)
 
632
{
 
633
    __table_.rehash(__n);
 
634
    insert(__il.begin(), __il.end());
 
635
}
 
636
 
 
637
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
638
unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 
639
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
640
        const key_equal& __eql, const allocator_type& __a)
 
641
    : __table_(__hf, __eql, __a)
 
642
{
 
643
    __table_.rehash(__n);
 
644
    insert(__il.begin(), __il.end());
 
645
}
 
646
 
 
647
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
648
 
 
649
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
650
 
 
651
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
652
inline _LIBCPP_INLINE_VISIBILITY
 
653
unordered_set<_Value, _Hash, _Pred, _Alloc>&
 
654
unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
 
655
    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 
656
{
 
657
    __table_ = _VSTD::move(__u.__table_);
 
658
    return *this;
 
659
}
 
660
 
 
661
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
662
 
 
663
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
664
 
 
665
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
666
inline _LIBCPP_INLINE_VISIBILITY
 
667
unordered_set<_Value, _Hash, _Pred, _Alloc>&
 
668
unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
 
669
        initializer_list<value_type> __il)
 
670
{
 
671
    __table_.__assign_unique(__il.begin(), __il.end());
 
672
    return *this;
 
673
}
 
674
 
 
675
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
676
 
 
677
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
678
template <class _InputIterator>
 
679
inline _LIBCPP_INLINE_VISIBILITY
 
680
void
 
681
unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
682
                                                    _InputIterator __last)
 
683
{
 
684
    for (; __first != __last; ++__first)
 
685
        __table_.__insert_unique(*__first);
 
686
}
 
687
 
 
688
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
689
inline _LIBCPP_INLINE_VISIBILITY
 
690
void
 
691
swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 
692
     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 
693
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 
694
{
 
695
    __x.swap(__y);
 
696
}
 
697
 
 
698
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
699
bool
 
700
operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 
701
           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 
702
{
 
703
    if (__x.size() != __y.size())
 
704
        return false;
 
705
    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 
706
                                                                 const_iterator;
 
707
    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 
708
            __i != __ex; ++__i)
 
709
    {
 
710
        const_iterator __j = __y.find(*__i);
 
711
        if (__j == __ey || !(*__i == *__j))
 
712
            return false;
 
713
    }
 
714
    return true;
 
715
}
 
716
 
 
717
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
718
inline _LIBCPP_INLINE_VISIBILITY
 
719
bool
 
720
operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 
721
           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 
722
{
 
723
    return !(__x == __y);
 
724
}
 
725
 
 
726
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 
727
          class _Alloc = allocator<_Value> >
 
728
class _LIBCPP_TYPE_VIS unordered_multiset
 
729
{
 
730
public:
 
731
    // types
 
732
    typedef _Value                                                     key_type;
 
733
    typedef key_type                                                   value_type;
 
734
    typedef _Hash                                                      hasher;
 
735
    typedef _Pred                                                      key_equal;
 
736
    typedef _Alloc                                                     allocator_type;
 
737
    typedef value_type&                                                reference;
 
738
    typedef const value_type&                                          const_reference;
 
739
 
 
740
private:
 
741
    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 
742
 
 
743
    __table __table_;
 
744
 
 
745
public:
 
746
    typedef typename __table::pointer         pointer;
 
747
    typedef typename __table::const_pointer   const_pointer;
 
748
    typedef typename __table::size_type       size_type;
 
749
    typedef typename __table::difference_type difference_type;
 
750
 
 
751
    typedef typename __table::const_iterator       iterator;
 
752
    typedef typename __table::const_iterator       const_iterator;
 
753
    typedef typename __table::const_local_iterator local_iterator;
 
754
    typedef typename __table::const_local_iterator const_local_iterator;
 
755
 
 
756
    _LIBCPP_INLINE_VISIBILITY
 
757
    unordered_multiset()
 
758
        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 
759
        {} // = default
 
760
    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
 
761
                                const key_equal& __eql = key_equal());
 
762
    unordered_multiset(size_type __n, const hasher& __hf,
 
763
                       const key_equal& __eql, const allocator_type& __a);
 
764
    template <class _InputIterator>
 
765
        unordered_multiset(_InputIterator __first, _InputIterator __last);
 
766
    template <class _InputIterator>
 
767
        unordered_multiset(_InputIterator __first, _InputIterator __last,
 
768
                      size_type __n, const hasher& __hf = hasher(),
 
769
                      const key_equal& __eql = key_equal());
 
770
    template <class _InputIterator>
 
771
        unordered_multiset(_InputIterator __first, _InputIterator __last,
 
772
                      size_type __n , const hasher& __hf,
 
773
                      const key_equal& __eql, const allocator_type& __a);
 
774
    explicit unordered_multiset(const allocator_type& __a);
 
775
    unordered_multiset(const unordered_multiset& __u);
 
776
    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
 
777
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
778
    unordered_multiset(unordered_multiset&& __u)
 
779
        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 
780
    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
 
781
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
782
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
783
    unordered_multiset(initializer_list<value_type> __il);
 
784
    unordered_multiset(initializer_list<value_type> __il, size_type __n,
 
785
                       const hasher& __hf = hasher(),
 
786
                       const key_equal& __eql = key_equal());
 
787
    unordered_multiset(initializer_list<value_type> __il, size_type __n,
 
788
                       const hasher& __hf, const key_equal& __eql,
 
789
                       const allocator_type& __a);
 
790
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
791
    // ~unordered_multiset() = default;
 
792
    _LIBCPP_INLINE_VISIBILITY
 
793
    unordered_multiset& operator=(const unordered_multiset& __u)
 
794
    {
 
795
        __table_ = __u.__table_;
 
796
        return *this;
 
797
    }
 
798
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
799
    unordered_multiset& operator=(unordered_multiset&& __u)
 
800
        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 
801
#endif
 
802
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
803
    unordered_multiset& operator=(initializer_list<value_type> __il);
 
804
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
805
 
 
806
    _LIBCPP_INLINE_VISIBILITY
 
807
    allocator_type get_allocator() const _NOEXCEPT
 
808
        {return allocator_type(__table_.__node_alloc());}
 
809
 
 
810
    _LIBCPP_INLINE_VISIBILITY
 
811
    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 
812
    _LIBCPP_INLINE_VISIBILITY
 
813
    size_type size() const _NOEXCEPT  {return __table_.size();}
 
814
    _LIBCPP_INLINE_VISIBILITY
 
815
    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 
816
 
 
817
    _LIBCPP_INLINE_VISIBILITY
 
818
    iterator       begin() _NOEXCEPT        {return __table_.begin();}
 
819
    _LIBCPP_INLINE_VISIBILITY
 
820
    iterator       end() _NOEXCEPT          {return __table_.end();}
 
821
    _LIBCPP_INLINE_VISIBILITY
 
822
    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 
823
    _LIBCPP_INLINE_VISIBILITY
 
824
    const_iterator end()    const _NOEXCEPT {return __table_.end();}
 
825
    _LIBCPP_INLINE_VISIBILITY
 
826
    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 
827
    _LIBCPP_INLINE_VISIBILITY
 
828
    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 
829
 
 
830
#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 
831
    template <class... _Args>
 
832
        _LIBCPP_INLINE_VISIBILITY
 
833
        iterator emplace(_Args&&... __args)
 
834
            {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
 
835
    template <class... _Args>
 
836
        _LIBCPP_INLINE_VISIBILITY
 
837
        iterator emplace_hint(const_iterator __p, _Args&&... __args)
 
838
            {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
 
839
#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 
840
    _LIBCPP_INLINE_VISIBILITY
 
841
    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 
842
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
843
    _LIBCPP_INLINE_VISIBILITY
 
844
    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
 
845
#endif
 
846
    _LIBCPP_INLINE_VISIBILITY
 
847
    iterator insert(const_iterator __p, const value_type& __x)
 
848
        {return __table_.__insert_multi(__p, __x);}
 
849
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
850
    _LIBCPP_INLINE_VISIBILITY
 
851
    iterator insert(const_iterator __p, value_type&& __x)
 
852
        {return __table_.__insert_multi(__p, _VSTD::move(__x));}
 
853
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
854
    template <class _InputIterator>
 
855
        void insert(_InputIterator __first, _InputIterator __last);
 
856
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
857
    _LIBCPP_INLINE_VISIBILITY
 
858
    void insert(initializer_list<value_type> __il)
 
859
        {insert(__il.begin(), __il.end());}
 
860
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
861
 
 
862
    _LIBCPP_INLINE_VISIBILITY
 
863
    iterator erase(const_iterator __p) {return __table_.erase(__p);}
 
864
    _LIBCPP_INLINE_VISIBILITY
 
865
    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 
866
    _LIBCPP_INLINE_VISIBILITY
 
867
    iterator erase(const_iterator __first, const_iterator __last)
 
868
        {return __table_.erase(__first, __last);}
 
869
    _LIBCPP_INLINE_VISIBILITY
 
870
    void clear() _NOEXCEPT {__table_.clear();}
 
871
 
 
872
    _LIBCPP_INLINE_VISIBILITY
 
873
    void swap(unordered_multiset& __u)
 
874
        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 
875
        {__table_.swap(__u.__table_);}
 
876
 
 
877
    _LIBCPP_INLINE_VISIBILITY
 
878
    hasher hash_function() const {return __table_.hash_function();}
 
879
    _LIBCPP_INLINE_VISIBILITY
 
880
    key_equal key_eq() const {return __table_.key_eq();}
 
881
 
 
882
    _LIBCPP_INLINE_VISIBILITY
 
883
    iterator       find(const key_type& __k)       {return __table_.find(__k);}
 
884
    _LIBCPP_INLINE_VISIBILITY
 
885
    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 
886
    _LIBCPP_INLINE_VISIBILITY
 
887
    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 
888
    _LIBCPP_INLINE_VISIBILITY
 
889
    pair<iterator, iterator>             equal_range(const key_type& __k)
 
890
        {return __table_.__equal_range_multi(__k);}
 
891
    _LIBCPP_INLINE_VISIBILITY
 
892
    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 
893
        {return __table_.__equal_range_multi(__k);}
 
894
 
 
895
    _LIBCPP_INLINE_VISIBILITY
 
896
    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 
897
    _LIBCPP_INLINE_VISIBILITY
 
898
    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
899
 
 
900
    _LIBCPP_INLINE_VISIBILITY
 
901
    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 
902
    _LIBCPP_INLINE_VISIBILITY
 
903
    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 
904
 
 
905
    _LIBCPP_INLINE_VISIBILITY
 
906
    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 
907
    _LIBCPP_INLINE_VISIBILITY
 
908
    local_iterator       end(size_type __n)          {return __table_.end(__n);}
 
909
    _LIBCPP_INLINE_VISIBILITY
 
910
    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 
911
    _LIBCPP_INLINE_VISIBILITY
 
912
    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 
913
    _LIBCPP_INLINE_VISIBILITY
 
914
    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 
915
    _LIBCPP_INLINE_VISIBILITY
 
916
    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 
917
 
 
918
    _LIBCPP_INLINE_VISIBILITY
 
919
    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 
920
    _LIBCPP_INLINE_VISIBILITY
 
921
    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 
922
    _LIBCPP_INLINE_VISIBILITY
 
923
    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 
924
    _LIBCPP_INLINE_VISIBILITY
 
925
    void rehash(size_type __n) {__table_.rehash(__n);}
 
926
    _LIBCPP_INLINE_VISIBILITY
 
927
    void reserve(size_type __n) {__table_.reserve(__n);}
 
928
};
 
929
 
 
930
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
931
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
932
        size_type __n, const hasher& __hf, const key_equal& __eql)
 
933
    : __table_(__hf, __eql)
 
934
{
 
935
    __table_.rehash(__n);
 
936
}
 
937
 
 
938
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
939
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
940
        size_type __n, const hasher& __hf, const key_equal& __eql,
 
941
        const allocator_type& __a)
 
942
    : __table_(__hf, __eql, __a)
 
943
{
 
944
    __table_.rehash(__n);
 
945
}
 
946
 
 
947
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
948
template <class _InputIterator>
 
949
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
950
        _InputIterator __first, _InputIterator __last)
 
951
{
 
952
    insert(__first, __last);
 
953
}
 
954
 
 
955
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
956
template <class _InputIterator>
 
957
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
958
        _InputIterator __first, _InputIterator __last, size_type __n,
 
959
        const hasher& __hf, const key_equal& __eql)
 
960
    : __table_(__hf, __eql)
 
961
{
 
962
    __table_.rehash(__n);
 
963
    insert(__first, __last);
 
964
}
 
965
 
 
966
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
967
template <class _InputIterator>
 
968
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
969
        _InputIterator __first, _InputIterator __last, size_type __n,
 
970
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
971
    : __table_(__hf, __eql, __a)
 
972
{
 
973
    __table_.rehash(__n);
 
974
    insert(__first, __last);
 
975
}
 
976
 
 
977
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
978
inline _LIBCPP_INLINE_VISIBILITY
 
979
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
980
        const allocator_type& __a)
 
981
    : __table_(__a)
 
982
{
 
983
}
 
984
 
 
985
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
986
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
987
        const unordered_multiset& __u)
 
988
    : __table_(__u.__table_)
 
989
{
 
990
    __table_.rehash(__u.bucket_count());
 
991
    insert(__u.begin(), __u.end());
 
992
}
 
993
 
 
994
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
995
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
996
        const unordered_multiset& __u, const allocator_type& __a)
 
997
    : __table_(__u.__table_, __a)
 
998
{
 
999
    __table_.rehash(__u.bucket_count());
 
1000
    insert(__u.begin(), __u.end());
 
1001
}
 
1002
 
 
1003
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1004
 
 
1005
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1006
inline _LIBCPP_INLINE_VISIBILITY
 
1007
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
1008
        unordered_multiset&& __u)
 
1009
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 
1010
    : __table_(_VSTD::move(__u.__table_))
 
1011
{
 
1012
}
 
1013
 
 
1014
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1015
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
1016
        unordered_multiset&& __u, const allocator_type& __a)
 
1017
    : __table_(_VSTD::move(__u.__table_), __a)
 
1018
{
 
1019
    if (__a != __u.get_allocator())
 
1020
    {
 
1021
        iterator __i = __u.begin();
 
1022
        while (__u.size() != 0)
 
1023
            __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
 
1024
    }
 
1025
}
 
1026
 
 
1027
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1028
 
 
1029
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1030
 
 
1031
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1032
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
1033
        initializer_list<value_type> __il)
 
1034
{
 
1035
    insert(__il.begin(), __il.end());
 
1036
}
 
1037
 
 
1038
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1039
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
1040
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
1041
        const key_equal& __eql)
 
1042
    : __table_(__hf, __eql)
 
1043
{
 
1044
    __table_.rehash(__n);
 
1045
    insert(__il.begin(), __il.end());
 
1046
}
 
1047
 
 
1048
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1049
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 
1050
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
1051
        const key_equal& __eql, const allocator_type& __a)
 
1052
    : __table_(__hf, __eql, __a)
 
1053
{
 
1054
    __table_.rehash(__n);
 
1055
    insert(__il.begin(), __il.end());
 
1056
}
 
1057
 
 
1058
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1059
 
 
1060
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1061
 
 
1062
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1063
inline _LIBCPP_INLINE_VISIBILITY
 
1064
unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
 
1065
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
 
1066
        unordered_multiset&& __u)
 
1067
    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 
1068
{
 
1069
    __table_ = _VSTD::move(__u.__table_);
 
1070
    return *this;
 
1071
}
 
1072
 
 
1073
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1074
 
 
1075
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1076
 
 
1077
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1078
inline
 
1079
unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
 
1080
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
 
1081
        initializer_list<value_type> __il)
 
1082
{
 
1083
    __table_.__assign_multi(__il.begin(), __il.end());
 
1084
    return *this;
 
1085
}
 
1086
 
 
1087
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1088
 
 
1089
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1090
template <class _InputIterator>
 
1091
inline _LIBCPP_INLINE_VISIBILITY
 
1092
void
 
1093
unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
1094
                                                         _InputIterator __last)
 
1095
{
 
1096
    for (; __first != __last; ++__first)
 
1097
        __table_.__insert_multi(*__first);
 
1098
}
 
1099
 
 
1100
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1101
inline _LIBCPP_INLINE_VISIBILITY
 
1102
void
 
1103
swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 
1104
     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 
1105
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 
1106
{
 
1107
    __x.swap(__y);
 
1108
}
 
1109
 
 
1110
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1111
bool
 
1112
operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 
1113
           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 
1114
{
 
1115
    if (__x.size() != __y.size())
 
1116
        return false;
 
1117
    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
 
1118
                                                                 const_iterator;
 
1119
    typedef pair<const_iterator, const_iterator> _EqRng;
 
1120
    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
 
1121
    {
 
1122
        _EqRng __xeq = __x.equal_range(*__i);
 
1123
        _EqRng __yeq = __y.equal_range(*__i);
 
1124
        if (_VSTD::distance(__xeq.first, __xeq.second) !=
 
1125
            _VSTD::distance(__yeq.first, __yeq.second) ||
 
1126
                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 
1127
            return false;
 
1128
        __i = __xeq.second;
 
1129
    }
 
1130
    return true;
 
1131
}
 
1132
 
 
1133
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
1134
inline _LIBCPP_INLINE_VISIBILITY
 
1135
bool
 
1136
operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 
1137
           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 
1138
{
 
1139
    return !(__x == __y);
 
1140
}
 
1141
 
 
1142
_LIBCPP_END_NAMESPACE_STD
 
1143
 
 
1144
#endif  // _LIBCPP_UNORDERED_SET