• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// -*- C++ -*-
2//===-------------------------- hash_map ----------------------------------===//
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_HASH_MAP
12#define _LIBCPP_HASH_MAP
13
14/*
15
16    hash_map synopsis
17
18namespace __gnu_cxx
19{
20
21template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
22          class Alloc = allocator<pair<const Key, T>>>
23class hash_map
24{
25public:
26    // types
27    typedef Key                                                        key_type;
28    typedef T                                                          mapped_type;
29    typedef Hash                                                       hasher;
30    typedef Pred                                                       key_equal;
31    typedef Alloc                                                      allocator_type;
32    typedef pair<const key_type, mapped_type>                          value_type;
33    typedef value_type&                                                reference;
34    typedef const value_type&                                          const_reference;
35    typedef typename allocator_traits<allocator_type>::pointer         pointer;
36    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
37    typedef typename allocator_traits<allocator_type>::size_type       size_type;
38    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
39
40    typedef /unspecified/ iterator;
41    typedef /unspecified/ const_iterator;
42
43    explicit hash_map(size_type n = 193, const hasher& hf = hasher(),
44                           const key_equal& eql = key_equal(),
45                           const allocator_type& a = allocator_type());
46    template <class InputIterator>
47        hash_map(InputIterator f, InputIterator l,
48                      size_type n = 193, const hasher& hf = hasher(),
49                      const key_equal& eql = key_equal(),
50                      const allocator_type& a = allocator_type());
51    hash_map(const hash_map&);
52    ~hash_map();
53    hash_map& operator=(const hash_map&);
54
55    allocator_type get_allocator() const;
56
57    bool      empty() const;
58    size_type size() const;
59    size_type max_size() const;
60
61    iterator       begin();
62    iterator       end();
63    const_iterator begin()  const;
64    const_iterator end()    const;
65
66    pair<iterator, bool> insert(const value_type& obj);
67    template <class InputIterator>
68        void insert(InputIterator first, InputIterator last);
69
70    void erase(const_iterator position);
71    size_type erase(const key_type& k);
72    void erase(const_iterator first, const_iterator last);
73    void clear();
74
75    void swap(hash_map&);
76
77    hasher hash_funct() const;
78    key_equal key_eq() const;
79
80    iterator       find(const key_type& k);
81    const_iterator find(const key_type& k) const;
82    size_type count(const key_type& k) const;
83    pair<iterator, iterator>             equal_range(const key_type& k);
84    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
85
86    mapped_type& operator[](const key_type& k);
87
88    size_type bucket_count() const;
89    size_type max_bucket_count() const;
90
91    size_type elems_in_bucket(size_type n) const;
92
93    void resize(size_type n);
94};
95
96template <class Key, class T, class Hash, class Pred, class Alloc>
97    void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,
98              hash_map<Key, T, Hash, Pred, Alloc>& y);
99
100template <class Key, class T, class Hash, class Pred, class Alloc>
101    bool
102    operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
103               const hash_map<Key, T, Hash, Pred, Alloc>& y);
104
105template <class Key, class T, class Hash, class Pred, class Alloc>
106    bool
107    operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
108               const hash_map<Key, T, Hash, Pred, Alloc>& y);
109
110template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
111          class Alloc = allocator<pair<const Key, T>>>
112class hash_multimap
113{
114public:
115    // types
116    typedef Key                                                        key_type;
117    typedef T                                                          mapped_type;
118    typedef Hash                                                       hasher;
119    typedef Pred                                                       key_equal;
120    typedef Alloc                                                      allocator_type;
121    typedef pair<const key_type, mapped_type>                          value_type;
122    typedef value_type&                                                reference;
123    typedef const value_type&                                          const_reference;
124    typedef typename allocator_traits<allocator_type>::pointer         pointer;
125    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
126    typedef typename allocator_traits<allocator_type>::size_type       size_type;
127    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
128
129    typedef /unspecified/ iterator;
130    typedef /unspecified/ const_iterator;
131
132    explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),
133                           const key_equal& eql = key_equal(),
134                           const allocator_type& a = allocator_type());
135    template <class InputIterator>
136        hash_multimap(InputIterator f, InputIterator l,
137                      size_type n = 193, const hasher& hf = hasher(),
138                      const key_equal& eql = key_equal(),
139                      const allocator_type& a = allocator_type());
140    explicit hash_multimap(const allocator_type&);
141    hash_multimap(const hash_multimap&);
142    ~hash_multimap();
143    hash_multimap& operator=(const hash_multimap&);
144
145    allocator_type get_allocator() const;
146
147    bool      empty() const;
148    size_type size() const;
149    size_type max_size() const;
150
151    iterator       begin();
152    iterator       end();
153    const_iterator begin()  const;
154    const_iterator end()    const;
155
156    iterator insert(const value_type& obj);
157    template <class InputIterator>
158        void insert(InputIterator first, InputIterator last);
159
160    void erase(const_iterator position);
161    size_type erase(const key_type& k);
162    void erase(const_iterator first, const_iterator last);
163    void clear();
164
165    void swap(hash_multimap&);
166
167    hasher hash_funct() const;
168    key_equal key_eq() const;
169
170    iterator       find(const key_type& k);
171    const_iterator find(const key_type& k) const;
172    size_type count(const key_type& k) const;
173    pair<iterator, iterator>             equal_range(const key_type& k);
174    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
175
176    size_type bucket_count() const;
177    size_type max_bucket_count() const;
178
179    size_type elems_in_bucket(size_type n) const;
180
181    void resize(size_type n);
182};
183
184template <class Key, class T, class Hash, class Pred, class Alloc>
185    void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,
186              hash_multimap<Key, T, Hash, Pred, Alloc>& y);
187
188template <class Key, class T, class Hash, class Pred, class Alloc>
189    bool
190    operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
191               const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
192
193template <class Key, class T, class Hash, class Pred, class Alloc>
194    bool
195    operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
196               const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
197
198}  // __gnu_cxx
199
200*/
201
202#include <__config>
203#include <__hash_table>
204#include <functional>
205#include <stdexcept>
206#include <type_traits>
207#include <ext/__hash>
208
209#if __DEPRECATED
210#if defined(_LIBCPP_WARNING)
211    _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated.  Migrate to <unordered_map>")
212#else
213#   warning Use of the header <ext/hash_map> is deprecated.  Migrate to <unordered_map>
214#endif
215#endif
216
217#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
218#pragma GCC system_header
219#endif
220
221namespace __gnu_cxx {
222
223using namespace std;
224
225template <class _Tp, class _Hash,
226          bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value
227        >
228class __hash_map_hasher
229    : private _Hash
230{
231public:
232    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {}
233    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
234    _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;}
235    _LIBCPP_INLINE_VISIBILITY
236    size_t operator()(const _Tp& __x) const
237        {return static_cast<const _Hash&>(*this)(__x.first);}
238    _LIBCPP_INLINE_VISIBILITY
239    size_t operator()(const typename _Tp::first_type& __x) const
240        {return static_cast<const _Hash&>(*this)(__x);}
241};
242
243template <class _Tp, class _Hash>
244class __hash_map_hasher<_Tp, _Hash, false>
245{
246    _Hash __hash_;
247public:
248    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {}
249    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
250    _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;}
251    _LIBCPP_INLINE_VISIBILITY
252    size_t operator()(const _Tp& __x) const
253        {return __hash_(__x.first);}
254    _LIBCPP_INLINE_VISIBILITY
255    size_t operator()(const typename _Tp::first_type& __x) const
256        {return __hash_(__x);}
257};
258
259template <class _Tp, class _Pred,
260          bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value
261         >
262class __hash_map_equal
263    : private _Pred
264{
265public:
266    _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {}
267    _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
268    _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;}
269    _LIBCPP_INLINE_VISIBILITY
270    bool operator()(const _Tp& __x, const _Tp& __y) const
271        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
272    _LIBCPP_INLINE_VISIBILITY
273    bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
274        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
275    _LIBCPP_INLINE_VISIBILITY
276    bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
277        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
278    _LIBCPP_INLINE_VISIBILITY
279    bool operator()(const typename _Tp::first_type& __x,
280                    const typename _Tp::first_type& __y) const
281        {return static_cast<const _Pred&>(*this)(__x, __y);}
282};
283
284template <class _Tp, class _Pred>
285class __hash_map_equal<_Tp, _Pred, false>
286{
287    _Pred __pred_;
288public:
289    _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {}
290    _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
291    _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;}
292    _LIBCPP_INLINE_VISIBILITY
293    bool operator()(const _Tp& __x, const _Tp& __y) const
294        {return __pred_(__x.first, __y.first);}
295    _LIBCPP_INLINE_VISIBILITY
296    bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
297        {return __pred_(__x, __y.first);}
298    _LIBCPP_INLINE_VISIBILITY
299    bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
300        {return __pred_(__x.first, __y);}
301    _LIBCPP_INLINE_VISIBILITY
302    bool operator()(const typename _Tp::first_type& __x,
303                    const typename _Tp::first_type& __y) const
304        {return __pred_(__x, __y);}
305};
306
307template <class _Alloc>
308class __hash_map_node_destructor
309{
310    typedef _Alloc                              allocator_type;
311    typedef allocator_traits<allocator_type>    __alloc_traits;
312    typedef typename __alloc_traits::value_type::__node_value_type value_type;
313public:
314    typedef typename __alloc_traits::pointer    pointer;
315private:
316    typedef typename value_type::first_type     first_type;
317    typedef typename value_type::second_type    second_type;
318
319    allocator_type& __na_;
320
321    __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
322
323public:
324    bool __first_constructed;
325    bool __second_constructed;
326
327    _LIBCPP_INLINE_VISIBILITY
328    explicit __hash_map_node_destructor(allocator_type& __na)
329        : __na_(__na),
330          __first_constructed(false),
331          __second_constructed(false)
332        {}
333
334#ifndef _LIBCPP_CXX03_LANG
335    _LIBCPP_INLINE_VISIBILITY
336    __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
337        : __na_(__x.__na_),
338          __first_constructed(__x.__value_constructed),
339          __second_constructed(__x.__value_constructed)
340        {
341            __x.__value_constructed = false;
342        }
343#else  // _LIBCPP_CXX03_LANG
344    _LIBCPP_INLINE_VISIBILITY
345    __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
346        : __na_(__x.__na_),
347          __first_constructed(__x.__value_constructed),
348          __second_constructed(__x.__value_constructed)
349        {
350            const_cast<bool&>(__x.__value_constructed) = false;
351        }
352#endif  // _LIBCPP_CXX03_LANG
353
354    _LIBCPP_INLINE_VISIBILITY
355    void operator()(pointer __p)
356    {
357        if (__second_constructed)
358            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
359        if (__first_constructed)
360            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
361        if (__p)
362            __alloc_traits::deallocate(__na_, __p, 1);
363    }
364};
365
366template <class _HashIterator>
367class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
368{
369    _HashIterator __i_;
370
371    typedef const typename _HashIterator::value_type::first_type key_type;
372    typedef typename _HashIterator::value_type::second_type      mapped_type;
373public:
374    typedef forward_iterator_tag                                 iterator_category;
375    typedef pair<key_type, mapped_type>                          value_type;
376    typedef typename _HashIterator::difference_type              difference_type;
377    typedef value_type&                                          reference;
378    typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type
379        pointer;
380
381    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}
382
383    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
384
385    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();}
386    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();}
387
388    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;}
389    _LIBCPP_INLINE_VISIBILITY
390    __hash_map_iterator operator++(int)
391    {
392        __hash_map_iterator __t(*this);
393        ++(*this);
394        return __t;
395    }
396
397    friend _LIBCPP_INLINE_VISIBILITY
398    bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
399        {return __x.__i_ == __y.__i_;}
400    friend _LIBCPP_INLINE_VISIBILITY
401    bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
402        {return __x.__i_ != __y.__i_;}
403
404    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map;
405    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
406    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
407    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
408    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
409};
410
411template <class _HashIterator>
412class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
413{
414    _HashIterator __i_;
415
416    typedef const typename _HashIterator::value_type::first_type key_type;
417    typedef typename _HashIterator::value_type::second_type      mapped_type;
418public:
419    typedef forward_iterator_tag                                 iterator_category;
420    typedef pair<key_type, mapped_type>                          value_type;
421    typedef typename _HashIterator::difference_type              difference_type;
422    typedef const value_type&                                    reference;
423    typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type
424        pointer;
425
426    _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}
427
428    _LIBCPP_INLINE_VISIBILITY
429    __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
430    _LIBCPP_INLINE_VISIBILITY
431    __hash_map_const_iterator(
432            __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
433                : __i_(__i.__i_) {}
434
435    _LIBCPP_INLINE_VISIBILITY
436    reference operator*() const {return *operator->();}
437    _LIBCPP_INLINE_VISIBILITY
438    pointer operator->() const {return (pointer)__i_.operator->();}
439
440    _LIBCPP_INLINE_VISIBILITY
441    __hash_map_const_iterator& operator++() {++__i_; return *this;}
442    _LIBCPP_INLINE_VISIBILITY
443    __hash_map_const_iterator operator++(int)
444    {
445        __hash_map_const_iterator __t(*this);
446        ++(*this);
447        return __t;
448    }
449
450    friend _LIBCPP_INLINE_VISIBILITY
451    bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
452        {return __x.__i_ == __y.__i_;}
453    friend _LIBCPP_INLINE_VISIBILITY
454    bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
455        {return __x.__i_ != __y.__i_;}
456
457    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map;
458    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
459    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
460    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
461};
462
463template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
464          class _Alloc = allocator<pair<const _Key, _Tp> > >
465class _LIBCPP_TEMPLATE_VIS hash_map
466{
467public:
468    // types
469    typedef _Key                                           key_type;
470    typedef _Tp                                            mapped_type;
471    typedef _Tp                                            data_type;
472    typedef _Hash                                          hasher;
473    typedef _Pred                                          key_equal;
474    typedef _Alloc                                         allocator_type;
475    typedef pair<const key_type, mapped_type>              value_type;
476    typedef value_type&                                    reference;
477    typedef const value_type&                              const_reference;
478
479private:
480    typedef pair<key_type, mapped_type>                    __value_type;
481    typedef __hash_map_hasher<__value_type, hasher>   __hasher;
482    typedef __hash_map_equal<__value_type, key_equal> __key_equal;
483    typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __value_type>::type __allocator_type;
484
485    typedef __hash_table<__value_type, __hasher,
486                         __key_equal,  __allocator_type>   __table;
487
488    __table __table_;
489
490    typedef typename __table::__node_pointer               __node_pointer;
491    typedef typename __table::__node_const_pointer         __node_const_pointer;
492    typedef typename __table::__node_traits                __node_traits;
493    typedef typename __table::__node_allocator             __node_allocator;
494    typedef typename __table::__node                       __node;
495    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
496    typedef unique_ptr<__node, _Dp>                         __node_holder;
497    typedef allocator_traits<allocator_type>               __alloc_traits;
498public:
499    typedef typename __alloc_traits::pointer         pointer;
500    typedef typename __alloc_traits::const_pointer   const_pointer;
501    typedef typename __alloc_traits::size_type       size_type;
502    typedef typename __alloc_traits::difference_type difference_type;
503
504    typedef __hash_map_iterator<typename __table::iterator>       iterator;
505    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
506
507    _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);}
508    explicit hash_map(size_type __n, const hasher& __hf = hasher(),
509                           const key_equal& __eql = key_equal());
510    hash_map(size_type __n, const hasher& __hf,
511                  const key_equal& __eql,
512                  const allocator_type& __a);
513    template <class _InputIterator>
514        hash_map(_InputIterator __first, _InputIterator __last);
515    template <class _InputIterator>
516        hash_map(_InputIterator __first, _InputIterator __last,
517                      size_type __n, const hasher& __hf = hasher(),
518                      const key_equal& __eql = key_equal());
519    template <class _InputIterator>
520        hash_map(_InputIterator __first, _InputIterator __last,
521                      size_type __n, const hasher& __hf,
522                      const key_equal& __eql,
523                      const allocator_type& __a);
524    hash_map(const hash_map& __u);
525
526    _LIBCPP_INLINE_VISIBILITY
527    allocator_type get_allocator() const
528        {return allocator_type(__table_.__node_alloc());}
529
530    _LIBCPP_INLINE_VISIBILITY
531    bool      empty() const {return __table_.size() == 0;}
532    _LIBCPP_INLINE_VISIBILITY
533    size_type size() const  {return __table_.size();}
534    _LIBCPP_INLINE_VISIBILITY
535    size_type max_size() const {return __table_.max_size();}
536
537    _LIBCPP_INLINE_VISIBILITY
538    iterator       begin()        {return __table_.begin();}
539    _LIBCPP_INLINE_VISIBILITY
540    iterator       end()          {return __table_.end();}
541    _LIBCPP_INLINE_VISIBILITY
542    const_iterator begin()  const {return __table_.begin();}
543    _LIBCPP_INLINE_VISIBILITY
544    const_iterator end()    const {return __table_.end();}
545
546    _LIBCPP_INLINE_VISIBILITY
547    pair<iterator, bool> insert(const value_type& __x)
548        {return __table_.__insert_unique(__x);}
549    _LIBCPP_INLINE_VISIBILITY
550    iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
551    template <class _InputIterator>
552        _LIBCPP_INLINE_VISIBILITY
553        void insert(_InputIterator __first, _InputIterator __last);
554
555    _LIBCPP_INLINE_VISIBILITY
556    void erase(const_iterator __p) {__table_.erase(__p.__i_);}
557    _LIBCPP_INLINE_VISIBILITY
558    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
559    _LIBCPP_INLINE_VISIBILITY
560    void erase(const_iterator __first, const_iterator __last)
561        {__table_.erase(__first.__i_, __last.__i_);}
562    _LIBCPP_INLINE_VISIBILITY
563    void clear() {__table_.clear();}
564
565    _LIBCPP_INLINE_VISIBILITY
566    void swap(hash_map& __u) {__table_.swap(__u.__table_);}
567
568    _LIBCPP_INLINE_VISIBILITY
569    hasher hash_funct() const
570        {return __table_.hash_function().hash_function();}
571    _LIBCPP_INLINE_VISIBILITY
572    key_equal key_eq() const
573        {return __table_.key_eq().key_eq();}
574
575    _LIBCPP_INLINE_VISIBILITY
576    iterator       find(const key_type& __k)       {return __table_.find(__k);}
577    _LIBCPP_INLINE_VISIBILITY
578    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
579    _LIBCPP_INLINE_VISIBILITY
580    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
581    _LIBCPP_INLINE_VISIBILITY
582    pair<iterator, iterator>             equal_range(const key_type& __k)
583        {return __table_.__equal_range_unique(__k);}
584    _LIBCPP_INLINE_VISIBILITY
585    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
586        {return __table_.__equal_range_unique(__k);}
587
588    mapped_type& operator[](const key_type& __k);
589
590    _LIBCPP_INLINE_VISIBILITY
591    size_type bucket_count() const {return __table_.bucket_count();}
592    _LIBCPP_INLINE_VISIBILITY
593    size_type max_bucket_count() const {return __table_.max_bucket_count();}
594
595    _LIBCPP_INLINE_VISIBILITY
596    size_type elems_in_bucket(size_type __n) const
597        {return __table_.bucket_size(__n);}
598
599    _LIBCPP_INLINE_VISIBILITY
600    void resize(size_type __n) {__table_.rehash(__n);}
601
602private:
603    __node_holder __construct_node(const key_type& __k);
604};
605
606template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
607hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
608        size_type __n, const hasher& __hf, const key_equal& __eql)
609    : __table_(__hf, __eql)
610{
611    __table_.rehash(__n);
612}
613
614template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
615hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
616        size_type __n, const hasher& __hf, const key_equal& __eql,
617        const allocator_type& __a)
618    : __table_(__hf, __eql, __a)
619{
620    __table_.rehash(__n);
621}
622
623template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
624template <class _InputIterator>
625hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
626        _InputIterator __first, _InputIterator __last)
627{
628    __table_.rehash(193);
629    insert(__first, __last);
630}
631
632template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
633template <class _InputIterator>
634hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
635        _InputIterator __first, _InputIterator __last, size_type __n,
636        const hasher& __hf, const key_equal& __eql)
637    : __table_(__hf, __eql)
638{
639    __table_.rehash(__n);
640    insert(__first, __last);
641}
642
643template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
644template <class _InputIterator>
645hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
646        _InputIterator __first, _InputIterator __last, size_type __n,
647        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
648    : __table_(__hf, __eql, __a)
649{
650    __table_.rehash(__n);
651    insert(__first, __last);
652}
653
654template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
655hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
656        const hash_map& __u)
657    : __table_(__u.__table_)
658{
659    __table_.rehash(__u.bucket_count());
660    insert(__u.begin(), __u.end());
661}
662
663template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
664typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
665hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
666{
667    __node_allocator& __na = __table_.__node_alloc();
668    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
669    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
670    __h.get_deleter().__first_constructed = true;
671    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
672    __h.get_deleter().__second_constructed = true;
673    return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
674}
675
676template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
677template <class _InputIterator>
678inline
679void
680hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
681                                                       _InputIterator __last)
682{
683    for (; __first != __last; ++__first)
684        __table_.__insert_unique(*__first);
685}
686
687template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
688_Tp&
689hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
690{
691    iterator __i = find(__k);
692    if (__i != end())
693        return __i->second;
694    __node_holder __h = __construct_node(__k);
695    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
696    __h.release();
697    return __r.first->second;
698}
699
700template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
701inline _LIBCPP_INLINE_VISIBILITY
702void
703swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
704     hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
705{
706    __x.swap(__y);
707}
708
709template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
710bool
711operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
712           const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
713{
714    if (__x.size() != __y.size())
715        return false;
716    typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
717                                                                 const_iterator;
718    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
719            __i != __ex; ++__i)
720    {
721        const_iterator __j = __y.find(__i->first);
722        if (__j == __ey || !(*__i == *__j))
723            return false;
724    }
725    return true;
726}
727
728template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
729inline _LIBCPP_INLINE_VISIBILITY
730bool
731operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
732           const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
733{
734    return !(__x == __y);
735}
736
737template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
738          class _Alloc = allocator<pair<const _Key, _Tp> > >
739class _LIBCPP_TEMPLATE_VIS hash_multimap
740{
741public:
742    // types
743    typedef _Key                                           key_type;
744    typedef _Tp                                            mapped_type;
745    typedef _Tp                                            data_type;
746    typedef _Hash                                          hasher;
747    typedef _Pred                                          key_equal;
748    typedef _Alloc                                         allocator_type;
749    typedef pair<const key_type, mapped_type>              value_type;
750    typedef value_type&                                    reference;
751    typedef const value_type&                              const_reference;
752
753private:
754    typedef pair<key_type, mapped_type>                    __value_type;
755    typedef __hash_map_hasher<__value_type, hasher>   __hasher;
756    typedef __hash_map_equal<__value_type, key_equal> __key_equal;
757    typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __value_type>::type __allocator_type;
758
759    typedef __hash_table<__value_type, __hasher,
760                         __key_equal,  __allocator_type>   __table;
761
762    __table __table_;
763
764    typedef typename __table::__node_traits                __node_traits;
765    typedef typename __table::__node_allocator             __node_allocator;
766    typedef typename __table::__node                       __node;
767    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
768    typedef unique_ptr<__node, _Dp>                         __node_holder;
769    typedef allocator_traits<allocator_type>               __alloc_traits;
770public:
771    typedef typename __alloc_traits::pointer         pointer;
772    typedef typename __alloc_traits::const_pointer   const_pointer;
773    typedef typename __alloc_traits::size_type       size_type;
774    typedef typename __alloc_traits::difference_type difference_type;
775
776    typedef __hash_map_iterator<typename __table::iterator>       iterator;
777    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
778
779    _LIBCPP_INLINE_VISIBILITY
780    hash_multimap() {__table_.rehash(193);}
781    explicit hash_multimap(size_type __n, const hasher& __hf = hasher(),
782                                const key_equal& __eql = key_equal());
783    hash_multimap(size_type __n, const hasher& __hf,
784                                const key_equal& __eql,
785                                const allocator_type& __a);
786    template <class _InputIterator>
787        hash_multimap(_InputIterator __first, _InputIterator __last);
788    template <class _InputIterator>
789        hash_multimap(_InputIterator __first, _InputIterator __last,
790                      size_type __n, const hasher& __hf = hasher(),
791                      const key_equal& __eql = key_equal());
792    template <class _InputIterator>
793        hash_multimap(_InputIterator __first, _InputIterator __last,
794                      size_type __n, const hasher& __hf,
795                      const key_equal& __eql,
796                      const allocator_type& __a);
797    hash_multimap(const hash_multimap& __u);
798
799    _LIBCPP_INLINE_VISIBILITY
800    allocator_type get_allocator() const
801        {return allocator_type(__table_.__node_alloc());}
802
803    _LIBCPP_INLINE_VISIBILITY
804    bool      empty() const {return __table_.size() == 0;}
805    _LIBCPP_INLINE_VISIBILITY
806    size_type size() const  {return __table_.size();}
807    _LIBCPP_INLINE_VISIBILITY
808    size_type max_size() const {return __table_.max_size();}
809
810    _LIBCPP_INLINE_VISIBILITY
811    iterator       begin()        {return __table_.begin();}
812    _LIBCPP_INLINE_VISIBILITY
813    iterator       end()          {return __table_.end();}
814    _LIBCPP_INLINE_VISIBILITY
815    const_iterator begin()  const {return __table_.begin();}
816    _LIBCPP_INLINE_VISIBILITY
817    const_iterator end()    const {return __table_.end();}
818
819    _LIBCPP_INLINE_VISIBILITY
820    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
821    _LIBCPP_INLINE_VISIBILITY
822    iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
823    template <class _InputIterator>
824        _LIBCPP_INLINE_VISIBILITY
825        void insert(_InputIterator __first, _InputIterator __last);
826
827    _LIBCPP_INLINE_VISIBILITY
828    void erase(const_iterator __p) {__table_.erase(__p.__i_);}
829    _LIBCPP_INLINE_VISIBILITY
830    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
831    _LIBCPP_INLINE_VISIBILITY
832    void erase(const_iterator __first, const_iterator __last)
833        {__table_.erase(__first.__i_, __last.__i_);}
834    _LIBCPP_INLINE_VISIBILITY
835    void clear() {__table_.clear();}
836
837    _LIBCPP_INLINE_VISIBILITY
838    void swap(hash_multimap& __u) {__table_.swap(__u.__table_);}
839
840    _LIBCPP_INLINE_VISIBILITY
841    hasher hash_funct() const
842        {return __table_.hash_function().hash_function();}
843    _LIBCPP_INLINE_VISIBILITY
844    key_equal key_eq() const
845        {return __table_.key_eq().key_eq();}
846
847    _LIBCPP_INLINE_VISIBILITY
848    iterator       find(const key_type& __k)       {return __table_.find(__k);}
849    _LIBCPP_INLINE_VISIBILITY
850    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
851    _LIBCPP_INLINE_VISIBILITY
852    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
853    _LIBCPP_INLINE_VISIBILITY
854    pair<iterator, iterator>             equal_range(const key_type& __k)
855        {return __table_.__equal_range_multi(__k);}
856    _LIBCPP_INLINE_VISIBILITY
857    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
858        {return __table_.__equal_range_multi(__k);}
859
860    _LIBCPP_INLINE_VISIBILITY
861    size_type bucket_count() const {return __table_.bucket_count();}
862    _LIBCPP_INLINE_VISIBILITY
863    size_type max_bucket_count() const {return __table_.max_bucket_count();}
864
865    _LIBCPP_INLINE_VISIBILITY
866    size_type elems_in_bucket(size_type __n) const
867        {return __table_.bucket_size(__n);}
868
869    _LIBCPP_INLINE_VISIBILITY
870    void resize(size_type __n) {__table_.rehash(__n);}
871};
872
873template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
874hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
875        size_type __n, const hasher& __hf, const key_equal& __eql)
876    : __table_(__hf, __eql)
877{
878    __table_.rehash(__n);
879}
880
881template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
882hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
883        size_type __n, const hasher& __hf, const key_equal& __eql,
884        const allocator_type& __a)
885    : __table_(__hf, __eql, __a)
886{
887    __table_.rehash(__n);
888}
889
890template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
891template <class _InputIterator>
892hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
893        _InputIterator __first, _InputIterator __last)
894{
895    __table_.rehash(193);
896    insert(__first, __last);
897}
898
899template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
900template <class _InputIterator>
901hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
902        _InputIterator __first, _InputIterator __last, size_type __n,
903        const hasher& __hf, const key_equal& __eql)
904    : __table_(__hf, __eql)
905{
906    __table_.rehash(__n);
907    insert(__first, __last);
908}
909
910template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
911template <class _InputIterator>
912hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
913        _InputIterator __first, _InputIterator __last, size_type __n,
914        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
915    : __table_(__hf, __eql, __a)
916{
917    __table_.rehash(__n);
918    insert(__first, __last);
919}
920
921template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
922hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
923        const hash_multimap& __u)
924    : __table_(__u.__table_)
925{
926    __table_.rehash(__u.bucket_count());
927    insert(__u.begin(), __u.end());
928}
929
930template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
931template <class _InputIterator>
932inline
933void
934hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
935                                                            _InputIterator __last)
936{
937    for (; __first != __last; ++__first)
938        __table_.__insert_multi(*__first);
939}
940
941template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
942inline _LIBCPP_INLINE_VISIBILITY
943void
944swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
945     hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
946{
947    __x.swap(__y);
948}
949
950template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
951bool
952operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
953           const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
954{
955    if (__x.size() != __y.size())
956        return false;
957    typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
958                                                                 const_iterator;
959    typedef pair<const_iterator, const_iterator> _EqRng;
960    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
961    {
962        _EqRng __xeq = __x.equal_range(__i->first);
963        _EqRng __yeq = __y.equal_range(__i->first);
964        if (_VSTD::distance(__xeq.first, __xeq.second) !=
965            _VSTD::distance(__yeq.first, __yeq.second) ||
966                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
967            return false;
968        __i = __xeq.second;
969    }
970    return true;
971}
972
973template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
974inline _LIBCPP_INLINE_VISIBILITY
975bool
976operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
977           const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
978{
979    return !(__x == __y);
980}
981
982} // __gnu_cxx
983
984#endif  // _LIBCPP_HASH_MAP
985