include/map

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