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