brintos / llvm-project-archived public Read only

1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___TREE11#define _LIBCPP___CXX03___TREE12 13#include <__cxx03/__algorithm/min.h>14#include <__cxx03/__assert>15#include <__cxx03/__config>16#include <__cxx03/__iterator/distance.h>17#include <__cxx03/__iterator/iterator_traits.h>18#include <__cxx03/__iterator/next.h>19#include <__cxx03/__memory/addressof.h>20#include <__cxx03/__memory/allocator_traits.h>21#include <__cxx03/__memory/compressed_pair.h>22#include <__cxx03/__memory/pointer_traits.h>23#include <__cxx03/__memory/swap_allocator.h>24#include <__cxx03/__memory/unique_ptr.h>25#include <__cxx03/__type_traits/can_extract_key.h>26#include <__cxx03/__type_traits/conditional.h>27#include <__cxx03/__type_traits/invoke.h>28#include <__cxx03/__type_traits/is_const.h>29#include <__cxx03/__type_traits/is_constructible.h>30#include <__cxx03/__type_traits/is_nothrow_assignable.h>31#include <__cxx03/__type_traits/is_nothrow_constructible.h>32#include <__cxx03/__type_traits/is_pointer.h>33#include <__cxx03/__type_traits/is_same.h>34#include <__cxx03/__type_traits/is_swappable.h>35#include <__cxx03/__type_traits/remove_const_ref.h>36#include <__cxx03/__type_traits/remove_cvref.h>37#include <__cxx03/__utility/forward.h>38#include <__cxx03/__utility/move.h>39#include <__cxx03/__utility/pair.h>40#include <__cxx03/__utility/swap.h>41#include <__cxx03/limits>42 43#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)44#  pragma GCC system_header45#endif46 47_LIBCPP_PUSH_MACROS48#include <__cxx03/__undef_macros>49 50_LIBCPP_BEGIN_NAMESPACE_STD51 52template <class, class, class, class>53class _LIBCPP_TEMPLATE_VIS map;54template <class, class, class, class>55class _LIBCPP_TEMPLATE_VIS multimap;56template <class, class, class>57class _LIBCPP_TEMPLATE_VIS set;58template <class, class, class>59class _LIBCPP_TEMPLATE_VIS multiset;60 61template <class _Tp, class _Compare, class _Allocator>62class __tree;63template <class _Tp, class _NodePtr, class _DiffType>64class _LIBCPP_TEMPLATE_VIS __tree_iterator;65template <class _Tp, class _ConstNodePtr, class _DiffType>66class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;67 68template <class _Pointer>69class __tree_end_node;70template <class _VoidPtr>71class __tree_node_base;72template <class _Tp, class _VoidPtr>73class __tree_node;74 75template <class _Key, class _Value>76struct __value_type;77 78template <class _Allocator>79class __map_node_destructor;80template <class _TreeIterator>81class _LIBCPP_TEMPLATE_VIS __map_iterator;82template <class _TreeIterator>83class _LIBCPP_TEMPLATE_VIS __map_const_iterator;84 85/*86 87_NodePtr algorithms88 89The algorithms taking _NodePtr are red black tree algorithms.  Those90algorithms taking a parameter named __root should assume that __root91points to a proper red black tree (unless otherwise specified).92 93Each algorithm herein assumes that __root->__parent_ points to a non-null94structure which has a member __left_ which points back to __root.  No other95member is read or written to at __root->__parent_.96 97__root->__parent_ will be referred to below (in comments only) as end_node.98end_node->__left_ is an externably accessible lvalue for __root, and can be99changed by node insertion and removal (without explicit reference to end_node).100 101All nodes (with the exception of end_node), even the node referred to as102__root, have a non-null __parent_ field.103 104*/105 106// Returns:  true if __x is a left child of its parent, else false107// Precondition:  __x != nullptr.108template <class _NodePtr>109inline _LIBCPP_HIDE_FROM_ABI bool __tree_is_left_child(_NodePtr __x) _NOEXCEPT {110  return __x == __x->__parent_->__left_;111}112 113// Determines if the subtree rooted at __x is a proper red black subtree.  If114//    __x is a proper subtree, returns the black height (null counts as 1).  If115//    __x is an improper subtree, returns 0.116template <class _NodePtr>117unsigned __tree_sub_invariant(_NodePtr __x) {118  if (__x == nullptr)119    return 1;120  // parent consistency checked by caller121  // check __x->__left_ consistency122  if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)123    return 0;124  // check __x->__right_ consistency125  if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)126    return 0;127  // check __x->__left_ != __x->__right_ unless both are nullptr128  if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)129    return 0;130  // If this is red, neither child can be red131  if (!__x->__is_black_) {132    if (__x->__left_ && !__x->__left_->__is_black_)133      return 0;134    if (__x->__right_ && !__x->__right_->__is_black_)135      return 0;136  }137  unsigned __h = std::__tree_sub_invariant(__x->__left_);138  if (__h == 0)139    return 0; // invalid left subtree140  if (__h != std::__tree_sub_invariant(__x->__right_))141    return 0;                    // invalid or different height right subtree142  return __h + __x->__is_black_; // return black height of this node143}144 145// Determines if the red black tree rooted at __root is a proper red black tree.146//    __root == nullptr is a proper tree.  Returns true is __root is a proper147//    red black tree, else returns false.148template <class _NodePtr>149_LIBCPP_HIDE_FROM_ABI bool __tree_invariant(_NodePtr __root) {150  if (__root == nullptr)151    return true;152  // check __x->__parent_ consistency153  if (__root->__parent_ == nullptr)154    return false;155  if (!std::__tree_is_left_child(__root))156    return false;157  // root must be black158  if (!__root->__is_black_)159    return false;160  // do normal node checks161  return std::__tree_sub_invariant(__root) != 0;162}163 164// Returns:  pointer to the left-most node under __x.165template <class _NodePtr>166inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_min(_NodePtr __x) _NOEXCEPT {167  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Root node shouldn't be null");168  while (__x->__left_ != nullptr)169    __x = __x->__left_;170  return __x;171}172 173// Returns:  pointer to the right-most node under __x.174template <class _NodePtr>175inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_max(_NodePtr __x) _NOEXCEPT {176  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Root node shouldn't be null");177  while (__x->__right_ != nullptr)178    __x = __x->__right_;179  return __x;180}181 182// Returns:  pointer to the next in-order node after __x.183template <class _NodePtr>184_LIBCPP_HIDE_FROM_ABI _NodePtr __tree_next(_NodePtr __x) _NOEXCEPT {185  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");186  if (__x->__right_ != nullptr)187    return std::__tree_min(__x->__right_);188  while (!std::__tree_is_left_child(__x))189    __x = __x->__parent_unsafe();190  return __x->__parent_unsafe();191}192 193template <class _EndNodePtr, class _NodePtr>194inline _LIBCPP_HIDE_FROM_ABI _EndNodePtr __tree_next_iter(_NodePtr __x) _NOEXCEPT {195  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");196  if (__x->__right_ != nullptr)197    return static_cast<_EndNodePtr>(std::__tree_min(__x->__right_));198  while (!std::__tree_is_left_child(__x))199    __x = __x->__parent_unsafe();200  return static_cast<_EndNodePtr>(__x->__parent_);201}202 203// Returns:  pointer to the previous in-order node before __x.204// Note: __x may be the end node.205template <class _NodePtr, class _EndNodePtr>206inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT {207  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");208  if (__x->__left_ != nullptr)209    return std::__tree_max(__x->__left_);210  _NodePtr __xx = static_cast<_NodePtr>(__x);211  while (std::__tree_is_left_child(__xx))212    __xx = __xx->__parent_unsafe();213  return __xx->__parent_unsafe();214}215 216// Returns:  pointer to a node which has no children217template <class _NodePtr>218_LIBCPP_HIDE_FROM_ABI _NodePtr __tree_leaf(_NodePtr __x) _NOEXCEPT {219  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");220  while (true) {221    if (__x->__left_ != nullptr) {222      __x = __x->__left_;223      continue;224    }225    if (__x->__right_ != nullptr) {226      __x = __x->__right_;227      continue;228    }229    break;230  }231  return __x;232}233 234// Effects:  Makes __x->__right_ the subtree root with __x as its left child235//           while preserving in-order order.236template <class _NodePtr>237_LIBCPP_HIDE_FROM_ABI void __tree_left_rotate(_NodePtr __x) _NOEXCEPT {238  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");239  _LIBCPP_ASSERT_INTERNAL(__x->__right_ != nullptr, "node should have a right child");240  _NodePtr __y  = __x->__right_;241  __x->__right_ = __y->__left_;242  if (__x->__right_ != nullptr)243    __x->__right_->__set_parent(__x);244  __y->__parent_ = __x->__parent_;245  if (std::__tree_is_left_child(__x))246    __x->__parent_->__left_ = __y;247  else248    __x->__parent_unsafe()->__right_ = __y;249  __y->__left_ = __x;250  __x->__set_parent(__y);251}252 253// Effects:  Makes __x->__left_ the subtree root with __x as its right child254//           while preserving in-order order.255template <class _NodePtr>256_LIBCPP_HIDE_FROM_ABI void __tree_right_rotate(_NodePtr __x) _NOEXCEPT {257  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");258  _LIBCPP_ASSERT_INTERNAL(__x->__left_ != nullptr, "node should have a left child");259  _NodePtr __y = __x->__left_;260  __x->__left_ = __y->__right_;261  if (__x->__left_ != nullptr)262    __x->__left_->__set_parent(__x);263  __y->__parent_ = __x->__parent_;264  if (std::__tree_is_left_child(__x))265    __x->__parent_->__left_ = __y;266  else267    __x->__parent_unsafe()->__right_ = __y;268  __y->__right_ = __x;269  __x->__set_parent(__y);270}271 272// Effects:  Rebalances __root after attaching __x to a leaf.273// Precondition:  __x has no children.274//                __x == __root or == a direct or indirect child of __root.275//                If __x were to be unlinked from __root (setting __root to276//                  nullptr if __root == __x), __tree_invariant(__root) == true.277// Postcondition: __tree_invariant(end_node->__left_) == true.  end_node->__left_278//                may be different than the value passed in as __root.279template <class _NodePtr>280_LIBCPP_HIDE_FROM_ABI void __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT {281  _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root of the tree shouldn't be null");282  _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Can't attach null node to a leaf");283  __x->__is_black_ = __x == __root;284  while (__x != __root && !__x->__parent_unsafe()->__is_black_) {285    // __x->__parent_ != __root because __x->__parent_->__is_black == false286    if (std::__tree_is_left_child(__x->__parent_unsafe())) {287      _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;288      if (__y != nullptr && !__y->__is_black_) {289        __x              = __x->__parent_unsafe();290        __x->__is_black_ = true;291        __x              = __x->__parent_unsafe();292        __x->__is_black_ = __x == __root;293        __y->__is_black_ = true;294      } else {295        if (!std::__tree_is_left_child(__x)) {296          __x = __x->__parent_unsafe();297          std::__tree_left_rotate(__x);298        }299        __x              = __x->__parent_unsafe();300        __x->__is_black_ = true;301        __x              = __x->__parent_unsafe();302        __x->__is_black_ = false;303        std::__tree_right_rotate(__x);304        break;305      }306    } else {307      _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;308      if (__y != nullptr && !__y->__is_black_) {309        __x              = __x->__parent_unsafe();310        __x->__is_black_ = true;311        __x              = __x->__parent_unsafe();312        __x->__is_black_ = __x == __root;313        __y->__is_black_ = true;314      } else {315        if (std::__tree_is_left_child(__x)) {316          __x = __x->__parent_unsafe();317          std::__tree_right_rotate(__x);318        }319        __x              = __x->__parent_unsafe();320        __x->__is_black_ = true;321        __x              = __x->__parent_unsafe();322        __x->__is_black_ = false;323        std::__tree_left_rotate(__x);324        break;325      }326    }327  }328}329 330// Precondition:  __z == __root or == a direct or indirect child of __root.331// Effects:  unlinks __z from the tree rooted at __root, rebalancing as needed.332// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_333//                nor any of its children refer to __z.  end_node->__left_334//                may be different than the value passed in as __root.335template <class _NodePtr>336_LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT {337  _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root node should not be null");338  _LIBCPP_ASSERT_INTERNAL(__z != nullptr, "The node to remove should not be null");339  _LIBCPP_ASSERT_INTERNAL(std::__tree_invariant(__root), "The tree invariants should hold");340  // __z will be removed from the tree.  Client still needs to destruct/deallocate it341  // __y is either __z, or if __z has two children, __tree_next(__z).342  // __y will have at most one child.343  // __y will be the initial hole in the tree (make the hole at a leaf)344  _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? __z : std::__tree_next(__z);345  // __x is __y's possibly null single child346  _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;347  // __w is __x's possibly null uncle (will become __x's sibling)348  _NodePtr __w = nullptr;349  // link __x to __y's parent, and find __w350  if (__x != nullptr)351    __x->__parent_ = __y->__parent_;352  if (std::__tree_is_left_child(__y)) {353    __y->__parent_->__left_ = __x;354    if (__y != __root)355      __w = __y->__parent_unsafe()->__right_;356    else357      __root = __x; // __w == nullptr358  } else {359    __y->__parent_unsafe()->__right_ = __x;360    // __y can't be root if it is a right child361    __w = __y->__parent_->__left_;362  }363  bool __removed_black = __y->__is_black_;364  // If we didn't remove __z, do so now by splicing in __y for __z,365  //    but copy __z's color.  This does not impact __x or __w.366  if (__y != __z) {367    // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr368    __y->__parent_ = __z->__parent_;369    if (std::__tree_is_left_child(__z))370      __y->__parent_->__left_ = __y;371    else372      __y->__parent_unsafe()->__right_ = __y;373    __y->__left_ = __z->__left_;374    __y->__left_->__set_parent(__y);375    __y->__right_ = __z->__right_;376    if (__y->__right_ != nullptr)377      __y->__right_->__set_parent(__y);378    __y->__is_black_ = __z->__is_black_;379    if (__root == __z)380      __root = __y;381  }382  // There is no need to rebalance if we removed a red, or if we removed383  //     the last node.384  if (__removed_black && __root != nullptr) {385    // Rebalance:386    // __x has an implicit black color (transferred from the removed __y)387    //    associated with it, no matter what its color is.388    // If __x is __root (in which case it can't be null), it is supposed389    //    to be black anyway, and if it is doubly black, then the double390    //    can just be ignored.391    // If __x is red (in which case it can't be null), then it can absorb392    //    the implicit black just by setting its color to black.393    // Since __y was black and only had one child (which __x points to), __x394    //   is either red with no children, else null, otherwise __y would have395    //   different black heights under left and right pointers.396    // if (__x == __root || __x != nullptr && !__x->__is_black_)397    if (__x != nullptr)398      __x->__is_black_ = true;399    else {400      //  Else __x isn't root, and is "doubly black", even though it may401      //     be null.  __w can not be null here, else the parent would402      //     see a black height >= 2 on the __x side and a black height403      //     of 1 on the __w side (__w must be a non-null black or a red404      //     with a non-null black child).405      while (true) {406        if (!std::__tree_is_left_child(__w)) // if x is left child407        {408          if (!__w->__is_black_) {409            __w->__is_black_                    = true;410            __w->__parent_unsafe()->__is_black_ = false;411            std::__tree_left_rotate(__w->__parent_unsafe());412            // __x is still valid413            // reset __root only if necessary414            if (__root == __w->__left_)415              __root = __w;416            // reset sibling, and it still can't be null417            __w = __w->__left_->__right_;418          }419          // __w->__is_black_ is now true, __w may have null children420          if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&421              (__w->__right_ == nullptr || __w->__right_->__is_black_)) {422            __w->__is_black_ = false;423            __x              = __w->__parent_unsafe();424            // __x can no longer be null425            if (__x == __root || !__x->__is_black_) {426              __x->__is_black_ = true;427              break;428            }429            // reset sibling, and it still can't be null430            __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_;431            // continue;432          } else // __w has a red child433          {434            if (__w->__right_ == nullptr || __w->__right_->__is_black_) {435              // __w left child is non-null and red436              __w->__left_->__is_black_ = true;437              __w->__is_black_          = false;438              std::__tree_right_rotate(__w);439              // __w is known not to be root, so root hasn't changed440              // reset sibling, and it still can't be null441              __w = __w->__parent_unsafe();442            }443            // __w has a right red child, left child may be null444            __w->__is_black_                    = __w->__parent_unsafe()->__is_black_;445            __w->__parent_unsafe()->__is_black_ = true;446            __w->__right_->__is_black_          = true;447            std::__tree_left_rotate(__w->__parent_unsafe());448            break;449          }450        } else {451          if (!__w->__is_black_) {452            __w->__is_black_                    = true;453            __w->__parent_unsafe()->__is_black_ = false;454            std::__tree_right_rotate(__w->__parent_unsafe());455            // __x is still valid456            // reset __root only if necessary457            if (__root == __w->__right_)458              __root = __w;459            // reset sibling, and it still can't be null460            __w = __w->__right_->__left_;461          }462          // __w->__is_black_ is now true, __w may have null children463          if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&464              (__w->__right_ == nullptr || __w->__right_->__is_black_)) {465            __w->__is_black_ = false;466            __x              = __w->__parent_unsafe();467            // __x can no longer be null468            if (!__x->__is_black_ || __x == __root) {469              __x->__is_black_ = true;470              break;471            }472            // reset sibling, and it still can't be null473            __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_;474            // continue;475          } else // __w has a red child476          {477            if (__w->__left_ == nullptr || __w->__left_->__is_black_) {478              // __w right child is non-null and red479              __w->__right_->__is_black_ = true;480              __w->__is_black_           = false;481              std::__tree_left_rotate(__w);482              // __w is known not to be root, so root hasn't changed483              // reset sibling, and it still can't be null484              __w = __w->__parent_unsafe();485            }486            // __w has a left red child, right child may be null487            __w->__is_black_                    = __w->__parent_unsafe()->__is_black_;488            __w->__parent_unsafe()->__is_black_ = true;489            __w->__left_->__is_black_           = true;490            std::__tree_right_rotate(__w->__parent_unsafe());491            break;492          }493        }494      }495    }496  }497}498 499// node traits500 501template <class _Tp>502struct __is_tree_value_type_imp : false_type {};503 504template <class _Key, class _Value>505struct __is_tree_value_type_imp<__value_type<_Key, _Value> > : true_type {};506 507template <class... _Args>508struct __is_tree_value_type : false_type {};509 510template <class _One>511struct __is_tree_value_type<_One> : __is_tree_value_type_imp<__remove_cvref_t<_One> > {};512 513template <class _Tp>514struct __tree_key_value_types {515  typedef _Tp key_type;516  typedef _Tp __node_value_type;517  typedef _Tp __container_value_type;518  static const bool __is_map = false;519 520  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; }521  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; }522  _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { return std::addressof(__n); }523  _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { return std::move(__v); }524};525 526template <class _Key, class _Tp>527struct __tree_key_value_types<__value_type<_Key, _Tp> > {528  typedef _Key key_type;529  typedef _Tp mapped_type;530  typedef __value_type<_Key, _Tp> __node_value_type;531  typedef pair<const _Key, _Tp> __container_value_type;532  typedef __container_value_type __map_value_type;533  static const bool __is_map = true;534 535  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__node_value_type const& __t) {536    return __t.__get_value().first;537  }538 539  template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>540  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Up& __t) {541    return __t.first;542  }543 544  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __t) {545    return __t.__get_value();546  }547 548  template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>549  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {550    return __t;551  }552 553  _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) {554    return std::addressof(__n.__get_value());555  }556 557  _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); }558};559 560template <class _VoidPtr>561struct __tree_node_base_types {562  typedef _VoidPtr __void_pointer;563 564  typedef __tree_node_base<__void_pointer> __node_base_type;565  typedef __rebind_pointer_t<_VoidPtr, __node_base_type> __node_base_pointer;566 567  typedef __tree_end_node<__node_base_pointer> __end_node_type;568  typedef __rebind_pointer_t<_VoidPtr, __end_node_type> __end_node_pointer;569#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)570  typedef __end_node_pointer __parent_pointer;571#else572  typedef __conditional_t< is_pointer<__end_node_pointer>::value, __end_node_pointer, __node_base_pointer>573      __parent_pointer;574#endif575 576private:577  static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,578                "_VoidPtr does not point to unqualified void type");579};580 581template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>, bool = _KVTypes::__is_map>582struct __tree_map_pointer_types {};583 584template <class _Tp, class _AllocPtr, class _KVTypes>585struct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {586  typedef typename _KVTypes::__map_value_type _Mv;587  typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer;588  typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer;589};590 591template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>592struct __tree_node_types;593 594template <class _NodePtr, class _Tp, class _VoidPtr>595struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> >596    : public __tree_node_base_types<_VoidPtr>, __tree_key_value_types<_Tp>, __tree_map_pointer_types<_Tp, _VoidPtr> {597  typedef __tree_node_base_types<_VoidPtr> __base;598  typedef __tree_key_value_types<_Tp> __key_base;599  typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base;600 601public:602  typedef typename pointer_traits<_NodePtr>::element_type __node_type;603  typedef _NodePtr __node_pointer;604 605  typedef _Tp __node_value_type;606  typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer;607  typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer;608#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)609  typedef typename __base::__end_node_pointer __iter_pointer;610#else611  typedef __conditional_t< is_pointer<__node_pointer>::value, typename __base::__end_node_pointer, __node_pointer>612      __iter_pointer;613#endif614 615private:616  static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");617  static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,618                "_VoidPtr does not rebind to _NodePtr.");619};620 621template <class _ValueTp, class _VoidPtr>622struct __make_tree_node_types {623  typedef __rebind_pointer_t<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> > _NodePtr;624  typedef __tree_node_types<_NodePtr> type;625};626 627// node628 629template <class _Pointer>630class __tree_end_node {631public:632  typedef _Pointer pointer;633  pointer __left_;634 635  _LIBCPP_HIDE_FROM_ABI __tree_end_node() _NOEXCEPT : __left_() {}636};637 638template <class _VoidPtr>639class _LIBCPP_STANDALONE_DEBUG __tree_node_base : public __tree_node_base_types<_VoidPtr>::__end_node_type {640  typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes;641 642public:643  typedef typename _NodeBaseTypes::__node_base_pointer pointer;644  typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer;645 646  pointer __right_;647  __parent_pointer __parent_;648  bool __is_black_;649 650  _LIBCPP_HIDE_FROM_ABI pointer __parent_unsafe() const { return static_cast<pointer>(__parent_); }651 652  _LIBCPP_HIDE_FROM_ABI void __set_parent(pointer __p) { __parent_ = static_cast<__parent_pointer>(__p); }653 654  ~__tree_node_base()                                  = delete;655  __tree_node_base(__tree_node_base const&)            = delete;656  __tree_node_base& operator=(__tree_node_base const&) = delete;657};658 659template <class _Tp, class _VoidPtr>660class _LIBCPP_STANDALONE_DEBUG __tree_node : public __tree_node_base<_VoidPtr> {661public:662  typedef _Tp __node_value_type;663 664  __node_value_type __value_;665 666  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }667 668  ~__tree_node()                             = delete;669  __tree_node(__tree_node const&)            = delete;670  __tree_node& operator=(__tree_node const&) = delete;671};672 673template <class _Allocator>674class __tree_node_destructor {675  typedef _Allocator allocator_type;676  typedef allocator_traits<allocator_type> __alloc_traits;677 678public:679  typedef typename __alloc_traits::pointer pointer;680 681private:682  typedef __tree_node_types<pointer> _NodeTypes;683  allocator_type& __na_;684 685public:686  bool __value_constructed;687 688  _LIBCPP_HIDE_FROM_ABI __tree_node_destructor(const __tree_node_destructor&) = default;689  __tree_node_destructor& operator=(const __tree_node_destructor&)            = delete;690 691  _LIBCPP_HIDE_FROM_ABI explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT692      : __na_(__na),693        __value_constructed(__val) {}694 695  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {696    if (__value_constructed)697      __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));698    if (__p)699      __alloc_traits::deallocate(__na_, __p, 1);700  }701 702  template <class>703  friend class __map_node_destructor;704};705 706template <class _Tp, class _NodePtr, class _DiffType>707class _LIBCPP_TEMPLATE_VIS __tree_iterator {708  typedef __tree_node_types<_NodePtr> _NodeTypes;709  typedef _NodePtr __node_pointer;710  typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;711  typedef typename _NodeTypes::__end_node_pointer __end_node_pointer;712  typedef typename _NodeTypes::__iter_pointer __iter_pointer;713  typedef pointer_traits<__node_pointer> __pointer_traits;714 715  __iter_pointer __ptr_;716 717public:718  typedef bidirectional_iterator_tag iterator_category;719  typedef _Tp value_type;720  typedef _DiffType difference_type;721  typedef value_type& reference;722  typedef typename _NodeTypes::__node_value_type_pointer pointer;723 724  _LIBCPP_HIDE_FROM_ABI __tree_iterator() _NOEXCEPT {}725 726  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; }727  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); }728 729  _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator++() {730    __ptr_ = static_cast<__iter_pointer>(731        std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));732    return *this;733  }734  _LIBCPP_HIDE_FROM_ABI __tree_iterator operator++(int) {735    __tree_iterator __t(*this);736    ++(*this);737    return __t;738  }739 740  _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator--() {741    __ptr_ = static_cast<__iter_pointer>(742        std::__tree_prev_iter<__node_base_pointer>(static_cast<__end_node_pointer>(__ptr_)));743    return *this;744  }745  _LIBCPP_HIDE_FROM_ABI __tree_iterator operator--(int) {746    __tree_iterator __t(*this);747    --(*this);748    return __t;749  }750 751  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) {752    return __x.__ptr_ == __y.__ptr_;753  }754  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) {755    return !(__x == __y);756  }757 758private:759  _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}760  _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}761  _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }762  template <class, class, class>763  friend class __tree;764  template <class, class, class>765  friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;766  template <class>767  friend class _LIBCPP_TEMPLATE_VIS __map_iterator;768  template <class, class, class, class>769  friend class _LIBCPP_TEMPLATE_VIS map;770  template <class, class, class, class>771  friend class _LIBCPP_TEMPLATE_VIS multimap;772  template <class, class, class>773  friend class _LIBCPP_TEMPLATE_VIS set;774  template <class, class, class>775  friend class _LIBCPP_TEMPLATE_VIS multiset;776};777 778template <class _Tp, class _NodePtr, class _DiffType>779class _LIBCPP_TEMPLATE_VIS __tree_const_iterator {780  typedef __tree_node_types<_NodePtr> _NodeTypes;781  typedef typename _NodeTypes::__node_pointer __node_pointer;782  typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;783  typedef typename _NodeTypes::__end_node_pointer __end_node_pointer;784  typedef typename _NodeTypes::__iter_pointer __iter_pointer;785  typedef pointer_traits<__node_pointer> __pointer_traits;786 787  __iter_pointer __ptr_;788 789public:790  typedef bidirectional_iterator_tag iterator_category;791  typedef _Tp value_type;792  typedef _DiffType difference_type;793  typedef const value_type& reference;794  typedef typename _NodeTypes::__const_node_value_type_pointer pointer;795 796  _LIBCPP_HIDE_FROM_ABI __tree_const_iterator() _NOEXCEPT {}797 798private:799  typedef __tree_iterator<value_type, __node_pointer, difference_type> __non_const_iterator;800 801public:802  _LIBCPP_HIDE_FROM_ABI __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT : __ptr_(__p.__ptr_) {}803 804  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; }805  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); }806 807  _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator++() {808    __ptr_ = static_cast<__iter_pointer>(809        std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));810    return *this;811  }812 813  _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator++(int) {814    __tree_const_iterator __t(*this);815    ++(*this);816    return __t;817  }818 819  _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator--() {820    __ptr_ = static_cast<__iter_pointer>(821        std::__tree_prev_iter<__node_base_pointer>(static_cast<__end_node_pointer>(__ptr_)));822    return *this;823  }824 825  _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator--(int) {826    __tree_const_iterator __t(*this);827    --(*this);828    return __t;829  }830 831  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) {832    return __x.__ptr_ == __y.__ptr_;833  }834  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) {835    return !(__x == __y);836  }837 838private:839  _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}840  _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}841  _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }842 843  template <class, class, class>844  friend class __tree;845  template <class, class, class, class>846  friend class _LIBCPP_TEMPLATE_VIS map;847  template <class, class, class, class>848  friend class _LIBCPP_TEMPLATE_VIS multimap;849  template <class, class, class>850  friend class _LIBCPP_TEMPLATE_VIS set;851  template <class, class, class>852  friend class _LIBCPP_TEMPLATE_VIS multiset;853  template <class>854  friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;855};856 857template <class _Tp, class _Compare>858int __diagnose_non_const_comparator();859 860template <class _Tp, class _Compare, class _Allocator>861class __tree {862public:863  typedef _Tp value_type;864  typedef _Compare value_compare;865  typedef _Allocator allocator_type;866 867private:868  typedef allocator_traits<allocator_type> __alloc_traits;869  typedef typename __make_tree_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;870  typedef typename _NodeTypes::key_type key_type;871 872public:873  typedef typename _NodeTypes::__node_value_type __node_value_type;874  typedef typename _NodeTypes::__container_value_type __container_value_type;875 876  typedef typename __alloc_traits::pointer pointer;877  typedef typename __alloc_traits::const_pointer const_pointer;878  typedef typename __alloc_traits::size_type size_type;879  typedef typename __alloc_traits::difference_type difference_type;880 881public:882  typedef typename _NodeTypes::__void_pointer __void_pointer;883 884  typedef typename _NodeTypes::__node_type __node;885  typedef typename _NodeTypes::__node_pointer __node_pointer;886 887  typedef typename _NodeTypes::__node_base_type __node_base;888  typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;889 890  typedef typename _NodeTypes::__end_node_type __end_node_t;891  typedef typename _NodeTypes::__end_node_pointer __end_node_ptr;892 893  typedef typename _NodeTypes::__parent_pointer __parent_pointer;894  typedef typename _NodeTypes::__iter_pointer __iter_pointer;895 896  typedef __rebind_alloc<__alloc_traits, __node> __node_allocator;897  typedef allocator_traits<__node_allocator> __node_traits;898 899private:900  // check for sane allocator pointer rebinding semantics. Rebinding the901  // allocator for a new pointer type should be exactly the same as rebinding902  // the pointer using 'pointer_traits'.903  static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,904                "Allocator does not rebind pointers in a sane manner.");905  typedef __rebind_alloc<__node_traits, __node_base> __node_base_allocator;906  typedef allocator_traits<__node_base_allocator> __node_base_traits;907  static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,908                "Allocator does not rebind pointers in a sane manner.");909 910private:911  __iter_pointer __begin_node_;912  __compressed_pair<__end_node_t, __node_allocator> __pair1_;913  __compressed_pair<size_type, value_compare> __pair3_;914 915public:916  _LIBCPP_HIDE_FROM_ABI __iter_pointer __end_node() _NOEXCEPT {917    return static_cast<__iter_pointer>(pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()));918  }919  _LIBCPP_HIDE_FROM_ABI __iter_pointer __end_node() const _NOEXCEPT {920    return static_cast<__iter_pointer>(921        pointer_traits<__end_node_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first())));922  }923  _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __pair1_.second(); }924 925private:926  _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __pair1_.second(); }927  _LIBCPP_HIDE_FROM_ABI __iter_pointer& __begin_node() _NOEXCEPT { return __begin_node_; }928  _LIBCPP_HIDE_FROM_ABI const __iter_pointer& __begin_node() const _NOEXCEPT { return __begin_node_; }929 930public:931  _LIBCPP_HIDE_FROM_ABI allocator_type __alloc() const _NOEXCEPT { return allocator_type(__node_alloc()); }932 933private:934  _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __pair3_.first(); }935 936public:937  _LIBCPP_HIDE_FROM_ABI const size_type& size() const _NOEXCEPT { return __pair3_.first(); }938  _LIBCPP_HIDE_FROM_ABI value_compare& value_comp() _NOEXCEPT { return __pair3_.second(); }939  _LIBCPP_HIDE_FROM_ABI const value_compare& value_comp() const _NOEXCEPT { return __pair3_.second(); }940 941public:942  _LIBCPP_HIDE_FROM_ABI __node_pointer __root() const _NOEXCEPT {943    return static_cast<__node_pointer>(__end_node()->__left_);944  }945 946  _LIBCPP_HIDE_FROM_ABI __node_base_pointer* __root_ptr() const _NOEXCEPT {947    return std::addressof(__end_node()->__left_);948  }949 950  typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator;951  typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;952 953  _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp);954  _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a);955  _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a);956  _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t);957  _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t);958  template <class _ForwardIterator>959  _LIBCPP_HIDE_FROM_ABI void __assign_unique(_ForwardIterator __first, _ForwardIterator __last);960  template <class _InputIterator>961  _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);962  _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t);963  _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a);964  _LIBCPP_HIDE_FROM_ABI __tree& operator=(__tree&& __t);965  _LIBCPP_HIDE_FROM_ABI ~__tree();966 967  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__begin_node()); }968  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__begin_node()); }969  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_node()); }970  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_node()); }971 972  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {973    return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());974  }975 976  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;977 978  _LIBCPP_HIDE_FROM_ABI void swap(__tree& __t);979 980  template <class _Key, class... _Args>981  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args);982  template <class _Key, class... _Args>983  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);984 985  template <class... _Args>986  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);987 988  template <class... _Args>989  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);990 991  template <class... _Args>992  _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);993 994  template <class... _Args>995  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);996 997  template <class _Pp>998  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {999    return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());1000  }1001 1002  template <class _First,1003            class _Second,1004            __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>1005  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {1006    return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));1007  }1008 1009  template <class... _Args>1010  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {1011    return __emplace_unique_impl(std::forward<_Args>(__args)...);1012  }1013 1014  template <class _Pp>1015  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {1016    return __emplace_unique_impl(std::forward<_Pp>(__x));1017  }1018 1019  template <class _Pp>1020  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {1021    return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));1022  }1023 1024  template <class _Pp>1025  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {1026    return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));1027  }1028 1029  template <class _Pp>1030  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {1031    return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());1032  }1033 1034  template <class _First,1035            class _Second,1036            __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>1037  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {1038    return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first;1039  }1040 1041  template <class... _Args>1042  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {1043    return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...);1044  }1045 1046  template <class _Pp>1047  _LIBCPP_HIDE_FROM_ABI iterator1048  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {1049    return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x));1050  }1051 1052  template <class _Pp>1053  _LIBCPP_HIDE_FROM_ABI iterator1054  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {1055    return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first;1056  }1057 1058  template <class _Pp>1059  _LIBCPP_HIDE_FROM_ABI iterator1060  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {1061    return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first;1062  }1063 1064  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __v) {1065    return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v);1066  }1067 1068  _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, const __container_value_type& __v) {1069    return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first;1070  }1071 1072  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __v) {1073    return __emplace_unique_key_args(_NodeTypes::__get_key(__v), std::move(__v));1074  }1075 1076  _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, __container_value_type&& __v) {1077    return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), std::move(__v)).first;1078  }1079 1080  template <class _Vp, __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value, int> = 0>1081  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Vp&& __v) {1082    return __emplace_unique(std::forward<_Vp>(__v));1083  }1084 1085  template <class _Vp, __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value, int> = 0>1086  _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, _Vp&& __v) {1087    return __emplace_hint_unique(__p, std::forward<_Vp>(__v));1088  }1089 1090  _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(__container_value_type&& __v) {1091    return __emplace_multi(std::move(__v));1092  }1093 1094  _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, __container_value_type&& __v) {1095    return __emplace_hint_multi(__p, std::move(__v));1096  }1097 1098  template <class _Vp>1099  _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Vp&& __v) {1100    return __emplace_multi(std::forward<_Vp>(__v));1101  }1102 1103  template <class _Vp>1104  _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Vp&& __v) {1105    return __emplace_hint_multi(__p, std::forward<_Vp>(__v));1106  }1107 1108  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool>1109  __node_assign_unique(const __container_value_type& __v, __node_pointer __dest);1110 1111  _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);1112  _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);1113 1114  _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT;1115 1116  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);1117  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);1118  template <class _Key>1119  _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);1120  template <class _Key>1121  _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);1122 1123  _LIBCPP_HIDE_FROM_ABI void1124  __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT;1125 1126  template <class _Key>1127  _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __v);1128  template <class _Key>1129  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __v) const;1130 1131  template <class _Key>1132  _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;1133  template <class _Key>1134  _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;1135 1136  template <class _Key>1137  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Key& __v) {1138    return __lower_bound(__v, __root(), __end_node());1139  }1140  template <class _Key>1141  _LIBCPP_HIDE_FROM_ABI iterator __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result);1142  template <class _Key>1143  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Key& __v) const {1144    return __lower_bound(__v, __root(), __end_node());1145  }1146  template <class _Key>1147  _LIBCPP_HIDE_FROM_ABI const_iterator1148  __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const;1149  template <class _Key>1150  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Key& __v) {1151    return __upper_bound(__v, __root(), __end_node());1152  }1153  template <class _Key>1154  _LIBCPP_HIDE_FROM_ABI iterator __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result);1155  template <class _Key>1156  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Key& __v) const {1157    return __upper_bound(__v, __root(), __end_node());1158  }1159  template <class _Key>1160  _LIBCPP_HIDE_FROM_ABI const_iterator1161  __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const;1162  template <class _Key>1163  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);1164  template <class _Key>1165  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;1166 1167  template <class _Key>1168  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);1169  template <class _Key>1170  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;1171 1172  typedef __tree_node_destructor<__node_allocator> _Dp;1173  typedef unique_ptr<__node, _Dp> __node_holder;1174 1175  _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;1176 1177private:1178  _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_low(__parent_pointer& __parent, const key_type& __v);1179  _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_high(__parent_pointer& __parent, const key_type& __v);1180  _LIBCPP_HIDE_FROM_ABI __node_base_pointer&1181  __find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v);1182  // FIXME: Make this function const qualified. Unfortunately doing so1183  // breaks existing code which uses non-const callable comparators.1184  template <class _Key>1185  _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v);1186  template <class _Key>1187  _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v) const {1188    return const_cast<__tree*>(this)->__find_equal(__parent, __v);1189  }1190  template <class _Key>1191  _LIBCPP_HIDE_FROM_ABI __node_base_pointer&1192  __find_equal(const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v);1193 1194  template <class... _Args>1195  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);1196 1197  // TODO: Make this _LIBCPP_HIDE_FROM_ABI1198  _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT;1199 1200  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t) {1201    __copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());1202  }1203 1204  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t, true_type) {1205    if (__node_alloc() != __t.__node_alloc())1206      clear();1207    __node_alloc() = __t.__node_alloc();1208  }1209  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree&, false_type) {}1210 1211  _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type);1212  _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type);1213 1214  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t) {1215    __move_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());1216  }1217 1218  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t, true_type) {1219    __node_alloc() = std::move(__t.__node_alloc());1220  }1221  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}1222 1223  struct _DetachedTreeCache {1224    _LIBCPP_HIDE_FROM_ABI explicit _DetachedTreeCache(__tree* __t) _NOEXCEPT1225        : __t_(__t),1226          __cache_root_(__detach_from_tree(__t)) {1227      __advance();1228    }1229 1230    _LIBCPP_HIDE_FROM_ABI __node_pointer __get() const _NOEXCEPT { return __cache_elem_; }1231 1232    _LIBCPP_HIDE_FROM_ABI void __advance() _NOEXCEPT {1233      __cache_elem_ = __cache_root_;1234      if (__cache_root_) {1235        __cache_root_ = __detach_next(__cache_root_);1236      }1237    }1238 1239    _LIBCPP_HIDE_FROM_ABI ~_DetachedTreeCache() {1240      __t_->destroy(__cache_elem_);1241      if (__cache_root_) {1242        while (__cache_root_->__parent_ != nullptr)1243          __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_);1244        __t_->destroy(__cache_root_);1245      }1246    }1247 1248    _DetachedTreeCache(_DetachedTreeCache const&)            = delete;1249    _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete;1250 1251  private:1252    _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_from_tree(__tree* __t) _NOEXCEPT;1253    _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_next(__node_pointer) _NOEXCEPT;1254 1255    __tree* __t_;1256    __node_pointer __cache_root_;1257    __node_pointer __cache_elem_;1258  };1259 1260  template <class, class, class, class>1261  friend class _LIBCPP_TEMPLATE_VIS map;1262  template <class, class, class, class>1263  friend class _LIBCPP_TEMPLATE_VIS multimap;1264};1265 1266template <class _Tp, class _Compare, class _Allocator>1267__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) : __pair3_(0, __comp) {1268  __begin_node() = __end_node();1269}1270 1271template <class _Tp, class _Compare, class _Allocator>1272__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)1273    : __begin_node_(__iter_pointer()),1274      __pair1_(__default_init_tag(), __node_allocator(__a)),1275      __pair3_(0, __default_init_tag()) {1276  __begin_node() = __end_node();1277}1278 1279template <class _Tp, class _Compare, class _Allocator>1280__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a)1281    : __begin_node_(__iter_pointer()), __pair1_(__default_init_tag(), __node_allocator(__a)), __pair3_(0, __comp) {1282  __begin_node() = __end_node();1283}1284 1285// Precondition:  size() != 01286template <class _Tp, class _Compare, class _Allocator>1287typename __tree<_Tp, _Compare, _Allocator>::__node_pointer1288__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT {1289  __node_pointer __cache                = static_cast<__node_pointer>(__t->__begin_node());1290  __t->__begin_node()                   = __t->__end_node();1291  __t->__end_node()->__left_->__parent_ = nullptr;1292  __t->__end_node()->__left_            = nullptr;1293  __t->size()                           = 0;1294  // __cache->__left_ == nullptr1295  if (__cache->__right_ != nullptr)1296    __cache = static_cast<__node_pointer>(__cache->__right_);1297  // __cache->__left_ == nullptr1298  // __cache->__right_ == nullptr1299  return __cache;1300}1301 1302// Precondition:  __cache != nullptr1303//    __cache->left_ == nullptr1304//    __cache->right_ == nullptr1305//    This is no longer a red-black tree1306template <class _Tp, class _Compare, class _Allocator>1307typename __tree<_Tp, _Compare, _Allocator>::__node_pointer1308__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT {1309  if (__cache->__parent_ == nullptr)1310    return nullptr;1311  if (std::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) {1312    __cache->__parent_->__left_ = nullptr;1313    __cache                     = static_cast<__node_pointer>(__cache->__parent_);1314    if (__cache->__right_ == nullptr)1315      return __cache;1316    return static_cast<__node_pointer>(std::__tree_leaf(__cache->__right_));1317  }1318  // __cache is right child1319  __cache->__parent_unsafe()->__right_ = nullptr;1320  __cache                              = static_cast<__node_pointer>(__cache->__parent_);1321  if (__cache->__left_ == nullptr)1322    return __cache;1323  return static_cast<__node_pointer>(std::__tree_leaf(__cache->__left_));1324}1325 1326template <class _Tp, class _Compare, class _Allocator>1327__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) {1328  if (this != std::addressof(__t)) {1329    value_comp() = __t.value_comp();1330    __copy_assign_alloc(__t);1331    __assign_multi(__t.begin(), __t.end());1332  }1333  return *this;1334}1335 1336template <class _Tp, class _Compare, class _Allocator>1337template <class _ForwardIterator>1338void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) {1339  typedef iterator_traits<_ForwardIterator> _ITraits;1340  typedef typename _ITraits::value_type _ItValueType;1341  static_assert(is_same<_ItValueType, __container_value_type>::value,1342                "__assign_unique may only be called with the containers value type");1343  static_assert(1344      __has_forward_iterator_category<_ForwardIterator>::value, "__assign_unique requires a forward iterator");1345  if (size() != 0) {1346    _DetachedTreeCache __cache(this);1347    for (; __cache.__get() != nullptr && __first != __last; ++__first) {1348      if (__node_assign_unique(*__first, __cache.__get()).second)1349        __cache.__advance();1350    }1351  }1352  for (; __first != __last; ++__first)1353    __insert_unique(*__first);1354}1355 1356template <class _Tp, class _Compare, class _Allocator>1357template <class _InputIterator>1358void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) {1359  typedef iterator_traits<_InputIterator> _ITraits;1360  typedef typename _ITraits::value_type _ItValueType;1361  static_assert(1362      (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value),1363      "__assign_multi may only be called with the containers value type"1364      " or the nodes value type");1365  if (size() != 0) {1366    _DetachedTreeCache __cache(this);1367    for (; __cache.__get() && __first != __last; ++__first) {1368      __cache.__get()->__value_ = *__first;1369      __node_insert_multi(__cache.__get());1370      __cache.__advance();1371    }1372  }1373  for (; __first != __last; ++__first)1374    __insert_multi(_NodeTypes::__get_value(*__first));1375}1376 1377template <class _Tp, class _Compare, class _Allocator>1378__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)1379    : __begin_node_(__iter_pointer()),1380      __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())),1381      __pair3_(0, __t.value_comp()) {1382  __begin_node() = __end_node();1383}1384 1385template <class _Tp, class _Compare, class _Allocator>1386__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)1387    : __begin_node_(std::move(__t.__begin_node_)),1388      __pair1_(std::move(__t.__pair1_)),1389      __pair3_(std::move(__t.__pair3_)) {1390  if (size() == 0)1391    __begin_node() = __end_node();1392  else {1393    __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());1394    __t.__begin_node()               = __t.__end_node();1395    __t.__end_node()->__left_        = nullptr;1396    __t.size()                       = 0;1397  }1398}1399 1400template <class _Tp, class _Compare, class _Allocator>1401__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)1402    : __pair1_(__default_init_tag(), __node_allocator(__a)), __pair3_(0, std::move(__t.value_comp())) {1403  if (__a == __t.__alloc()) {1404    if (__t.size() == 0)1405      __begin_node() = __end_node();1406    else {1407      __begin_node()                   = __t.__begin_node();1408      __end_node()->__left_            = __t.__end_node()->__left_;1409      __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());1410      size()                           = __t.size();1411      __t.__begin_node()               = __t.__end_node();1412      __t.__end_node()->__left_        = nullptr;1413      __t.size()                       = 0;1414    }1415  } else {1416    __begin_node() = __end_node();1417  }1418}1419 1420template <class _Tp, class _Compare, class _Allocator>1421void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) {1422  destroy(static_cast<__node_pointer>(__end_node()->__left_));1423  __begin_node_    = __t.__begin_node_;1424  __pair1_.first() = __t.__pair1_.first();1425  __move_assign_alloc(__t);1426  __pair3_ = std::move(__t.__pair3_);1427  if (size() == 0)1428    __begin_node() = __end_node();1429  else {1430    __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());1431    __t.__begin_node()               = __t.__end_node();1432    __t.__end_node()->__left_        = nullptr;1433    __t.size()                       = 0;1434  }1435}1436 1437template <class _Tp, class _Compare, class _Allocator>1438void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) {1439  if (__node_alloc() == __t.__node_alloc())1440    __move_assign(__t, true_type());1441  else {1442    value_comp()       = std::move(__t.value_comp());1443    const_iterator __e = end();1444    if (size() != 0) {1445      _DetachedTreeCache __cache(this);1446      while (__cache.__get() != nullptr && __t.size() != 0) {1447        __cache.__get()->__value_ = std::move(__t.remove(__t.begin())->__value_);1448        __node_insert_multi(__cache.__get());1449        __cache.__advance();1450      }1451    }1452    while (__t.size() != 0)1453      __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_));1454  }1455}1456 1457template <class _Tp, class _Compare, class _Allocator>1458__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) {1459  __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());1460  return *this;1461}1462 1463template <class _Tp, class _Compare, class _Allocator>1464__tree<_Tp, _Compare, _Allocator>::~__tree() {1465  static_assert(is_copy_constructible<value_compare>::value, "Comparator must be copy-constructible.");1466  destroy(__root());1467}1468 1469template <class _Tp, class _Compare, class _Allocator>1470void __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT {1471  if (__nd != nullptr) {1472    destroy(static_cast<__node_pointer>(__nd->__left_));1473    destroy(static_cast<__node_pointer>(__nd->__right_));1474    __node_allocator& __na = __node_alloc();1475    __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_));1476    __node_traits::deallocate(__na, __nd, 1);1477  }1478}1479 1480template <class _Tp, class _Compare, class _Allocator>1481void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) {1482  using std::swap;1483  swap(__begin_node_, __t.__begin_node_);1484  swap(__pair1_.first(), __t.__pair1_.first());1485  std::__swap_allocator(__node_alloc(), __t.__node_alloc());1486  __pair3_.swap(__t.__pair3_);1487  if (size() == 0)1488    __begin_node() = __end_node();1489  else1490    __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());1491  if (__t.size() == 0)1492    __t.__begin_node() = __t.__end_node();1493  else1494    __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());1495}1496 1497template <class _Tp, class _Compare, class _Allocator>1498void __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT {1499  destroy(__root());1500  size()                = 0;1501  __begin_node()        = __end_node();1502  __end_node()->__left_ = nullptr;1503}1504 1505// Find lower_bound place to insert1506// Set __parent to parent of null leaf1507// Return reference to null leaf1508template <class _Tp, class _Compare, class _Allocator>1509typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&1510__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent, const key_type& __v) {1511  __node_pointer __nd = __root();1512  if (__nd != nullptr) {1513    while (true) {1514      if (value_comp()(__nd->__value_, __v)) {1515        if (__nd->__right_ != nullptr)1516          __nd = static_cast<__node_pointer>(__nd->__right_);1517        else {1518          __parent = static_cast<__parent_pointer>(__nd);1519          return __nd->__right_;1520        }1521      } else {1522        if (__nd->__left_ != nullptr)1523          __nd = static_cast<__node_pointer>(__nd->__left_);1524        else {1525          __parent = static_cast<__parent_pointer>(__nd);1526          return __parent->__left_;1527        }1528      }1529    }1530  }1531  __parent = static_cast<__parent_pointer>(__end_node());1532  return __parent->__left_;1533}1534 1535// Find upper_bound place to insert1536// Set __parent to parent of null leaf1537// Return reference to null leaf1538template <class _Tp, class _Compare, class _Allocator>1539typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&1540__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent, const key_type& __v) {1541  __node_pointer __nd = __root();1542  if (__nd != nullptr) {1543    while (true) {1544      if (value_comp()(__v, __nd->__value_)) {1545        if (__nd->__left_ != nullptr)1546          __nd = static_cast<__node_pointer>(__nd->__left_);1547        else {1548          __parent = static_cast<__parent_pointer>(__nd);1549          return __parent->__left_;1550        }1551      } else {1552        if (__nd->__right_ != nullptr)1553          __nd = static_cast<__node_pointer>(__nd->__right_);1554        else {1555          __parent = static_cast<__parent_pointer>(__nd);1556          return __nd->__right_;1557        }1558      }1559    }1560  }1561  __parent = static_cast<__parent_pointer>(__end_node());1562  return __parent->__left_;1563}1564 1565// Find leaf place to insert closest to __hint1566// First check prior to __hint.1567// Next check after __hint.1568// Next do O(log N) search.1569// Set __parent to parent of null leaf1570// Return reference to null leaf1571template <class _Tp, class _Compare, class _Allocator>1572typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&1573__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v) {1574  if (__hint == end() || !value_comp()(*__hint, __v)) // check before1575  {1576    // __v <= *__hint1577    const_iterator __prior = __hint;1578    if (__prior == begin() || !value_comp()(__v, *--__prior)) {1579      // *prev(__hint) <= __v <= *__hint1580      if (__hint.__ptr_->__left_ == nullptr) {1581        __parent = static_cast<__parent_pointer>(__hint.__ptr_);1582        return __parent->__left_;1583      } else {1584        __parent = static_cast<__parent_pointer>(__prior.__ptr_);1585        return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;1586      }1587    }1588    // __v < *prev(__hint)1589    return __find_leaf_high(__parent, __v);1590  }1591  // else __v > *__hint1592  return __find_leaf_low(__parent, __v);1593}1594 1595// Find place to insert if __v doesn't exist1596// Set __parent to parent of null leaf1597// Return reference to null leaf1598// If __v exists, set parent to node of __v and return reference to node of __v1599template <class _Tp, class _Compare, class _Allocator>1600template <class _Key>1601typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&1602__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent, const _Key& __v) {1603  __node_pointer __nd           = __root();1604  __node_base_pointer* __nd_ptr = __root_ptr();1605  if (__nd != nullptr) {1606    while (true) {1607      if (value_comp()(__v, __nd->__value_)) {1608        if (__nd->__left_ != nullptr) {1609          __nd_ptr = std::addressof(__nd->__left_);1610          __nd     = static_cast<__node_pointer>(__nd->__left_);1611        } else {1612          __parent = static_cast<__parent_pointer>(__nd);1613          return __parent->__left_;1614        }1615      } else if (value_comp()(__nd->__value_, __v)) {1616        if (__nd->__right_ != nullptr) {1617          __nd_ptr = std::addressof(__nd->__right_);1618          __nd     = static_cast<__node_pointer>(__nd->__right_);1619        } else {1620          __parent = static_cast<__parent_pointer>(__nd);1621          return __nd->__right_;1622        }1623      } else {1624        __parent = static_cast<__parent_pointer>(__nd);1625        return *__nd_ptr;1626      }1627    }1628  }1629  __parent = static_cast<__parent_pointer>(__end_node());1630  return __parent->__left_;1631}1632 1633// Find place to insert if __v doesn't exist1634// First check prior to __hint.1635// Next check after __hint.1636// Next do O(log N) search.1637// Set __parent to parent of null leaf1638// Return reference to null leaf1639// If __v exists, set parent to node of __v and return reference to node of __v1640template <class _Tp, class _Compare, class _Allocator>1641template <class _Key>1642typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_equal(1643    const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v) {1644  if (__hint == end() || value_comp()(__v, *__hint)) // check before1645  {1646    // __v < *__hint1647    const_iterator __prior = __hint;1648    if (__prior == begin() || value_comp()(*--__prior, __v)) {1649      // *prev(__hint) < __v < *__hint1650      if (__hint.__ptr_->__left_ == nullptr) {1651        __parent = static_cast<__parent_pointer>(__hint.__ptr_);1652        return __parent->__left_;1653      } else {1654        __parent = static_cast<__parent_pointer>(__prior.__ptr_);1655        return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;1656      }1657    }1658    // __v <= *prev(__hint)1659    return __find_equal(__parent, __v);1660  } else if (value_comp()(*__hint, __v)) // check after1661  {1662    // *__hint < __v1663    const_iterator __next = std::next(__hint);1664    if (__next == end() || value_comp()(__v, *__next)) {1665      // *__hint < __v < *std::next(__hint)1666      if (__hint.__get_np()->__right_ == nullptr) {1667        __parent = static_cast<__parent_pointer>(__hint.__ptr_);1668        return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;1669      } else {1670        __parent = static_cast<__parent_pointer>(__next.__ptr_);1671        return __parent->__left_;1672      }1673    }1674    // *next(__hint) <= __v1675    return __find_equal(__parent, __v);1676  }1677  // else __v == *__hint1678  __parent = static_cast<__parent_pointer>(__hint.__ptr_);1679  __dummy  = static_cast<__node_base_pointer>(__hint.__ptr_);1680  return __dummy;1681}1682 1683template <class _Tp, class _Compare, class _Allocator>1684void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(1685    __parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT {1686  __new_node->__left_   = nullptr;1687  __new_node->__right_  = nullptr;1688  __new_node->__parent_ = __parent;1689  // __new_node->__is_black_ is initialized in __tree_balance_after_insert1690  __child = __new_node;1691  if (__begin_node()->__left_ != nullptr)1692    __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);1693  std::__tree_balance_after_insert(__end_node()->__left_, __child);1694  ++size();1695}1696 1697template <class _Tp, class _Compare, class _Allocator>1698template <class _Key, class... _Args>1699pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>1700__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {1701  __parent_pointer __parent;1702  __node_base_pointer& __child = __find_equal(__parent, __k);1703  __node_pointer __r           = static_cast<__node_pointer>(__child);1704  bool __inserted              = false;1705  if (__child == nullptr) {1706    __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1707    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1708    __r        = __h.release();1709    __inserted = true;1710  }1711  return pair<iterator, bool>(iterator(__r), __inserted);1712}1713 1714template <class _Tp, class _Compare, class _Allocator>1715template <class _Key, class... _Args>1716pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>1717__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(1718    const_iterator __p, _Key const& __k, _Args&&... __args) {1719  __parent_pointer __parent;1720  __node_base_pointer __dummy;1721  __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);1722  __node_pointer __r           = static_cast<__node_pointer>(__child);1723  bool __inserted              = false;1724  if (__child == nullptr) {1725    __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1726    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1727    __r        = __h.release();1728    __inserted = true;1729  }1730  return pair<iterator, bool>(iterator(__r), __inserted);1731}1732 1733template <class _Tp, class _Compare, class _Allocator>1734template <class... _Args>1735typename __tree<_Tp, _Compare, _Allocator>::__node_holder1736__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {1737  static_assert(!__is_tree_value_type<_Args...>::value, "Cannot construct from __value_type");1738  __node_allocator& __na = __node_alloc();1739  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1740  __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), std::forward<_Args>(__args)...);1741  __h.get_deleter().__value_constructed = true;1742  return __h;1743}1744 1745template <class _Tp, class _Compare, class _Allocator>1746template <class... _Args>1747pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>1748__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) {1749  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1750  __parent_pointer __parent;1751  __node_base_pointer& __child = __find_equal(__parent, __h->__value_);1752  __node_pointer __r           = static_cast<__node_pointer>(__child);1753  bool __inserted              = false;1754  if (__child == nullptr) {1755    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1756    __r        = __h.release();1757    __inserted = true;1758  }1759  return pair<iterator, bool>(iterator(__r), __inserted);1760}1761 1762template <class _Tp, class _Compare, class _Allocator>1763template <class... _Args>1764typename __tree<_Tp, _Compare, _Allocator>::iterator1765__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) {1766  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1767  __parent_pointer __parent;1768  __node_base_pointer __dummy;1769  __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);1770  __node_pointer __r           = static_cast<__node_pointer>(__child);1771  if (__child == nullptr) {1772    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1773    __r = __h.release();1774  }1775  return iterator(__r);1776}1777 1778template <class _Tp, class _Compare, class _Allocator>1779template <class... _Args>1780typename __tree<_Tp, _Compare, _Allocator>::iterator1781__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) {1782  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1783  __parent_pointer __parent;1784  __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));1785  __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1786  return iterator(static_cast<__node_pointer>(__h.release()));1787}1788 1789template <class _Tp, class _Compare, class _Allocator>1790template <class... _Args>1791typename __tree<_Tp, _Compare, _Allocator>::iterator1792__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {1793  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1794  __parent_pointer __parent;1795  __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));1796  __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1797  return iterator(static_cast<__node_pointer>(__h.release()));1798}1799 1800template <class _Tp, class _Compare, class _Allocator>1801pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>1802__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd) {1803  __parent_pointer __parent;1804  __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__v));1805  __node_pointer __r           = static_cast<__node_pointer>(__child);1806  bool __inserted              = false;1807  if (__child == nullptr) {1808    __nd->__value_ = __v;1809    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));1810    __r        = __nd;1811    __inserted = true;1812  }1813  return pair<iterator, bool>(iterator(__r), __inserted);1814}1815 1816template <class _Tp, class _Compare, class _Allocator>1817typename __tree<_Tp, _Compare, _Allocator>::iterator1818__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) {1819  __parent_pointer __parent;1820  __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));1821  __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));1822  return iterator(__nd);1823}1824 1825template <class _Tp, class _Compare, class _Allocator>1826typename __tree<_Tp, _Compare, _Allocator>::iterator1827__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) {1828  __parent_pointer __parent;1829  __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));1830  __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));1831  return iterator(__nd);1832}1833 1834template <class _Tp, class _Compare, class _Allocator>1835typename __tree<_Tp, _Compare, _Allocator>::iterator1836__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT {1837  iterator __r(__ptr);1838  ++__r;1839  if (__begin_node() == __ptr)1840    __begin_node() = __r.__ptr_;1841  --size();1842  std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__ptr));1843  return __r;1844}1845 1846template <class _Tp, class _Compare, class _Allocator>1847typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) {1848  __node_pointer __np    = __p.__get_np();1849  iterator __r           = __remove_node_pointer(__np);1850  __node_allocator& __na = __node_alloc();1851  __node_traits::destroy(__na, _NodeTypes::__get_ptr(const_cast<__node_value_type&>(*__p)));1852  __node_traits::deallocate(__na, __np, 1);1853  return __r;1854}1855 1856template <class _Tp, class _Compare, class _Allocator>1857typename __tree<_Tp, _Compare, _Allocator>::iterator1858__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) {1859  while (__f != __l)1860    __f = erase(__f);1861  return iterator(__l.__ptr_);1862}1863 1864template <class _Tp, class _Compare, class _Allocator>1865template <class _Key>1866typename __tree<_Tp, _Compare, _Allocator>::size_type1867__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) {1868  iterator __i = find(__k);1869  if (__i == end())1870    return 0;1871  erase(__i);1872  return 1;1873}1874 1875template <class _Tp, class _Compare, class _Allocator>1876template <class _Key>1877typename __tree<_Tp, _Compare, _Allocator>::size_type1878__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) {1879  pair<iterator, iterator> __p = __equal_range_multi(__k);1880  size_type __r                = 0;1881  for (; __p.first != __p.second; ++__r)1882    __p.first = erase(__p.first);1883  return __r;1884}1885 1886template <class _Tp, class _Compare, class _Allocator>1887template <class _Key>1888typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) {1889  iterator __p = __lower_bound(__v, __root(), __end_node());1890  if (__p != end() && !value_comp()(__v, *__p))1891    return __p;1892  return end();1893}1894 1895template <class _Tp, class _Compare, class _Allocator>1896template <class _Key>1897typename __tree<_Tp, _Compare, _Allocator>::const_iterator1898__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const {1899  const_iterator __p = __lower_bound(__v, __root(), __end_node());1900  if (__p != end() && !value_comp()(__v, *__p))1901    return __p;1902  return end();1903}1904 1905template <class _Tp, class _Compare, class _Allocator>1906template <class _Key>1907typename __tree<_Tp, _Compare, _Allocator>::size_type1908__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const {1909  __node_pointer __rt = __root();1910  while (__rt != nullptr) {1911    if (value_comp()(__k, __rt->__value_)) {1912      __rt = static_cast<__node_pointer>(__rt->__left_);1913    } else if (value_comp()(__rt->__value_, __k))1914      __rt = static_cast<__node_pointer>(__rt->__right_);1915    else1916      return 1;1917  }1918  return 0;1919}1920 1921template <class _Tp, class _Compare, class _Allocator>1922template <class _Key>1923typename __tree<_Tp, _Compare, _Allocator>::size_type1924__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const {1925  __iter_pointer __result = __end_node();1926  __node_pointer __rt     = __root();1927  while (__rt != nullptr) {1928    if (value_comp()(__k, __rt->__value_)) {1929      __result = static_cast<__iter_pointer>(__rt);1930      __rt     = static_cast<__node_pointer>(__rt->__left_);1931    } else if (value_comp()(__rt->__value_, __k))1932      __rt = static_cast<__node_pointer>(__rt->__right_);1933    else1934      return std::distance(1935          __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),1936          __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));1937  }1938  return 0;1939}1940 1941template <class _Tp, class _Compare, class _Allocator>1942template <class _Key>1943typename __tree<_Tp, _Compare, _Allocator>::iterator1944__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) {1945  while (__root != nullptr) {1946    if (!value_comp()(__root->__value_, __v)) {1947      __result = static_cast<__iter_pointer>(__root);1948      __root   = static_cast<__node_pointer>(__root->__left_);1949    } else1950      __root = static_cast<__node_pointer>(__root->__right_);1951  }1952  return iterator(__result);1953}1954 1955template <class _Tp, class _Compare, class _Allocator>1956template <class _Key>1957typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound(1958    const _Key& __v, __node_pointer __root, __iter_pointer __result) const {1959  while (__root != nullptr) {1960    if (!value_comp()(__root->__value_, __v)) {1961      __result = static_cast<__iter_pointer>(__root);1962      __root   = static_cast<__node_pointer>(__root->__left_);1963    } else1964      __root = static_cast<__node_pointer>(__root->__right_);1965  }1966  return const_iterator(__result);1967}1968 1969template <class _Tp, class _Compare, class _Allocator>1970template <class _Key>1971typename __tree<_Tp, _Compare, _Allocator>::iterator1972__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) {1973  while (__root != nullptr) {1974    if (value_comp()(__v, __root->__value_)) {1975      __result = static_cast<__iter_pointer>(__root);1976      __root   = static_cast<__node_pointer>(__root->__left_);1977    } else1978      __root = static_cast<__node_pointer>(__root->__right_);1979  }1980  return iterator(__result);1981}1982 1983template <class _Tp, class _Compare, class _Allocator>1984template <class _Key>1985typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound(1986    const _Key& __v, __node_pointer __root, __iter_pointer __result) const {1987  while (__root != nullptr) {1988    if (value_comp()(__v, __root->__value_)) {1989      __result = static_cast<__iter_pointer>(__root);1990      __root   = static_cast<__node_pointer>(__root->__left_);1991    } else1992      __root = static_cast<__node_pointer>(__root->__right_);1993  }1994  return const_iterator(__result);1995}1996 1997template <class _Tp, class _Compare, class _Allocator>1998template <class _Key>1999pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>2000__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) {2001  typedef pair<iterator, iterator> _Pp;2002  __iter_pointer __result = __end_node();2003  __node_pointer __rt     = __root();2004  while (__rt != nullptr) {2005    if (value_comp()(__k, __rt->__value_)) {2006      __result = static_cast<__iter_pointer>(__rt);2007      __rt     = static_cast<__node_pointer>(__rt->__left_);2008    } else if (value_comp()(__rt->__value_, __k))2009      __rt = static_cast<__node_pointer>(__rt->__right_);2010    else2011      return _Pp(iterator(__rt),2012                 iterator(__rt->__right_ != nullptr ? static_cast<__iter_pointer>(std::__tree_min(__rt->__right_))2013                                                    : __result));2014  }2015  return _Pp(iterator(__result), iterator(__result));2016}2017 2018template <class _Tp, class _Compare, class _Allocator>2019template <class _Key>2020pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,2021     typename __tree<_Tp, _Compare, _Allocator>::const_iterator>2022__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const {2023  typedef pair<const_iterator, const_iterator> _Pp;2024  __iter_pointer __result = __end_node();2025  __node_pointer __rt     = __root();2026  while (__rt != nullptr) {2027    if (value_comp()(__k, __rt->__value_)) {2028      __result = static_cast<__iter_pointer>(__rt);2029      __rt     = static_cast<__node_pointer>(__rt->__left_);2030    } else if (value_comp()(__rt->__value_, __k))2031      __rt = static_cast<__node_pointer>(__rt->__right_);2032    else2033      return _Pp(2034          const_iterator(__rt),2035          const_iterator(2036              __rt->__right_ != nullptr ? static_cast<__iter_pointer>(std::__tree_min(__rt->__right_)) : __result));2037  }2038  return _Pp(const_iterator(__result), const_iterator(__result));2039}2040 2041template <class _Tp, class _Compare, class _Allocator>2042template <class _Key>2043pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>2044__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) {2045  typedef pair<iterator, iterator> _Pp;2046  __iter_pointer __result = __end_node();2047  __node_pointer __rt     = __root();2048  while (__rt != nullptr) {2049    if (value_comp()(__k, __rt->__value_)) {2050      __result = static_cast<__iter_pointer>(__rt);2051      __rt     = static_cast<__node_pointer>(__rt->__left_);2052    } else if (value_comp()(__rt->__value_, __k))2053      __rt = static_cast<__node_pointer>(__rt->__right_);2054    else2055      return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),2056                 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));2057  }2058  return _Pp(iterator(__result), iterator(__result));2059}2060 2061template <class _Tp, class _Compare, class _Allocator>2062template <class _Key>2063pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,2064     typename __tree<_Tp, _Compare, _Allocator>::const_iterator>2065__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const {2066  typedef pair<const_iterator, const_iterator> _Pp;2067  __iter_pointer __result = __end_node();2068  __node_pointer __rt     = __root();2069  while (__rt != nullptr) {2070    if (value_comp()(__k, __rt->__value_)) {2071      __result = static_cast<__iter_pointer>(__rt);2072      __rt     = static_cast<__node_pointer>(__rt->__left_);2073    } else if (value_comp()(__rt->__value_, __k))2074      __rt = static_cast<__node_pointer>(__rt->__right_);2075    else2076      return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),2077                 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));2078  }2079  return _Pp(const_iterator(__result), const_iterator(__result));2080}2081 2082template <class _Tp, class _Compare, class _Allocator>2083typename __tree<_Tp, _Compare, _Allocator>::__node_holder2084__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT {2085  __node_pointer __np = __p.__get_np();2086  if (__begin_node() == __p.__ptr_) {2087    if (__np->__right_ != nullptr)2088      __begin_node() = static_cast<__iter_pointer>(__np->__right_);2089    else2090      __begin_node() = static_cast<__iter_pointer>(__np->__parent_);2091  }2092  --size();2093  std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np));2094  return __node_holder(__np, _Dp(__node_alloc(), true));2095}2096 2097template <class _Tp, class _Compare, class _Allocator>2098inline _LIBCPP_HIDE_FROM_ABI void swap(__tree<_Tp, _Compare, _Allocator>& __x, __tree<_Tp, _Compare, _Allocator>& __y) {2099  __x.swap(__y);2100}2101 2102_LIBCPP_END_NAMESPACE_STD2103 2104_LIBCPP_POP_MACROS2105 2106#endif // _LIBCPP___CXX03___TREE2107