contrib/llvm-project/libcxx/include/ext/hash_map

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