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