contrib/libc++/include/unordered_map

   1 // -*- C++ -*-
   2 //===-------------------------- unordered_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_UNORDERED_MAP
  12 #define _LIBCPP_UNORDERED_MAP
  13
  14 /*
  15
  16     unordered_map synopsis
  17
  18 #include <initializer_list>
  19
  20 namespace std
  21 {
  22
  23 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
  24           class Alloc = allocator<pair<const Key, T>>>
  25 class unordered_map
  26 {
  27 public:
  28     // types
  29     typedef Key                                                        key_type;
  30     typedef T                                                          mapped_type;
  31     typedef Hash                                                       hasher;
  32     typedef Pred                                                       key_equal;
  33     typedef Alloc                                                      allocator_type;
  34     typedef pair<const key_type, mapped_type>                          value_type;
  35     typedef value_type&                                                reference;
  36     typedef const value_type&                                          const_reference;
  37     typedef typename allocator_traits<allocator_type>::pointer         pointer;
  38     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
  39     typedef typename allocator_traits<allocator_type>::size_type       size_type;
  40     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  41
  42     typedef /unspecified/ iterator;
  43     typedef /unspecified/ const_iterator;
  44     typedef /unspecified/ local_iterator;
  45     typedef /unspecified/ const_local_iterator;
  46
  47     unordered_map()
  48         noexcept(
  49             is_nothrow_default_constructible<hasher>::value &&
  50             is_nothrow_default_constructible<key_equal>::value &&
  51             is_nothrow_default_constructible<allocator_type>::value);
  52     explicit unordered_map(size_type n, const hasher& hf = hasher(),
  53                            const key_equal& eql = key_equal(),
  54                            const allocator_type& a = allocator_type());
  55     template <class InputIterator>
  56         unordered_map(InputIterator f, InputIterator l,
  57                       size_type n = 0, const hasher& hf = hasher(),
  58                       const key_equal& eql = key_equal(),
  59                       const allocator_type& a = allocator_type());
  60     explicit unordered_map(const allocator_type&);
  61     unordered_map(const unordered_map&);
  62     unordered_map(const unordered_map&, const Allocator&);
  63     unordered_map(unordered_map&&)
  64         noexcept(
  65             is_nothrow_move_constructible<hasher>::value &&
  66             is_nothrow_move_constructible<key_equal>::value &&
  67             is_nothrow_move_constructible<allocator_type>::value);
  68     unordered_map(unordered_map&&, const Allocator&);
  69     unordered_map(initializer_list<value_type>, size_type n = 0,
  70                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  71                   const allocator_type& a = allocator_type());
  72     ~unordered_map();
  73     unordered_map& operator=(const unordered_map&);
  74     unordered_map& operator=(unordered_map&&)
  75         noexcept(
  76             allocator_type::propagate_on_container_move_assignment::value &&
  77             is_nothrow_move_assignable<allocator_type>::value &&
  78             is_nothrow_move_assignable<hasher>::value &&
  79             is_nothrow_move_assignable<key_equal>::value);
  80     unordered_map& operator=(initializer_list<value_type>);
  81
  82     allocator_type get_allocator() const noexcept;
  83
  84     bool      empty() const noexcept;
  85     size_type size() const noexcept;
  86     size_type max_size() const noexcept;
  87
  88     iterator       begin() noexcept;
  89     iterator       end() noexcept;
  90     const_iterator begin()  const noexcept;
  91     const_iterator end()    const noexcept;
  92     const_iterator cbegin() const noexcept;
  93     const_iterator cend()   const noexcept;
  94
  95     template <class... Args>
  96         pair<iterator, bool> emplace(Args&&... args);
  97     template <class... Args>
  98         iterator emplace_hint(const_iterator position, Args&&... args);
  99     pair<iterator, bool> insert(const value_type& obj);
 100     template <class P>
 101         pair<iterator, bool> insert(P&& obj);
 102     iterator insert(const_iterator hint, const value_type& obj);
 103     template <class P>
 104         iterator insert(const_iterator hint, P&& obj);
 105     template <class InputIterator>
 106         void insert(InputIterator first, InputIterator last);
 107     void insert(initializer_list<value_type>);
 108
 109     iterator erase(const_iterator position);
 110     size_type erase(const key_type& k);
 111     iterator erase(const_iterator first, const_iterator last);
 112     void clear() noexcept;
 113
 114     void swap(unordered_map&)
 115         noexcept(
 116             (!allocator_type::propagate_on_container_swap::value ||
 117              __is_nothrow_swappable<allocator_type>::value) &&
 118             __is_nothrow_swappable<hasher>::value &&
 119             __is_nothrow_swappable<key_equal>::value);
 120
 121     hasher hash_function() const;
 122     key_equal key_eq() const;
 123
 124     iterator       find(const key_type& k);
 125     const_iterator find(const key_type& k) const;
 126     size_type count(const key_type& k) const;
 127     pair<iterator, iterator>             equal_range(const key_type& k);
 128     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 129
 130     mapped_type& operator[](const key_type& k);
 131     mapped_type& operator[](key_type&& k);
 132
 133     mapped_type&       at(const key_type& k);
 134     const mapped_type& at(const key_type& k) const;
 135
 136     size_type bucket_count() const noexcept;
 137     size_type max_bucket_count() const noexcept;
 138
 139     size_type bucket_size(size_type n) const;
 140     size_type bucket(const key_type& k) const;
 141
 142     local_iterator       begin(size_type n);
 143     local_iterator       end(size_type n);
 144     const_local_iterator begin(size_type n) const;
 145     const_local_iterator end(size_type n) const;
 146     const_local_iterator cbegin(size_type n) const;
 147     const_local_iterator cend(size_type n) const;
 148
 149     float load_factor() const noexcept;
 150     float max_load_factor() const noexcept;
 151     void max_load_factor(float z);
 152     void rehash(size_type n);
 153     void reserve(size_type n);
 154 };
 155
 156 template <class Key, class T, class Hash, class Pred, class Alloc>
 157     void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
 158               unordered_map<Key, T, Hash, Pred, Alloc>& y)
 159               noexcept(noexcept(x.swap(y)));
 160
 161 template <class Key, class T, class Hash, class Pred, class Alloc>
 162     bool
 163     operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
 164                const unordered_map<Key, T, Hash, Pred, Alloc>& y);
 165
 166 template <class Key, class T, class Hash, class Pred, class Alloc>
 167     bool
 168     operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
 169                const unordered_map<Key, T, Hash, Pred, Alloc>& y);
 170
 171 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
 172           class Alloc = allocator<pair<const Key, T>>>
 173 class unordered_multimap
 174 {
 175 public:
 176     // types
 177     typedef Key                                                        key_type;
 178     typedef T                                                          mapped_type;
 179     typedef Hash                                                       hasher;
 180     typedef Pred                                                       key_equal;
 181     typedef Alloc                                                      allocator_type;
 182     typedef pair<const key_type, mapped_type>                          value_type;
 183     typedef value_type&                                                reference;
 184     typedef const value_type&                                          const_reference;
 185     typedef typename allocator_traits<allocator_type>::pointer         pointer;
 186     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 187     typedef typename allocator_traits<allocator_type>::size_type       size_type;
 188     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 189
 190     typedef /unspecified/ iterator;
 191     typedef /unspecified/ const_iterator;
 192     typedef /unspecified/ local_iterator;
 193     typedef /unspecified/ const_local_iterator;
 194
 195     unordered_multimap()
 196         noexcept(
 197             is_nothrow_default_constructible<hasher>::value &&
 198             is_nothrow_default_constructible<key_equal>::value &&
 199             is_nothrow_default_constructible<allocator_type>::value);
 200     explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
 201                            const key_equal& eql = key_equal(),
 202                            const allocator_type& a = allocator_type());
 203     template <class InputIterator>
 204         unordered_multimap(InputIterator f, InputIterator l,
 205                       size_type n = 0, const hasher& hf = hasher(),
 206                       const key_equal& eql = key_equal(),
 207                       const allocator_type& a = allocator_type());
 208     explicit unordered_multimap(const allocator_type&);
 209     unordered_multimap(const unordered_multimap&);
 210     unordered_multimap(const unordered_multimap&, const Allocator&);
 211     unordered_multimap(unordered_multimap&&)
 212         noexcept(
 213             is_nothrow_move_constructible<hasher>::value &&
 214             is_nothrow_move_constructible<key_equal>::value &&
 215             is_nothrow_move_constructible<allocator_type>::value);
 216     unordered_multimap(unordered_multimap&&, const Allocator&);
 217     unordered_multimap(initializer_list<value_type>, size_type n = 0,
 218                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 219                   const allocator_type& a = allocator_type());
 220     ~unordered_multimap();
 221     unordered_multimap& operator=(const unordered_multimap&);
 222     unordered_multimap& operator=(unordered_multimap&&)
 223         noexcept(
 224             allocator_type::propagate_on_container_move_assignment::value &&
 225             is_nothrow_move_assignable<allocator_type>::value &&
 226             is_nothrow_move_assignable<hasher>::value &&
 227             is_nothrow_move_assignable<key_equal>::value);
 228     unordered_multimap& operator=(initializer_list<value_type>);
 229
 230     allocator_type get_allocator() const noexcept;
 231
 232     bool      empty() const noexcept;
 233     size_type size() const noexcept;
 234     size_type max_size() const noexcept;
 235
 236     iterator       begin() noexcept;
 237     iterator       end() noexcept;
 238     const_iterator begin()  const noexcept;
 239     const_iterator end()    const noexcept;
 240     const_iterator cbegin() const noexcept;
 241     const_iterator cend()   const noexcept;
 242
 243     template <class... Args>
 244         iterator emplace(Args&&... args);
 245     template <class... Args>
 246         iterator emplace_hint(const_iterator position, Args&&... args);
 247     iterator insert(const value_type& obj);
 248     template <class P>
 249         iterator insert(P&& obj);
 250     iterator insert(const_iterator hint, const value_type& obj);
 251     template <class P>
 252         iterator insert(const_iterator hint, P&& obj);
 253     template <class InputIterator>
 254         void insert(InputIterator first, InputIterator last);
 255     void insert(initializer_list<value_type>);
 256
 257     iterator erase(const_iterator position);
 258     size_type erase(const key_type& k);
 259     iterator erase(const_iterator first, const_iterator last);
 260     void clear() noexcept;
 261
 262     void swap(unordered_multimap&)
 263         noexcept(
 264             (!allocator_type::propagate_on_container_swap::value ||
 265              __is_nothrow_swappable<allocator_type>::value) &&
 266             __is_nothrow_swappable<hasher>::value &&
 267             __is_nothrow_swappable<key_equal>::value);
 268
 269     hasher hash_function() const;
 270     key_equal key_eq() const;
 271
 272     iterator       find(const key_type& k);
 273     const_iterator find(const key_type& k) const;
 274     size_type count(const key_type& k) const;
 275     pair<iterator, iterator>             equal_range(const key_type& k);
 276     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 277
 278     size_type bucket_count() const noexcept;
 279     size_type max_bucket_count() const noexcept;
 280
 281     size_type bucket_size(size_type n) const;
 282     size_type bucket(const key_type& k) const;
 283
 284     local_iterator       begin(size_type n);
 285     local_iterator       end(size_type n);
 286     const_local_iterator begin(size_type n) const;
 287     const_local_iterator end(size_type n) const;
 288     const_local_iterator cbegin(size_type n) const;
 289     const_local_iterator cend(size_type n) const;
 290
 291     float load_factor() const noexcept;
 292     float max_load_factor() const noexcept;
 293     void max_load_factor(float z);
 294     void rehash(size_type n);
 295     void reserve(size_type n);
 296 };
 297
 298 template <class Key, class T, class Hash, class Pred, class Alloc>
 299     void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
 300               unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
 301               noexcept(noexcept(x.swap(y)));
 302
 303 template <class Key, class T, class Hash, class Pred, class Alloc>
 304     bool
 305     operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
 306                const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 307
 308 template <class Key, class T, class Hash, class Pred, class Alloc>
 309     bool
 310     operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
 311                const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 312
 313 }  // std
 314
 315 */
 316
 317 #include <__config>
 318 #include <__hash_table>
 319 #include <functional>
 320 #include <stdexcept>
 321
 322 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 323 #pragma GCC system_header
 324 #endif
 325
 326 _LIBCPP_BEGIN_NAMESPACE_STD
 327
 328 template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value
 329 #if __has_feature(is_final)
 330                                          && !__is_final(_Hash)
 331 #endif
 332          >
 333 class __unordered_map_hasher
 334     : private _Hash
 335 {
 336 public:
 337     _LIBCPP_INLINE_VISIBILITY
 338     __unordered_map_hasher()
 339         _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
 340         : _Hash() {}
 341     _LIBCPP_INLINE_VISIBILITY
 342     __unordered_map_hasher(const _Hash& __h)
 343         _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
 344         : _Hash(__h) {}
 345     _LIBCPP_INLINE_VISIBILITY
 346     const _Hash& hash_function() const _NOEXCEPT {return *this;}
 347     _LIBCPP_INLINE_VISIBILITY
 348     size_t operator()(const _Cp& __x) const
 349         {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
 350     _LIBCPP_INLINE_VISIBILITY
 351     size_t operator()(const _Key& __x) const
 352         {return static_cast<const _Hash&>(*this)(__x);}
 353 };
 354
 355 template <class _Key, class _Cp, class _Hash>
 356 class __unordered_map_hasher<_Key, _Cp, _Hash, false>
 357 {
 358     _Hash __hash_;
 359
 360 public:
 361     _LIBCPP_INLINE_VISIBILITY
 362     __unordered_map_hasher()
 363         _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
 364         : __hash_() {}
 365     _LIBCPP_INLINE_VISIBILITY
 366     __unordered_map_hasher(const _Hash& __h)
 367         _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
 368         : __hash_(__h) {}
 369     _LIBCPP_INLINE_VISIBILITY
 370     const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
 371     _LIBCPP_INLINE_VISIBILITY
 372     size_t operator()(const _Cp& __x) const
 373         {return __hash_(__x.__cc.first);}
 374     _LIBCPP_INLINE_VISIBILITY
 375     size_t operator()(const _Key& __x) const
 376         {return __hash_(__x);}
 377 };
 378
 379 template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
 380 #if __has_feature(is_final)
 381                                          && !__is_final(_Pred)
 382 #endif
 383          >
 384 class __unordered_map_equal
 385     : private _Pred
 386 {
 387 public:
 388     _LIBCPP_INLINE_VISIBILITY
 389     __unordered_map_equal()
 390         _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
 391         : _Pred() {}
 392     _LIBCPP_INLINE_VISIBILITY
 393     __unordered_map_equal(const _Pred& __p)
 394         _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
 395         : _Pred(__p) {}
 396     _LIBCPP_INLINE_VISIBILITY
 397     const _Pred& key_eq() const _NOEXCEPT {return *this;}
 398     _LIBCPP_INLINE_VISIBILITY
 399     bool operator()(const _Cp& __x, const _Cp& __y) const
 400         {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
 401     _LIBCPP_INLINE_VISIBILITY
 402     bool operator()(const _Cp& __x, const _Key& __y) const
 403         {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
 404     _LIBCPP_INLINE_VISIBILITY
 405     bool operator()(const _Key& __x, const _Cp& __y) const
 406         {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
 407 };
 408
 409 template <class _Key, class _Cp, class _Pred>
 410 class __unordered_map_equal<_Key, _Cp, _Pred, false>
 411 {
 412     _Pred __pred_;
 413
 414 public:
 415     _LIBCPP_INLINE_VISIBILITY
 416     __unordered_map_equal()
 417         _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
 418         : __pred_() {}
 419     _LIBCPP_INLINE_VISIBILITY
 420     __unordered_map_equal(const _Pred& __p)
 421         _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
 422         : __pred_(__p) {}
 423     _LIBCPP_INLINE_VISIBILITY
 424     const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
 425     _LIBCPP_INLINE_VISIBILITY
 426     bool operator()(const _Cp& __x, const _Cp& __y) const
 427         {return __pred_(__x.__cc.first, __y.__cc.first);}
 428     _LIBCPP_INLINE_VISIBILITY
 429     bool operator()(const _Cp& __x, const _Key& __y) const
 430         {return __pred_(__x.__cc.first, __y);}
 431     _LIBCPP_INLINE_VISIBILITY
 432     bool operator()(const _Key& __x, const _Cp& __y) const
 433         {return __pred_(__x, __y.__cc.first);}
 434 };
 435
 436 template <class _Alloc>
 437 class __hash_map_node_destructor
 438 {
 439     typedef _Alloc                              allocator_type;
 440     typedef allocator_traits<allocator_type>    __alloc_traits;
 441     typedef typename __alloc_traits::value_type::value_type value_type;
 442 public:
 443     typedef typename __alloc_traits::pointer    pointer;
 444 private:
 445     typedef typename value_type::value_type::first_type     first_type;
 446     typedef typename value_type::value_type::second_type    second_type;
 447
 448     allocator_type& __na_;
 449
 450     __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
 451
 452 public:
 453     bool __first_constructed;
 454     bool __second_constructed;
 455
 456     _LIBCPP_INLINE_VISIBILITY
 457     explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
 458         : __na_(__na),
 459           __first_constructed(false),
 460           __second_constructed(false)
 461         {}
 462
 463 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 464     _LIBCPP_INLINE_VISIBILITY
 465     __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
 466         _NOEXCEPT
 467         : __na_(__x.__na_),
 468           __first_constructed(__x.__value_constructed),
 469           __second_constructed(__x.__value_constructed)
 470         {
 471             __x.__value_constructed = false;
 472         }
 473 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 474     _LIBCPP_INLINE_VISIBILITY
 475     __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
 476         : __na_(__x.__na_),
 477           __first_constructed(__x.__value_constructed),
 478           __second_constructed(__x.__value_constructed)
 479         {
 480             const_cast<bool&>(__x.__value_constructed) = false;
 481         }
 482 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 483
 484     _LIBCPP_INLINE_VISIBILITY
 485     void operator()(pointer __p) _NOEXCEPT
 486     {
 487         if (__second_constructed)
 488             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
 489         if (__first_constructed)
 490             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
 491         if (__p)
 492             __alloc_traits::deallocate(__na_, __p, 1);
 493     }
 494 };
 495
 496 template <class _HashIterator>
 497 class _LIBCPP_TYPE_VIS __hash_map_iterator
 498 {
 499     _HashIterator __i_;
 500
 501     typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 502     typedef const typename _HashIterator::value_type::value_type::first_type key_type;
 503     typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;
 504 public:
 505     typedef forward_iterator_tag                                 iterator_category;
 506     typedef pair<key_type, mapped_type>                          value_type;
 507     typedef typename _HashIterator::difference_type              difference_type;
 508     typedef value_type&                                          reference;
 509     typedef typename __pointer_traits::template
 510 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 511             rebind<value_type>
 512 #else
 513             rebind<value_type>::other
 514 #endif
 515                                                                  pointer;
 516
 517     _LIBCPP_INLINE_VISIBILITY
 518     __hash_map_iterator() _NOEXCEPT {}
 519
 520     _LIBCPP_INLINE_VISIBILITY
 521     __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 522
 523     _LIBCPP_INLINE_VISIBILITY
 524     reference operator*() const {return __i_->__cc;}
 525     _LIBCPP_INLINE_VISIBILITY
 526     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
 527
 528     _LIBCPP_INLINE_VISIBILITY
 529     __hash_map_iterator& operator++() {++__i_; return *this;}
 530     _LIBCPP_INLINE_VISIBILITY
 531     __hash_map_iterator operator++(int)
 532     {
 533         __hash_map_iterator __t(*this);
 534         ++(*this);
 535         return __t;
 536     }
 537
 538     friend _LIBCPP_INLINE_VISIBILITY
 539         bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 540         {return __x.__i_ == __y.__i_;}
 541     friend _LIBCPP_INLINE_VISIBILITY
 542         bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 543         {return __x.__i_ != __y.__i_;}
 544
 545     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 546     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 547     template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 548     template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 549     template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
 550 };
 551
 552 template <class _HashIterator>
 553 class _LIBCPP_TYPE_VIS __hash_map_const_iterator
 554 {
 555     _HashIterator __i_;
 556
 557     typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 558     typedef const typename _HashIterator::value_type::value_type::first_type key_type;
 559     typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;
 560 public:
 561     typedef forward_iterator_tag                                 iterator_category;
 562     typedef pair<key_type, mapped_type>                          value_type;
 563     typedef typename _HashIterator::difference_type              difference_type;
 564     typedef const value_type&                                    reference;
 565     typedef typename __pointer_traits::template
 566 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 567             rebind<const value_type>
 568 #else
 569             rebind<const value_type>::other
 570 #endif
 571                                                                  pointer;
 572
 573     _LIBCPP_INLINE_VISIBILITY
 574     __hash_map_const_iterator() _NOEXCEPT {}
 575
 576     _LIBCPP_INLINE_VISIBILITY
 577     __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 578     _LIBCPP_INLINE_VISIBILITY
 579     __hash_map_const_iterator(
 580             __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
 581                  _NOEXCEPT
 582                 : __i_(__i.__i_) {}
 583
 584     _LIBCPP_INLINE_VISIBILITY
 585     reference operator*() const {return __i_->__cc;}
 586     _LIBCPP_INLINE_VISIBILITY
 587     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
 588
 589     _LIBCPP_INLINE_VISIBILITY
 590     __hash_map_const_iterator& operator++() {++__i_; return *this;}
 591     _LIBCPP_INLINE_VISIBILITY
 592     __hash_map_const_iterator operator++(int)
 593     {
 594         __hash_map_const_iterator __t(*this);
 595         ++(*this);
 596         return __t;
 597     }
 598
 599     friend _LIBCPP_INLINE_VISIBILITY
 600         bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 601         {return __x.__i_ == __y.__i_;}
 602     friend _LIBCPP_INLINE_VISIBILITY
 603         bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 604         {return __x.__i_ != __y.__i_;}
 605
 606     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 607     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 608     template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 609     template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 610 };
 611
 612 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 613           class _Alloc = allocator<pair<const _Key, _Tp> > >
 614 class _LIBCPP_TYPE_VIS unordered_map
 615 {
 616 public:
 617     // types
 618     typedef _Key                                           key_type;
 619     typedef _Tp                                            mapped_type;
 620     typedef _Hash                                          hasher;
 621     typedef _Pred                                          key_equal;
 622     typedef _Alloc                                         allocator_type;
 623     typedef pair<const key_type, mapped_type>              value_type;
 624     typedef pair<key_type, mapped_type>                    __nc_value_type;
 625     typedef value_type&                                    reference;
 626     typedef const value_type&                              const_reference;
 627
 628 private:
 629 #if __cplusplus >= 201103L
 630     union __value_type
 631     {
 632         typedef typename unordered_map::value_type value_type;
 633         typedef typename unordered_map::__nc_value_type __nc_value_type;
 634         value_type __cc;
 635         __nc_value_type __nc;
 636
 637         template <class ..._Args>
 638         __value_type(_Args&& ...__args)
 639             : __cc(std::forward<_Args>(__args)...) {}
 640
 641         __value_type(const __value_type& __v)
 642             : __cc(std::move(__v.__cc)) {}
 643
 644         __value_type(__value_type&& __v)
 645             : __nc(std::move(__v.__nc)) {}
 646
 647         __value_type& operator=(const __value_type& __v)
 648             {__nc = __v.__cc; return *this;}
 649
 650         __value_type& operator=(__value_type&& __v)
 651             {__nc = std::move(__v.__nc); return *this;}
 652
 653         ~__value_type() {__cc.~value_type();}
 654     };
 655 #else
 656     struct __value_type
 657     {
 658         typedef typename unordered_map::value_type value_type;
 659         value_type __cc;
 660
 661         __value_type() {}
 662
 663         template <class _A0>
 664         __value_type(const _A0& __a0)
 665             : __cc(__a0) {}
 666
 667         template <class _A0, class _A1>
 668         __value_type(const _A0& __a0, const _A1& __a1)
 669             : __cc(__a0, __a1) {}
 670     };
 671 #endif
 672     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
 673     typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
 674     typedef typename allocator_traits<allocator_type>::template
 675 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 676             rebind_alloc<__value_type>
 677 #else
 678             rebind_alloc<__value_type>::other
 679 #endif
 680                                                            __allocator_type;
 681
 682     typedef __hash_table<__value_type, __hasher,
 683                          __key_equal,  __allocator_type>   __table;
 684
 685     __table __table_;
 686
 687     typedef typename __table::__node_pointer               __node_pointer;
 688     typedef typename __table::__node_const_pointer         __node_const_pointer;
 689     typedef typename __table::__node_traits                __node_traits;
 690     typedef typename __table::__node_allocator             __node_allocator;
 691     typedef typename __table::__node                       __node;
 692     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 693     typedef unique_ptr<__node, _Dp>                         __node_holder;
 694     typedef allocator_traits<allocator_type>               __alloc_traits;
 695 public:
 696     typedef typename __alloc_traits::pointer         pointer;
 697     typedef typename __alloc_traits::const_pointer   const_pointer;
 698     typedef typename __alloc_traits::size_type       size_type;
 699     typedef typename __alloc_traits::difference_type difference_type;
 700
 701     typedef __hash_map_iterator<typename __table::iterator>       iterator;
 702     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 703     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
 704     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 705
 706     _LIBCPP_INLINE_VISIBILITY
 707     unordered_map()
 708         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 709         {} // = default;
 710     explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
 711                            const key_equal& __eql = key_equal());
 712     unordered_map(size_type __n, const hasher& __hf,
 713                   const key_equal& __eql,
 714                   const allocator_type& __a);
 715     template <class _InputIterator>
 716         unordered_map(_InputIterator __first, _InputIterator __last);
 717     template <class _InputIterator>
 718         unordered_map(_InputIterator __first, _InputIterator __last,
 719                       size_type __n, const hasher& __hf = hasher(),
 720                       const key_equal& __eql = key_equal());
 721     template <class _InputIterator>
 722         unordered_map(_InputIterator __first, _InputIterator __last,
 723                       size_type __n, const hasher& __hf,
 724                       const key_equal& __eql,
 725                       const allocator_type& __a);
 726     explicit unordered_map(const allocator_type& __a);
 727     unordered_map(const unordered_map& __u);
 728     unordered_map(const unordered_map& __u, const allocator_type& __a);
 729 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 730     unordered_map(unordered_map&& __u)
 731         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 732     unordered_map(unordered_map&& __u, const allocator_type& __a);
 733 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 734 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 735     unordered_map(initializer_list<value_type> __il);
 736     unordered_map(initializer_list<value_type> __il, size_type __n,
 737                   const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 738     unordered_map(initializer_list<value_type> __il, size_type __n,
 739                   const hasher& __hf, const key_equal& __eql,
 740                   const allocator_type& __a);
 741 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 742     // ~unordered_map() = default;
 743     _LIBCPP_INLINE_VISIBILITY
 744     unordered_map& operator=(const unordered_map& __u)
 745     {
 746 #if __cplusplus >= 201103L
 747         __table_ = __u.__table_;
 748 #else
 749         __table_.clear();
 750         __table_.hash_function() = __u.__table_.hash_function();
 751         __table_.key_eq() = __u.__table_.key_eq();
 752         __table_.max_load_factor() = __u.__table_.max_load_factor();
 753         __table_.__copy_assign_alloc(__u.__table_);
 754         insert(__u.begin(), __u.end());
 755 #endif
 756         return *this;
 757     }
 758 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 759     unordered_map& operator=(unordered_map&& __u)
 760         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 761 #endif
 762 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 763     unordered_map& operator=(initializer_list<value_type> __il);
 764 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 765
 766     _LIBCPP_INLINE_VISIBILITY
 767     allocator_type get_allocator() const _NOEXCEPT
 768         {return allocator_type(__table_.__node_alloc());}
 769
 770     _LIBCPP_INLINE_VISIBILITY
 771     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 772     _LIBCPP_INLINE_VISIBILITY
 773     size_type size() const _NOEXCEPT  {return __table_.size();}
 774     _LIBCPP_INLINE_VISIBILITY
 775     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 776
 777     _LIBCPP_INLINE_VISIBILITY
 778     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 779     _LIBCPP_INLINE_VISIBILITY
 780     iterator       end() _NOEXCEPT          {return __table_.end();}
 781     _LIBCPP_INLINE_VISIBILITY
 782     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 783     _LIBCPP_INLINE_VISIBILITY
 784     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 785     _LIBCPP_INLINE_VISIBILITY
 786     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 787     _LIBCPP_INLINE_VISIBILITY
 788     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 789
 790 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 791 #ifndef _LIBCPP_HAS_NO_VARIADICS
 792
 793     template <class... _Args>
 794         pair<iterator, bool> emplace(_Args&&... __args);
 795
 796     template <class... _Args>
 797         _LIBCPP_INLINE_VISIBILITY
 798         iterator emplace_hint(const_iterator, _Args&&... __args)
 799             {return emplace(_VSTD::forward<_Args>(__args)...).first;}
 800 #endif  // _LIBCPP_HAS_NO_VARIADICS
 801 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 802     _LIBCPP_INLINE_VISIBILITY
 803     pair<iterator, bool> insert(const value_type& __x)
 804         {return __table_.__insert_unique(__x);}
 805 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 806     template <class _Pp,
 807               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 808         _LIBCPP_INLINE_VISIBILITY
 809         pair<iterator, bool> insert(_Pp&& __x)
 810             {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
 811 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 812     _LIBCPP_INLINE_VISIBILITY
 813     iterator insert(const_iterator, const value_type& __x)
 814         {return insert(__x).first;}
 815 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 816     template <class _Pp,
 817               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 818         _LIBCPP_INLINE_VISIBILITY
 819         iterator insert(const_iterator, _Pp&& __x)
 820             {return insert(_VSTD::forward<_Pp>(__x)).first;}
 821 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 822     template <class _InputIterator>
 823         void insert(_InputIterator __first, _InputIterator __last);
 824 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 825     _LIBCPP_INLINE_VISIBILITY
 826     void insert(initializer_list<value_type> __il)
 827         {insert(__il.begin(), __il.end());}
 828 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 829
 830     _LIBCPP_INLINE_VISIBILITY
 831     iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
 832     _LIBCPP_INLINE_VISIBILITY
 833     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 834     _LIBCPP_INLINE_VISIBILITY
 835     iterator erase(const_iterator __first, const_iterator __last)
 836         {return __table_.erase(__first.__i_, __last.__i_);}
 837     _LIBCPP_INLINE_VISIBILITY
 838     void clear() _NOEXCEPT {__table_.clear();}
 839
 840     _LIBCPP_INLINE_VISIBILITY
 841     void swap(unordered_map& __u)
 842         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 843         {__table_.swap(__u.__table_);}
 844
 845     _LIBCPP_INLINE_VISIBILITY
 846     hasher hash_function() const
 847         {return __table_.hash_function().hash_function();}
 848     _LIBCPP_INLINE_VISIBILITY
 849     key_equal key_eq() const
 850         {return __table_.key_eq().key_eq();}
 851
 852     _LIBCPP_INLINE_VISIBILITY
 853     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 854     _LIBCPP_INLINE_VISIBILITY
 855     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 856     _LIBCPP_INLINE_VISIBILITY
 857     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 858     _LIBCPP_INLINE_VISIBILITY
 859     pair<iterator, iterator>             equal_range(const key_type& __k)
 860         {return __table_.__equal_range_unique(__k);}
 861     _LIBCPP_INLINE_VISIBILITY
 862     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 863         {return __table_.__equal_range_unique(__k);}
 864
 865     mapped_type& operator[](const key_type& __k);
 866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 867     mapped_type& operator[](key_type&& __k);
 868 #endif
 869
 870     mapped_type&       at(const key_type& __k);
 871     const mapped_type& at(const key_type& __k) const;
 872
 873     _LIBCPP_INLINE_VISIBILITY
 874     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 875     _LIBCPP_INLINE_VISIBILITY
 876     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 877
 878     _LIBCPP_INLINE_VISIBILITY
 879     size_type bucket_size(size_type __n) const
 880         {return __table_.bucket_size(__n);}
 881     _LIBCPP_INLINE_VISIBILITY
 882     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 883
 884     _LIBCPP_INLINE_VISIBILITY
 885     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 886     _LIBCPP_INLINE_VISIBILITY
 887     local_iterator       end(size_type __n)          {return __table_.end(__n);}
 888     _LIBCPP_INLINE_VISIBILITY
 889     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 890     _LIBCPP_INLINE_VISIBILITY
 891     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 892     _LIBCPP_INLINE_VISIBILITY
 893     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 894     _LIBCPP_INLINE_VISIBILITY
 895     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 896
 897     _LIBCPP_INLINE_VISIBILITY
 898     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 899     _LIBCPP_INLINE_VISIBILITY
 900     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 901     _LIBCPP_INLINE_VISIBILITY
 902     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 903     _LIBCPP_INLINE_VISIBILITY
 904     void rehash(size_type __n) {__table_.rehash(__n);}
 905     _LIBCPP_INLINE_VISIBILITY
 906     void reserve(size_type __n) {__table_.reserve(__n);}
 907
 908 private:
 909 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 910     __node_holder __construct_node();
 911     template <class _A0>
 912         __node_holder
 913          __construct_node(_A0&& __a0);
 914     __node_holder __construct_node_with_key(key_type&& __k);
 915 #ifndef _LIBCPP_HAS_NO_VARIADICS
 916     template <class _A0, class _A1, class ..._Args>
 917         __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
 918 #endif  // _LIBCPP_HAS_NO_VARIADICS
 919 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 920     __node_holder __construct_node_with_key(const key_type& __k);
 921 };
 922
 923 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 924 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 925         size_type __n, const hasher& __hf, const key_equal& __eql)
 926     : __table_(__hf, __eql)
 927 {
 928     __table_.rehash(__n);
 929 }
 930
 931 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 932 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 933         size_type __n, const hasher& __hf, const key_equal& __eql,
 934         const allocator_type& __a)
 935     : __table_(__hf, __eql, __a)
 936 {
 937     __table_.rehash(__n);
 938 }
 939
 940 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 941 inline _LIBCPP_INLINE_VISIBILITY
 942 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 943         const allocator_type& __a)
 944     : __table_(__a)
 945 {
 946 }
 947
 948 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 949 template <class _InputIterator>
 950 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 951         _InputIterator __first, _InputIterator __last)
 952 {
 953     insert(__first, __last);
 954 }
 955
 956 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 957 template <class _InputIterator>
 958 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 959         _InputIterator __first, _InputIterator __last, size_type __n,
 960         const hasher& __hf, const key_equal& __eql)
 961     : __table_(__hf, __eql)
 962 {
 963     __table_.rehash(__n);
 964     insert(__first, __last);
 965 }
 966
 967 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 968 template <class _InputIterator>
 969 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 970         _InputIterator __first, _InputIterator __last, size_type __n,
 971         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 972     : __table_(__hf, __eql, __a)
 973 {
 974     __table_.rehash(__n);
 975     insert(__first, __last);
 976 }
 977
 978 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 979 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 980         const unordered_map& __u)
 981     : __table_(__u.__table_)
 982 {
 983     __table_.rehash(__u.bucket_count());
 984     insert(__u.begin(), __u.end());
 985 }
 986
 987 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 988 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 989         const unordered_map& __u, const allocator_type& __a)
 990     : __table_(__u.__table_, __a)
 991 {
 992     __table_.rehash(__u.bucket_count());
 993     insert(__u.begin(), __u.end());
 994 }
 995
 996 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 997
 998 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 999 inline _LIBCPP_INLINE_VISIBILITY
