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_TEMPLATE_VIS __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_TEMPLATE_VIS map;
 739     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 740     template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
 741 };
 742
 743 template <class _TreeIterator>
 744 class _LIBCPP_TEMPLATE_VIS __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_TEMPLATE_VIS map;
 801     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 802     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __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_TEMPLATE_VIS 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_TEMPLATE_VIS 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     typedef typename __base::__parent_pointer          __parent_pointer;
1301
1302     typedef __map_node_destructor<__node_allocator> _Dp;
1303     typedef unique_ptr<__node, _Dp> __node_holder;
1304
1305 #ifdef _LIBCPP_CXX03_LANG
1306     __node_holder __construct_node_with_key(const key_type& __k);
1307 #endif
1308 };
1309
1310
1311 #ifndef _LIBCPP_CXX03_LANG
1312
1313 template <class _Key, class _Tp, class _Compare, class _Allocator>
1314 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1315     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1316 {
1317     if (__a != __m.get_allocator())
1318     {
1319         const_iterator __e = cend();
1320         while (!__m.empty())
1321             __tree_.__insert_unique(__e.__i_,
1322                     _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
1323     }
1324 }
1325
1326 #endif  // !_LIBCPP_CXX03_LANG
1327
1328
1329 #ifdef _LIBCPP_CXX03_LANG
1330
1331 template <class _Key, class _Tp, class _Compare, class _Allocator>
1332 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1333 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1334 {
1335     __node_allocator& __na = __tree_.__node_alloc();
1336     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1337     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1338     __h.get_deleter().__first_constructed = true;
1339     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1340     __h.get_deleter().__second_constructed = true;
1341     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1342 }
1343
1344 template <class _Key, class _Tp, class _Compare, class _Allocator>
1345 _Tp&
1346 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1347 {
1348     __parent_pointer __parent;
1349     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1350     __node_pointer __r = static_cast<__node_pointer>(__child);
1351     if (__child == nullptr)
1352     {
1353         __node_holder __h = __construct_node_with_key(__k);
1354         __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1355         __r = __h.release();
1356     }
1357     return __r->__value_.__cc.second;
1358 }
1359
1360 #else
1361
1362 template <class _Key, class _Tp, class _Compare, class _Allocator>
1363 _Tp&
1364 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1365 {
1366     return __tree_.__emplace_unique_key_args(__k,
1367         _VSTD::piecewise_construct,
1368         _VSTD::forward_as_tuple(__k),
1369         _VSTD::forward_as_tuple()).first->__cc.second;
1370 }
1371
1372 template <class _Key, class _Tp, class _Compare, class _Allocator>
1373 _Tp&
1374 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1375 {
1376     return __tree_.__emplace_unique_key_args(__k,
1377         _VSTD::piecewise_construct,
1378         _VSTD::forward_as_tuple(_VSTD::move(__k)),
1379         _VSTD::forward_as_tuple()).first->__cc.second;
1380 }
1381
1382 #endif  // !_LIBCPP_CXX03_LANG
1383
1384 template <class _Key, class _Tp, class _Compare, class _Allocator>
1385 _Tp&
1386 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1387 {
1388     __parent_pointer __parent;
1389     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1390 #ifndef _LIBCPP_NO_EXCEPTIONS
1391     if (__child == nullptr)
1392         throw out_of_range("map::at:  key not found");
1393 #endif  // _LIBCPP_NO_EXCEPTIONS
1394     return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1395 }
1396
1397 template <class _Key, class _Tp, class _Compare, class _Allocator>
1398 const _Tp&
1399 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1400 {
1401     __parent_pointer __parent;
1402     __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1403 #ifndef _LIBCPP_NO_EXCEPTIONS
1404     if (__child == nullptr)
1405         throw out_of_range("map::at:  key not found");
1406 #endif  // _LIBCPP_NO_EXCEPTIONS
1407     return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1408 }
1409
1410
1411 template <class _Key, class _Tp, class _Compare, class _Allocator>
1412 inline _LIBCPP_INLINE_VISIBILITY
1413 bool
1414 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1415            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1416 {
1417     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1418 }
1419
1420 template <class _Key, class _Tp, class _Compare, class _Allocator>
1421 inline _LIBCPP_INLINE_VISIBILITY
1422 bool
1423 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1424            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1425 {
1426     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1427 }
1428
1429 template <class _Key, class _Tp, class _Compare, class _Allocator>
1430 inline _LIBCPP_INLINE_VISIBILITY
1431 bool
1432 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1433            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1434 {
1435     return !(__x == __y);
1436 }
1437
1438 template <class _Key, class _Tp, class _Compare, class _Allocator>
1439 inline _LIBCPP_INLINE_VISIBILITY
1440 bool
1441 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1442            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1443 {
1444     return __y < __x;
1445 }
1446
1447 template <class _Key, class _Tp, class _Compare, class _Allocator>
1448 inline _LIBCPP_INLINE_VISIBILITY
1449 bool
1450 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1451            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1452 {
1453     return !(__x < __y);
1454 }
1455
1456 template <class _Key, class _Tp, class _Compare, class _Allocator>
1457 inline _LIBCPP_INLINE_VISIBILITY
1458 bool
1459 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1460            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1461 {
1462     return !(__y < __x);
1463 }
1464
1465 template <class _Key, class _Tp, class _Compare, class _Allocator>
1466 inline _LIBCPP_INLINE_VISIBILITY
1467 void
1468 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1469      map<_Key, _Tp, _Compare, _Allocator>& __y)
1470     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1471 {
1472     __x.swap(__y);
1473 }
1474
1475 template <class _Key, class _Tp, class _Compare = less<_Key>,
1476           class _Allocator = allocator<pair<const _Key, _Tp> > >
1477 class _LIBCPP_TEMPLATE_VIS multimap
1478 {
1479 public:
1480     // types:
1481     typedef _Key                                     key_type;
1482     typedef _Tp                                      mapped_type;
1483     typedef pair<const key_type, mapped_type>        value_type;
1484     typedef pair<key_type, mapped_type>              __nc_value_type;
1485     typedef _Compare                                 key_compare;
1486     typedef _Allocator                               allocator_type;
1487     typedef value_type&                              reference;
1488     typedef const value_type&                        const_reference;
1489
1490     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1491                   "Allocator::value_type must be same type as value_type");
1492
1493     class _LIBCPP_TEMPLATE_VIS value_compare
1494         : public binary_function<value_type, value_type, bool>
1495     {
1496         friend class multimap;
1497     protected:
1498         key_compare comp;
1499
1500         _LIBCPP_INLINE_VISIBILITY
1501         value_compare(key_compare c) : comp(c) {}
1502     public:
1503         _LIBCPP_INLINE_VISIBILITY
1504         bool operator()(const value_type& __x, const value_type& __y) const
1505             {return comp(__x.first, __y.first);}
1506     };
1507
1508 private:
1509
1510     typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
1511     typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1512     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1513                                                  __value_type>::type __allocator_type;
1514     typedef __tree<__value_type, __vc, __allocator_type>            __base;
1515     typedef typename __base::__node_traits                          __node_traits;
1516     typedef allocator_traits<allocator_type>                        __alloc_traits;
1517
1518     __base __tree_;
1519
1520 public:
1521     typedef typename __alloc_traits::pointer               pointer;
1522     typedef typename __alloc_traits::const_pointer         const_pointer;
1523     typedef typename __alloc_traits::size_type             size_type;
1524     typedef typename __alloc_traits::difference_type       difference_type;
1525     typedef __map_iterator<typename __base::iterator>      iterator;
1526     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1527     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
1528     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
1529
1530     _LIBCPP_INLINE_VISIBILITY
1531     multimap()
1532         _NOEXCEPT_(
1533             is_nothrow_default_constructible<allocator_type>::value &&
1534             is_nothrow_default_constructible<key_compare>::value &&
1535             is_nothrow_copy_constructible<key_compare>::value)
1536         : __tree_(__vc(key_compare())) {}
1537
1538     _LIBCPP_INLINE_VISIBILITY
1539     explicit multimap(const key_compare& __comp)
1540         _NOEXCEPT_(
1541             is_nothrow_default_constructible<allocator_type>::value &&
1542             is_nothrow_copy_constructible<key_compare>::value)
1543         : __tree_(__vc(__comp)) {}
1544
1545     _LIBCPP_INLINE_VISIBILITY
1546     explicit multimap(const key_compare& __comp, const allocator_type& __a)
1547         : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1548
1549     template <class _InputIterator>
1550         _LIBCPP_INLINE_VISIBILITY
1551         multimap(_InputIterator __f, _InputIterator __l,
1552             const key_compare& __comp = key_compare())
1553         : __tree_(__vc(__comp))
1554         {
1555             insert(__f, __l);
1556         }
1557
1558     template <class _InputIterator>
1559         _LIBCPP_INLINE_VISIBILITY
1560         multimap(_InputIterator __f, _InputIterator __l,
1561             const key_compare& __comp, const allocator_type& __a)
1562         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1563         {
1564             insert(__f, __l);
1565         }
1566
1567 #if _LIBCPP_STD_VER > 11
1568     template <class _InputIterator>
1569     _LIBCPP_INLINE_VISIBILITY
1570     multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1571         : multimap(__f, __l, key_compare(), __a) {}
1572 #endif
1573
1574     _LIBCPP_INLINE_VISIBILITY
1575     multimap(const multimap& __m)
1576         : __tree_(__m.__tree_.value_comp(),
1577           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1578         {
1579             insert(__m.begin(), __m.end());
1580         }
1581
1582     _LIBCPP_INLINE_VISIBILITY
1583     multimap& operator=(const multimap& __m)
1584         {
1585 #ifndef _LIBCPP_CXX03_LANG
1586             __tree_ = __m.__tree_;
1587 #else
1588             if (this != &__m) {
1589                 __tree_.clear();
1590                 __tree_.value_comp() = __m.__tree_.value_comp();
1591                 __tree_.__copy_assign_alloc(__m.__tree_);
1592                 insert(__m.begin(), __m.end());
1593             }
1594 #endif
1595             return *this;
1596         }
1597
1598 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1599
1600     _LIBCPP_INLINE_VISIBILITY
1601     multimap(multimap&& __m)
1602         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1603         : __tree_(_VSTD::move(__m.__tree_))
1604         {
1605         }
1606
1607     multimap(multimap&& __m, const allocator_type& __a);
1608
1609     _LIBCPP_INLINE_VISIBILITY
1610     multimap& operator=(multimap&& __m)
1611         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1612         {
1613             __tree_ = _VSTD::move(__m.__tree_);
1614             return *this;
1615         }
1616
1617 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1618
1619 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1620
1621     _LIBCPP_INLINE_VISIBILITY
1622     multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1623         : __tree_(__vc(__comp))
1624         {
1625             insert(__il.begin(), __il.end());
1626         }
1627
1628     _LIBCPP_INLINE_VISIBILITY
1629     multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1630         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1631         {
1632             insert(__il.begin(), __il.end());
1633         }
1634
1635 #if _LIBCPP_STD_VER > 11
1636     _LIBCPP_INLINE_VISIBILITY
1637     multimap(initializer_list<value_type> __il, const allocator_type& __a)
1638         : multimap(__il, key_compare(), __a) {}
1639 #endif
1640
1641     _LIBCPP_INLINE_VISIBILITY
1642     multimap& operator=(initializer_list<value_type> __il)
1643         {
1644             __tree_.__assign_multi(__il.begin(), __il.end());
1645             return *this;
1646         }
1647
1648 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1649
1650     _LIBCPP_INLINE_VISIBILITY
1651     explicit multimap(const allocator_type& __a)
1652         : __tree_(typename __base::allocator_type(__a))
1653         {
1654         }
1655
1656     _LIBCPP_INLINE_VISIBILITY
1657     multimap(const multimap& __m, const allocator_type& __a)
1658         : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1659         {
1660             insert(__m.begin(), __m.end());
1661         }
1662
1663     _LIBCPP_INLINE_VISIBILITY
1664           iterator begin() _NOEXCEPT {return __tree_.begin();}
1665     _LIBCPP_INLINE_VISIBILITY
1666     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1667     _LIBCPP_INLINE_VISIBILITY
1668           iterator end() _NOEXCEPT {return __tree_.end();}
1669     _LIBCPP_INLINE_VISIBILITY
1670     const_iterator end() const _NOEXCEPT {return __tree_.end();}
1671
1672     _LIBCPP_INLINE_VISIBILITY
1673           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1674     _LIBCPP_INLINE_VISIBILITY
1675     const_reverse_iterator rbegin() const _NOEXCEPT
1676         {return const_reverse_iterator(end());}
1677     _LIBCPP_INLINE_VISIBILITY
1678           reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1679     _LIBCPP_INLINE_VISIBILITY
1680     const_reverse_iterator rend() const _NOEXCEPT
1681         {return const_reverse_iterator(begin());}
1682
1683     _LIBCPP_INLINE_VISIBILITY
1684     const_iterator cbegin()  const _NOEXCEPT {return begin();}
1685     _LIBCPP_INLINE_VISIBILITY
1686     const_iterator cend() const _NOEXCEPT {return end();}
1687     _LIBCPP_INLINE_VISIBILITY
1688     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1689     _LIBCPP_INLINE_VISIBILITY
1690     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1691
1692     _LIBCPP_INLINE_VISIBILITY
1693     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1694     _LIBCPP_INLINE_VISIBILITY
1695     size_type size() const _NOEXCEPT {return __tree_.size();}
1696     _LIBCPP_INLINE_VISIBILITY
1697     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1698
1699     _LIBCPP_INLINE_VISIBILITY
1700     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1701     _LIBCPP_INLINE_VISIBILITY
1702     key_compare    key_comp() const {return __tree_.value_comp().key_comp();}
1703     _LIBCPP_INLINE_VISIBILITY
1704     value_compare  value_comp() const
1705         {return value_compare(__tree_.value_comp().key_comp());}
1706
1707 #ifndef _LIBCPP_CXX03_LANG
1708
1709     template <class ..._Args>
1710     _LIBCPP_INLINE_VISIBILITY
1711     iterator emplace(_Args&& ...__args) {
1712         return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1713     }
1714
1715     template <class ..._Args>
1716     _LIBCPP_INLINE_VISIBILITY
1717     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1718         return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1719     }
1720
1721     template <class _Pp,
1722               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1723         _LIBCPP_INLINE_VISIBILITY
1724         iterator insert(_Pp&& __p)
1725             {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1726
1727     template <class _Pp,
1728               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1729         _LIBCPP_INLINE_VISIBILITY
1730         iterator insert(const_iterator __pos, _Pp&& __p)
1731             {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1732
1733     _LIBCPP_INLINE_VISIBILITY
1734     iterator insert(value_type&& __v)
1735         {return __tree_.__insert_multi(_VSTD::move(__v));}
1736
1737     _LIBCPP_INLINE_VISIBILITY
1738     iterator insert(const_iterator __p, value_type&& __v)
1739         {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1740
1741 #endif  // _LIBCPP_CXX03_LANG
1742
1743     _LIBCPP_INLINE_VISIBILITY
1744     iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1745
1746     _LIBCPP_INLINE_VISIBILITY
1747     iterator insert(const_iterator __p, const value_type& __v)
1748             {return __tree_.__insert_multi(__p.__i_, __v);}
1749
1750     template <class _InputIterator>
1751         _LIBCPP_INLINE_VISIBILITY
1752         void insert(_InputIterator __f, _InputIterator __l)
1753         {
1754             for (const_iterator __e = cend(); __f != __l; ++__f)
1755                 __tree_.__insert_multi(__e.__i_, *__f);
1756         }
1757
1758 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1759
1760     _LIBCPP_INLINE_VISIBILITY
1761     void insert(initializer_list<value_type> __il)
1762         {insert(__il.begin(), __il.end());}
1763
1764 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1765
1766     _LIBCPP_INLINE_VISIBILITY
1767     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1768     _LIBCPP_INLINE_VISIBILITY
1769     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
1770     _LIBCPP_INLINE_VISIBILITY
1771     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1772     _LIBCPP_INLINE_VISIBILITY
1773     iterator  erase(const_iterator __f, const_iterator __l)
1774         {return __tree_.erase(__f.__i_, __l.__i_);}
1775     _LIBCPP_INLINE_VISIBILITY
1776     void clear() {__tree_.clear();}
1777
1778     _LIBCPP_INLINE_VISIBILITY
1779     void swap(multimap& __m)
1780         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1781         {__tree_.swap(__m.__tree_);}
1782
1783     _LIBCPP_INLINE_VISIBILITY
1784     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1785     _LIBCPP_INLINE_VISIBILITY
1786     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1787 #if _LIBCPP_STD_VER > 11
1788     template <typename _K2>
1789     _LIBCPP_INLINE_VISIBILITY
1790     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1791     find(const _K2& __k)                           {return __tree_.find(__k);}
1792     template <typename _K2>
1793     _LIBCPP_INLINE_VISIBILITY
1794     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1795     find(const _K2& __k) const                     {return __tree_.find(__k);}
1796 #endif
1797
1798     _LIBCPP_INLINE_VISIBILITY
1799     size_type      count(const key_type& __k) const
1800         {return __tree_.__count_multi(__k);}
1801 #if _LIBCPP_STD_VER > 11
1802     template <typename _K2>
1803     _LIBCPP_INLINE_VISIBILITY
1804     typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1805     count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1806 #endif
1807     _LIBCPP_INLINE_VISIBILITY
1808     iterator lower_bound(const key_type& __k)
1809         {return __tree_.lower_bound(__k);}
1810     _LIBCPP_INLINE_VISIBILITY
1811     const_iterator lower_bound(const key_type& __k) const
1812             {return __tree_.lower_bound(__k);}
1813 #if _LIBCPP_STD_VER > 11
1814     template <typename _K2>
1815     _LIBCPP_INLINE_VISIBILITY
1816     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1817     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1818
1819     template <typename _K2>
1820     _LIBCPP_INLINE_VISIBILITY
1821     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1822     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1823 #endif
1824
1825     _LIBCPP_INLINE_VISIBILITY
1826     iterator upper_bound(const key_type& __k)
1827             {return __tree_.upper_bound(__k);}
1828     _LIBCPP_INLINE_VISIBILITY
1829     const_iterator upper_bound(const key_type& __k) const
1830             {return __tree_.upper_bound(__k);}
1831 #if _LIBCPP_STD_VER > 11
1832     template <typename _K2>
1833     _LIBCPP_INLINE_VISIBILITY
1834     typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1835     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1836     template <typename _K2>
1837     _LIBCPP_INLINE_VISIBILITY
1838     typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1839     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1840 #endif
1841
1842     _LIBCPP_INLINE_VISIBILITY
1843     pair<iterator,iterator>             equal_range(const key_type& __k)
1844             {return __tree_.__equal_range_multi(__k);}
1845     _LIBCPP_INLINE_VISIBILITY
1846     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1847             {return __tree_.__equal_range_multi(__k);}
1848 #if _LIBCPP_STD_VER > 11
1849     template <typename _K2>
1850     _LIBCPP_INLINE_VISIBILITY
1851     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1852     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1853     template <typename _K2>
1854     _LIBCPP_INLINE_VISIBILITY
1855     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1856     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1857 #endif
1858
1859 private:
1860     typedef typename __base::__node                    __node;
1861     typedef typename __base::__node_allocator          __node_allocator;
1862     typedef typename __base::__node_pointer            __node_pointer;
1863
1864     typedef __map_node_destructor<__node_allocator> _Dp;
1865     typedef unique_ptr<__node, _Dp> __node_holder;
1866 };
1867
1868 #ifndef _LIBCPP_CXX03_LANG
1869 template <class _Key, class _Tp, class _Compare, class _Allocator>
1870 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1871     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1872 {
1873     if (__a != __m.get_allocator())
1874     {
1875         const_iterator __e = cend();
1876         while (!__m.empty())
1877             __tree_.__insert_multi(__e.__i_,
1878                     _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
1879     }
1880 }
1881 #endif
1882
1883 template <class _Key, class _Tp, class _Compare, class _Allocator>
1884 inline _LIBCPP_INLINE_VISIBILITY
1885 bool
1886 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1887            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1888 {
1889     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1890 }
1891
1892 template <class _Key, class _Tp, class _Compare, class _Allocator>
1893 inline _LIBCPP_INLINE_VISIBILITY
1894 bool
1895 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1896            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1897 {
1898     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1899 }
1900
1901 template <class _Key, class _Tp, class _Compare, class _Allocator>
1902 inline _LIBCPP_INLINE_VISIBILITY
1903 bool
1904 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1905            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1906 {
1907     return !(__x == __y);
1908 }
1909
1910 template <class _Key, class _Tp, class _Compare, class _Allocator>
1911 inline _LIBCPP_INLINE_VISIBILITY
1912 bool
1913 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1914            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1915 {
1916     return __y < __x;
1917 }
1918
1919 template <class _Key, class _Tp, class _Compare, class _Allocator>
1920 inline _LIBCPP_INLINE_VISIBILITY
1921 bool
1922 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1923            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1924 {
1925     return !(__x < __y);
1926 }
1927
1928 template <class _Key, class _Tp, class _Compare, class _Allocator>
1929 inline _LIBCPP_INLINE_VISIBILITY
1930 bool
1931 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1932            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1933 {
1934     return !(__y < __x);
1935 }
1936
1937 template <class _Key, class _Tp, class _Compare, class _Allocator>
1938 inline _LIBCPP_INLINE_VISIBILITY
1939 void
1940 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1941      multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1942     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1943 {
1944     __x.swap(__y);
1945 }
1946
1947 _LIBCPP_END_NAMESPACE_STD
1948
1949 #endif  // _LIBCPP_MAP