include/ext/hash_map

   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
  18 namespace __gnu_cxx
  19 {
  20
  21 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
  22           class Alloc = allocator<pair<const Key, T>>>
  23 class hash_map
  24 {
  25 public:
  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
  96 template <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
 100 template <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
 105 template <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
 110 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
 111           class Alloc = allocator<pair<const Key, T>>>
 112 class hash_multimap
 113 {
 114 public:
 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
 184 template <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
 188 template <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
 193 template <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_MSVC)
 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
 221 namespace __gnu_cxx {
 222
 223 using namespace std;
 224
 225 template <class _Tp, class _Hash,
 226           bool = is_empty<_Hash>::value && !__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 = is_empty<_Pred>::value && !__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 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     __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
 322
 323 public:
 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_HAS_NO_RVALUE_REFERENCES
 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_HAS_NO_RVALUE_REFERENCES
 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_HAS_NO_RVALUE_REFERENCES
 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
 366 template <class _HashIterator>
 367 class _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;
 373 public:
 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
 411 template <class _HashIterator>
 412 class _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;
 418 public:
 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
 463 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 464           class _Alloc = allocator<pair<const _Key, _Tp> > >
 465 class _LIBCPP_TEMPLATE_VIS hash_map
 466 {
 467 public:
 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
 479 private:
 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;
 498 public:
 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
 602 private:
 603     __node_holder __construct_node(const key_type& __k);
 604 };
 605
 606 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 607 hash_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
 614 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 615 hash_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
 623 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 624 template <class _InputIterator>
 625 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 626         _InputIterator __first, _InputIterator __last)
 627 {
 628     __table_.rehash(193);
 629     insert(__first, __last);
 630 }
 631
 632 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 633 template <class _InputIterator>
 634 hash_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
 643 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 644 template <class _InputIterator>
 645 hash_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
 654 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 655 hash_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
 663 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 664 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 665 hash_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
 676 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 677 template <class _InputIterator>
 678 inline
 679 void
 680 hash_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
 687 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 688 _Tp&
 689 hash_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
 700 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 701 inline _LIBCPP_INLINE_VISIBILITY
 702 void
 703 swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 704      hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 705 {
 706     __x.swap(__y);
 707 }
 708
 709 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 710 bool
 711 operator==(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
 728 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 729 inline _LIBCPP_INLINE_VISIBILITY
 730 bool
 731 operator!=(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
 737 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 738           class _Alloc = allocator<pair<const _Key, _Tp> > >
 739 class _LIBCPP_TEMPLATE_VIS hash_multimap
 740 {
 741 public:
 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
 753 private:
 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;
 770 public:
 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
 873 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 874 hash_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
 881 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 882 hash_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
 890 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 891 template <class _InputIterator>
 892 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 893         _InputIterator __first, _InputIterator __last)
 894 {
 895     __table_.rehash(193);
 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 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