external/bsd/libc++/dist/libcxx/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(_MSC_VER) && ! defined(__clang__)
 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::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_TYPE_VIS_ONLY __hash_map_iterator
 368 {
 369     _HashIterator __i_;
 370
 371     typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 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 forward_iterator_tag                                 iterator_category;
 376     typedef pair<key_type, mapped_type>                          value_type;
 377     typedef typename _HashIterator::difference_type              difference_type;
 378     typedef value_type&                                          reference;
 379     typedef typename __pointer_traits::template
 380 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 381             rebind<value_type>
 382 #else
 383             rebind<value_type>::other
 384 #endif
 385                                                                  pointer;
 386
 387     _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}
 388
 389     _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
 390
 391     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();}
 392     _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();}
 393
 394     _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;}
 395     _LIBCPP_INLINE_VISIBILITY
 396     __hash_map_iterator operator++(int)
 397     {
 398         __hash_map_iterator __t(*this);
 399         ++(*this);
 400         return __t;
 401     }
 402
 403     friend _LIBCPP_INLINE_VISIBILITY
 404     bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 405         {return __x.__i_ == __y.__i_;}
 406     friend _LIBCPP_INLINE_VISIBILITY
 407     bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 408         {return __x.__i_ != __y.__i_;}
 409
 410     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map;
 411     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap;
 412     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
 413     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
 414     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
 415 };
 416
 417 template <class _HashIterator>
 418 class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
 419 {
 420     _HashIterator __i_;
 421
 422     typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 423     typedef const typename _HashIterator::value_type::first_type key_type;
 424     typedef typename _HashIterator::value_type::second_type      mapped_type;
 425 public:
 426     typedef forward_iterator_tag                                 iterator_category;
 427     typedef pair<key_type, mapped_type>                          value_type;
 428     typedef typename _HashIterator::difference_type              difference_type;
 429     typedef const value_type&                                    reference;
 430     typedef typename __pointer_traits::template
 431 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 432             rebind<const value_type>
 433 #else
 434             rebind<const value_type>::other
 435 #endif
 436                                                                  pointer;
 437
 438     _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}
 439
 440     _LIBCPP_INLINE_VISIBILITY
 441     __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
 442     _LIBCPP_INLINE_VISIBILITY
 443     __hash_map_const_iterator(
 444             __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
 445                 : __i_(__i.__i_) {}
 446
 447     _LIBCPP_INLINE_VISIBILITY
 448     reference operator*() const {return *operator->();}
 449     _LIBCPP_INLINE_VISIBILITY
 450     pointer operator->() const {return (pointer)__i_.operator->();}
 451
 452     _LIBCPP_INLINE_VISIBILITY
 453     __hash_map_const_iterator& operator++() {++__i_; return *this;}
 454     _LIBCPP_INLINE_VISIBILITY
 455     __hash_map_const_iterator operator++(int)
 456     {
 457         __hash_map_const_iterator __t(*this);
 458         ++(*this);
 459         return __t;
 460     }
 461
 462     friend _LIBCPP_INLINE_VISIBILITY
 463     bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 464         {return __x.__i_ == __y.__i_;}
 465     friend _LIBCPP_INLINE_VISIBILITY
 466     bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 467         {return __x.__i_ != __y.__i_;}
 468
 469     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map;
 470     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap;
 471     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
 472     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
 473 };
 474
 475 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 476           class _Alloc = allocator<pair<const _Key, _Tp> > >
 477 class _LIBCPP_TYPE_VIS_ONLY hash_map
 478 {
 479 public:
 480     // types
 481     typedef _Key                                           key_type;
 482     typedef _Tp                                            mapped_type;
 483     typedef _Tp                                            data_type;
 484     typedef _Hash                                          hasher;
 485     typedef _Pred                                          key_equal;
 486     typedef _Alloc                                         allocator_type;
 487     typedef pair<const key_type, mapped_type>              value_type;
 488     typedef value_type&                                    reference;
 489     typedef const value_type&                              const_reference;
 490
 491 private:
 492     typedef pair<key_type, mapped_type>                    __value_type;
 493     typedef __hash_map_hasher<__value_type, hasher>   __hasher;
 494     typedef __hash_map_equal<__value_type, key_equal> __key_equal;
 495     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __value_type>::type __allocator_type;
 496
 497     typedef __hash_table<__value_type, __hasher,
 498                          __key_equal,  __allocator_type>   __table;
 499
 500     __table __table_;
 501
 502     typedef typename __table::__node_pointer               __node_pointer;
 503     typedef typename __table::__node_const_pointer         __node_const_pointer;
 504     typedef typename __table::__node_traits                __node_traits;
 505     typedef typename __table::__node_allocator             __node_allocator;
 506     typedef typename __table::__node                       __node;
 507     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 508     typedef unique_ptr<__node, _Dp>                         __node_holder;
 509     typedef allocator_traits<allocator_type>               __alloc_traits;
 510 public:
 511     typedef typename __alloc_traits::pointer         pointer;
 512     typedef typename __alloc_traits::const_pointer   const_pointer;
 513     typedef typename __alloc_traits::size_type       size_type;
 514     typedef typename __alloc_traits::difference_type difference_type;
 515
 516     typedef __hash_map_iterator<typename __table::iterator>       iterator;
 517     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 518
 519     _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);}
 520     explicit hash_map(size_type __n, const hasher& __hf = hasher(),
 521                            const key_equal& __eql = key_equal());
 522     hash_map(size_type __n, const hasher& __hf,
 523                   const key_equal& __eql,
 524                   const allocator_type& __a);
 525     template <class _InputIterator>
 526         hash_map(_InputIterator __first, _InputIterator __last);
 527     template <class _InputIterator>
 528         hash_map(_InputIterator __first, _InputIterator __last,
 529                       size_type __n, const hasher& __hf = hasher(),
 530                       const key_equal& __eql = key_equal());
 531     template <class _InputIterator>
 532         hash_map(_InputIterator __first, _InputIterator __last,
 533                       size_type __n, const hasher& __hf,
 534                       const key_equal& __eql,
 535                       const allocator_type& __a);
 536     hash_map(const hash_map& __u);
 537
 538     _LIBCPP_INLINE_VISIBILITY
 539     allocator_type get_allocator() const
 540         {return allocator_type(__table_.__node_alloc());}
 541
 542     _LIBCPP_INLINE_VISIBILITY
 543     bool      empty() const {return __table_.size() == 0;}
 544     _LIBCPP_INLINE_VISIBILITY
 545     size_type size() const  {return __table_.size();}
 546     _LIBCPP_INLINE_VISIBILITY
 547     size_type max_size() const {return __table_.max_size();}
 548
 549     _LIBCPP_INLINE_VISIBILITY
 550     iterator       begin()        {return __table_.begin();}
 551     _LIBCPP_INLINE_VISIBILITY
 552     iterator       end()          {return __table_.end();}
 553     _LIBCPP_INLINE_VISIBILITY
 554     const_iterator begin()  const {return __table_.begin();}
 555     _LIBCPP_INLINE_VISIBILITY
 556     const_iterator end()    const {return __table_.end();}
 557
 558     _LIBCPP_INLINE_VISIBILITY
 559     pair<iterator, bool> insert(const value_type& __x)
 560         {return __table_.__insert_unique(__x);}
 561     _LIBCPP_INLINE_VISIBILITY
 562     iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
 563     template <class _InputIterator>
 564         void insert(_InputIterator __first, _InputIterator __last);
 565
 566     _LIBCPP_INLINE_VISIBILITY
 567     void erase(const_iterator __p) {__table_.erase(__p.__i_);}
 568     _LIBCPP_INLINE_VISIBILITY
 569     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 570     _LIBCPP_INLINE_VISIBILITY
 571     void erase(const_iterator __first, const_iterator __last)
 572         {__table_.erase(__first.__i_, __last.__i_);}
 573     _LIBCPP_INLINE_VISIBILITY
 574     void clear() {__table_.clear();}
 575
 576     _LIBCPP_INLINE_VISIBILITY
 577     void swap(hash_map& __u) {__table_.swap(__u.__table_);}
 578
 579     _LIBCPP_INLINE_VISIBILITY
 580     hasher hash_funct() const
 581         {return __table_.hash_function().hash_function();}
 582     _LIBCPP_INLINE_VISIBILITY
 583     key_equal key_eq() const
 584         {return __table_.key_eq().key_eq();}
 585
 586     _LIBCPP_INLINE_VISIBILITY
 587     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 588     _LIBCPP_INLINE_VISIBILITY
 589     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 590     _LIBCPP_INLINE_VISIBILITY
 591     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 592     _LIBCPP_INLINE_VISIBILITY
 593     pair<iterator, iterator>             equal_range(const key_type& __k)
 594         {return __table_.__equal_range_unique(__k);}
 595     _LIBCPP_INLINE_VISIBILITY
 596     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 597         {return __table_.__equal_range_unique(__k);}
 598
 599     mapped_type& operator[](const key_type& __k);
 600
 601     _LIBCPP_INLINE_VISIBILITY
 602     size_type bucket_count() const {return __table_.bucket_count();}
 603     _LIBCPP_INLINE_VISIBILITY
 604     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 605
 606     _LIBCPP_INLINE_VISIBILITY
 607     size_type elems_in_bucket(size_type __n) const
 608         {return __table_.bucket_size(__n);}
 609
 610     _LIBCPP_INLINE_VISIBILITY
 611     void resize(size_type __n) {__table_.rehash(__n);}
 612
 613 private:
 614     __node_holder __construct_node(const key_type& __k);
 615 };
 616
 617 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 618 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 619         size_type __n, const hasher& __hf, const key_equal& __eql)
 620     : __table_(__hf, __eql)
 621 {
 622     __table_.rehash(__n);
 623 }
 624
 625 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 626 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 627         size_type __n, const hasher& __hf, const key_equal& __eql,
 628         const allocator_type& __a)
 629     : __table_(__hf, __eql, __a)
 630 {
 631     __table_.rehash(__n);
 632 }
 633
 634 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 635 template <class _InputIterator>
 636 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 637         _InputIterator __first, _InputIterator __last)
 638 {
 639     __table_.rehash(193);
 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)
 648     : __table_(__hf, __eql)
 649 {
 650     __table_.rehash(__n);
 651     insert(__first, __last);
 652 }
 653
 654 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 655 template <class _InputIterator>
 656 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 657         _InputIterator __first, _InputIterator __last, size_type __n,
 658         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 659     : __table_(__hf, __eql, __a)
 660 {
 661     __table_.rehash(__n);
 662     insert(__first, __last);
 663 }
 664
 665 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 666 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 667         const hash_map& __u)
 668     : __table_(__u.__table_)
 669 {
 670     __table_.rehash(__u.bucket_count());
 671     insert(__u.begin(), __u.end());
 672 }
 673
 674 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 675 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 676 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
 677 {
 678     __node_allocator& __na = __table_.__node_alloc();
 679     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 680     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
 681     __h.get_deleter().__first_constructed = true;
 682     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 683     __h.get_deleter().__second_constructed = true;
 684     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 685 }
 686
 687 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 688 template <class _InputIterator>
 689 inline _LIBCPP_INLINE_VISIBILITY
 690 void
 691 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 692                                                        _InputIterator __last)
 693 {
 694     for (; __first != __last; ++__first)
 695         __table_.__insert_unique(*__first);
 696 }
 697
 698 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 699 _Tp&
 700 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
 701 {
 702     iterator __i = find(__k);
 703     if (__i != end())
 704         return __i->second;
 705     __node_holder __h = __construct_node(__k);
 706     pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
 707     __h.release();
 708     return __r.first->second;
 709 }
 710
 711 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 712 inline _LIBCPP_INLINE_VISIBILITY
 713 void
 714 swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 715      hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 716 {
 717     __x.swap(__y);
 718 }
 719
 720 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 721 bool
 722 operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 723            const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 724 {
 725     if (__x.size() != __y.size())
 726         return false;
 727     typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
 728                                                                  const_iterator;
 729     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 730             __i != __ex; ++__i)
 731     {
 732         const_iterator __j = __y.find(__i->first);
 733         if (__j == __ey || !(*__i == *__j))
 734             return false;
 735     }
 736     return true;
 737 }
 738
 739 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 740 inline _LIBCPP_INLINE_VISIBILITY
 741 bool
 742 operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 743            const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 744 {
 745     return !(__x == __y);
 746 }
 747
 748 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 749           class _Alloc = allocator<pair<const _Key, _Tp> > >
 750 class _LIBCPP_TYPE_VIS_ONLY hash_multimap
 751 {
 752 public:
 753     // types
 754     typedef _Key                                           key_type;
 755     typedef _Tp                                            mapped_type;
 756     typedef _Tp                                            data_type;
 757     typedef _Hash                                          hasher;
 758     typedef _Pred                                          key_equal;
 759     typedef _Alloc                                         allocator_type;
 760     typedef pair<const key_type, mapped_type>              value_type;
 761     typedef value_type&                                    reference;
 762     typedef const value_type&                              const_reference;
 763
 764 private:
 765     typedef pair<key_type, mapped_type>                    __value_type;
 766     typedef __hash_map_hasher<__value_type, hasher>   __hasher;
 767     typedef __hash_map_equal<__value_type, key_equal> __key_equal;
 768     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __value_type>::type __allocator_type;
 769
 770     typedef __hash_table<__value_type, __hasher,
 771                          __key_equal,  __allocator_type>   __table;
 772
 773     __table __table_;
 774
 775     typedef typename __table::__node_traits                __node_traits;
 776     typedef typename __table::__node_allocator             __node_allocator;
 777     typedef typename __table::__node                       __node;
 778     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 779     typedef unique_ptr<__node, _Dp>                         __node_holder;
 780     typedef allocator_traits<allocator_type>               __alloc_traits;
 781 public:
 782     typedef typename __alloc_traits::pointer         pointer;
 783     typedef typename __alloc_traits::const_pointer   const_pointer;
 784     typedef typename __alloc_traits::size_type       size_type;
 785     typedef typename __alloc_traits::difference_type difference_type;
 786
 787     typedef __hash_map_iterator<typename __table::iterator>       iterator;
 788     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 789
 790     _LIBCPP_INLINE_VISIBILITY
 791     hash_multimap() {__table_.rehash(193);}
 792     explicit hash_multimap(size_type __n, const hasher& __hf = hasher(),
 793                                 const key_equal& __eql = key_equal());
 794     hash_multimap(size_type __n, const hasher& __hf,
 795                                 const key_equal& __eql,
 796                                 const allocator_type& __a);
 797     template <class _InputIterator>
 798         hash_multimap(_InputIterator __first, _InputIterator __last);
 799     template <class _InputIterator>
 800         hash_multimap(_InputIterator __first, _InputIterator __last,
 801                       size_type __n, const hasher& __hf = hasher(),
 802                       const key_equal& __eql = key_equal());
 803     template <class _InputIterator>
 804         hash_multimap(_InputIterator __first, _InputIterator __last,
 805                       size_type __n, const hasher& __hf,
 806                       const key_equal& __eql,
 807                       const allocator_type& __a);
 808     hash_multimap(const hash_multimap& __u);
 809
 810     _LIBCPP_INLINE_VISIBILITY
 811     allocator_type get_allocator() const
 812         {return allocator_type(__table_.__node_alloc());}
 813
 814     _LIBCPP_INLINE_VISIBILITY
 815     bool      empty() const {return __table_.size() == 0;}
 816     _LIBCPP_INLINE_VISIBILITY
 817     size_type size() const  {return __table_.size();}
 818     _LIBCPP_INLINE_VISIBILITY
 819     size_type max_size() const {return __table_.max_size();}
 820
 821     _LIBCPP_INLINE_VISIBILITY
 822     iterator       begin()        {return __table_.begin();}
 823     _LIBCPP_INLINE_VISIBILITY
 824     iterator       end()          {return __table_.end();}
 825     _LIBCPP_INLINE_VISIBILITY
 826     const_iterator begin()  const {return __table_.begin();}
 827     _LIBCPP_INLINE_VISIBILITY
 828     const_iterator end()    const {return __table_.end();}
 829
 830     _LIBCPP_INLINE_VISIBILITY
 831     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 832     _LIBCPP_INLINE_VISIBILITY
 833     iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
 834     template <class _InputIterator>
 835         void insert(_InputIterator __first, _InputIterator __last);
 836
 837     _LIBCPP_INLINE_VISIBILITY
 838     void erase(const_iterator __p) {__table_.erase(__p.__i_);}
 839     _LIBCPP_INLINE_VISIBILITY
 840     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 841     _LIBCPP_INLINE_VISIBILITY
 842     void erase(const_iterator __first, const_iterator __last)
 843         {__table_.erase(__first.__i_, __last.__i_);}
 844     _LIBCPP_INLINE_VISIBILITY
 845     void clear() {__table_.clear();}
 846
 847     _LIBCPP_INLINE_VISIBILITY
 848     void swap(hash_multimap& __u) {__table_.swap(__u.__table_);}
 849
 850     _LIBCPP_INLINE_VISIBILITY
 851     hasher hash_funct() const
 852         {return __table_.hash_function().hash_function();}
 853     _LIBCPP_INLINE_VISIBILITY
 854     key_equal key_eq() const
 855         {return __table_.key_eq().key_eq();}
 856
 857     _LIBCPP_INLINE_VISIBILITY
 858     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 859     _LIBCPP_INLINE_VISIBILITY
 860     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 861     _LIBCPP_INLINE_VISIBILITY
 862     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 863     _LIBCPP_INLINE_VISIBILITY
 864     pair<iterator, iterator>             equal_range(const key_type& __k)
 865         {return __table_.__equal_range_multi(__k);}
 866     _LIBCPP_INLINE_VISIBILITY
 867     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 868         {return __table_.__equal_range_multi(__k);}
 869
 870     _LIBCPP_INLINE_VISIBILITY
 871     size_type bucket_count() const {return __table_.bucket_count();}
 872     _LIBCPP_INLINE_VISIBILITY
 873     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 874
 875     _LIBCPP_INLINE_VISIBILITY
 876     size_type elems_in_bucket(size_type __n) const
 877         {return __table_.bucket_size(__n);}
 878
 879     _LIBCPP_INLINE_VISIBILITY
 880     void resize(size_type __n) {__table_.rehash(__n);}
 881 };
 882
 883 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 884 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 885         size_type __n, const hasher& __hf, const key_equal& __eql)
 886     : __table_(__hf, __eql)
 887 {
 888     __table_.rehash(__n);
 889 }
 890
 891 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 892 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 893         size_type __n, const hasher& __hf, const key_equal& __eql,
 894         const allocator_type& __a)
 895     : __table_(__hf, __eql, __a)
 896 {
 897     __table_.rehash(__n);
 898 }
 899
 900 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 901 template <class _InputIterator>
 902 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 903         _InputIterator __first, _InputIterator __last)
 904 {
 905     __table_.rehash(193);
 906     insert(__first, __last);
 907 }
 908
 909 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 910 template <class _InputIterator>
 911 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 912         _InputIterator __first, _InputIterator __last, size_type __n,
 913         const hasher& __hf, const key_equal& __eql)
 914     : __table_(__hf, __eql)
 915 {
 916     __table_.rehash(__n);
 917     insert(__first, __last);
 918 }
 919
 920 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 921 template <class _InputIterator>
 922 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 923         _InputIterator __first, _InputIterator __last, size_type __n,
 924         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 925     : __table_(__hf, __eql, __a)
 926 {
 927     __table_.rehash(__n);
 928     insert(__first, __last);
 929 }
 930
 931 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 932 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 933         const hash_multimap& __u)
 934     : __table_(__u.__table_)
 935 {
 936     __table_.rehash(__u.bucket_count());
 937     insert(__u.begin(), __u.end());
 938 }
 939
 940 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 941 template <class _InputIterator>
 942 inline _LIBCPP_INLINE_VISIBILITY
 943 void
 944 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 945                                                             _InputIterator __last)
 946 {
 947     for (; __first != __last; ++__first)
 948         __table_.__insert_multi(*__first);
 949 }
 950
 951 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 952 inline _LIBCPP_INLINE_VISIBILITY
 953 void
 954 swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 955      hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 956 {
 957     __x.swap(__y);
 958 }
 959
 960 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 961 bool
 962 operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 963            const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 964 {
 965     if (__x.size() != __y.size())
 966         return false;
 967     typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
 968                                                                  const_iterator;
 969     typedef pair<const_iterator, const_iterator> _EqRng;
 970     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
 971     {
 972         _EqRng __xeq = __x.equal_range(__i->first);
 973         _EqRng __yeq = __y.equal_range(__i->first);
 974         if (_VSTD::distance(__xeq.first, __xeq.second) !=
 975             _VSTD::distance(__yeq.first, __yeq.second) ||
 976                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 977             return false;
 978         __i = __xeq.second;
 979     }
 980     return true;
 981 }
 982
 983 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 984 inline _LIBCPP_INLINE_VISIBILITY
 985 bool
 986 operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 987            const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 988 {
 989     return !(__x == __y);
 990 }
 991
 992 } // __gnu_cxx
 993
 994 #endif  // _LIBCPP_HASH_MAP