1000 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1001         unordered_map&& __u)
1002     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1003     : __table_(_VSTD::move(__u.__table_))
1004 {
1005 }
1006
1007 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1008 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1009         unordered_map&& __u, const allocator_type& __a)
1010     : __table_(_VSTD::move(__u.__table_), __a)
1011 {
1012     if (__a != __u.get_allocator())
1013     {
1014         iterator __i = __u.begin();
1015         while (__u.size() != 0)
1016             __table_.__insert_unique(
1017                 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1018                                     );
1019     }
1020 }
1021
1022 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1023
1024 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1025
1026 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1027 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1028         initializer_list<value_type> __il)
1029 {
1030     insert(__il.begin(), __il.end());
1031 }
1032
1033 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1034 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1035         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1036         const key_equal& __eql)
1037     : __table_(__hf, __eql)
1038 {
1039     __table_.rehash(__n);
1040     insert(__il.begin(), __il.end());
1041 }
1042
1043 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1044 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1045         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1046         const key_equal& __eql, const allocator_type& __a)
1047     : __table_(__hf, __eql, __a)
1048 {
1049     __table_.rehash(__n);
1050     insert(__il.begin(), __il.end());
1051 }
1052
1053 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1054
1055 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1056
1057 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1058 inline _LIBCPP_INLINE_VISIBILITY
1059 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1060 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1061     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1062 {
1063     __table_ = _VSTD::move(__u.__table_);
1064     return *this;
1065 }
1066
1067 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1068
1069 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1070
1071 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1072 inline _LIBCPP_INLINE_VISIBILITY
1073 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1074 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1075         initializer_list<value_type> __il)
1076 {
1077     __table_.__assign_unique(__il.begin(), __il.end());
1078     return *this;
1079 }
1080
1081 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1082
1083 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1084
1085 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1086 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1087 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1088 {
1089     __node_allocator& __na = __table_.__node_alloc();
1090     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1091     __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1092     __h.get_deleter().__first_constructed = true;
1093     __h.get_deleter().__second_constructed = true;
1094     return __h;
1095 }
1096
1097 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1098 template <class _A0>
1099 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1100 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1101 {
1102     __node_allocator& __na = __table_.__node_alloc();
1103     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1104     __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1105                              _VSTD::forward<_A0>(__a0));
1106     __h.get_deleter().__first_constructed = true;
1107     __h.get_deleter().__second_constructed = true;
1108     return __h;
1109 }
1110
1111 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1112 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1113 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
1114 {
1115     __node_allocator& __na = __table_.__node_alloc();
1116     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1117     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1118     __h.get_deleter().__first_constructed = true;
1119     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1120     __h.get_deleter().__second_constructed = true;
1121     return _VSTD::move(__h);
1122 }
1123
1124 #ifndef _LIBCPP_HAS_NO_VARIADICS
1125
1126 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1127 template <class _A0, class _A1, class ..._Args>
1128 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1129 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1130                                                                  _A1&& __a1,
1131                                                                  _Args&&... __args)
1132 {
1133     __node_allocator& __na = __table_.__node_alloc();
1134     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1135     __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1136                              _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1137                              _VSTD::forward<_Args>(__args)...);
1138     __h.get_deleter().__first_constructed = true;
1139     __h.get_deleter().__second_constructed = true;
1140     return __h;
1141 }
1142
1143 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1144 template <class... _Args>
1145 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1146 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1147 {
1148     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1149     pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1150     if (__r.second)
1151         __h.release();
1152     return __r;
1153 }
1154
1155 #endif  // _LIBCPP_HAS_NO_VARIADICS
1156 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1157
1158 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1159 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1160 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1161 {
1162     __node_allocator& __na = __table_.__node_alloc();
1163     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1164     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1165     __h.get_deleter().__first_constructed = true;
1166     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1167     __h.get_deleter().__second_constructed = true;
1168     return _VSTD::move(__h);
1169 }
1170
1171 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1172 template <class _InputIterator>
1173 inline _LIBCPP_INLINE_VISIBILITY
1174 void
1175 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1176                                                        _InputIterator __last)
1177 {
1178     for (; __first != __last; ++__first)
1179         __table_.__insert_unique(*__first);
1180 }
1181
1182 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1183 _Tp&
1184 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1185 {
1186     iterator __i = find(__k);
1187     if (__i != end())
1188         return __i->second;
1189     __node_holder __h = __construct_node_with_key(__k);
1190     pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1191     __h.release();
1192     return __r.first->second;
1193 }
1194
1195 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1196
1197 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1198 _Tp&
1199 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1200 {
1201     iterator __i = find(__k);
1202     if (__i != end())
1203         return __i->second;
1204     __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1205     pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1206     __h.release();
1207     return __r.first->second;
1208 }
1209
1210 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1211
1212 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1213 _Tp&
1214 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1215 {
1216     iterator __i = find(__k);
1217 #ifndef _LIBCPP_NO_EXCEPTIONS
1218     if (__i == end())
1219         throw out_of_range("unordered_map::at: key not found");
1220 #endif  // _LIBCPP_NO_EXCEPTIONS
1221     return __i->second;
1222 }
1223
1224 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1225 const _Tp&
1226 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1227 {
1228     const_iterator __i = find(__k);
1229 #ifndef _LIBCPP_NO_EXCEPTIONS
1230     if (__i == end())
1231         throw out_of_range("unordered_map::at: key not found");
1232 #endif  // _LIBCPP_NO_EXCEPTIONS
1233     return __i->second;
1234 }
1235
1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1237 inline _LIBCPP_INLINE_VISIBILITY
1238 void
1239 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1240      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1241     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1242 {
1243     __x.swap(__y);
1244 }
1245
1246 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1247 bool
1248 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1249            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1250 {
1251     if (__x.size() != __y.size())
1252         return false;
1253     typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1254                                                                  const_iterator;
1255     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1256             __i != __ex; ++__i)
1257     {
1258         const_iterator __j = __y.find(__i->first);
1259         if (__j == __ey || !(*__i == *__j))
1260             return false;
1261     }
1262     return true;
1263 }
1264
1265 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1266 inline _LIBCPP_INLINE_VISIBILITY
1267 bool
1268 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1269            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1270 {
1271     return !(__x == __y);
1272 }
1273
1274 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1275           class _Alloc = allocator<pair<const _Key, _Tp> > >
1276 class _LIBCPP_TYPE_VIS unordered_multimap
1277 {
1278 public:
1279     // types
1280     typedef _Key                                           key_type;
1281     typedef _Tp                                            mapped_type;
1282     typedef _Hash                                          hasher;
1283     typedef _Pred                                          key_equal;
1284     typedef _Alloc                                         allocator_type;
1285     typedef pair<const key_type, mapped_type>              value_type;
1286     typedef pair<key_type, mapped_type>                    __nc_value_type;
1287     typedef value_type&                                    reference;
1288     typedef const value_type&                              const_reference;
1289
1290 private:
1291 #if __cplusplus >= 201103L
1292     union __value_type
1293     {
1294         typedef typename unordered_multimap::value_type value_type;
1295         typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1296         value_type __cc;
1297         __nc_value_type __nc;
1298
1299         template <class ..._Args>
1300         __value_type(_Args&& ...__args)
1301             : __cc(std::forward<_Args>(__args)...) {}
1302
1303         __value_type(const __value_type& __v)
1304             : __cc(std::move(__v.__cc)) {}
1305
1306         __value_type(__value_type&& __v)
1307             : __nc(std::move(__v.__nc)) {}
1308
1309         __value_type& operator=(const __value_type& __v)
1310             {__nc = __v.__cc; return *this;}
1311
1312         __value_type& operator=(__value_type&& __v)
1313             {__nc = std::move(__v.__nc); return *this;}
1314
1315         ~__value_type() {__cc.~value_type();}
1316     };
1317 #else
1318     struct __value_type
1319     {
1320         typedef typename unordered_multimap::value_type value_type;
1321         value_type __cc;
1322
1323         __value_type() {}
1324
1325         template <class _A0>
1326         __value_type(const _A0& __a0)
1327             : __cc(__a0) {}
1328
1329         template <class _A0, class _A1>
1330         __value_type(const _A0& __a0, const _A1& __a1)
1331             : __cc(__a0, __a1) {}
1332     };
1333 #endif
1334     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
1335     typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1336     typedef typename allocator_traits<allocator_type>::template
1337 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1338             rebind_alloc<__value_type>
1339 #else
1340             rebind_alloc<__value_type>::other
1341 #endif
1342                                                            __allocator_type;
1343
1344     typedef __hash_table<__value_type, __hasher,
1345                          __key_equal,  __allocator_type>   __table;
1346
1347     __table __table_;
1348
1349     typedef typename __table::__node_traits                __node_traits;
1350     typedef typename __table::__node_allocator             __node_allocator;
1351     typedef typename __table::__node                       __node;
1352     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
1353     typedef unique_ptr<__node, _Dp>                         __node_holder;
1354     typedef allocator_traits<allocator_type>               __alloc_traits;
1355 public:
1356     typedef typename __alloc_traits::pointer         pointer;
1357     typedef typename __alloc_traits::const_pointer   const_pointer;
1358     typedef typename __alloc_traits::size_type       size_type;
1359     typedef typename __alloc_traits::difference_type difference_type;
1360
1361     typedef __hash_map_iterator<typename __table::iterator>       iterator;
1362     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1363     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1364     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1365
1366     _LIBCPP_INLINE_VISIBILITY
1367     unordered_multimap()
1368         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1369         {} // = default;
1370     explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1371                                 const key_equal& __eql = key_equal());
1372     unordered_multimap(size_type __n, const hasher& __hf,
1373                                 const key_equal& __eql,
1374                                 const allocator_type& __a);
1375     template <class _InputIterator>
1376         unordered_multimap(_InputIterator __first, _InputIterator __last);
1377     template <class _InputIterator>
1378         unordered_multimap(_InputIterator __first, _InputIterator __last,
1379                       size_type __n, const hasher& __hf = hasher(),
1380                       const key_equal& __eql = key_equal());
1381     template <class _InputIterator>
1382         unordered_multimap(_InputIterator __first, _InputIterator __last,
1383                       size_type __n, const hasher& __hf,
1384                       const key_equal& __eql,
1385                       const allocator_type& __a);
1386     explicit unordered_multimap(const allocator_type& __a);
1387     unordered_multimap(const unordered_multimap& __u);
1388     unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1389 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1390     unordered_multimap(unordered_multimap&& __u)
1391         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1392     unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1393 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1394 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1395     unordered_multimap(initializer_list<value_type> __il);
1396     unordered_multimap(initializer_list<value_type> __il, size_type __n,
1397                        const hasher& __hf = hasher(),
1398                        const key_equal& __eql = key_equal());
1399     unordered_multimap(initializer_list<value_type> __il, size_type __n,
1400                        const hasher& __hf, const key_equal& __eql,
1401                        const allocator_type& __a);
1402 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1403     // ~unordered_multimap() = default;
1404     _LIBCPP_INLINE_VISIBILITY
1405     unordered_multimap& operator=(const unordered_multimap& __u)
1406     {
1407 #if __cplusplus >= 201103L
1408         __table_ = __u.__table_;
1409 #else
1410         __table_.clear();
1411         __table_.hash_function() = __u.__table_.hash_function();
1412         __table_.key_eq() = __u.__table_.key_eq();
1413         __table_.max_load_factor() = __u.__table_.max_load_factor();
1414         __table_.__copy_assign_alloc(__u.__table_);
1415         insert(__u.begin(), __u.end());
1416 #endif
1417         return *this;
1418     }
1419 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1420     unordered_multimap& operator=(unordered_multimap&& __u)
1421         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1422 #endif
1423 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1424     unordered_multimap& operator=(initializer_list<value_type> __il);
1425 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1426
1427     _LIBCPP_INLINE_VISIBILITY
1428     allocator_type get_allocator() const _NOEXCEPT
1429         {return allocator_type(__table_.__node_alloc());}
1430
1431     _LIBCPP_INLINE_VISIBILITY
1432     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1433     _LIBCPP_INLINE_VISIBILITY
1434     size_type size() const _NOEXCEPT  {return __table_.size();}
1435     _LIBCPP_INLINE_VISIBILITY
1436     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1437
1438     _LIBCPP_INLINE_VISIBILITY
1439     iterator       begin() _NOEXCEPT        {return __table_.begin();}
1440     _LIBCPP_INLINE_VISIBILITY
1441     iterator       end() _NOEXCEPT          {return __table_.end();}
1442     _LIBCPP_INLINE_VISIBILITY
1443     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1444     _LIBCPP_INLINE_VISIBILITY
1445     const_iterator end()    const _NOEXCEPT {return __table_.end();}
1446     _LIBCPP_INLINE_VISIBILITY
1447     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1448     _LIBCPP_INLINE_VISIBILITY
1449     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1450
1451 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1452 #ifndef _LIBCPP_HAS_NO_VARIADICS
1453
1454     template <class... _Args>
1455         iterator emplace(_Args&&... __args);
1456
1457     template <class... _Args>
1458         iterator emplace_hint(const_iterator __p, _Args&&... __args);
1459 #endif  // _LIBCPP_HAS_NO_VARIADICS
1460 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1461     _LIBCPP_INLINE_VISIBILITY
1462     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1463 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1464     template <class _Pp,
1465               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1466         _LIBCPP_INLINE_VISIBILITY
1467         iterator insert(_Pp&& __x)
1468             {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1469 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1470     _LIBCPP_INLINE_VISIBILITY
1471     iterator insert(const_iterator __p, const value_type& __x)
1472         {return __table_.__insert_multi(__p.__i_, __x);}
1473 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1474     template <class _Pp,
1475               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1476         _LIBCPP_INLINE_VISIBILITY
1477         iterator insert(const_iterator __p, _Pp&& __x)
1478             {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1479 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1480     template <class _InputIterator>
1481         void insert(_InputIterator __first, _InputIterator __last);
1482 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1483     _LIBCPP_INLINE_VISIBILITY
1484     void insert(initializer_list<value_type> __il)
1485         {insert(__il.begin(), __il.end());}
1486 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1487
1488     _LIBCPP_INLINE_VISIBILITY
1489     iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1490     _LIBCPP_INLINE_VISIBILITY
1491     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1492     _LIBCPP_INLINE_VISIBILITY
1493     iterator erase(const_iterator __first, const_iterator __last)
1494         {return __table_.erase(__first.__i_, __last.__i_);}
1495     _LIBCPP_INLINE_VISIBILITY
1496     void clear() _NOEXCEPT {__table_.clear();}
1497
1498     _LIBCPP_INLINE_VISIBILITY
1499     void swap(unordered_multimap& __u)
1500         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1501         {__table_.swap(__u.__table_);}
1502
1503     _LIBCPP_INLINE_VISIBILITY
1504     hasher hash_function() const
1505         {return __table_.hash_function().hash_function();}
1506     _LIBCPP_INLINE_VISIBILITY
1507     key_equal key_eq() const
1508         {return __table_.key_eq().key_eq();}
1509
1510     _LIBCPP_INLINE_VISIBILITY
1511     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1512     _LIBCPP_INLINE_VISIBILITY
1513     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1514     _LIBCPP_INLINE_VISIBILITY
1515     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1516     _LIBCPP_INLINE_VISIBILITY
1517     pair<iterator, iterator>             equal_range(const key_type& __k)
1518         {return __table_.__equal_range_multi(__k);}
1519     _LIBCPP_INLINE_VISIBILITY
1520     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1521         {return __table_.__equal_range_multi(__k);}
1522
1523     _LIBCPP_INLINE_VISIBILITY
1524     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1525     _LIBCPP_INLINE_VISIBILITY
1526     size_type max_bucket_count() const _NOEXCEPT
1527         {return __table_.max_bucket_count();}
1528
1529     _LIBCPP_INLINE_VISIBILITY
1530     size_type bucket_size(size_type __n) const
1531         {return __table_.bucket_size(__n);}
1532     _LIBCPP_INLINE_VISIBILITY
1533     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1534
1535     _LIBCPP_INLINE_VISIBILITY
1536     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1537     _LIBCPP_INLINE_VISIBILITY
1538     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1539     _LIBCPP_INLINE_VISIBILITY
1540     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1541     _LIBCPP_INLINE_VISIBILITY
1542     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1543     _LIBCPP_INLINE_VISIBILITY
1544     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1545     _LIBCPP_INLINE_VISIBILITY
1546     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1547
1548     _LIBCPP_INLINE_VISIBILITY
1549     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1550     _LIBCPP_INLINE_VISIBILITY
1551     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1552     _LIBCPP_INLINE_VISIBILITY
1553     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1554     _LIBCPP_INLINE_VISIBILITY
1555     void rehash(size_type __n) {__table_.rehash(__n);}
1556     _LIBCPP_INLINE_VISIBILITY
1557     void reserve(size_type __n) {__table_.reserve(__n);}
1558
1559 private:
1560 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1561     __node_holder __construct_node();
1562     template <class _A0>
1563         __node_holder
1564          __construct_node(_A0&& __a0);
1565 #ifndef _LIBCPP_HAS_NO_VARIADICS
1566     template <class _A0, class _A1, class ..._Args>
1567         __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1568 #endif  // _LIBCPP_HAS_NO_VARIADICS
1569 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1570 };
1571
1572 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1573 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1574         size_type __n, const hasher& __hf, const key_equal& __eql)
1575     : __table_(__hf, __eql)
1576 {
1577     __table_.rehash(__n);
1578 }
1579
1580 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1581 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1582         size_type __n, const hasher& __hf, const key_equal& __eql,
1583         const allocator_type& __a)
1584     : __table_(__hf, __eql, __a)
1585 {
1586     __table_.rehash(__n);
1587 }
1588
1589 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1590 template <class _InputIterator>
1591 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1592         _InputIterator __first, _InputIterator __last)
1593 {
1594     insert(__first, __last);
1595 }
1596
1597 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1598 template <class _InputIterator>
1599 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1600         _InputIterator __first, _InputIterator __last, size_type __n,
1601         const hasher& __hf, const key_equal& __eql)
1602     : __table_(__hf, __eql)
1603 {
1604     __table_.rehash(__n);
1605     insert(__first, __last);
1606 }
1607
1608 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1609 template <class _InputIterator>
1610 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1611         _InputIterator __first, _InputIterator __last, size_type __n,
1612         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1613     : __table_(__hf, __eql, __a)
1614 {
1615     __table_.rehash(__n);
1616     insert(__first, __last);
1617 }
1618
1619 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1620 inline _LIBCPP_INLINE_VISIBILITY
1621 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1622         const allocator_type& __a)
1623     : __table_(__a)
1624 {
1625 }
1626
1627 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1628 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1629         const unordered_multimap& __u)
1630     : __table_(__u.__table_)
1631 {
1632     __table_.rehash(__u.bucket_count());
1633     insert(__u.begin(), __u.end());
1634 }
1635
1636 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1637 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638         const unordered_multimap& __u, const allocator_type& __a)
1639     : __table_(__u.__table_, __a)
1640 {
1641     __table_.rehash(__u.bucket_count());
1642     insert(__u.begin(), __u.end());
1643 }
1644
1645 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1646
1647 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1648 inline _LIBCPP_INLINE_VISIBILITY
1649 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1650         unordered_multimap&& __u)
1651     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1652     : __table_(_VSTD::move(__u.__table_))
1653 {
1654 }
1655
1656 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1657 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1658         unordered_multimap&& __u, const allocator_type& __a)
1659     : __table_(_VSTD::move(__u.__table_), __a)
1660 {
1661     if (__a != __u.get_allocator())
1662     {
1663         iterator __i = __u.begin();
1664         while (__u.size() != 0)
1665 {
1666             __table_.__insert_multi(
1667                 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1668                                    );
1669 }
1670     }
1671 }
1672
1673 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1674
1675 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1676
1677 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1678 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1679         initializer_list<value_type> __il)
1680 {
1681     insert(__il.begin(), __il.end());
1682 }
1683
1684 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1685 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1686         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1687         const key_equal& __eql)
1688     : __table_(__hf, __eql)
1689 {
1690     __table_.rehash(__n);
1691     insert(__il.begin(), __il.end());
1692 }
1693
1694 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1695 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1696         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1697         const key_equal& __eql, const allocator_type& __a)
1698     : __table_(__hf, __eql, __a)
1699 {
1700     __table_.rehash(__n);
1701     insert(__il.begin(), __il.end());
1702 }
1703
1704 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1705
1706 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1707
1708 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1709 inline _LIBCPP_INLINE_VISIBILITY
1710 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1711 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1712     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1713 {
1714     __table_ = _VSTD::move(__u.__table_);
1715     return *this;
1716 }
1717
1718 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1719
1720 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1721
1722 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1723 inline _LIBCPP_INLINE_VISIBILITY
1724 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1725 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1726         initializer_list<value_type> __il)
1727 {
1728     __table_.__assign_multi(__il.begin(), __il.end());
1729     return *this;
1730 }
1731
1732 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1733
1734 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1735
1736 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1737 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1738 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1739 {
1740     __node_allocator& __na = __table_.__node_alloc();
1741     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1742     __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1743     __h.get_deleter().__first_constructed = true;
1744     __h.get_deleter().__second_constructed = true;
1745     return __h;
1746 }
1747
1748 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1749 template <class _A0>
1750 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1751 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1752 {
1753     __node_allocator& __na = __table_.__node_alloc();
1754     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1755     __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1756                              _VSTD::forward<_A0>(__a0));
1757     __h.get_deleter().__first_constructed = true;
1758     __h.get_deleter().__second_constructed = true;
1759     return __h;
1760 }
1761
1762 #ifndef _LIBCPP_HAS_NO_VARIADICS
1763
1764 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1765 template <class _A0, class _A1, class ..._Args>
1766 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1767 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1768         _A0&& __a0, _A1&& __a1, _Args&&... __args)
1769 {
1770     __node_allocator& __na = __table_.__node_alloc();
1771     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1772     __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1773                              _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1774                              _VSTD::forward<_Args>(__args)...);
1775     __h.get_deleter().__first_constructed = true;
1776     __h.get_deleter().__second_constructed = true;
1777     return __h;
1778 }
1779
1780 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1781 template <class... _Args>
1782 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1783 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1784 {
1785     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1786     iterator __r = __table_.__node_insert_multi(__h.get());
1787     __h.release();
1788     return __r;
1789 }
1790
1791 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1792 template <class... _Args>
1793 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1794 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1795         const_iterator __p, _Args&&... __args)
1796 {
1797     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1798     iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1799     __h.release();
1800     return __r;
1801 }
1802
1803 #endif  // _LIBCPP_HAS_NO_VARIADICS
1804 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1805
1806 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1807 template <class _InputIterator>
1808 inline _LIBCPP_INLINE_VISIBILITY
1809 void
1810 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1811                                                             _InputIterator __last)
1812 {
1813     for (; __first != __last; ++__first)
1814         __table_.__insert_multi(*__first);
1815 }
1816
1817 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1818 inline _LIBCPP_INLINE_VISIBILITY
1819 void
1820 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1821      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1822     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1823 {
1824     __x.swap(__y);
1825 }
1826
1827 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1828 bool
1829 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1830            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1831 {
1832     if (__x.size() != __y.size())
1833         return false;
1834     typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1835                                                                  const_iterator;
1836     typedef pair<const_iterator, const_iterator> _EqRng;
1837     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1838     {
1839         _EqRng __xeq = __x.equal_range(__i->first);
1840         _EqRng __yeq = __y.equal_range(__i->first);
1841         if (_VSTD::distance(__xeq.first, __xeq.second) !=
1842             _VSTD::distance(__yeq.first, __yeq.second) ||
1843                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1844             return false;
1845         __i = __xeq.second;
1846     }
1847     return true;
1848 }
1849
1850 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1851 inline _LIBCPP_INLINE_VISIBILITY
1852 bool
1853 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1854            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1855 {
1856     return !(__x == __y);
1857 }
1858
1859 _LIBCPP_END_NAMESPACE_STD
1860
1861 #endif  // _LIBCPP_UNORDERED_MAP