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