contrib/libc++/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,
 457           bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value
 458          >
 459 class __map_value_compare
 460     : private _Compare
 461 {
 462 public:
 463     _LIBCPP_INLINE_VISIBILITY
 464     __map_value_compare()
 465         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
 466         : _Compare() {}
 467     _LIBCPP_INLINE_VISIBILITY
 468     __map_value_compare(_Compare c)
 469         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
 470         : _Compare(c) {}
 471     _LIBCPP_INLINE_VISIBILITY
 472     const _Compare& key_comp() const _NOEXCEPT {return *this;}
 473     _LIBCPP_INLINE_VISIBILITY
 474     bool operator()(const _CP& __x, const _CP& __y) const
 475         {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
 476     _LIBCPP_INLINE_VISIBILITY
 477     bool operator()(const _CP& __x, const _Key& __y) const
 478         {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
 479     _LIBCPP_INLINE_VISIBILITY
 480     bool operator()(const _Key& __x, const _CP& __y) const
 481         {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
 482     void swap(__map_value_compare&__y)
 483         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
 484     {
 485         using _VSTD::swap;
 486         swap(static_cast<const _Compare&>(*this), static_cast<const _Compare&>(__y));
 487     }
 488
 489 #if _LIBCPP_STD_VER > 11
 490     template <typename _K2>
 491     _LIBCPP_INLINE_VISIBILITY
 492     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 493     operator () ( const _K2& __x, const _CP& __y ) const
 494         {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
 495
 496     template <typename _K2>
 497     _LIBCPP_INLINE_VISIBILITY
 498     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 499     operator () (const _CP& __x, const _K2& __y) const
 500         {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
 501 #endif
 502 };
 503
 504 template <class _Key, class _CP, class _Compare>
 505 class __map_value_compare<_Key, _CP, _Compare, false>
 506 {
 507     _Compare comp;
 508
 509 public:
 510     _LIBCPP_INLINE_VISIBILITY
 511     __map_value_compare()
 512         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
 513         : comp() {}
 514     _LIBCPP_INLINE_VISIBILITY
 515     __map_value_compare(_Compare c)
 516         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
 517         : comp(c) {}
 518     _LIBCPP_INLINE_VISIBILITY
 519     const _Compare& key_comp() const _NOEXCEPT {return comp;}
 520
 521     _LIBCPP_INLINE_VISIBILITY
 522     bool operator()(const _CP& __x, const _CP& __y) const
 523         {return comp(__x.__cc.first, __y.__cc.first);}
 524     _LIBCPP_INLINE_VISIBILITY
 525     bool operator()(const _CP& __x, const _Key& __y) const
 526         {return comp(__x.__cc.first, __y);}
 527     _LIBCPP_INLINE_VISIBILITY
 528     bool operator()(const _Key& __x, const _CP& __y) const
 529         {return comp(__x, __y.__cc.first);}
 530     void swap(__map_value_compare&__y)
 531         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
 532     {
 533         using _VSTD::swap;
 534         swap(comp, __y.comp);
 535     }
 536
 537 #if _LIBCPP_STD_VER > 11
 538     template <typename _K2>
 539     _LIBCPP_INLINE_VISIBILITY
 540     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 541     operator () ( const _K2& __x, const _CP& __y ) const
 542         {return comp (__x, __y.__cc.first);}
 543
 544     template <typename _K2>
 545     _LIBCPP_INLINE_VISIBILITY
 546     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
 547     operator () (const _CP& __x, const _K2& __y) const
 548         {return comp (__x.__cc.first, __y);}
 549 #endif
 550 };
 551
 552 template <class _Key, class _CP, class _Compare, bool __b>
 553 inline _LIBCPP_INLINE_VISIBILITY
 554 void
 555 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
 556      __map_value_compare<_Key, _CP, _Compare, __b>& __y)
 557     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 558 {
 559     __x.swap(__y);
 560 }
 561
 562 template <class _Allocator>
 563 class __map_node_destructor
 564 {
 565     typedef _Allocator                          allocator_type;
 566     typedef allocator_traits<allocator_type>    __alloc_traits;
 567
 568 public:
 569     typedef typename __alloc_traits::pointer    pointer;
 570
 571 private:
 572     allocator_type& __na_;
 573
 574     __map_node_destructor& operator=(const __map_node_destructor&);
 575
 576 public:
 577     bool __first_constructed;
 578     bool __second_constructed;
 579
 580     _LIBCPP_INLINE_VISIBILITY
 581     explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
 582         : __na_(__na),
 583           __first_constructed(false),
 584           __second_constructed(false)
 585         {}
 586
 587 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 588     _LIBCPP_INLINE_VISIBILITY
 589     __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
 590         : __na_(__x.__na_),
 591           __first_constructed(__x.__value_constructed),
 592           __second_constructed(__x.__value_constructed)
 593         {
 594             __x.__value_constructed = false;
 595         }
 596 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 597
 598     _LIBCPP_INLINE_VISIBILITY
 599     void operator()(pointer __p) _NOEXCEPT
 600     {
 601         if (__second_constructed)
 602             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
 603         if (__first_constructed)
 604             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
 605         if (__p)
 606             __alloc_traits::deallocate(__na_, __p, 1);
 607     }
 608 };
 609
 610 template <class _Key, class _Tp, class _Compare, class _Allocator>
 611     class map;
 612 template <class _Key, class _Tp, class _Compare, class _Allocator>
 613     class multimap;
 614 template <class _TreeIterator> class __map_const_iterator;
 615
 616 #ifndef _LIBCPP_CXX03_LANG
 617
 618 template <class _Key, class _Tp>
 619 union __value_type
 620 {
 621     typedef _Key                                     key_type;
 622     typedef _Tp                                      mapped_type;
 623     typedef pair<const key_type, mapped_type>        value_type;
 624     typedef pair<key_type, mapped_type>              __nc_value_type;
 625
 626     value_type __cc;
 627     __nc_value_type __nc;
 628
 629     _LIBCPP_INLINE_VISIBILITY
 630     __value_type& operator=(const __value_type& __v)
 631         {__nc = __v.__cc; return *this;}
 632
 633     _LIBCPP_INLINE_VISIBILITY
 634     __value_type& operator=(__value_type&& __v)
 635         {__nc = _VSTD::move(__v.__nc); return *this;}
 636
 637     template <class _ValueTp,
 638               class = typename enable_if<
 639                     __is_same_uncvref<_ValueTp, value_type>::value
 640                  >::type
 641              >
 642     _LIBCPP_INLINE_VISIBILITY
 643     __value_type& operator=(_ValueTp&& __v) {
 644         __nc = _VSTD::forward<_ValueTp>(__v); return *this;
 645     }
 646
 647 private:
 648     __value_type() _LIBCPP_EQUAL_DELETE;
 649     ~__value_type() _LIBCPP_EQUAL_DELETE;
 650     __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
 651     __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
 652 };
 653
 654 #else
 655
 656 template <class _Key, class _Tp>
 657 struct __value_type
 658 {
 659     typedef _Key                                     key_type;
 660     typedef _Tp                                      mapped_type;
 661     typedef pair<const key_type, mapped_type>        value_type;
 662
 663     value_type __cc;
 664
 665 private:
 666    __value_type();
 667    __value_type(__value_type const&);
 668    __value_type& operator=(__value_type const&);
 669    ~__value_type();
 670 };
 671
 672 #endif
 673
 674 template <class _Tp>
 675 struct __extract_key_value_types;
 676
 677 template <class _Key, class _Tp>
 678 struct __extract_key_value_types<__value_type<_Key, _Tp> >
 679 {
 680   typedef _Key const __key_type;
 681   typedef _Tp        __mapped_type;
 682 };
 683
 684 template <class _TreeIterator>
 685 class _LIBCPP_TYPE_VIS_ONLY __map_iterator
 686 {
 687     typedef typename _TreeIterator::_NodeTypes                   _NodeTypes;
 688     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
 689
 690     _TreeIterator __i_;
 691
 692 public:
 693     typedef bidirectional_iterator_tag                           iterator_category;
 694     typedef typename _NodeTypes::__map_value_type                value_type;
 695     typedef typename _TreeIterator::difference_type              difference_type;
 696     typedef value_type&                                          reference;
 697     typedef typename _NodeTypes::__map_value_type_pointer        pointer;
 698
 699     _LIBCPP_INLINE_VISIBILITY
 700     __map_iterator() _NOEXCEPT {}
 701
 702     _LIBCPP_INLINE_VISIBILITY
 703     __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 704
 705     _LIBCPP_INLINE_VISIBILITY
 706     reference operator*() const {return __i_->__cc;}
 707     _LIBCPP_INLINE_VISIBILITY
 708     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
 709
 710     _LIBCPP_INLINE_VISIBILITY
 711     __map_iterator& operator++() {++__i_; return *this;}
 712     _LIBCPP_INLINE_VISIBILITY
 713     __map_iterator operator++(int)
 714     {
 715         __map_iterator __t(*this);
 716         ++(*this);
 717         return __t;
 718     }
 719
 720     _LIBCPP_INLINE_VISIBILITY
 721     __map_iterator& operator--() {--__i_; return *this;}
 722     _LIBCPP_INLINE_VISIBILITY
 723     __map_iterator operator--(int)
 724     {
 725         __map_iterator __t(*this);
 726         --(*this);
 727         return __t;
 728     }
 729
 730     friend _LIBCPP_INLINE_VISIBILITY
 731     bool operator==(const __map_iterator& __x, const __map_iterator& __y)
 732         {return __x.__i_ == __y.__i_;}
 733     friend
 734     _LIBCPP_INLINE_VISIBILITY
 735     bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
 736         {return __x.__i_ != __y.__i_;}
 737
 738     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
 739     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
 740     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
 741 };
 742
 743 template <class _TreeIterator>
 744 class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
 745 {
 746     typedef typename _TreeIterator::_NodeTypes                   _NodeTypes;
 747     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
 748
 749     _TreeIterator __i_;
 750
 751 public:
 752     typedef bidirectional_iterator_tag                           iterator_category;
 753     typedef typename _NodeTypes::__map_value_type                value_type;
 754     typedef typename _TreeIterator::difference_type              difference_type;
 755     typedef const value_type&                                    reference;
 756     typedef typename _NodeTypes::__const_map_value_type_pointer  pointer;
 757
 758     _LIBCPP_INLINE_VISIBILITY
 759     __map_const_iterator() _NOEXCEPT {}
 760
 761     _LIBCPP_INLINE_VISIBILITY
 762     __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 763     _LIBCPP_INLINE_VISIBILITY
 764     __map_const_iterator(__map_iterator<
 765         typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
 766         : __i_(__i.__i_) {}
 767
 768     _LIBCPP_INLINE_VISIBILITY
 769     reference operator*() const {return __i_->__cc;}
 770     _LIBCPP_INLINE_VISIBILITY
 771     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
 772
 773     _LIBCPP_INLINE_VISIBILITY
 774     __map_const_iterator& operator++() {++__i_; return *this;}
 775     _LIBCPP_INLINE_VISIBILITY
 776     __map_const_iterator operator++(int)
 777     {
 778         __map_const_iterator __t(*this);
 779         ++(*this);
 780         return __t;
 781     }
 782
 783     _LIBCPP_INLINE_VISIBILITY
 784     __map_const_iterator& operator--() {--__i_; return *this;}
 785     _LIBCPP_INLINE_VISIBILITY
 786     __map_const_iterator operator--(int)
 787     {
 788         __map_const_iterator __t(*this);
 789         --(*this);
 790         return __t;
 791     }
 792
 793     friend _LIBCPP_INLINE_VISIBILITY
 794     bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
 795         {return __x.__i_ == __y.__i_;}
 796     friend _LIBCPP_INLINE_VISIBILITY
 797     bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
 798         {return __x.__i_ != __y.__i_;}
 799
 800     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
 801     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
 802     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
 803 };
 804
 805 template <class _Key, class _Tp, class _Compare = less<_Key>,
 806           class _Allocator = allocator<pair<const _Key, _Tp> > >
 807 class _LIBCPP_TYPE_VIS_ONLY map
 808 {
 809 public:
 810     // types:
 811     typedef _Key                                     key_type;
 812     typedef _Tp                                      mapped_type;
 813     typedef pair<const key_type, mapped_type>        value_type;
 814     typedef pair<key_type, mapped_type>              __nc_value_type;
 815     typedef _Compare                                 key_compare;
 816     typedef _Allocator                               allocator_type;
 817     typedef value_type&                              reference;
 818     typedef const value_type&                        const_reference;
 819
 820     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
 821                   "Allocator::value_type must be same type as value_type");
 822
 823     class _LIBCPP_TYPE_VIS_ONLY value_compare
 824         : public binary_function<value_type, value_type, bool>
 825     {
 826         friend class map;
 827     protected:
 828         key_compare comp;
 829
 830         _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
 831     public:
 832         _LIBCPP_INLINE_VISIBILITY
 833         bool operator()(const value_type& __x, const value_type& __y) const
 834             {return comp(__x.first, __y.first);}
 835     };
 836
 837 private:
 838
 839     typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
 840     typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
 841     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
 842                                                  __value_type>::type __allocator_type;
 843     typedef __tree<__value_type, __vc, __allocator_type>   __base;
 844     typedef typename __base::__node_traits                 __node_traits;
 845     typedef allocator_traits<allocator_type>               __alloc_traits;
 846
 847     __base __tree_;
 848
 849 public:
 850     typedef typename __alloc_traits::pointer               pointer;
 851     typedef typename __alloc_traits::const_pointer         const_pointer;
 852     typedef typename __alloc_traits::size_type             size_type;
 853     typedef typename __alloc_traits::difference_type       difference_type;
 854     typedef __map_iterator<typename __base::iterator>             iterator;
 855     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
 856     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
 857     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
 858
 859     _LIBCPP_INLINE_VISIBILITY
 860     map()
 861         _NOEXCEPT_(
 862             is_nothrow_default_constructible<allocator_type>::value &&
 863             is_nothrow_default_constructible<key_compare>::value &&
 864             is_nothrow_copy_constructible<key_compare>::value)
 865         : __tree_(__vc(key_compare())) {}
 866
 867     _LIBCPP_INLINE_VISIBILITY
 868     explicit map(const key_compare& __comp)
 869         _NOEXCEPT_(
 870             is_nothrow_default_constructible<allocator_type>::value &&
 871             is_nothrow_copy_constructible<key_compare>::value)
 872         : __tree_(__vc(__comp)) {}
 873
 874     _LIBCPP_INLINE_VISIBILITY
 875     explicit map(const key_compare& __comp, const allocator_type& __a)
 876         : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
 877
 878     template <class _InputIterator>
 879     _LIBCPP_INLINE_VISIBILITY
 880         map(_InputIterator __f, _InputIterator __l,
 881             const key_compare& __comp = key_compare())
 882         : __tree_(__vc(__comp))
 883         {
 884             insert(__f, __l);
 885         }
 886
 887     template <class _InputIterator>
 888     _LIBCPP_INLINE_VISIBILITY
 889         map(_InputIterator __f, _InputIterator __l,
 890             const key_compare& __comp, const allocator_type& __a)
 891         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
 892         {
 893             insert(__f, __l);
 894         }
 895
 896 #if _LIBCPP_STD_VER > 11
 897     template <class _InputIterator>
 898     _LIBCPP_INLINE_VISIBILITY
 899     map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
 900         : map(__f, __l, key_compare(), __a) {}
 901 #endif
 902
 903     _LIBCPP_INLINE_VISIBILITY
 904     map(const map& __m)
 905         : __tree_(__m.__tree_)
 906         {
 907             insert(__m.begin(), __m.end());
 908         }
 909
 910     _LIBCPP_INLINE_VISIBILITY
 911     map& operator=(const map& __m)
 912         {
 913 #ifndef _LIBCPP_CXX03_LANG
 914             __tree_ = __m.__tree_;
 915 #else
 916             if (this != &__m) {
 917                 __tree_.clear();
 918                 __tree_.value_comp() = __m.__tree_.value_comp();
 919                 __tree_.__copy_assign_alloc(__m.__tree_);
 920                 insert(__m.begin(), __m.end());
 921             }
 922 #endif
 923             return *this;
 924         }
 925
 926 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 927
 928     _LIBCPP_INLINE_VISIBILITY
 929     map(map&& __m)
 930         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
 931         : __tree_(_VSTD::move(__m.__tree_))
 932         {
 933         }
 934
 935     map(map&& __m, const allocator_type& __a);
 936
 937     _LIBCPP_INLINE_VISIBILITY
 938     map& operator=(map&& __m)
 939         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
 940         {
 941             __tree_ = _VSTD::move(__m.__tree_);
 942             return *this;
 943         }
 944
 945 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 946
 947 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 948
 949     _LIBCPP_INLINE_VISIBILITY
 950     map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
 951         : __tree_(__vc(__comp))
 952         {
 953             insert(__il.begin(), __il.end());
 954         }
 955
 956     _LIBCPP_INLINE_VISIBILITY
 957     map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
 958         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
 959         {
 960             insert(__il.begin(), __il.end());
 961         }
 962
 963 #if _LIBCPP_STD_VER > 11
 964     _LIBCPP_INLINE_VISIBILITY
 965     map(initializer_list<value_type> __il, const allocator_type& __a)
 966         : map(__il, key_compare(), __a) {}
 967 #endif
 968
 969     _LIBCPP_INLINE_VISIBILITY
 970     map& operator=(initializer_list<value_type> __il)
 971         {
 972             __tree_.__assign_unique(__il.begin(), __il.end());
 973             return *this;
 974         }
 975
 976 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 977
 978     _LIBCPP_INLINE_VISIBILITY
 979     explicit map(const allocator_type& __a)
 980         : __tree_(typename __base::allocator_type(__a))
 981         {
 982         }
 983
 984     _LIBCPP_INLINE_VISIBILITY
 985     map(const map& __m, const allocator_type& __a)
 986         : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
 987         {
 988             insert(__m.begin(), __m.end());
 989         }
 990
 991     _LIBCPP_INLINE_VISIBILITY
 992           iterator begin() _NOEXCEPT {return __tree_.begin();}
 993     _LIBCPP_INLINE_VISIBILITY
 994     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
 995     _LIBCPP_INLINE_VISIBILITY
 996           iterator end() _NOEXCEPT {return __tree_.end();}
 997     _LIBCPP_INLINE_VISIBILITY
 998     const_iterator end() const _NOEXCEPT {return __tree_.end();}
 999
1000     _LIBCPP_INLINE_VISIBILITY
1001           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1002     _LIBCPP_INLINE_VISIBILITY
1003     const_reverse_iterator rbegin() const _NOEXCEPT
1004         {return const_reverse_iterator(end());}
1005     _LIBCPP_INLINE_VISIBILITY
1006           reverse_iterator rend() _NOEXCEPT
1007             {return       reverse_iterator(begin());}
1008     _LIBCPP_INLINE_VISIBILITY
1009     const_reverse_iterator rend() const _NOEXCEPT
1010         {return const_reverse_iterator(begin());}
1011
1012     _LIBCPP_INLINE_VISIBILITY
1013     const_iterator cbegin() const _NOEXCEPT {return begin();}
1014     _LIBCPP_INLINE_VISIBILITY
1015     const_iterator cend() const _NOEXCEPT {return end();}
1016     _LIBCPP_INLINE_VISIBILITY
1017     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1018     _LIBCPP_INLINE_VISIBILITY
1019     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1020
1021     _LIBCPP_INLINE_VISIBILITY
1022     bool      empty() const _NOEXCEPT {return __tree_.size() == 0;}
1023     _LIBCPP_INLINE_VISIBILITY
1024     size_type size() const _NOEXCEPT {return __tree_.size();}
1025     _LIBCPP_INLINE_VISIBILITY
1026     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1027
1028     mapped_type& operator[](const key_type& __k);
1029 #ifndef _LIBCPP_CXX03_LANG
1030     mapped_type& operator[](key_type&& __k);
1031 #endif
1032
1033           mapped_type& at(const key_type& __k);
1034     const mapped_type& at(const key_type& __k) const;
1035
1036     _LIBCPP_INLINE_VISIBILITY
1037     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1038     _LIBCPP_INLINE_VISIBILITY
1039     key_compare    key_comp()      const {return __tree_.value_comp().key_comp();}
1040     _LIBCPP_INLINE_VISIBILITY
1041     value_compare  value_comp()    const {return value_compare(__tree_.value_comp().key_comp());}
1042
1043 #ifndef _LIBCPP_CXX03_LANG
1044     template <class ..._Args>
1045     _LIBCPP_INLINE_VISIBILITY
1046     pair<iterator, bool> emplace(_Args&& ...__args) {
1047         return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1048     }
1049
1050     template <class ..._Args>
1051     _LIBCPP_INLINE_VISIBILITY
1052     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1053         return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1054     }
1055
1056     template <class _Pp,
1057               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1058         _LIBCPP_INLINE_VISIBILITY
1059         pair<iterator, bool> insert(_Pp&& __p)
1060             {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1061
1062     template <class _Pp,
1063               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1064         _LIBCPP_INLINE_VISIBILITY
1065         iterator insert(const_iterator __pos, _Pp&& __p)
1066             {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1067
1068 #endif  // _LIBCPP_CXX03_LANG
1069
1070     _LIBCPP_INLINE_VISIBILITY
1071     pair<iterator, bool>
1072         insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1073
1074     _LIBCPP_INLINE_VISIBILITY
1075     iterator
1076         insert(const_iterator __p, const value_type& __v)
1077             {return __tree_.__insert_unique(__p.__i_, __v);}
1078
1079 #ifndef _LIBCPP_CXX03_LANG
1080     _LIBCPP_INLINE_VISIBILITY
1081     pair<iterator, bool>
1082     insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1083
1084     _LIBCPP_INLINE_VISIBILITY
1085     iterator insert(const_iterator __p,  value_type&& __v)
1086     {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1087 #endif
1088
1089     template <class _InputIterator>
1090         _LIBCPP_INLINE_VISIBILITY
1091         void insert(_InputIterator __f, _InputIterator __l)
1092         {
1093             for (const_iterator __e = cend(); __f != __l; ++__f)
1094                 insert(__e.__i_, *__f);
1095         }
1096
1097 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1098
1099     _LIBCPP_INLINE_VISIBILITY
1100     void insert(initializer_list<value_type> __il)
1101         {insert(__il.begin(), __il.end());}
1102
1103 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1104
1105 #if _LIBCPP_STD_VER > 14
1106
1107     template <class... _Args>
1108         _LIBCPP_INLINE_VISIBILITY
1109         pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1110     {
1111         return __tree_.__emplace_unique_key_args(__k,
1112             _VSTD::piecewise_construct,
1113             _VSTD::forward_as_tuple(__k),
1114             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1115     }
1116
1117     template <class... _Args>
1118         _LIBCPP_INLINE_VISIBILITY
1119         pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1120     {
1121         return __tree_.__emplace_unique_key_args(__k,
1122             _VSTD::piecewise_construct,
1123             _VSTD::forward_as_tuple(_VSTD::move(__k)),
1124             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1125     }
1126
1127     template <class... _Args>
1128         _LIBCPP_INLINE_VISIBILITY
1129         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1130     {
1131         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1132             _VSTD::piecewise_construct,
1133             _VSTD::forward_as_tuple(__k),
1134             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1135     }
1136
1137     template <class... _Args>
1138         _LIBCPP_INLINE_VISIBILITY
1139         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1140     {
1141         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1142             _VSTD::piecewise_construct,
1143             _VSTD::forward_as_tuple(_VSTD::move(__k)),
1144             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1145     }
1146
1147     template <class _Vp>
1148         _LIBCPP_INLINE_VISIBILITY
1149         pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1150     {
1151         iterator __p = lower_bound(__k);
1152         if ( __p != end() && !key_comp()(__k, __p->first))
1153         {
1154             __p->second = _VSTD::forward<_Vp>(__v);
1155             return _VSTD::make_pair(__p, false);
1156         }
1157         return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1158     }
1159
1160     template <class _Vp>
1161         _LIBCPP_INLINE_VISIBILITY
1162         pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1163     {
1164         iterator __p = lower_bound(__k);
1165         if ( __p != end() && !key_comp()(__k, __p->first))
1166         {
1167             __p->second = _VSTD::forward<_Vp>(__v);
1168             return _VSTD::make_pair(__p, false);
1169         }
1170         return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1171     }
1172
1173     template <class _Vp>
1174         _LIBCPP_INLINE_VISIBILITY
1175         iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1176      {
1177         iterator __p = lower_bound(__k);
1178         if ( __p != end() && !key_comp()(__k, __p->first))
1179         {
1180             __p->second = _VSTD::forward<_Vp>(__v);
1181             return __p;
1182         }
1183         return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1184      }
1185
1186     template <class _Vp>
1187         _LIBCPP_INLINE_VISIBILITY
1188         iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1189      {
1190         iterator __p = lower_bound(__k);
1191         if ( __p != end() && !key_comp()(__k, __p->first))
1192         {
1193             __p->second = _VSTD::forward<_Vp>(__v);
1194             return __p;
1195         }
1196         return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1197      }
1198
1199 #endif
1200
1201     _LIBCPP_INLINE_VISIBILITY
1202     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1203     _LIBCPP_INLINE_VISIBILITY
1204     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
1205     _LIBCPP_INLINE_VISIBILITY
1206     size_type erase(const key_type& __k)
1207         {return __tree_.__erase_unique(__k);}
1208     _LIBCPP_INLINE_VISIBILITY
1209     iterator  erase(const_iterator __f, const_iterator __l)
1210         {return __tree_.erase(__f.__i_, __l.__i_);}
1211     _LIBCPP_INLINE_VISIBILITY
1212     void clear() _NOEXCEPT {__tree_.clear();}
1213
1214     _LIBCPP_INLINE_VISIBILITY
1215     void swap(map& __m)
1216         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1217         {__tree_.swap(__m.__tree_);}
1218
1219     _LIBCPP_INLINE_VISIBILITY
1220     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1221     _LIBCPP_INLINE_VISIBILITY
1222     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1223 #if _LIBCPP_STD_VER > 11
1224     template <typename _K2>
1225     _LIBCPP_INLINE_VISIBILITY
1226     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1227     find(const _K2& __k)                           {return __tree_.find(__k);}
1228     template <typename _K2>
1229     _LIBCPP_INLINE_VISIBILITY
1230     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1231     find(const _K2& __k) const                     {return __tree_.find(__k);}
1232 #endif
1233
1234     _LIBCPP_INLINE_VISIBILITY
1235     size_type      count(const key_type& __k) const
1236         {return __tree_.__count_unique(__k);}
1237 #if _LIBCPP_STD_VER > 11
1238     template <typename _K2>
1239     _LIBCPP_INLINE_VISIBILITY
1240     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1241     count(const _K2& __k) const {return __tree_.__count_unique(__k);}
1242 #endif
1243     _LIBCPP_INLINE_VISIBILITY
1244     iterator lower_bound(const key_type& __k)
1245         {return __tree_.lower_bound(__k);}
1246     _LIBCPP_INLINE_VISIBILITY
1247     const_iterator lower_bound(const key_type& __k) const
1248         {return __tree_.lower_bound(__k);}
1249 #if _LIBCPP_STD_VER > 11
1250     template <typename _K2>
1251     _LIBCPP_INLINE_VISIBILITY
1252     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1253     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1254
1255     template <typename _K2>
1256     _LIBCPP_INLINE_VISIBILITY
1257     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1258     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1259 #endif
1260
1261     _LIBCPP_INLINE_VISIBILITY
1262     iterator upper_bound(const key_type& __k)
1263         {return __tree_.upper_bound(__k);}
1264     _LIBCPP_INLINE_VISIBILITY
1265     const_iterator upper_bound(const key_type& __k) const
1266         {return __tree_.upper_bound(__k);}
1267 #if _LIBCPP_STD_VER > 11
1268     template <typename _K2>
1269     _LIBCPP_INLINE_VISIBILITY
1270     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1271     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1272     template <typename _K2>
1273     _LIBCPP_INLINE_VISIBILITY
1274     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1275     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1276 #endif
1277
1278     _LIBCPP_INLINE_VISIBILITY
1279     pair<iterator,iterator> equal_range(const key_type& __k)
1280         {return __tree_.__equal_range_unique(__k);}
1281     _LIBCPP_INLINE_VISIBILITY
1282     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1283         {return __tree_.__equal_range_unique(__k);}
1284 #if _LIBCPP_STD_VER > 11
1285     template <typename _K2>
1286     _LIBCPP_INLINE_VISIBILITY
1287     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1288     equal_range(const _K2& __k)       {return __tree_.__equal_range_unique(__k);}
1289     template <typename _K2>
1290     _LIBCPP_INLINE_VISIBILITY
1291     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1292     equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1293 #endif
1294
1295 private:
1296     typedef typename __base::__node                    __node;
1297     typedef typename __base::__node_allocator          __node_allocator;
1298     typedef typename __base::__node_pointer            __node_pointer;
1299     typedef typename __base::__node_base_pointer       __node_base_pointer;
1300
1301     typedef __map_node_destructor<__node_allocator> _Dp;
1302     typedef unique_ptr<__node, _Dp> __node_holder;
1303
1304 #ifdef _LIBCPP_CXX03_LANG
1305     __node_holder __construct_node_with_key(const key_type& __k);
1306 #endif
1307
1308     __node_base_pointer const&
1309     __find_equal_key(__node_base_pointer& __parent, const key_type& __k) const;
1310
1311     _LIBCPP_INLINE_VISIBILITY
1312     __node_base_pointer&
1313     __find_equal_key(__node_base_pointer& __parent, const key_type& __k) {
1314         map const* __const_this = this;
1315         return const_cast<__node_base_pointer&>(
1316             __const_this->__find_equal_key(__parent, __k));
1317     }
1318 };
1319
1320
1321 // Find __k
1322 // Set __parent to parent of null leaf and
1323 //    return reference to null leaf iv __k does not exist.
1324 // If __k exists, set parent to node of __k and return reference to node of __k
1325 template <class _Key, class _Tp, class _Compare, class _Allocator>
1326 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer const&
1327 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1328                                                        const key_type& __k) const
1329 {
1330     __node_pointer __nd = __tree_.__root();
1331     if (__nd != nullptr)
1332     {
1333         while (true)
1334         {
1335             if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1336             {
1337                 if (__nd->__left_ != nullptr)
1338                     __nd = static_cast<__node_pointer>(__nd->__left_);
1339                 else
1340                 {
1341                     __parent = static_cast<__node_base_pointer>(__nd);
1342                     return __parent->__left_;
1343                 }
1344             }
1345             else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1346             {
1347                 if (__nd->__right_ != nullptr)
1348                     __nd = static_cast<__node_pointer>(__nd->__right_);
1349                 else
1350                 {
1351                     __parent = static_cast<__node_base_pointer>(__nd);
1352                     return __parent->__right_;
1353                 }
1354             }
1355             else
1356             {
1357                 __parent = static_cast<__node_base_pointer>(__nd);
1358                 return __parent;
1359             }
1360         }
1361     }
1362     __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1363     return __parent->__left_;
1364 }
1365
1366 #ifndef _LIBCPP_CXX03_LANG
1367
1368 template <class _Key, class _Tp, class _Compare, class _Allocator>
1369 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1370     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1371 {
1372     if (__a != __m.get_allocator())
1373     {
1374         const_iterator __e = cend();
1375         while (!__m.empty())
1376             __tree_.__insert_unique(__e.__i_,
1377                     _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
1378     }
1379 }
1380
1381 #endif  // !_LIBCPP_CXX03_LANG
1382
1383
1384 #ifdef _LIBCPP_CXX03_LANG
1385
1386 template <class _Key, class _Tp, class _Compare, class _Allocator>
1387 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1388 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1389 {
1390     __node_allocator& __na = __tree_.__node_alloc();
1391     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1392     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1393     __h.get_deleter().__first_constructed = true;
1394     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1395     __h.get_deleter().__second_constructed = true;
1396     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1397 }
1398
1399 template <class _Key, class _Tp, class _Compare, class _Allocator>
1400 _Tp&
1401 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1402 {
1403     __node_base_pointer __parent;
1404     __node_base_pointer& __child = __find_equal_key(__parent, __k);
1405     __node_pointer __r = static_cast<__node_pointer>(__child);
1406     if (__child == nullptr)
1407     {
1408         __node_holder __h = __construct_node_with_key(__k);
1409         __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1410         __r = __h.release();
1411     }
1412     return __r->__value_.__cc.second;
1413 }
1414
1415 #else
1416
1417 template <class _Key, class _Tp, class _Compare, class _Allocator>
1418 _Tp&
1419 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1420 {
1421     return __tree_.__emplace_unique_key_args(__k,
1422         _VSTD::piecewise_construct,
1423         _VSTD::forward_as_tuple(__k),
1424         _VSTD::forward_as_tuple()).first->__cc.second;
1425 }
1426
1427 template <class _Key, class _Tp, class _Compare, class _Allocator>
1428 _Tp&
1429 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1430 {
1431     return __tree_.__emplace_unique_key_args(__k,
1432         _VSTD::piecewise_construct,
1433         _VSTD::forward_as_tuple(_VSTD::move(__k)),
1434         _VSTD::forward_as_tuple()).first->__cc.second;
1435 }
1436
1437 #endif  // !_LIBCPP_CXX03_LANG
1438
1439 template <class _Key, class _Tp, class _Compare, class _Allocator>
1440 _Tp&
1441 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1442 {
1443     __node_base_pointer __parent;
1444     __node_base_pointer& __child = __find_equal_key(__parent, __k);
1445 #ifndef _LIBCPP_NO_EXCEPTIONS
1446     if (__child == nullptr)
1447         throw out_of_range("map::at:  key not found");
1448 #endif  // _LIBCPP_NO_EXCEPTIONS
1449     return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1450 }
1451
1452 template <class _Key, class _Tp, class _Compare, class _Allocator>
1453 const _Tp&
1454 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1455 {
1456     __node_base_pointer __parent;
1457     __node_base_pointer __child = __find_equal_key(__parent, __k);
1458 #ifndef _LIBCPP_NO_EXCEPTIONS
1459     if (__child == nullptr)
1460         throw out_of_range("map::at:  key not found");
1461 #endif  // _LIBCPP_NO_EXCEPTIONS
1462     return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1463 }
1464
1465
1466 template <class _Key, class _Tp, class _Compare, class _Allocator>
1467 inline _LIBCPP_INLINE_VISIBILITY
1468 bool
1469 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1470            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1471 {
1472     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1473 }
1474
1475 template <class _Key, class _Tp, class _Compare, class _Allocator>
1476 inline _LIBCPP_INLINE_VISIBILITY
1477 bool
1478 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1479            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1480 {
1481     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1482 }
1483
1484 template <class _Key, class _Tp, class _Compare, class _Allocator>
1485 inline _LIBCPP_INLINE_VISIBILITY
1486 bool
1487 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1488            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1489 {
1490     return !(__x == __y);
1491 }
1492
1493 template <class _Key, class _Tp, class _Compare, class _Allocator>
1494 inline _LIBCPP_INLINE_VISIBILITY
1495 bool
1496 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1497            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1498 {
1499     return __y < __x;
1500 }
1501
1502 template <class _Key, class _Tp, class _Compare, class _Allocator>
1503 inline _LIBCPP_INLINE_VISIBILITY
1504 bool
1505 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1506            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1507 {
1508     return !(__x < __y);
1509 }
1510
1511 template <class _Key, class _Tp, class _Compare, class _Allocator>
1512 inline _LIBCPP_INLINE_VISIBILITY
1513 bool
1514 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1515            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1516 {
1517     return !(__y < __x);
1518 }
1519
1520 template <class _Key, class _Tp, class _Compare, class _Allocator>
1521 inline _LIBCPP_INLINE_VISIBILITY
1522 void
1523 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1524      map<_Key, _Tp, _Compare, _Allocator>& __y)
1525     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1526 {
1527     __x.swap(__y);
1528 }
1529
1530 template <class _Key, class _Tp, class _Compare = less<_Key>,
1531           class _Allocator = allocator<pair<const _Key, _Tp> > >
1532 class _LIBCPP_TYPE_VIS_ONLY multimap
1533 {
1534 public:
1535     // types:
1536     typedef _Key                                     key_type;
1537     typedef _Tp                                      mapped_type;
1538     typedef pair<const key_type, mapped_type>        value_type;
1539     typedef pair<key_type, mapped_type>              __nc_value_type;
1540     typedef _Compare                                 key_compare;
1541     typedef _Allocator                               allocator_type;
1542     typedef value_type&                              reference;
1543     typedef const value_type&                        const_reference;
1544
1545     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1546                   "Allocator::value_type must be same type as value_type");
1547
1548     class _LIBCPP_TYPE_VIS_ONLY value_compare
1549         : public binary_function<value_type, value_type, bool>
1550     {
1551         friend class multimap;
1552     protected:
1553         key_compare comp;
1554
1555         _LIBCPP_INLINE_VISIBILITY
1556         value_compare(key_compare c) : comp(c) {}
1557     public:
1558         _LIBCPP_INLINE_VISIBILITY
1559         bool operator()(const value_type& __x, const value_type& __y) const
1560             {return comp(__x.first, __y.first);}
1561     };
1562
1563 private:
1564
1565     typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
1566     typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1567     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1568                                                  __value_type>::type __allocator_type;
1569     typedef __tree<__value_type, __vc, __allocator_type>            __base;
1570     typedef typename __base::__node_traits                          __node_traits;
1571     typedef allocator_traits<allocator_type>                        __alloc_traits;
1572
1573     __base __tree_;
1574
1575 public:
1576     typedef typename __alloc_traits::pointer               pointer;
1577     typedef typename __alloc_traits::const_pointer         const_pointer;
1578     typedef typename __alloc_traits::size_type             size_type;
1579     typedef typename __alloc_traits::difference_type       difference_type;
1580     typedef __map_iterator<typename __base::iterator>      iterator;
1581     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1582     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
1583     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
1584
1585     _LIBCPP_INLINE_VISIBILITY
1586     multimap()
1587         _NOEXCEPT_(
1588             is_nothrow_default_constructible<allocator_type>::value &&
1589             is_nothrow_default_constructible<key_compare>::value &&
1590             is_nothrow_copy_constructible<key_compare>::value)
1591         : __tree_(__vc(key_compare())) {}
1592
1593     _LIBCPP_INLINE_VISIBILITY
1594     explicit multimap(const key_compare& __comp)
1595         _NOEXCEPT_(
1596             is_nothrow_default_constructible<allocator_type>::value &&
1597             is_nothrow_copy_constructible<key_compare>::value)
1598         : __tree_(__vc(__comp)) {}
1599
1600     _LIBCPP_INLINE_VISIBILITY
1601     explicit multimap(const key_compare& __comp, const allocator_type& __a)
1602         : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1603
1604     template <class _InputIterator>
1605         _LIBCPP_INLINE_VISIBILITY
1606         multimap(_InputIterator __f, _InputIterator __l,
1607             const key_compare& __comp = key_compare())
1608         : __tree_(__vc(__comp))
1609         {
1610             insert(__f, __l);
1611         }
1612
1613     template <class _InputIterator>
1614         _LIBCPP_INLINE_VISIBILITY
1615         multimap(_InputIterator __f, _InputIterator __l,
1616             const key_compare& __comp, const allocator_type& __a)
1617         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1618         {
1619             insert(__f, __l);
1620         }
1621
1622 #if _LIBCPP_STD_VER > 11
1623     template <class _InputIterator>
1624     _LIBCPP_INLINE_VISIBILITY
1625     multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1626         : multimap(__f, __l, key_compare(), __a) {}
1627 #endif
1628
1629     _LIBCPP_INLINE_VISIBILITY
1630     multimap(const multimap& __m)
1631         : __tree_(__m.__tree_.value_comp(),
1632           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1633         {
1634             insert(__m.begin(), __m.end());
1635         }
1636
1637     _LIBCPP_INLINE_VISIBILITY
1638     multimap& operator=(const multimap& __m)
1639         {
1640 #ifndef _LIBCPP_CXX03_LANG
1641             __tree_ = __m.__tree_;
1642 #else
1643             if (this != &__m) {
1644                 __tree_.clear();
1645                 __tree_.value_comp() = __m.__tree_.value_comp();
1646                 __tree_.__copy_assign_alloc(__m.__tree_);
1647                 insert(__m.begin(), __m.end());
1648             }
1649 #endif
1650             return *this;
1651         }
1652
1653 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1654
1655     _LIBCPP_INLINE_VISIBILITY
1656     multimap(multimap&& __m)
1657         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1658         : __tree_(_VSTD::move(__m.__tree_))
1659         {
1660         }
1661
1662     multimap(multimap&& __m, const allocator_type& __a);
1663
1664     _LIBCPP_INLINE_VISIBILITY
1665     multimap& operator=(multimap&& __m)
1666         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1667         {
1668             __tree_ = _VSTD::move(__m.__tree_);
1669             return *this;
1670         }
1671
1672 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1673
1674 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1675
1676     _LIBCPP_INLINE_VISIBILITY
1677     multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1678         : __tree_(__vc(__comp))
1679         {
1680             insert(__il.begin(), __il.end());
1681         }
1682
1683     _LIBCPP_INLINE_VISIBILITY
1684     multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1685         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1686         {
1687             insert(__il.begin(), __il.end());
1688         }
1689
1690 #if _LIBCPP_STD_VER > 11
1691     _LIBCPP_INLINE_VISIBILITY
1692     multimap(initializer_list<value_type> __il, const allocator_type& __a)
1693         : multimap(__il, key_compare(), __a) {}
1694 #endif
1695
1696     _LIBCPP_INLINE_VISIBILITY
1697     multimap& operator=(initializer_list<value_type> __il)
1698         {
1699             __tree_.__assign_multi(__il.begin(), __il.end());
1700             return *this;
1701         }
1702
1703 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1704
1705     _LIBCPP_INLINE_VISIBILITY
1706     explicit multimap(const allocator_type& __a)
1707         : __tree_(typename __base::allocator_type(__a))
1708         {
1709         }
1710
1711     _LIBCPP_INLINE_VISIBILITY
1712     multimap(const multimap& __m, const allocator_type& __a)
1713         : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1714         {
1715             insert(__m.begin(), __m.end());
1716         }
1717
1718     _LIBCPP_INLINE_VISIBILITY
1719           iterator begin() _NOEXCEPT {return __tree_.begin();}
1720     _LIBCPP_INLINE_VISIBILITY
1721     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1722     _LIBCPP_INLINE_VISIBILITY
1723           iterator end() _NOEXCEPT {return __tree_.end();}
1724     _LIBCPP_INLINE_VISIBILITY
1725     const_iterator end() const _NOEXCEPT {return __tree_.end();}
1726
1727     _LIBCPP_INLINE_VISIBILITY
1728           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1729     _LIBCPP_INLINE_VISIBILITY
1730     const_reverse_iterator rbegin() const _NOEXCEPT
1731         {return const_reverse_iterator(end());}
1732     _LIBCPP_INLINE_VISIBILITY
1733           reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1734     _LIBCPP_INLINE_VISIBILITY
1735     const_reverse_iterator rend() const _NOEXCEPT
1736         {return const_reverse_iterator(begin());}
1737
1738     _LIBCPP_INLINE_VISIBILITY
1739     const_iterator cbegin()  const _NOEXCEPT {return begin();}
1740     _LIBCPP_INLINE_VISIBILITY
1741     const_iterator cend() const _NOEXCEPT {return end();}
1742     _LIBCPP_INLINE_VISIBILITY
1743     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1744     _LIBCPP_INLINE_VISIBILITY
1745     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1746
1747     _LIBCPP_INLINE_VISIBILITY
1748     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1749     _LIBCPP_INLINE_VISIBILITY
1750     size_type size() const _NOEXCEPT {return __tree_.size();}
1751     _LIBCPP_INLINE_VISIBILITY
1752     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1753
1754     _LIBCPP_INLINE_VISIBILITY
1755     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1756     _LIBCPP_INLINE_VISIBILITY
1757     key_compare    key_comp() const {return __tree_.value_comp().key_comp();}
1758     _LIBCPP_INLINE_VISIBILITY
1759     value_compare  value_comp() const
1760         {return value_compare(__tree_.value_comp().key_comp());}
1761
1762 #ifndef _LIBCPP_CXX03_LANG
1763
1764     template <class ..._Args>
1765     _LIBCPP_INLINE_VISIBILITY
1766     iterator emplace(_Args&& ...__args) {
1767         return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1768     }
1769
1770     template <class ..._Args>
1771     _LIBCPP_INLINE_VISIBILITY
1772     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1773         return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1774     }
1775
1776     template <class _Pp,
1777               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1778         _LIBCPP_INLINE_VISIBILITY
1779         iterator insert(_Pp&& __p)
1780             {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1781
1782     template <class _Pp,
1783               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1784         _LIBCPP_INLINE_VISIBILITY
1785         iterator insert(const_iterator __pos, _Pp&& __p)
1786             {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1787
1788     _LIBCPP_INLINE_VISIBILITY
1789     iterator insert(value_type&& __v)
1790         {return __tree_.__insert_multi(_VSTD::move(__v));}
1791
1792     _LIBCPP_INLINE_VISIBILITY
1793     iterator insert(const_iterator __p, value_type&& __v)
1794         {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1795
1796 #endif  // _LIBCPP_CXX03_LANG
1797
1798     _LIBCPP_INLINE_VISIBILITY
1799     iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1800
1801     _LIBCPP_INLINE_VISIBILITY
1802     iterator insert(const_iterator __p, const value_type& __v)
1803             {return __tree_.__insert_multi(__p.__i_, __v);}
1804
1805     template <class _InputIterator>
1806         _LIBCPP_INLINE_VISIBILITY
1807         void insert(_InputIterator __f, _InputIterator __l)
1808         {
1809             for (const_iterator __e = cend(); __f != __l; ++__f)
1810                 __tree_.__insert_multi(__e.__i_, *__f);
1811         }
1812
1813 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1814
1815     _LIBCPP_INLINE_VISIBILITY
1816     void insert(initializer_list<value_type> __il)
1817         {insert(__il.begin(), __il.end());}
1818
1819 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1820
1821     _LIBCPP_INLINE_VISIBILITY
1822     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1823     _LIBCPP_INLINE_VISIBILITY
1824     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
1825     _LIBCPP_INLINE_VISIBILITY
1826     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1827     _LIBCPP_INLINE_VISIBILITY
1828     iterator  erase(const_iterator __f, const_iterator __l)
1829         {return __tree_.erase(__f.__i_, __l.__i_);}
1830     _LIBCPP_INLINE_VISIBILITY
1831     void clear() {__tree_.clear();}
1832
1833     _LIBCPP_INLINE_VISIBILITY
1834     void swap(multimap& __m)
1835         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1836         {__tree_.swap(__m.__tree_);}
1837
1838     _LIBCPP_INLINE_VISIBILITY
1839     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1840     _LIBCPP_INLINE_VISIBILITY
1841     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1842 #if _LIBCPP_STD_VER > 11
1843     template <typename _K2>
1844     _LIBCPP_INLINE_VISIBILITY
1845     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1846     find(const _K2& __k)                           {return __tree_.find(__k);}
1847     template <typename _K2>
1848     _LIBCPP_INLINE_VISIBILITY
1849     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1850     find(const _K2& __k) const                     {return __tree_.find(__k);}
1851 #endif
1852
1853     _LIBCPP_INLINE_VISIBILITY
1854     size_type      count(const key_type& __k) const
1855         {return __tree_.__count_multi(__k);}
1856 #if _LIBCPP_STD_VER > 11
1857     template <typename _K2>
1858     _LIBCPP_INLINE_VISIBILITY
1859     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1860     count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1861 #endif
1862     _LIBCPP_INLINE_VISIBILITY
1863     iterator lower_bound(const key_type& __k)
1864         {return __tree_.lower_bound(__k);}
1865     _LIBCPP_INLINE_VISIBILITY
1866     const_iterator lower_bound(const key_type& __k) const
1867             {return __tree_.lower_bound(__k);}
1868 #if _LIBCPP_STD_VER > 11
1869     template <typename _K2>
1870     _LIBCPP_INLINE_VISIBILITY
1871     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1872     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1873
1874     template <typename _K2>
1875     _LIBCPP_INLINE_VISIBILITY
1876     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1877     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1878 #endif
1879
1880     _LIBCPP_INLINE_VISIBILITY
1881     iterator upper_bound(const key_type& __k)
1882             {return __tree_.upper_bound(__k);}
1883     _LIBCPP_INLINE_VISIBILITY
1884     const_iterator upper_bound(const key_type& __k) const
1885             {return __tree_.upper_bound(__k);}
1886 #if _LIBCPP_STD_VER > 11
1887     template <typename _K2>
1888     _LIBCPP_INLINE_VISIBILITY
1889     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1890     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1891     template <typename _K2>
1892     _LIBCPP_INLINE_VISIBILITY
1893     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1894     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1895 #endif
1896
1897     _LIBCPP_INLINE_VISIBILITY
1898     pair<iterator,iterator>             equal_range(const key_type& __k)
1899             {return __tree_.__equal_range_multi(__k);}
1900     _LIBCPP_INLINE_VISIBILITY
1901     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1902             {return __tree_.__equal_range_multi(__k);}
1903 #if _LIBCPP_STD_VER > 11
1904     template <typename _K2>
1905     _LIBCPP_INLINE_VISIBILITY
1906     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1907     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1908     template <typename _K2>
1909     _LIBCPP_INLINE_VISIBILITY
1910     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1911     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1912 #endif
1913
1914 private:
1915     typedef typename __base::__node                    __node;
1916     typedef typename __base::__node_allocator          __node_allocator;
1917     typedef typename __base::__node_pointer            __node_pointer;
1918
1919     typedef __map_node_destructor<__node_allocator> _Dp;
1920     typedef unique_ptr<__node, _Dp> __node_holder;
1921 };
1922
1923 #ifndef _LIBCPP_CXX03_LANG
1924 template <class _Key, class _Tp, class _Compare, class _Allocator>
1925 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1926     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1927 {
1928     if (__a != __m.get_allocator())
1929     {
1930         const_iterator __e = cend();
1931         while (!__m.empty())
1932             __tree_.__insert_multi(__e.__i_,
1933                     _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
1934     }
1935 }
1936 #endif
1937
1938 template <class _Key, class _Tp, class _Compare, class _Allocator>
1939 inline _LIBCPP_INLINE_VISIBILITY
1940 bool
1941 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1942            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1943 {
1944     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1945 }
1946
1947 template <class _Key, class _Tp, class _Compare, class _Allocator>
1948 inline _LIBCPP_INLINE_VISIBILITY
1949 bool
1950 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1951            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1952 {
1953     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1954 }
1955
1956 template <class _Key, class _Tp, class _Compare, class _Allocator>
1957 inline _LIBCPP_INLINE_VISIBILITY
1958 bool
1959 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1960            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1961 {
1962     return !(__x == __y);
1963 }
1964
1965 template <class _Key, class _Tp, class _Compare, class _Allocator>
1966 inline _LIBCPP_INLINE_VISIBILITY
1967 bool
1968 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1969            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1970 {
1971     return __y < __x;
1972 }
1973
1974 template <class _Key, class _Tp, class _Compare, class _Allocator>
1975 inline _LIBCPP_INLINE_VISIBILITY
1976 bool
1977 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1978            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1979 {
1980     return !(__x < __y);
1981 }
1982
1983 template <class _Key, class _Tp, class _Compare, class _Allocator>
1984 inline _LIBCPP_INLINE_VISIBILITY
1985 bool
1986 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1987            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1988 {
1989     return !(__y < __x);
1990 }
1991
1992 template <class _Key, class _Tp, class _Compare, class _Allocator>
1993 inline _LIBCPP_INLINE_VISIBILITY
1994 void
1995 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1996      multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1997     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1998 {
1999     __x.swap(__y);
2000 }
2001
2002 _LIBCPP_END_NAMESPACE_STD
2003
2004 #endif  // _LIBCPP_MAP