__tree revision 253159
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===----------------------------------------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP___TREE 12227825Stheraven#define _LIBCPP___TREE 13227825Stheraven 14227825Stheraven#include <__config> 15227825Stheraven#include <iterator> 16227825Stheraven#include <memory> 17227825Stheraven#include <stdexcept> 18227825Stheraven#include <algorithm> 19227825Stheraven 20227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21227825Stheraven#pragma GCC system_header 22227825Stheraven#endif 23227825Stheraven 24227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 25227825Stheraven 26227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> class __tree; 27227825Stheraventemplate <class _Tp, class _NodePtr, class _DiffType> 28249998Sdim class _LIBCPP_TYPE_VIS __tree_iterator; 29227825Stheraventemplate <class _Tp, class _ConstNodePtr, class _DiffType> 30249998Sdim class _LIBCPP_TYPE_VIS __tree_const_iterator; 31227825Stheraventemplate <class _Key, class _Tp, class _Compare, class _Allocator> 32249998Sdim class _LIBCPP_TYPE_VIS map; 33227825Stheraventemplate <class _Key, class _Tp, class _Compare, class _Allocator> 34249998Sdim class _LIBCPP_TYPE_VIS multimap; 35227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 36249998Sdim class _LIBCPP_TYPE_VIS set; 37227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 38249998Sdim class _LIBCPP_TYPE_VIS multiset; 39227825Stheraven 40227825Stheraven/* 41227825Stheraven 42227825Stheraven_NodePtr algorithms 43227825Stheraven 44227825StheravenThe algorithms taking _NodePtr are red black tree algorithms. Those 45227825Stheravenalgorithms taking a parameter named __root should assume that __root 46227825Stheravenpoints to a proper red black tree (unless otherwise specified). 47227825Stheraven 48227825StheravenEach algorithm herein assumes that __root->__parent_ points to a non-null 49227825Stheravenstructure which has a member __left_ which points back to __root. No other 50227825Stheravenmember is read or written to at __root->__parent_. 51227825Stheraven 52227825Stheraven__root->__parent_ will be referred to below (in comments only) as end_node. 53227825Stheravenend_node->__left_ is an externably accessible lvalue for __root, and can be 54227825Stheravenchanged by node insertion and removal (without explicit reference to end_node). 55227825Stheraven 56227825StheravenAll nodes (with the exception of end_node), even the node referred to as 57227825Stheraven__root, have a non-null __parent_ field. 58227825Stheraven 59227825Stheraven*/ 60227825Stheraven 61227825Stheraven// Returns: true if __x is a left child of its parent, else false 62227825Stheraven// Precondition: __x != nullptr. 63227825Stheraventemplate <class _NodePtr> 64227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 65227825Stheravenbool 66227825Stheraven__tree_is_left_child(_NodePtr __x) _NOEXCEPT 67227825Stheraven{ 68227825Stheraven return __x == __x->__parent_->__left_; 69227825Stheraven} 70227825Stheraven 71227825Stheraven// Determintes if the subtree rooted at __x is a proper red black subtree. If 72227825Stheraven// __x is a proper subtree, returns the black height (null counts as 1). If 73227825Stheraven// __x is an improper subtree, returns 0. 74227825Stheraventemplate <class _NodePtr> 75227825Stheravenunsigned 76227825Stheraven__tree_sub_invariant(_NodePtr __x) 77227825Stheraven{ 78227825Stheraven if (__x == nullptr) 79227825Stheraven return 1; 80227825Stheraven // parent consistency checked by caller 81227825Stheraven // check __x->__left_ consistency 82227825Stheraven if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x) 83227825Stheraven return 0; 84227825Stheraven // check __x->__right_ consistency 85227825Stheraven if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x) 86227825Stheraven return 0; 87227825Stheraven // check __x->__left_ != __x->__right_ unless both are nullptr 88227825Stheraven if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) 89227825Stheraven return 0; 90227825Stheraven // If this is red, neither child can be red 91227825Stheraven if (!__x->__is_black_) 92227825Stheraven { 93227825Stheraven if (__x->__left_ && !__x->__left_->__is_black_) 94227825Stheraven return 0; 95227825Stheraven if (__x->__right_ && !__x->__right_->__is_black_) 96227825Stheraven return 0; 97227825Stheraven } 98227825Stheraven unsigned __h = __tree_sub_invariant(__x->__left_); 99227825Stheraven if (__h == 0) 100227825Stheraven return 0; // invalid left subtree 101227825Stheraven if (__h != __tree_sub_invariant(__x->__right_)) 102227825Stheraven return 0; // invalid or different height right subtree 103227825Stheraven return __h + __x->__is_black_; // return black height of this node 104227825Stheraven} 105227825Stheraven 106227825Stheraven// Determintes if the red black tree rooted at __root is a proper red black tree. 107227825Stheraven// __root == nullptr is a proper tree. Returns true is __root is a proper 108227825Stheraven// red black tree, else returns false. 109227825Stheraventemplate <class _NodePtr> 110227825Stheravenbool 111227825Stheraven__tree_invariant(_NodePtr __root) 112227825Stheraven{ 113227825Stheraven if (__root == nullptr) 114227825Stheraven return true; 115227825Stheraven // check __x->__parent_ consistency 116227825Stheraven if (__root->__parent_ == nullptr) 117227825Stheraven return false; 118227825Stheraven if (!__tree_is_left_child(__root)) 119227825Stheraven return false; 120227825Stheraven // root must be black 121227825Stheraven if (!__root->__is_black_) 122227825Stheraven return false; 123227825Stheraven // do normal node checks 124227825Stheraven return __tree_sub_invariant(__root) != 0; 125227825Stheraven} 126227825Stheraven 127227825Stheraven// Returns: pointer to the left-most node under __x. 128227825Stheraven// Precondition: __x != nullptr. 129227825Stheraventemplate <class _NodePtr> 130227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 131227825Stheraven_NodePtr 132227825Stheraven__tree_min(_NodePtr __x) _NOEXCEPT 133227825Stheraven{ 134227825Stheraven while (__x->__left_ != nullptr) 135227825Stheraven __x = __x->__left_; 136227825Stheraven return __x; 137227825Stheraven} 138227825Stheraven 139227825Stheraven// Returns: pointer to the right-most node under __x. 140227825Stheraven// Precondition: __x != nullptr. 141227825Stheraventemplate <class _NodePtr> 142227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 143227825Stheraven_NodePtr 144227825Stheraven__tree_max(_NodePtr __x) _NOEXCEPT 145227825Stheraven{ 146227825Stheraven while (__x->__right_ != nullptr) 147227825Stheraven __x = __x->__right_; 148227825Stheraven return __x; 149227825Stheraven} 150227825Stheraven 151227825Stheraven// Returns: pointer to the next in-order node after __x. 152227825Stheraven// Precondition: __x != nullptr. 153227825Stheraventemplate <class _NodePtr> 154227825Stheraven_NodePtr 155227825Stheraven__tree_next(_NodePtr __x) _NOEXCEPT 156227825Stheraven{ 157227825Stheraven if (__x->__right_ != nullptr) 158227825Stheraven return __tree_min(__x->__right_); 159227825Stheraven while (!__tree_is_left_child(__x)) 160227825Stheraven __x = __x->__parent_; 161227825Stheraven return __x->__parent_; 162227825Stheraven} 163227825Stheraven 164227825Stheraven// Returns: pointer to the previous in-order node before __x. 165227825Stheraven// Precondition: __x != nullptr. 166227825Stheraventemplate <class _NodePtr> 167227825Stheraven_NodePtr 168227825Stheraven__tree_prev(_NodePtr __x) _NOEXCEPT 169227825Stheraven{ 170227825Stheraven if (__x->__left_ != nullptr) 171227825Stheraven return __tree_max(__x->__left_); 172227825Stheraven while (__tree_is_left_child(__x)) 173227825Stheraven __x = __x->__parent_; 174227825Stheraven return __x->__parent_; 175227825Stheraven} 176227825Stheraven 177227825Stheraven// Returns: pointer to a node which has no children 178227825Stheraven// Precondition: __x != nullptr. 179227825Stheraventemplate <class _NodePtr> 180227825Stheraven_NodePtr 181227825Stheraven__tree_leaf(_NodePtr __x) _NOEXCEPT 182227825Stheraven{ 183227825Stheraven while (true) 184227825Stheraven { 185227825Stheraven if (__x->__left_ != nullptr) 186227825Stheraven { 187227825Stheraven __x = __x->__left_; 188227825Stheraven continue; 189227825Stheraven } 190227825Stheraven if (__x->__right_ != nullptr) 191227825Stheraven { 192227825Stheraven __x = __x->__right_; 193227825Stheraven continue; 194227825Stheraven } 195227825Stheraven break; 196227825Stheraven } 197227825Stheraven return __x; 198227825Stheraven} 199227825Stheraven 200227825Stheraven// Effects: Makes __x->__right_ the subtree root with __x as its left child 201227825Stheraven// while preserving in-order order. 202227825Stheraven// Precondition: __x->__right_ != nullptr 203227825Stheraventemplate <class _NodePtr> 204227825Stheravenvoid 205227825Stheraven__tree_left_rotate(_NodePtr __x) _NOEXCEPT 206227825Stheraven{ 207227825Stheraven _NodePtr __y = __x->__right_; 208227825Stheraven __x->__right_ = __y->__left_; 209227825Stheraven if (__x->__right_ != nullptr) 210227825Stheraven __x->__right_->__parent_ = __x; 211227825Stheraven __y->__parent_ = __x->__parent_; 212227825Stheraven if (__tree_is_left_child(__x)) 213227825Stheraven __x->__parent_->__left_ = __y; 214227825Stheraven else 215227825Stheraven __x->__parent_->__right_ = __y; 216227825Stheraven __y->__left_ = __x; 217227825Stheraven __x->__parent_ = __y; 218227825Stheraven} 219227825Stheraven 220227825Stheraven// Effects: Makes __x->__left_ the subtree root with __x as its right child 221227825Stheraven// while preserving in-order order. 222227825Stheraven// Precondition: __x->__left_ != nullptr 223227825Stheraventemplate <class _NodePtr> 224227825Stheravenvoid 225227825Stheraven__tree_right_rotate(_NodePtr __x) _NOEXCEPT 226227825Stheraven{ 227227825Stheraven _NodePtr __y = __x->__left_; 228227825Stheraven __x->__left_ = __y->__right_; 229227825Stheraven if (__x->__left_ != nullptr) 230227825Stheraven __x->__left_->__parent_ = __x; 231227825Stheraven __y->__parent_ = __x->__parent_; 232227825Stheraven if (__tree_is_left_child(__x)) 233227825Stheraven __x->__parent_->__left_ = __y; 234227825Stheraven else 235227825Stheraven __x->__parent_->__right_ = __y; 236227825Stheraven __y->__right_ = __x; 237227825Stheraven __x->__parent_ = __y; 238227825Stheraven} 239227825Stheraven 240227825Stheraven// Effects: Rebalances __root after attaching __x to a leaf. 241227825Stheraven// Precondition: __root != nulptr && __x != nullptr. 242227825Stheraven// __x has no children. 243227825Stheraven// __x == __root or == a direct or indirect child of __root. 244227825Stheraven// If __x were to be unlinked from __root (setting __root to 245227825Stheraven// nullptr if __root == __x), __tree_invariant(__root) == true. 246227825Stheraven// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_ 247227825Stheraven// may be different than the value passed in as __root. 248227825Stheraventemplate <class _NodePtr> 249227825Stheravenvoid 250227825Stheraven__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT 251227825Stheraven{ 252227825Stheraven __x->__is_black_ = __x == __root; 253227825Stheraven while (__x != __root && !__x->__parent_->__is_black_) 254227825Stheraven { 255227825Stheraven // __x->__parent_ != __root because __x->__parent_->__is_black == false 256227825Stheraven if (__tree_is_left_child(__x->__parent_)) 257227825Stheraven { 258227825Stheraven _NodePtr __y = __x->__parent_->__parent_->__right_; 259227825Stheraven if (__y != nullptr && !__y->__is_black_) 260227825Stheraven { 261227825Stheraven __x = __x->__parent_; 262227825Stheraven __x->__is_black_ = true; 263227825Stheraven __x = __x->__parent_; 264227825Stheraven __x->__is_black_ = __x == __root; 265227825Stheraven __y->__is_black_ = true; 266227825Stheraven } 267227825Stheraven else 268227825Stheraven { 269227825Stheraven if (!__tree_is_left_child(__x)) 270227825Stheraven { 271227825Stheraven __x = __x->__parent_; 272227825Stheraven __tree_left_rotate(__x); 273227825Stheraven } 274227825Stheraven __x = __x->__parent_; 275227825Stheraven __x->__is_black_ = true; 276227825Stheraven __x = __x->__parent_; 277227825Stheraven __x->__is_black_ = false; 278227825Stheraven __tree_right_rotate(__x); 279227825Stheraven break; 280227825Stheraven } 281227825Stheraven } 282227825Stheraven else 283227825Stheraven { 284227825Stheraven _NodePtr __y = __x->__parent_->__parent_->__left_; 285227825Stheraven if (__y != nullptr && !__y->__is_black_) 286227825Stheraven { 287227825Stheraven __x = __x->__parent_; 288227825Stheraven __x->__is_black_ = true; 289227825Stheraven __x = __x->__parent_; 290227825Stheraven __x->__is_black_ = __x == __root; 291227825Stheraven __y->__is_black_ = true; 292227825Stheraven } 293227825Stheraven else 294227825Stheraven { 295227825Stheraven if (__tree_is_left_child(__x)) 296227825Stheraven { 297227825Stheraven __x = __x->__parent_; 298227825Stheraven __tree_right_rotate(__x); 299227825Stheraven } 300227825Stheraven __x = __x->__parent_; 301227825Stheraven __x->__is_black_ = true; 302227825Stheraven __x = __x->__parent_; 303227825Stheraven __x->__is_black_ = false; 304227825Stheraven __tree_left_rotate(__x); 305227825Stheraven break; 306227825Stheraven } 307227825Stheraven } 308227825Stheraven } 309227825Stheraven} 310227825Stheraven 311227825Stheraven// Precondition: __root != nullptr && __z != nullptr. 312227825Stheraven// __tree_invariant(__root) == true. 313227825Stheraven// __z == __root or == a direct or indirect child of __root. 314227825Stheraven// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed. 315227825Stheraven// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_ 316227825Stheraven// nor any of its children refer to __z. end_node->__left_ 317227825Stheraven// may be different than the value passed in as __root. 318227825Stheraventemplate <class _NodePtr> 319227825Stheravenvoid 320227825Stheraven__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT 321227825Stheraven{ 322227825Stheraven // __z will be removed from the tree. Client still needs to destruct/deallocate it 323227825Stheraven // __y is either __z, or if __z has two children, __tree_next(__z). 324227825Stheraven // __y will have at most one child. 325227825Stheraven // __y will be the initial hole in the tree (make the hole at a leaf) 326227825Stheraven _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? 327227825Stheraven __z : __tree_next(__z); 328227825Stheraven // __x is __y's possibly null single child 329227825Stheraven _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; 330227825Stheraven // __w is __x's possibly null uncle (will become __x's sibling) 331227825Stheraven _NodePtr __w = nullptr; 332227825Stheraven // link __x to __y's parent, and find __w 333227825Stheraven if (__x != nullptr) 334227825Stheraven __x->__parent_ = __y->__parent_; 335227825Stheraven if (__tree_is_left_child(__y)) 336227825Stheraven { 337227825Stheraven __y->__parent_->__left_ = __x; 338227825Stheraven if (__y != __root) 339227825Stheraven __w = __y->__parent_->__right_; 340227825Stheraven else 341227825Stheraven __root = __x; // __w == nullptr 342227825Stheraven } 343227825Stheraven else 344227825Stheraven { 345227825Stheraven __y->__parent_->__right_ = __x; 346227825Stheraven // __y can't be root if it is a right child 347227825Stheraven __w = __y->__parent_->__left_; 348227825Stheraven } 349227825Stheraven bool __removed_black = __y->__is_black_; 350227825Stheraven // If we didn't remove __z, do so now by splicing in __y for __z, 351227825Stheraven // but copy __z's color. This does not impact __x or __w. 352227825Stheraven if (__y != __z) 353227825Stheraven { 354227825Stheraven // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr 355227825Stheraven __y->__parent_ = __z->__parent_; 356227825Stheraven if (__tree_is_left_child(__z)) 357227825Stheraven __y->__parent_->__left_ = __y; 358227825Stheraven else 359227825Stheraven __y->__parent_->__right_ = __y; 360227825Stheraven __y->__left_ = __z->__left_; 361227825Stheraven __y->__left_->__parent_ = __y; 362227825Stheraven __y->__right_ = __z->__right_; 363227825Stheraven if (__y->__right_ != nullptr) 364227825Stheraven __y->__right_->__parent_ = __y; 365227825Stheraven __y->__is_black_ = __z->__is_black_; 366227825Stheraven if (__root == __z) 367227825Stheraven __root = __y; 368227825Stheraven } 369227825Stheraven // There is no need to rebalance if we removed a red, or if we removed 370227825Stheraven // the last node. 371227825Stheraven if (__removed_black && __root != nullptr) 372227825Stheraven { 373227825Stheraven // Rebalance: 374227825Stheraven // __x has an implicit black color (transferred from the removed __y) 375227825Stheraven // associated with it, no matter what its color is. 376227825Stheraven // If __x is __root (in which case it can't be null), it is supposed 377227825Stheraven // to be black anyway, and if it is doubly black, then the double 378227825Stheraven // can just be ignored. 379227825Stheraven // If __x is red (in which case it can't be null), then it can absorb 380227825Stheraven // the implicit black just by setting its color to black. 381227825Stheraven // Since __y was black and only had one child (which __x points to), __x 382227825Stheraven // is either red with no children, else null, otherwise __y would have 383227825Stheraven // different black heights under left and right pointers. 384227825Stheraven // if (__x == __root || __x != nullptr && !__x->__is_black_) 385227825Stheraven if (__x != nullptr) 386227825Stheraven __x->__is_black_ = true; 387227825Stheraven else 388227825Stheraven { 389227825Stheraven // Else __x isn't root, and is "doubly black", even though it may 390227825Stheraven // be null. __w can not be null here, else the parent would 391227825Stheraven // see a black height >= 2 on the __x side and a black height 392227825Stheraven // of 1 on the __w side (__w must be a non-null black or a red 393227825Stheraven // with a non-null black child). 394227825Stheraven while (true) 395227825Stheraven { 396227825Stheraven if (!__tree_is_left_child(__w)) // if x is left child 397227825Stheraven { 398227825Stheraven if (!__w->__is_black_) 399227825Stheraven { 400227825Stheraven __w->__is_black_ = true; 401227825Stheraven __w->__parent_->__is_black_ = false; 402227825Stheraven __tree_left_rotate(__w->__parent_); 403227825Stheraven // __x is still valid 404227825Stheraven // reset __root only if necessary 405227825Stheraven if (__root == __w->__left_) 406227825Stheraven __root = __w; 407227825Stheraven // reset sibling, and it still can't be null 408227825Stheraven __w = __w->__left_->__right_; 409227825Stheraven } 410227825Stheraven // __w->__is_black_ is now true, __w may have null children 411227825Stheraven if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 412227825Stheraven (__w->__right_ == nullptr || __w->__right_->__is_black_)) 413227825Stheraven { 414227825Stheraven __w->__is_black_ = false; 415227825Stheraven __x = __w->__parent_; 416227825Stheraven // __x can no longer be null 417227825Stheraven if (__x == __root || !__x->__is_black_) 418227825Stheraven { 419227825Stheraven __x->__is_black_ = true; 420227825Stheraven break; 421227825Stheraven } 422227825Stheraven // reset sibling, and it still can't be null 423227825Stheraven __w = __tree_is_left_child(__x) ? 424227825Stheraven __x->__parent_->__right_ : 425227825Stheraven __x->__parent_->__left_; 426227825Stheraven // continue; 427227825Stheraven } 428227825Stheraven else // __w has a red child 429227825Stheraven { 430227825Stheraven if (__w->__right_ == nullptr || __w->__right_->__is_black_) 431227825Stheraven { 432227825Stheraven // __w left child is non-null and red 433227825Stheraven __w->__left_->__is_black_ = true; 434227825Stheraven __w->__is_black_ = false; 435227825Stheraven __tree_right_rotate(__w); 436227825Stheraven // __w is known not to be root, so root hasn't changed 437227825Stheraven // reset sibling, and it still can't be null 438227825Stheraven __w = __w->__parent_; 439227825Stheraven } 440227825Stheraven // __w has a right red child, left child may be null 441227825Stheraven __w->__is_black_ = __w->__parent_->__is_black_; 442227825Stheraven __w->__parent_->__is_black_ = true; 443227825Stheraven __w->__right_->__is_black_ = true; 444227825Stheraven __tree_left_rotate(__w->__parent_); 445227825Stheraven break; 446227825Stheraven } 447227825Stheraven } 448227825Stheraven else 449227825Stheraven { 450227825Stheraven if (!__w->__is_black_) 451227825Stheraven { 452227825Stheraven __w->__is_black_ = true; 453227825Stheraven __w->__parent_->__is_black_ = false; 454227825Stheraven __tree_right_rotate(__w->__parent_); 455227825Stheraven // __x is still valid 456227825Stheraven // reset __root only if necessary 457227825Stheraven if (__root == __w->__right_) 458227825Stheraven __root = __w; 459227825Stheraven // reset sibling, and it still can't be null 460227825Stheraven __w = __w->__right_->__left_; 461227825Stheraven } 462227825Stheraven // __w->__is_black_ is now true, __w may have null children 463227825Stheraven if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 464227825Stheraven (__w->__right_ == nullptr || __w->__right_->__is_black_)) 465227825Stheraven { 466227825Stheraven __w->__is_black_ = false; 467227825Stheraven __x = __w->__parent_; 468227825Stheraven // __x can no longer be null 469227825Stheraven if (!__x->__is_black_ || __x == __root) 470227825Stheraven { 471227825Stheraven __x->__is_black_ = true; 472227825Stheraven break; 473227825Stheraven } 474227825Stheraven // reset sibling, and it still can't be null 475227825Stheraven __w = __tree_is_left_child(__x) ? 476227825Stheraven __x->__parent_->__right_ : 477227825Stheraven __x->__parent_->__left_; 478227825Stheraven // continue; 479227825Stheraven } 480227825Stheraven else // __w has a red child 481227825Stheraven { 482227825Stheraven if (__w->__left_ == nullptr || __w->__left_->__is_black_) 483227825Stheraven { 484227825Stheraven // __w right child is non-null and red 485227825Stheraven __w->__right_->__is_black_ = true; 486227825Stheraven __w->__is_black_ = false; 487227825Stheraven __tree_left_rotate(__w); 488227825Stheraven // __w is known not to be root, so root hasn't changed 489227825Stheraven // reset sibling, and it still can't be null 490227825Stheraven __w = __w->__parent_; 491227825Stheraven } 492227825Stheraven // __w has a left red child, right child may be null 493227825Stheraven __w->__is_black_ = __w->__parent_->__is_black_; 494227825Stheraven __w->__parent_->__is_black_ = true; 495227825Stheraven __w->__left_->__is_black_ = true; 496227825Stheraven __tree_right_rotate(__w->__parent_); 497227825Stheraven break; 498227825Stheraven } 499227825Stheraven } 500227825Stheraven } 501227825Stheraven } 502227825Stheraven } 503227825Stheraven} 504227825Stheraven 505227825Stheraventemplate <class _Allocator> class __map_node_destructor; 506227825Stheraven 507227825Stheraventemplate <class _Allocator> 508227825Stheravenclass __tree_node_destructor 509227825Stheraven{ 510227825Stheraven typedef _Allocator allocator_type; 511227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 512227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 513227825Stheravenpublic: 514227825Stheraven typedef typename __alloc_traits::pointer pointer; 515227825Stheravenprivate: 516227825Stheraven 517227825Stheraven allocator_type& __na_; 518227825Stheraven 519227825Stheraven __tree_node_destructor& operator=(const __tree_node_destructor&); 520227825Stheraven 521227825Stheravenpublic: 522227825Stheraven bool __value_constructed; 523227825Stheraven 524227825Stheraven _LIBCPP_INLINE_VISIBILITY 525227825Stheraven explicit __tree_node_destructor(allocator_type& __na) _NOEXCEPT 526227825Stheraven : __na_(__na), 527227825Stheraven __value_constructed(false) 528227825Stheraven {} 529227825Stheraven 530227825Stheraven _LIBCPP_INLINE_VISIBILITY 531227825Stheraven void operator()(pointer __p) _NOEXCEPT 532227825Stheraven { 533227825Stheraven if (__value_constructed) 534227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 535227825Stheraven if (__p) 536227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 537227825Stheraven } 538227825Stheraven 539227825Stheraven template <class> friend class __map_node_destructor; 540227825Stheraven}; 541227825Stheraven 542227825Stheraven// node 543227825Stheraven 544227825Stheraventemplate <class _Pointer> 545227825Stheravenclass __tree_end_node 546227825Stheraven{ 547227825Stheravenpublic: 548227825Stheraven typedef _Pointer pointer; 549227825Stheraven pointer __left_; 550227825Stheraven 551227825Stheraven _LIBCPP_INLINE_VISIBILITY 552227825Stheraven __tree_end_node() _NOEXCEPT : __left_() {} 553227825Stheraven}; 554227825Stheraven 555227825Stheraventemplate <class _VoidPtr> 556227825Stheravenclass __tree_node_base 557227825Stheraven : public __tree_end_node 558227825Stheraven < 559227825Stheraven typename pointer_traits<_VoidPtr>::template 560227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 561227825Stheraven rebind<__tree_node_base<_VoidPtr> > 562227825Stheraven#else 563227825Stheraven rebind<__tree_node_base<_VoidPtr> >::other 564227825Stheraven#endif 565227825Stheraven > 566227825Stheraven{ 567227825Stheraven __tree_node_base(const __tree_node_base&); 568227825Stheraven __tree_node_base& operator=(const __tree_node_base&); 569227825Stheravenpublic: 570227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 571227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 572227825Stheraven rebind<__tree_node_base> 573227825Stheraven#else 574227825Stheraven rebind<__tree_node_base>::other 575227825Stheraven#endif 576227825Stheraven pointer; 577227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 578227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 579227825Stheraven rebind<const __tree_node_base> 580227825Stheraven#else 581227825Stheraven rebind<const __tree_node_base>::other 582227825Stheraven#endif 583227825Stheraven const_pointer; 584227825Stheraven typedef __tree_end_node<pointer> base; 585227825Stheraven 586227825Stheraven pointer __right_; 587227825Stheraven pointer __parent_; 588227825Stheraven bool __is_black_; 589227825Stheraven 590227825Stheraven _LIBCPP_INLINE_VISIBILITY 591227825Stheraven __tree_node_base() _NOEXCEPT 592227825Stheraven : __right_(), __parent_(), __is_black_(false) {} 593227825Stheraven}; 594227825Stheraven 595227825Stheraventemplate <class _Tp, class _VoidPtr> 596227825Stheravenclass __tree_node 597227825Stheraven : public __tree_node_base<_VoidPtr> 598227825Stheraven{ 599227825Stheravenpublic: 600227825Stheraven typedef __tree_node_base<_VoidPtr> base; 601227825Stheraven typedef _Tp value_type; 602227825Stheraven 603227825Stheraven value_type __value_; 604227825Stheraven 605227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 606227825Stheraven template <class ..._Args> 607227825Stheraven _LIBCPP_INLINE_VISIBILITY 608227825Stheraven explicit __tree_node(_Args&& ...__args) 609227825Stheraven : __value_(_VSTD::forward<_Args>(__args)...) {} 610227825Stheraven#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 611227825Stheraven _LIBCPP_INLINE_VISIBILITY 612227825Stheraven explicit __tree_node(const value_type& __v) 613227825Stheraven : __value_(__v) {} 614227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 615227825Stheraven}; 616227825Stheraven 617249998Sdimtemplate <class _TreeIterator> class _LIBCPP_TYPE_VIS __map_iterator; 618249998Sdimtemplate <class _TreeIterator> class _LIBCPP_TYPE_VIS __map_const_iterator; 619227825Stheraven 620227825Stheraventemplate <class _Tp, class _NodePtr, class _DiffType> 621249998Sdimclass _LIBCPP_TYPE_VIS __tree_iterator 622227825Stheraven{ 623227825Stheraven typedef _NodePtr __node_pointer; 624227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type __node; 625227825Stheraven typedef typename __node::base __node_base; 626227825Stheraven typedef typename __node_base::pointer __node_base_pointer; 627227825Stheraven 628227825Stheraven __node_pointer __ptr_; 629227825Stheraven 630227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 631227825Stheravenpublic: 632227825Stheraven typedef bidirectional_iterator_tag iterator_category; 633227825Stheraven typedef _Tp value_type; 634227825Stheraven typedef _DiffType difference_type; 635227825Stheraven typedef value_type& reference; 636227825Stheraven typedef typename pointer_traits<__node_pointer>::template 637227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 638227825Stheraven rebind<value_type> 639227825Stheraven#else 640227825Stheraven rebind<value_type>::other 641227825Stheraven#endif 642227825Stheraven pointer; 643227825Stheraven 644227825Stheraven _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT {} 645227825Stheraven 646227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 647253159Stheraven _LIBCPP_INLINE_VISIBILITY pointer operator->() const 648253159Stheraven {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 649227825Stheraven 650227825Stheraven _LIBCPP_INLINE_VISIBILITY 651227825Stheraven __tree_iterator& operator++() 652227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); 653227825Stheraven return *this;} 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655227825Stheraven __tree_iterator operator++(int) 656227825Stheraven {__tree_iterator __t(*this); ++(*this); return __t;} 657227825Stheraven 658227825Stheraven _LIBCPP_INLINE_VISIBILITY 659227825Stheraven __tree_iterator& operator--() 660227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); 661227825Stheraven return *this;} 662227825Stheraven _LIBCPP_INLINE_VISIBILITY 663227825Stheraven __tree_iterator operator--(int) 664227825Stheraven {__tree_iterator __t(*this); --(*this); return __t;} 665227825Stheraven 666227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 667227825Stheraven bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 668227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 669227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 670227825Stheraven bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 671227825Stheraven {return !(__x == __y);} 672227825Stheraven 673227825Stheravenprivate: 674227825Stheraven _LIBCPP_INLINE_VISIBILITY 675227825Stheraven explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 676227825Stheraven template <class, class, class> friend class __tree; 677249998Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS __tree_const_iterator; 678249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __map_iterator; 679249998Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map; 680249998Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap; 681249998Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS set; 682249998Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS multiset; 683227825Stheraven}; 684227825Stheraven 685227825Stheraventemplate <class _Tp, class _ConstNodePtr, class _DiffType> 686249998Sdimclass _LIBCPP_TYPE_VIS __tree_const_iterator 687227825Stheraven{ 688227825Stheraven typedef _ConstNodePtr __node_pointer; 689227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type __node; 690253159Stheraven typedef typename __node::base __node_base; 691227825Stheraven typedef typename pointer_traits<__node_pointer>::template 692227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 693227825Stheraven rebind<__node_base> 694227825Stheraven#else 695227825Stheraven rebind<__node_base>::other 696227825Stheraven#endif 697227825Stheraven __node_base_pointer; 698227825Stheraven 699227825Stheraven __node_pointer __ptr_; 700227825Stheraven 701227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 702227825Stheravenpublic: 703227825Stheraven typedef bidirectional_iterator_tag iterator_category; 704227825Stheraven typedef _Tp value_type; 705227825Stheraven typedef _DiffType difference_type; 706227825Stheraven typedef const value_type& reference; 707227825Stheraven typedef typename pointer_traits<__node_pointer>::template 708227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 709227825Stheraven rebind<const value_type> 710227825Stheraven#else 711227825Stheraven rebind<const value_type>::other 712227825Stheraven#endif 713227825Stheraven pointer; 714227825Stheraven 715227825Stheraven _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() {} 716227825Stheravenprivate: 717227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 718227825Stheraven typedef typename pointer_traits<__node_pointer>::template 719227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 720227825Stheraven rebind<__non_const_node> 721227825Stheraven#else 722227825Stheraven rebind<__non_const_node>::other 723227825Stheraven#endif 724227825Stheraven __non_const_node_pointer; 725227825Stheraven typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> 726227825Stheraven __non_const_iterator; 727227825Stheravenpublic: 728227825Stheraven _LIBCPP_INLINE_VISIBILITY 729227825Stheraven __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 730227825Stheraven : __ptr_(__p.__ptr_) {} 731227825Stheraven 732227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 733253159Stheraven _LIBCPP_INLINE_VISIBILITY pointer operator->() const 734253159Stheraven {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 735227825Stheraven 736227825Stheraven _LIBCPP_INLINE_VISIBILITY 737227825Stheraven __tree_const_iterator& operator++() 738227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); 739227825Stheraven return *this;} 740227825Stheraven _LIBCPP_INLINE_VISIBILITY 741227825Stheraven __tree_const_iterator operator++(int) 742227825Stheraven {__tree_const_iterator __t(*this); ++(*this); return __t;} 743227825Stheraven 744227825Stheraven _LIBCPP_INLINE_VISIBILITY 745227825Stheraven __tree_const_iterator& operator--() 746227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); 747227825Stheraven return *this;} 748227825Stheraven _LIBCPP_INLINE_VISIBILITY 749227825Stheraven __tree_const_iterator operator--(int) 750227825Stheraven {__tree_const_iterator __t(*this); --(*this); return __t;} 751227825Stheraven 752227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 753227825Stheraven bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 754227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 755227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 756227825Stheraven bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 757227825Stheraven {return !(__x == __y);} 758227825Stheraven 759227825Stheravenprivate: 760227825Stheraven _LIBCPP_INLINE_VISIBILITY 761227825Stheraven explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 762227825Stheraven : __ptr_(__p) {} 763227825Stheraven template <class, class, class> friend class __tree; 764249998Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map; 765249998Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap; 766249998Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS set; 767249998Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS multiset; 768249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __map_const_iterator; 769227825Stheraven}; 770227825Stheraven 771227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 772227825Stheravenclass __tree 773227825Stheraven{ 774227825Stheravenpublic: 775227825Stheraven typedef _Tp value_type; 776227825Stheraven typedef _Compare value_compare; 777227825Stheraven typedef _Allocator allocator_type; 778227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 779227825Stheraven typedef typename __alloc_traits::pointer pointer; 780227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 781227825Stheraven typedef typename __alloc_traits::size_type size_type; 782227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 783227825Stheraven 784253159Stheraven typedef typename __alloc_traits::void_pointer __void_pointer; 785253159Stheraven 786253159Stheraven typedef __tree_node<value_type, __void_pointer> __node; 787253159Stheraven typedef __tree_node_base<__void_pointer> __node_base; 788227825Stheraven typedef typename __alloc_traits::template 789227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 790227825Stheraven rebind_alloc<__node> 791227825Stheraven#else 792227825Stheraven rebind_alloc<__node>::other 793227825Stheraven#endif 794227825Stheraven __node_allocator; 795227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 796227825Stheraven typedef typename __node_traits::pointer __node_pointer; 797253159Stheraven typedef typename __node_traits::pointer __node_const_pointer; 798227825Stheraven typedef typename __node_base::pointer __node_base_pointer; 799253159Stheraven typedef typename __node_base::pointer __node_base_const_pointer; 800227825Stheravenprivate: 801227825Stheraven typedef typename __node_base::base __end_node_t; 802227825Stheraven typedef typename pointer_traits<__node_pointer>::template 803227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 804227825Stheraven rebind<__end_node_t> 805227825Stheraven#else 806227825Stheraven rebind<__end_node_t>::other 807227825Stheraven#endif 808227825Stheraven __end_node_ptr; 809227825Stheraven typedef typename pointer_traits<__node_pointer>::template 810227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 811253159Stheraven rebind<__end_node_t> 812227825Stheraven#else 813253159Stheraven rebind<__end_node_t>::other 814227825Stheraven#endif 815227825Stheraven __end_node_const_ptr; 816227825Stheraven 817227825Stheraven __node_pointer __begin_node_; 818227825Stheraven __compressed_pair<__end_node_t, __node_allocator> __pair1_; 819227825Stheraven __compressed_pair<size_type, value_compare> __pair3_; 820227825Stheraven 821227825Stheravenpublic: 822227825Stheraven _LIBCPP_INLINE_VISIBILITY 823227825Stheraven __node_pointer __end_node() _NOEXCEPT 824227825Stheraven { 825227825Stheraven return static_cast<__node_pointer> 826227825Stheraven ( 827227825Stheraven pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 828227825Stheraven ); 829227825Stheraven } 830227825Stheraven _LIBCPP_INLINE_VISIBILITY 831227825Stheraven __node_const_pointer __end_node() const _NOEXCEPT 832227825Stheraven { 833227825Stheraven return static_cast<__node_const_pointer> 834227825Stheraven ( 835253159Stheraven pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first())) 836227825Stheraven ); 837227825Stheraven } 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 840227825Stheravenprivate: 841227825Stheraven _LIBCPP_INLINE_VISIBILITY 842227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 843227825Stheraven {return __pair1_.second();} 844227825Stheraven _LIBCPP_INLINE_VISIBILITY 845227825Stheraven __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 846227825Stheraven _LIBCPP_INLINE_VISIBILITY 847227825Stheraven const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 848227825Stheravenpublic: 849227825Stheraven _LIBCPP_INLINE_VISIBILITY 850227825Stheraven allocator_type __alloc() const _NOEXCEPT 851227825Stheraven {return allocator_type(__node_alloc());} 852227825Stheravenprivate: 853227825Stheraven _LIBCPP_INLINE_VISIBILITY 854227825Stheraven size_type& size() _NOEXCEPT {return __pair3_.first();} 855227825Stheravenpublic: 856227825Stheraven _LIBCPP_INLINE_VISIBILITY 857227825Stheraven const size_type& size() const _NOEXCEPT {return __pair3_.first();} 858227825Stheraven _LIBCPP_INLINE_VISIBILITY 859227825Stheraven value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 860227825Stheraven _LIBCPP_INLINE_VISIBILITY 861227825Stheraven const value_compare& value_comp() const _NOEXCEPT 862227825Stheraven {return __pair3_.second();} 863227825Stheravenpublic: 864227825Stheraven _LIBCPP_INLINE_VISIBILITY 865227825Stheraven __node_pointer __root() _NOEXCEPT 866227825Stheraven {return static_cast<__node_pointer> (__end_node()->__left_);} 867227825Stheraven _LIBCPP_INLINE_VISIBILITY 868227825Stheraven __node_const_pointer __root() const _NOEXCEPT 869227825Stheraven {return static_cast<__node_const_pointer>(__end_node()->__left_);} 870227825Stheraven 871227825Stheraven typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 872253159Stheraven typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 873227825Stheraven 874227825Stheraven explicit __tree(const value_compare& __comp) 875227825Stheraven _NOEXCEPT_( 876227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 877227825Stheraven is_nothrow_copy_constructible<value_compare>::value); 878227825Stheraven explicit __tree(const allocator_type& __a); 879227825Stheraven __tree(const value_compare& __comp, const allocator_type& __a); 880227825Stheraven __tree(const __tree& __t); 881227825Stheraven __tree& operator=(const __tree& __t); 882227825Stheraven template <class _InputIterator> 883227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 884227825Stheraven template <class _InputIterator> 885227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 886227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 887227825Stheraven __tree(__tree&& __t) 888227825Stheraven _NOEXCEPT_( 889227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 890227825Stheraven is_nothrow_move_constructible<value_compare>::value); 891227825Stheraven __tree(__tree&& __t, const allocator_type& __a); 892227825Stheraven __tree& operator=(__tree&& __t) 893227825Stheraven _NOEXCEPT_( 894227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 895227825Stheraven is_nothrow_move_assignable<value_compare>::value && 896227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 897227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 898227825Stheraven 899227825Stheraven ~__tree(); 900227825Stheraven 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven iterator begin() _NOEXCEPT {return iterator(__begin_node());} 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven iterator end() _NOEXCEPT {return iterator(__end_node());} 907227825Stheraven _LIBCPP_INLINE_VISIBILITY 908227825Stheraven const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 909227825Stheraven 910227825Stheraven _LIBCPP_INLINE_VISIBILITY 911227825Stheraven size_type max_size() const _NOEXCEPT 912227825Stheraven {return __node_traits::max_size(__node_alloc());} 913227825Stheraven 914227825Stheraven void clear() _NOEXCEPT; 915227825Stheraven 916227825Stheraven void swap(__tree& __t) 917227825Stheraven _NOEXCEPT_( 918227825Stheraven __is_nothrow_swappable<value_compare>::value && 919227825Stheraven (!__node_traits::propagate_on_container_swap::value || 920227825Stheraven __is_nothrow_swappable<__node_allocator>::value)); 921227825Stheraven 922227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 923227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 924227825Stheraven template <class... _Args> 925227825Stheraven pair<iterator, bool> 926227825Stheraven __emplace_unique(_Args&&... __args); 927227825Stheraven template <class... _Args> 928227825Stheraven iterator 929227825Stheraven __emplace_multi(_Args&&... __args); 930227825Stheraven 931227825Stheraven template <class... _Args> 932227825Stheraven iterator 933227825Stheraven __emplace_hint_unique(const_iterator __p, _Args&&... __args); 934227825Stheraven template <class... _Args> 935227825Stheraven iterator 936227825Stheraven __emplace_hint_multi(const_iterator __p, _Args&&... __args); 937227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 938227825Stheraven 939232950Stheraven template <class _Vp> 940232950Stheraven pair<iterator, bool> __insert_unique(_Vp&& __v); 941232950Stheraven template <class _Vp> 942232950Stheraven iterator __insert_unique(const_iterator __p, _Vp&& __v); 943232950Stheraven template <class _Vp> 944232950Stheraven iterator __insert_multi(_Vp&& __v); 945232950Stheraven template <class _Vp> 946232950Stheraven iterator __insert_multi(const_iterator __p, _Vp&& __v); 947227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 948227825Stheraven 949227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __v); 950227825Stheraven iterator __insert_unique(const_iterator __p, const value_type& __v); 951227825Stheraven iterator __insert_multi(const value_type& __v); 952227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __v); 953227825Stheraven 954227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 955227825Stheraven iterator __node_insert_unique(const_iterator __p, 956227825Stheraven __node_pointer __nd); 957227825Stheraven 958227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 959227825Stheraven iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 960227825Stheraven 961227825Stheraven iterator erase(const_iterator __p); 962227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 963227825Stheraven template <class _Key> 964227825Stheraven size_type __erase_unique(const _Key& __k); 965227825Stheraven template <class _Key> 966227825Stheraven size_type __erase_multi(const _Key& __k); 967227825Stheraven 968227825Stheraven void __insert_node_at(__node_base_pointer __parent, 969227825Stheraven __node_base_pointer& __child, 970227825Stheraven __node_base_pointer __new_node); 971227825Stheraven 972227825Stheraven template <class _Key> 973227825Stheraven iterator find(const _Key& __v); 974227825Stheraven template <class _Key> 975227825Stheraven const_iterator find(const _Key& __v) const; 976227825Stheraven 977227825Stheraven template <class _Key> 978227825Stheraven size_type __count_unique(const _Key& __k) const; 979227825Stheraven template <class _Key> 980227825Stheraven size_type __count_multi(const _Key& __k) const; 981227825Stheraven 982227825Stheraven template <class _Key> 983227825Stheraven _LIBCPP_INLINE_VISIBILITY 984227825Stheraven iterator lower_bound(const _Key& __v) 985227825Stheraven {return __lower_bound(__v, __root(), __end_node());} 986227825Stheraven template <class _Key> 987227825Stheraven iterator __lower_bound(const _Key& __v, 988227825Stheraven __node_pointer __root, 989227825Stheraven __node_pointer __result); 990227825Stheraven template <class _Key> 991227825Stheraven _LIBCPP_INLINE_VISIBILITY 992227825Stheraven const_iterator lower_bound(const _Key& __v) const 993227825Stheraven {return __lower_bound(__v, __root(), __end_node());} 994227825Stheraven template <class _Key> 995227825Stheraven const_iterator __lower_bound(const _Key& __v, 996227825Stheraven __node_const_pointer __root, 997227825Stheraven __node_const_pointer __result) const; 998227825Stheraven template <class _Key> 999227825Stheraven _LIBCPP_INLINE_VISIBILITY 1000227825Stheraven iterator upper_bound(const _Key& __v) 1001227825Stheraven {return __upper_bound(__v, __root(), __end_node());} 1002227825Stheraven template <class _Key> 1003227825Stheraven iterator __upper_bound(const _Key& __v, 1004227825Stheraven __node_pointer __root, 1005227825Stheraven __node_pointer __result); 1006227825Stheraven template <class _Key> 1007227825Stheraven _LIBCPP_INLINE_VISIBILITY 1008227825Stheraven const_iterator upper_bound(const _Key& __v) const 1009227825Stheraven {return __upper_bound(__v, __root(), __end_node());} 1010227825Stheraven template <class _Key> 1011227825Stheraven const_iterator __upper_bound(const _Key& __v, 1012227825Stheraven __node_const_pointer __root, 1013227825Stheraven __node_const_pointer __result) const; 1014227825Stheraven template <class _Key> 1015227825Stheraven pair<iterator, iterator> 1016227825Stheraven __equal_range_unique(const _Key& __k); 1017227825Stheraven template <class _Key> 1018227825Stheraven pair<const_iterator, const_iterator> 1019227825Stheraven __equal_range_unique(const _Key& __k) const; 1020227825Stheraven 1021227825Stheraven template <class _Key> 1022227825Stheraven pair<iterator, iterator> 1023227825Stheraven __equal_range_multi(const _Key& __k); 1024227825Stheraven template <class _Key> 1025227825Stheraven pair<const_iterator, const_iterator> 1026227825Stheraven __equal_range_multi(const _Key& __k) const; 1027227825Stheraven 1028232950Stheraven typedef __tree_node_destructor<__node_allocator> _Dp; 1029232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1030227825Stheraven 1031227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 1032227825Stheravenprivate: 1033227825Stheraven typename __node_base::pointer& 1034227825Stheraven __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v); 1035227825Stheraven typename __node_base::pointer& 1036227825Stheraven __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v); 1037227825Stheraven typename __node_base::pointer& 1038227825Stheraven __find_leaf(const_iterator __hint, 1039227825Stheraven typename __node_base::pointer& __parent, const value_type& __v); 1040227825Stheraven template <class _Key> 1041227825Stheraven typename __node_base::pointer& 1042227825Stheraven __find_equal(typename __node_base::pointer& __parent, const _Key& __v); 1043227825Stheraven template <class _Key> 1044227825Stheraven typename __node_base::pointer& 1045227825Stheraven __find_equal(const_iterator __hint, typename __node_base::pointer& __parent, 1046227825Stheraven const _Key& __v); 1047227825Stheraven 1048227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1049227825Stheraven template <class ..._Args> 1050227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1051227825Stheraven#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1052227825Stheraven __node_holder __construct_node(const value_type& __v); 1053227825Stheraven#endif 1054227825Stheraven 1055227825Stheraven void destroy(__node_pointer __nd) _NOEXCEPT; 1056227825Stheraven 1057227825Stheraven _LIBCPP_INLINE_VISIBILITY 1058227825Stheraven void __copy_assign_alloc(const __tree& __t) 1059227825Stheraven {__copy_assign_alloc(__t, integral_constant<bool, 1060227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1061227825Stheraven 1062227825Stheraven _LIBCPP_INLINE_VISIBILITY 1063227825Stheraven void __copy_assign_alloc(const __tree& __t, true_type) 1064227825Stheraven {__node_alloc() = __t.__node_alloc();} 1065227825Stheraven _LIBCPP_INLINE_VISIBILITY 1066227825Stheraven void __copy_assign_alloc(const __tree& __t, false_type) {} 1067227825Stheraven 1068227825Stheraven void __move_assign(__tree& __t, false_type); 1069227825Stheraven void __move_assign(__tree& __t, true_type) 1070227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1071227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 1072227825Stheraven 1073227825Stheraven _LIBCPP_INLINE_VISIBILITY 1074227825Stheraven void __move_assign_alloc(__tree& __t) 1075227825Stheraven _NOEXCEPT_( 1076227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1077227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1078227825Stheraven {__move_assign_alloc(__t, integral_constant<bool, 1079227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1080227825Stheraven 1081227825Stheraven _LIBCPP_INLINE_VISIBILITY 1082227825Stheraven void __move_assign_alloc(__tree& __t, true_type) 1083227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1084227825Stheraven {__node_alloc() = _VSTD::move(__t.__node_alloc());} 1085227825Stheraven _LIBCPP_INLINE_VISIBILITY 1086227825Stheraven void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {} 1087227825Stheraven 1088227825Stheraven _LIBCPP_INLINE_VISIBILITY 1089227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 1090227825Stheraven _NOEXCEPT_( 1091227825Stheraven !__node_traits::propagate_on_container_swap::value || 1092227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 1093227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 1094227825Stheraven __node_traits::propagate_on_container_swap::value>());} 1095227825Stheraven _LIBCPP_INLINE_VISIBILITY 1096227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) 1097227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 1098227825Stheraven { 1099227825Stheraven using _VSTD::swap; 1100227825Stheraven swap(__x, __y); 1101227825Stheraven } 1102227825Stheraven _LIBCPP_INLINE_VISIBILITY 1103227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) 1104227825Stheraven _NOEXCEPT 1105227825Stheraven {} 1106227825Stheraven 1107227825Stheraven __node_pointer __detach(); 1108227825Stheraven static __node_pointer __detach(__node_pointer); 1109253159Stheraven 1110253159Stheraven template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map; 1111253159Stheraven template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap; 1112227825Stheraven}; 1113227825Stheraven 1114227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1115227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 1116227825Stheraven _NOEXCEPT_( 1117227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 1118227825Stheraven is_nothrow_copy_constructible<value_compare>::value) 1119227825Stheraven : __pair3_(0, __comp) 1120227825Stheraven{ 1121227825Stheraven __begin_node() = __end_node(); 1122227825Stheraven} 1123227825Stheraven 1124227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1125227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1126227825Stheraven : __pair1_(__node_allocator(__a)), 1127227825Stheraven __begin_node_(__node_pointer()), 1128227825Stheraven __pair3_(0) 1129227825Stheraven{ 1130227825Stheraven __begin_node() = __end_node(); 1131227825Stheraven} 1132227825Stheraven 1133227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1134227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 1135227825Stheraven const allocator_type& __a) 1136227825Stheraven : __pair1_(__node_allocator(__a)), 1137227825Stheraven __begin_node_(__node_pointer()), 1138227825Stheraven __pair3_(0, __comp) 1139227825Stheraven{ 1140227825Stheraven __begin_node() = __end_node(); 1141227825Stheraven} 1142227825Stheraven 1143227825Stheraven// Precondition: size() != 0 1144227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1145227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1146227825Stheraven__tree<_Tp, _Compare, _Allocator>::__detach() 1147227825Stheraven{ 1148227825Stheraven __node_pointer __cache = __begin_node(); 1149227825Stheraven __begin_node() = __end_node(); 1150227825Stheraven __end_node()->__left_->__parent_ = nullptr; 1151227825Stheraven __end_node()->__left_ = nullptr; 1152227825Stheraven size() = 0; 1153227825Stheraven // __cache->__left_ == nullptr 1154227825Stheraven if (__cache->__right_ != nullptr) 1155227825Stheraven __cache = static_cast<__node_pointer>(__cache->__right_); 1156227825Stheraven // __cache->__left_ == nullptr 1157227825Stheraven // __cache->__right_ == nullptr 1158227825Stheraven return __cache; 1159227825Stheraven} 1160227825Stheraven 1161227825Stheraven// Precondition: __cache != nullptr 1162227825Stheraven// __cache->left_ == nullptr 1163227825Stheraven// __cache->right_ == nullptr 1164227825Stheraven// This is no longer a red-black tree 1165227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1166227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1167227825Stheraven__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache) 1168227825Stheraven{ 1169227825Stheraven if (__cache->__parent_ == nullptr) 1170227825Stheraven return nullptr; 1171253159Stheraven if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 1172227825Stheraven { 1173227825Stheraven __cache->__parent_->__left_ = nullptr; 1174227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1175227825Stheraven if (__cache->__right_ == nullptr) 1176227825Stheraven return __cache; 1177227825Stheraven return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); 1178227825Stheraven } 1179227825Stheraven // __cache is right child 1180227825Stheraven __cache->__parent_->__right_ = nullptr; 1181227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1182227825Stheraven if (__cache->__left_ == nullptr) 1183227825Stheraven return __cache; 1184227825Stheraven return static_cast<__node_pointer>(__tree_leaf(__cache->__left_)); 1185227825Stheraven} 1186227825Stheraven 1187227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1188227825Stheraven__tree<_Tp, _Compare, _Allocator>& 1189227825Stheraven__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 1190227825Stheraven{ 1191227825Stheraven if (this != &__t) 1192227825Stheraven { 1193227825Stheraven value_comp() = __t.value_comp(); 1194227825Stheraven __copy_assign_alloc(__t); 1195227825Stheraven __assign_multi(__t.begin(), __t.end()); 1196227825Stheraven } 1197227825Stheraven return *this; 1198227825Stheraven} 1199227825Stheraven 1200227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1201227825Stheraventemplate <class _InputIterator> 1202227825Stheravenvoid 1203227825Stheraven__tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last) 1204227825Stheraven{ 1205227825Stheraven if (size() != 0) 1206227825Stheraven { 1207227825Stheraven __node_pointer __cache = __detach(); 1208227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1209227825Stheraven try 1210227825Stheraven { 1211227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1212227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1213227825Stheraven { 1214227825Stheraven __cache->__value_ = *__first; 1215227825Stheraven __node_pointer __next = __detach(__cache); 1216227825Stheraven __node_insert_unique(__cache); 1217227825Stheraven __cache = __next; 1218227825Stheraven } 1219227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1220227825Stheraven } 1221227825Stheraven catch (...) 1222227825Stheraven { 1223227825Stheraven while (__cache->__parent_ != nullptr) 1224227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1225227825Stheraven destroy(__cache); 1226227825Stheraven throw; 1227227825Stheraven } 1228227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1229227825Stheraven if (__cache != nullptr) 1230227825Stheraven { 1231227825Stheraven while (__cache->__parent_ != nullptr) 1232227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1233227825Stheraven destroy(__cache); 1234227825Stheraven } 1235227825Stheraven } 1236227825Stheraven for (; __first != __last; ++__first) 1237227825Stheraven __insert_unique(*__first); 1238227825Stheraven} 1239227825Stheraven 1240227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1241227825Stheraventemplate <class _InputIterator> 1242227825Stheravenvoid 1243227825Stheraven__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 1244227825Stheraven{ 1245227825Stheraven if (size() != 0) 1246227825Stheraven { 1247227825Stheraven __node_pointer __cache = __detach(); 1248227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1249227825Stheraven try 1250227825Stheraven { 1251227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1252227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1253227825Stheraven { 1254227825Stheraven __cache->__value_ = *__first; 1255227825Stheraven __node_pointer __next = __detach(__cache); 1256227825Stheraven __node_insert_multi(__cache); 1257227825Stheraven __cache = __next; 1258227825Stheraven } 1259227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1260227825Stheraven } 1261227825Stheraven catch (...) 1262227825Stheraven { 1263227825Stheraven while (__cache->__parent_ != nullptr) 1264227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1265227825Stheraven destroy(__cache); 1266227825Stheraven throw; 1267227825Stheraven } 1268227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1269227825Stheraven if (__cache != nullptr) 1270227825Stheraven { 1271227825Stheraven while (__cache->__parent_ != nullptr) 1272227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1273227825Stheraven destroy(__cache); 1274227825Stheraven } 1275227825Stheraven } 1276227825Stheraven for (; __first != __last; ++__first) 1277227825Stheraven __insert_multi(*__first); 1278227825Stheraven} 1279227825Stheraven 1280227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1281227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1282227825Stheraven : __begin_node_(__node_pointer()), 1283227825Stheraven __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1284227825Stheraven __pair3_(0, __t.value_comp()) 1285227825Stheraven{ 1286227825Stheraven __begin_node() = __end_node(); 1287227825Stheraven} 1288227825Stheraven 1289227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1290227825Stheraven 1291227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1292227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 1293227825Stheraven _NOEXCEPT_( 1294227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 1295227825Stheraven is_nothrow_move_constructible<value_compare>::value) 1296227825Stheraven : __begin_node_(_VSTD::move(__t.__begin_node_)), 1297227825Stheraven __pair1_(_VSTD::move(__t.__pair1_)), 1298227825Stheraven __pair3_(_VSTD::move(__t.__pair3_)) 1299227825Stheraven{ 1300227825Stheraven if (size() == 0) 1301227825Stheraven __begin_node() = __end_node(); 1302227825Stheraven else 1303227825Stheraven { 1304253159Stheraven __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1305227825Stheraven __t.__begin_node() = __t.__end_node(); 1306227825Stheraven __t.__end_node()->__left_ = nullptr; 1307227825Stheraven __t.size() = 0; 1308227825Stheraven } 1309227825Stheraven} 1310227825Stheraven 1311227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1312227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1313227825Stheraven : __pair1_(__node_allocator(__a)), 1314227825Stheraven __pair3_(0, _VSTD::move(__t.value_comp())) 1315227825Stheraven{ 1316227825Stheraven if (__a == __t.__alloc()) 1317227825Stheraven { 1318227825Stheraven if (__t.size() == 0) 1319227825Stheraven __begin_node() = __end_node(); 1320227825Stheraven else 1321227825Stheraven { 1322227825Stheraven __begin_node() = __t.__begin_node(); 1323227825Stheraven __end_node()->__left_ = __t.__end_node()->__left_; 1324253159Stheraven __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1325227825Stheraven size() = __t.size(); 1326227825Stheraven __t.__begin_node() = __t.__end_node(); 1327227825Stheraven __t.__end_node()->__left_ = nullptr; 1328227825Stheraven __t.size() = 0; 1329227825Stheraven } 1330227825Stheraven } 1331227825Stheraven else 1332227825Stheraven { 1333227825Stheraven __begin_node() = __end_node(); 1334227825Stheraven } 1335227825Stheraven} 1336227825Stheraven 1337227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1338227825Stheravenvoid 1339227825Stheraven__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1340227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1341227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1342227825Stheraven{ 1343227825Stheraven destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1344227825Stheraven __begin_node_ = __t.__begin_node_; 1345227825Stheraven __pair1_.first() = __t.__pair1_.first(); 1346227825Stheraven __move_assign_alloc(__t); 1347227825Stheraven __pair3_ = _VSTD::move(__t.__pair3_); 1348227825Stheraven if (size() == 0) 1349227825Stheraven __begin_node() = __end_node(); 1350227825Stheraven else 1351227825Stheraven { 1352253159Stheraven __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1353227825Stheraven __t.__begin_node() = __t.__end_node(); 1354227825Stheraven __t.__end_node()->__left_ = nullptr; 1355227825Stheraven __t.size() = 0; 1356227825Stheraven } 1357227825Stheraven} 1358227825Stheraven 1359227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1360227825Stheravenvoid 1361227825Stheraven__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 1362227825Stheraven{ 1363227825Stheraven if (__node_alloc() == __t.__node_alloc()) 1364227825Stheraven __move_assign(__t, true_type()); 1365227825Stheraven else 1366227825Stheraven { 1367227825Stheraven value_comp() = _VSTD::move(__t.value_comp()); 1368227825Stheraven const_iterator __e = end(); 1369227825Stheraven if (size() != 0) 1370227825Stheraven { 1371227825Stheraven __node_pointer __cache = __detach(); 1372227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1373227825Stheraven try 1374227825Stheraven { 1375227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1376227825Stheraven while (__cache != nullptr && __t.size() != 0) 1377227825Stheraven { 1378227825Stheraven __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 1379227825Stheraven __node_pointer __next = __detach(__cache); 1380227825Stheraven __node_insert_multi(__cache); 1381227825Stheraven __cache = __next; 1382227825Stheraven } 1383227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1384227825Stheraven } 1385227825Stheraven catch (...) 1386227825Stheraven { 1387227825Stheraven while (__cache->__parent_ != nullptr) 1388227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1389227825Stheraven destroy(__cache); 1390227825Stheraven throw; 1391227825Stheraven } 1392227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1393227825Stheraven if (__cache != nullptr) 1394227825Stheraven { 1395227825Stheraven while (__cache->__parent_ != nullptr) 1396227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1397227825Stheraven destroy(__cache); 1398227825Stheraven } 1399227825Stheraven } 1400227825Stheraven while (__t.size() != 0) 1401227825Stheraven __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_)); 1402227825Stheraven } 1403227825Stheraven} 1404227825Stheraven 1405227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1406227825Stheraven__tree<_Tp, _Compare, _Allocator>& 1407227825Stheraven__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 1408227825Stheraven _NOEXCEPT_( 1409227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1410227825Stheraven is_nothrow_move_assignable<value_compare>::value && 1411227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1412227825Stheraven 1413227825Stheraven{ 1414227825Stheraven __move_assign(__t, integral_constant<bool, 1415227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1416227825Stheraven return *this; 1417227825Stheraven} 1418227825Stheraven 1419227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1420227825Stheraven 1421227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1422227825Stheraven__tree<_Tp, _Compare, _Allocator>::~__tree() 1423227825Stheraven{ 1424227825Stheraven destroy(__root()); 1425227825Stheraven} 1426227825Stheraven 1427227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1428227825Stheravenvoid 1429227825Stheraven__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 1430227825Stheraven{ 1431227825Stheraven if (__nd != nullptr) 1432227825Stheraven { 1433227825Stheraven destroy(static_cast<__node_pointer>(__nd->__left_)); 1434227825Stheraven destroy(static_cast<__node_pointer>(__nd->__right_)); 1435227825Stheraven __node_allocator& __na = __node_alloc(); 1436227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_)); 1437227825Stheraven __node_traits::deallocate(__na, __nd, 1); 1438227825Stheraven } 1439227825Stheraven} 1440227825Stheraven 1441227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1442227825Stheravenvoid 1443227825Stheraven__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1444227825Stheraven _NOEXCEPT_( 1445227825Stheraven __is_nothrow_swappable<value_compare>::value && 1446227825Stheraven (!__node_traits::propagate_on_container_swap::value || 1447227825Stheraven __is_nothrow_swappable<__node_allocator>::value)) 1448227825Stheraven{ 1449227825Stheraven using _VSTD::swap; 1450227825Stheraven swap(__begin_node_, __t.__begin_node_); 1451227825Stheraven swap(__pair1_.first(), __t.__pair1_.first()); 1452227825Stheraven __swap_alloc(__node_alloc(), __t.__node_alloc()); 1453227825Stheraven __pair3_.swap(__t.__pair3_); 1454227825Stheraven if (size() == 0) 1455227825Stheraven __begin_node() = __end_node(); 1456227825Stheraven else 1457253159Stheraven __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1458227825Stheraven if (__t.size() == 0) 1459227825Stheraven __t.__begin_node() = __t.__end_node(); 1460227825Stheraven else 1461253159Stheraven __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node()); 1462227825Stheraven} 1463227825Stheraven 1464227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1465227825Stheravenvoid 1466227825Stheraven__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 1467227825Stheraven{ 1468227825Stheraven destroy(__root()); 1469227825Stheraven size() = 0; 1470227825Stheraven __begin_node() = __end_node(); 1471227825Stheraven __end_node()->__left_ = nullptr; 1472227825Stheraven} 1473227825Stheraven 1474227825Stheraven// Find lower_bound place to insert 1475227825Stheraven// Set __parent to parent of null leaf 1476227825Stheraven// Return reference to null leaf 1477227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1478227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1479227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent, 1480227825Stheraven const value_type& __v) 1481227825Stheraven{ 1482227825Stheraven __node_pointer __nd = __root(); 1483227825Stheraven if (__nd != nullptr) 1484227825Stheraven { 1485227825Stheraven while (true) 1486227825Stheraven { 1487227825Stheraven if (value_comp()(__nd->__value_, __v)) 1488227825Stheraven { 1489227825Stheraven if (__nd->__right_ != nullptr) 1490227825Stheraven __nd = static_cast<__node_pointer>(__nd->__right_); 1491227825Stheraven else 1492227825Stheraven { 1493253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1494227825Stheraven return __parent->__right_; 1495227825Stheraven } 1496227825Stheraven } 1497227825Stheraven else 1498227825Stheraven { 1499227825Stheraven if (__nd->__left_ != nullptr) 1500227825Stheraven __nd = static_cast<__node_pointer>(__nd->__left_); 1501227825Stheraven else 1502227825Stheraven { 1503253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1504227825Stheraven return __parent->__left_; 1505227825Stheraven } 1506227825Stheraven } 1507227825Stheraven } 1508227825Stheraven } 1509253159Stheraven __parent = static_cast<__node_base_pointer>(__end_node()); 1510227825Stheraven return __parent->__left_; 1511227825Stheraven} 1512227825Stheraven 1513227825Stheraven// Find upper_bound place to insert 1514227825Stheraven// Set __parent to parent of null leaf 1515227825Stheraven// Return reference to null leaf 1516227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1517227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1518227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent, 1519227825Stheraven const value_type& __v) 1520227825Stheraven{ 1521227825Stheraven __node_pointer __nd = __root(); 1522227825Stheraven if (__nd != nullptr) 1523227825Stheraven { 1524227825Stheraven while (true) 1525227825Stheraven { 1526227825Stheraven if (value_comp()(__v, __nd->__value_)) 1527227825Stheraven { 1528227825Stheraven if (__nd->__left_ != nullptr) 1529227825Stheraven __nd = static_cast<__node_pointer>(__nd->__left_); 1530227825Stheraven else 1531227825Stheraven { 1532253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1533227825Stheraven return __parent->__left_; 1534227825Stheraven } 1535227825Stheraven } 1536227825Stheraven else 1537227825Stheraven { 1538227825Stheraven if (__nd->__right_ != nullptr) 1539227825Stheraven __nd = static_cast<__node_pointer>(__nd->__right_); 1540227825Stheraven else 1541227825Stheraven { 1542253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1543227825Stheraven return __parent->__right_; 1544227825Stheraven } 1545227825Stheraven } 1546227825Stheraven } 1547227825Stheraven } 1548253159Stheraven __parent = static_cast<__node_base_pointer>(__end_node()); 1549227825Stheraven return __parent->__left_; 1550227825Stheraven} 1551227825Stheraven 1552227825Stheraven// Find leaf place to insert closest to __hint 1553227825Stheraven// First check prior to __hint. 1554227825Stheraven// Next check after __hint. 1555227825Stheraven// Next do O(log N) search. 1556227825Stheraven// Set __parent to parent of null leaf 1557227825Stheraven// Return reference to null leaf 1558227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1559227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1560227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 1561227825Stheraven typename __node_base::pointer& __parent, 1562227825Stheraven const value_type& __v) 1563227825Stheraven{ 1564227825Stheraven if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1565227825Stheraven { 1566227825Stheraven // __v <= *__hint 1567227825Stheraven const_iterator __prior = __hint; 1568227825Stheraven if (__prior == begin() || !value_comp()(__v, *--__prior)) 1569227825Stheraven { 1570227825Stheraven // *prev(__hint) <= __v <= *__hint 1571227825Stheraven if (__hint.__ptr_->__left_ == nullptr) 1572227825Stheraven { 1573253159Stheraven __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1574227825Stheraven return __parent->__left_; 1575227825Stheraven } 1576227825Stheraven else 1577227825Stheraven { 1578253159Stheraven __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1579227825Stheraven return __parent->__right_; 1580227825Stheraven } 1581227825Stheraven } 1582227825Stheraven // __v < *prev(__hint) 1583227825Stheraven return __find_leaf_high(__parent, __v); 1584227825Stheraven } 1585227825Stheraven // else __v > *__hint 1586227825Stheraven return __find_leaf_low(__parent, __v); 1587227825Stheraven} 1588227825Stheraven 1589227825Stheraven// Find place to insert if __v doesn't exist 1590227825Stheraven// Set __parent to parent of null leaf 1591227825Stheraven// Return reference to null leaf 1592227825Stheraven// If __v exists, set parent to node of __v and return reference to node of __v 1593227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1594227825Stheraventemplate <class _Key> 1595227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1596227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent, 1597227825Stheraven const _Key& __v) 1598227825Stheraven{ 1599227825Stheraven __node_pointer __nd = __root(); 1600227825Stheraven if (__nd != nullptr) 1601227825Stheraven { 1602227825Stheraven while (true) 1603227825Stheraven { 1604227825Stheraven if (value_comp()(__v, __nd->__value_)) 1605227825Stheraven { 1606227825Stheraven if (__nd->__left_ != nullptr) 1607227825Stheraven __nd = static_cast<__node_pointer>(__nd->__left_); 1608227825Stheraven else 1609227825Stheraven { 1610253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1611227825Stheraven return __parent->__left_; 1612227825Stheraven } 1613227825Stheraven } 1614227825Stheraven else if (value_comp()(__nd->__value_, __v)) 1615227825Stheraven { 1616227825Stheraven if (__nd->__right_ != nullptr) 1617227825Stheraven __nd = static_cast<__node_pointer>(__nd->__right_); 1618227825Stheraven else 1619227825Stheraven { 1620253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1621227825Stheraven return __parent->__right_; 1622227825Stheraven } 1623227825Stheraven } 1624227825Stheraven else 1625227825Stheraven { 1626253159Stheraven __parent = static_cast<__node_base_pointer>(__nd); 1627227825Stheraven return __parent; 1628227825Stheraven } 1629227825Stheraven } 1630227825Stheraven } 1631253159Stheraven __parent = static_cast<__node_base_pointer>(__end_node()); 1632227825Stheraven return __parent->__left_; 1633227825Stheraven} 1634227825Stheraven 1635227825Stheraven// Find place to insert if __v doesn't exist 1636227825Stheraven// First check prior to __hint. 1637227825Stheraven// Next check after __hint. 1638227825Stheraven// Next do O(log N) search. 1639227825Stheraven// Set __parent to parent of null leaf 1640227825Stheraven// Return reference to null leaf 1641227825Stheraven// If __v exists, set parent to node of __v and return reference to node of __v 1642227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1643227825Stheraventemplate <class _Key> 1644227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1645227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, 1646227825Stheraven typename __node_base::pointer& __parent, 1647227825Stheraven const _Key& __v) 1648227825Stheraven{ 1649227825Stheraven if (__hint == end() || value_comp()(__v, *__hint)) // check before 1650227825Stheraven { 1651227825Stheraven // __v < *__hint 1652227825Stheraven const_iterator __prior = __hint; 1653227825Stheraven if (__prior == begin() || value_comp()(*--__prior, __v)) 1654227825Stheraven { 1655227825Stheraven // *prev(__hint) < __v < *__hint 1656227825Stheraven if (__hint.__ptr_->__left_ == nullptr) 1657227825Stheraven { 1658253159Stheraven __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1659227825Stheraven return __parent->__left_; 1660227825Stheraven } 1661227825Stheraven else 1662227825Stheraven { 1663253159Stheraven __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1664227825Stheraven return __parent->__right_; 1665227825Stheraven } 1666227825Stheraven } 1667227825Stheraven // __v <= *prev(__hint) 1668227825Stheraven return __find_equal(__parent, __v); 1669227825Stheraven } 1670227825Stheraven else if (value_comp()(*__hint, __v)) // check after 1671227825Stheraven { 1672227825Stheraven // *__hint < __v 1673227825Stheraven const_iterator __next = _VSTD::next(__hint); 1674227825Stheraven if (__next == end() || value_comp()(__v, *__next)) 1675227825Stheraven { 1676227825Stheraven // *__hint < __v < *_VSTD::next(__hint) 1677227825Stheraven if (__hint.__ptr_->__right_ == nullptr) 1678227825Stheraven { 1679253159Stheraven __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1680227825Stheraven return __parent->__right_; 1681227825Stheraven } 1682227825Stheraven else 1683227825Stheraven { 1684253159Stheraven __parent = static_cast<__node_base_pointer>(__next.__ptr_); 1685227825Stheraven return __parent->__left_; 1686227825Stheraven } 1687227825Stheraven } 1688227825Stheraven // *next(__hint) <= __v 1689227825Stheraven return __find_equal(__parent, __v); 1690227825Stheraven } 1691227825Stheraven // else __v == *__hint 1692253159Stheraven __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1693227825Stheraven return __parent; 1694227825Stheraven} 1695227825Stheraven 1696227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1697227825Stheravenvoid 1698227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent, 1699227825Stheraven __node_base_pointer& __child, 1700227825Stheraven __node_base_pointer __new_node) 1701227825Stheraven{ 1702227825Stheraven __new_node->__left_ = nullptr; 1703227825Stheraven __new_node->__right_ = nullptr; 1704227825Stheraven __new_node->__parent_ = __parent; 1705227825Stheraven __child = __new_node; 1706227825Stheraven if (__begin_node()->__left_ != nullptr) 1707227825Stheraven __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_); 1708227825Stheraven __tree_balance_after_insert(__end_node()->__left_, __child); 1709227825Stheraven ++size(); 1710227825Stheraven} 1711227825Stheraven 1712227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1713227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1714227825Stheraven 1715227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1716227825Stheraventemplate <class ..._Args> 1717227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_holder 1718227825Stheraven__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 1719227825Stheraven{ 1720227825Stheraven __node_allocator& __na = __node_alloc(); 1721232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1722227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1723227825Stheraven __h.get_deleter().__value_constructed = true; 1724227825Stheraven return __h; 1725227825Stheraven} 1726227825Stheraven 1727227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1728227825Stheraventemplate <class... _Args> 1729227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1730227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args) 1731227825Stheraven{ 1732227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1733227825Stheraven __node_base_pointer __parent; 1734227825Stheraven __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 1735227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1736227825Stheraven bool __inserted = false; 1737227825Stheraven if (__child == nullptr) 1738227825Stheraven { 1739253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1740227825Stheraven __r = __h.release(); 1741227825Stheraven __inserted = true; 1742227825Stheraven } 1743227825Stheraven return pair<iterator, bool>(iterator(__r), __inserted); 1744227825Stheraven} 1745227825Stheraven 1746227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1747227825Stheraventemplate <class... _Args> 1748227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1749227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args) 1750227825Stheraven{ 1751227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1752227825Stheraven __node_base_pointer __parent; 1753227825Stheraven __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_); 1754227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1755227825Stheraven if (__child == nullptr) 1756227825Stheraven { 1757253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1758227825Stheraven __r = __h.release(); 1759227825Stheraven } 1760227825Stheraven return iterator(__r); 1761227825Stheraven} 1762227825Stheraven 1763227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1764227825Stheraventemplate <class... _Args> 1765227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1766227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 1767227825Stheraven{ 1768227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1769227825Stheraven __node_base_pointer __parent; 1770227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1771253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1772227825Stheraven return iterator(static_cast<__node_pointer>(__h.release())); 1773227825Stheraven} 1774227825Stheraven 1775227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1776227825Stheraventemplate <class... _Args> 1777227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1778227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 1779227825Stheraven _Args&&... __args) 1780227825Stheraven{ 1781227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1782227825Stheraven __node_base_pointer __parent; 1783227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1784253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1785227825Stheraven return iterator(static_cast<__node_pointer>(__h.release())); 1786227825Stheraven} 1787227825Stheraven 1788227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1789227825Stheraven 1790227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1791232950Stheraventemplate <class _Vp> 1792227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1793232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) 1794227825Stheraven{ 1795232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1796227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1797227825Stheraven if (__r.second) 1798227825Stheraven __h.release(); 1799227825Stheraven return __r; 1800227825Stheraven} 1801227825Stheraven 1802227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1803232950Stheraventemplate <class _Vp> 1804227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1805232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v) 1806227825Stheraven{ 1807232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1808227825Stheraven iterator __r = __node_insert_unique(__p, __h.get()); 1809227825Stheraven if (__r.__ptr_ == __h.get()) 1810227825Stheraven __h.release(); 1811227825Stheraven return __r; 1812227825Stheraven} 1813227825Stheraven 1814227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1815232950Stheraventemplate <class _Vp> 1816227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1817232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) 1818227825Stheraven{ 1819232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1820227825Stheraven __node_base_pointer __parent; 1821227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1822253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1823227825Stheraven return iterator(__h.release()); 1824227825Stheraven} 1825227825Stheraven 1826227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1827232950Stheraventemplate <class _Vp> 1828227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1829232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v) 1830227825Stheraven{ 1831232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1832227825Stheraven __node_base_pointer __parent; 1833227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1834253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1835227825Stheraven return iterator(__h.release()); 1836227825Stheraven} 1837227825Stheraven 1838227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1839227825Stheraven 1840227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1841227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_holder 1842227825Stheraven__tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v) 1843227825Stheraven{ 1844227825Stheraven __node_allocator& __na = __node_alloc(); 1845232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1846227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1847227825Stheraven __h.get_deleter().__value_constructed = true; 1848227825Stheraven return _VSTD::move(__h); 1849227825Stheraven} 1850227825Stheraven 1851227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1852227825Stheraven 1853227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1854227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1855227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v) 1856227825Stheraven{ 1857227825Stheraven __node_base_pointer __parent; 1858227825Stheraven __node_base_pointer& __child = __find_equal(__parent, __v); 1859227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1860227825Stheraven bool __inserted = false; 1861227825Stheraven if (__child == nullptr) 1862227825Stheraven { 1863227825Stheraven __node_holder __h = __construct_node(__v); 1864253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1865227825Stheraven __r = __h.release(); 1866227825Stheraven __inserted = true; 1867227825Stheraven } 1868227825Stheraven return pair<iterator, bool>(iterator(__r), __inserted); 1869227825Stheraven} 1870227825Stheraven 1871227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1872227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1873227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v) 1874227825Stheraven{ 1875227825Stheraven __node_base_pointer __parent; 1876227825Stheraven __node_base_pointer& __child = __find_equal(__p, __parent, __v); 1877227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1878227825Stheraven if (__child == nullptr) 1879227825Stheraven { 1880227825Stheraven __node_holder __h = __construct_node(__v); 1881253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1882227825Stheraven __r = __h.release(); 1883227825Stheraven } 1884227825Stheraven return iterator(__r); 1885227825Stheraven} 1886227825Stheraven 1887227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1888227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1889227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v) 1890227825Stheraven{ 1891227825Stheraven __node_base_pointer __parent; 1892227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __v); 1893227825Stheraven __node_holder __h = __construct_node(__v); 1894253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1895227825Stheraven return iterator(__h.release()); 1896227825Stheraven} 1897227825Stheraven 1898227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1899227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1900227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v) 1901227825Stheraven{ 1902227825Stheraven __node_base_pointer __parent; 1903227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __v); 1904227825Stheraven __node_holder __h = __construct_node(__v); 1905253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1906227825Stheraven return iterator(__h.release()); 1907227825Stheraven} 1908227825Stheraven 1909227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1910227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1911227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd) 1912227825Stheraven{ 1913227825Stheraven __node_base_pointer __parent; 1914227825Stheraven __node_base_pointer& __child = __find_equal(__parent, __nd->__value_); 1915227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1916227825Stheraven bool __inserted = false; 1917227825Stheraven if (__child == nullptr) 1918227825Stheraven { 1919253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1920227825Stheraven __r = __nd; 1921227825Stheraven __inserted = true; 1922227825Stheraven } 1923227825Stheraven return pair<iterator, bool>(iterator(__r), __inserted); 1924227825Stheraven} 1925227825Stheraven 1926227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1927227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1928227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p, 1929227825Stheraven __node_pointer __nd) 1930227825Stheraven{ 1931227825Stheraven __node_base_pointer __parent; 1932227825Stheraven __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_); 1933227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1934227825Stheraven if (__child == nullptr) 1935227825Stheraven { 1936253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1937227825Stheraven __r = __nd; 1938227825Stheraven } 1939227825Stheraven return iterator(__r); 1940227825Stheraven} 1941227825Stheraven 1942227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1943227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1944227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) 1945227825Stheraven{ 1946227825Stheraven __node_base_pointer __parent; 1947227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_); 1948253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1949227825Stheraven return iterator(__nd); 1950227825Stheraven} 1951227825Stheraven 1952227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1953227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1954227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, 1955227825Stheraven __node_pointer __nd) 1956227825Stheraven{ 1957227825Stheraven __node_base_pointer __parent; 1958227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_); 1959253159Stheraven __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1960227825Stheraven return iterator(__nd); 1961227825Stheraven} 1962227825Stheraven 1963227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1964227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1965227825Stheraven__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) 1966227825Stheraven{ 1967253159Stheraven __node_pointer __np = __p.__ptr_; 1968227825Stheraven iterator __r(__np); 1969227825Stheraven ++__r; 1970227825Stheraven if (__begin_node() == __np) 1971227825Stheraven __begin_node() = __r.__ptr_; 1972227825Stheraven --size(); 1973227825Stheraven __node_allocator& __na = __node_alloc(); 1974227825Stheraven __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p))); 1975227825Stheraven __tree_remove(__end_node()->__left_, 1976227825Stheraven static_cast<__node_base_pointer>(__np)); 1977227825Stheraven __node_traits::deallocate(__na, __np, 1); 1978227825Stheraven return __r; 1979227825Stheraven} 1980227825Stheraven 1981227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1982227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1983227825Stheraven__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) 1984227825Stheraven{ 1985227825Stheraven while (__f != __l) 1986227825Stheraven __f = erase(__f); 1987253159Stheraven return iterator(__l.__ptr_); 1988227825Stheraven} 1989227825Stheraven 1990227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1991227825Stheraventemplate <class _Key> 1992227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 1993227825Stheraven__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) 1994227825Stheraven{ 1995227825Stheraven iterator __i = find(__k); 1996227825Stheraven if (__i == end()) 1997227825Stheraven return 0; 1998227825Stheraven erase(__i); 1999227825Stheraven return 1; 2000227825Stheraven} 2001227825Stheraven 2002227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2003227825Stheraventemplate <class _Key> 2004227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2005227825Stheraven__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) 2006227825Stheraven{ 2007227825Stheraven pair<iterator, iterator> __p = __equal_range_multi(__k); 2008227825Stheraven size_type __r = 0; 2009227825Stheraven for (; __p.first != __p.second; ++__r) 2010227825Stheraven __p.first = erase(__p.first); 2011227825Stheraven return __r; 2012227825Stheraven} 2013227825Stheraven 2014227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2015227825Stheraventemplate <class _Key> 2016227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 2017227825Stheraven__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) 2018227825Stheraven{ 2019227825Stheraven iterator __p = __lower_bound(__v, __root(), __end_node()); 2020227825Stheraven if (__p != end() && !value_comp()(__v, *__p)) 2021227825Stheraven return __p; 2022227825Stheraven return end(); 2023227825Stheraven} 2024227825Stheraven 2025227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2026227825Stheraventemplate <class _Key> 2027227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2028227825Stheraven__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const 2029227825Stheraven{ 2030227825Stheraven const_iterator __p = __lower_bound(__v, __root(), __end_node()); 2031227825Stheraven if (__p != end() && !value_comp()(__v, *__p)) 2032227825Stheraven return __p; 2033227825Stheraven return end(); 2034227825Stheraven} 2035227825Stheraven 2036227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2037227825Stheraventemplate <class _Key> 2038227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2039227825Stheraven__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const 2040227825Stheraven{ 2041227825Stheraven __node_const_pointer __result = __end_node(); 2042227825Stheraven __node_const_pointer __rt = __root(); 2043227825Stheraven while (__rt != nullptr) 2044227825Stheraven { 2045227825Stheraven if (value_comp()(__k, __rt->__value_)) 2046227825Stheraven { 2047227825Stheraven __result = __rt; 2048227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2049227825Stheraven } 2050227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2051227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2052227825Stheraven else 2053227825Stheraven return 1; 2054227825Stheraven } 2055227825Stheraven return 0; 2056227825Stheraven} 2057227825Stheraven 2058227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2059227825Stheraventemplate <class _Key> 2060227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2061227825Stheraven__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const 2062227825Stheraven{ 2063232950Stheraven typedef pair<const_iterator, const_iterator> _Pp; 2064227825Stheraven __node_const_pointer __result = __end_node(); 2065227825Stheraven __node_const_pointer __rt = __root(); 2066227825Stheraven while (__rt != nullptr) 2067227825Stheraven { 2068227825Stheraven if (value_comp()(__k, __rt->__value_)) 2069227825Stheraven { 2070227825Stheraven __result = __rt; 2071227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2072227825Stheraven } 2073227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2074227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2075227825Stheraven else 2076227825Stheraven return _VSTD::distance( 2077227825Stheraven __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2078227825Stheraven __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result) 2079227825Stheraven ); 2080227825Stheraven } 2081227825Stheraven return 0; 2082227825Stheraven} 2083227825Stheraven 2084227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2085227825Stheraventemplate <class _Key> 2086227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 2087227825Stheraven__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2088227825Stheraven __node_pointer __root, 2089227825Stheraven __node_pointer __result) 2090227825Stheraven{ 2091227825Stheraven while (__root != nullptr) 2092227825Stheraven { 2093227825Stheraven if (!value_comp()(__root->__value_, __v)) 2094227825Stheraven { 2095227825Stheraven __result = __root; 2096227825Stheraven __root = static_cast<__node_pointer>(__root->__left_); 2097227825Stheraven } 2098227825Stheraven else 2099227825Stheraven __root = static_cast<__node_pointer>(__root->__right_); 2100227825Stheraven } 2101227825Stheraven return iterator(__result); 2102227825Stheraven} 2103227825Stheraven 2104227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2105227825Stheraventemplate <class _Key> 2106227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2107227825Stheraven__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2108227825Stheraven __node_const_pointer __root, 2109227825Stheraven __node_const_pointer __result) const 2110227825Stheraven{ 2111227825Stheraven while (__root != nullptr) 2112227825Stheraven { 2113227825Stheraven if (!value_comp()(__root->__value_, __v)) 2114227825Stheraven { 2115227825Stheraven __result = __root; 2116227825Stheraven __root = static_cast<__node_const_pointer>(__root->__left_); 2117227825Stheraven } 2118227825Stheraven else 2119227825Stheraven __root = static_cast<__node_const_pointer>(__root->__right_); 2120227825Stheraven } 2121227825Stheraven return const_iterator(__result); 2122227825Stheraven} 2123227825Stheraven 2124227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2125227825Stheraventemplate <class _Key> 2126227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 2127227825Stheraven__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2128227825Stheraven __node_pointer __root, 2129227825Stheraven __node_pointer __result) 2130227825Stheraven{ 2131227825Stheraven while (__root != nullptr) 2132227825Stheraven { 2133227825Stheraven if (value_comp()(__v, __root->__value_)) 2134227825Stheraven { 2135227825Stheraven __result = __root; 2136227825Stheraven __root = static_cast<__node_pointer>(__root->__left_); 2137227825Stheraven } 2138227825Stheraven else 2139227825Stheraven __root = static_cast<__node_pointer>(__root->__right_); 2140227825Stheraven } 2141227825Stheraven return iterator(__result); 2142227825Stheraven} 2143227825Stheraven 2144227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2145227825Stheraventemplate <class _Key> 2146227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2147227825Stheraven__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2148227825Stheraven __node_const_pointer __root, 2149227825Stheraven __node_const_pointer __result) const 2150227825Stheraven{ 2151227825Stheraven while (__root != nullptr) 2152227825Stheraven { 2153227825Stheraven if (value_comp()(__v, __root->__value_)) 2154227825Stheraven { 2155227825Stheraven __result = __root; 2156227825Stheraven __root = static_cast<__node_const_pointer>(__root->__left_); 2157227825Stheraven } 2158227825Stheraven else 2159227825Stheraven __root = static_cast<__node_const_pointer>(__root->__right_); 2160227825Stheraven } 2161227825Stheraven return const_iterator(__result); 2162227825Stheraven} 2163227825Stheraven 2164227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2165227825Stheraventemplate <class _Key> 2166227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2167227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::iterator> 2168227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 2169227825Stheraven{ 2170232950Stheraven typedef pair<iterator, iterator> _Pp; 2171227825Stheraven __node_pointer __result = __end_node(); 2172227825Stheraven __node_pointer __rt = __root(); 2173227825Stheraven while (__rt != nullptr) 2174227825Stheraven { 2175227825Stheraven if (value_comp()(__k, __rt->__value_)) 2176227825Stheraven { 2177227825Stheraven __result = __rt; 2178227825Stheraven __rt = static_cast<__node_pointer>(__rt->__left_); 2179227825Stheraven } 2180227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2181227825Stheraven __rt = static_cast<__node_pointer>(__rt->__right_); 2182227825Stheraven else 2183232950Stheraven return _Pp(iterator(__rt), 2184227825Stheraven iterator( 2185227825Stheraven __rt->__right_ != nullptr ? 2186227825Stheraven static_cast<__node_pointer>(__tree_min(__rt->__right_)) 2187227825Stheraven : __result)); 2188227825Stheraven } 2189232950Stheraven return _Pp(iterator(__result), iterator(__result)); 2190227825Stheraven} 2191227825Stheraven 2192227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2193227825Stheraventemplate <class _Key> 2194227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2195227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2196227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 2197227825Stheraven{ 2198232950Stheraven typedef pair<const_iterator, const_iterator> _Pp; 2199227825Stheraven __node_const_pointer __result = __end_node(); 2200227825Stheraven __node_const_pointer __rt = __root(); 2201227825Stheraven while (__rt != nullptr) 2202227825Stheraven { 2203227825Stheraven if (value_comp()(__k, __rt->__value_)) 2204227825Stheraven { 2205227825Stheraven __result = __rt; 2206227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2207227825Stheraven } 2208227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2209227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2210227825Stheraven else 2211232950Stheraven return _Pp(const_iterator(__rt), 2212227825Stheraven const_iterator( 2213227825Stheraven __rt->__right_ != nullptr ? 2214227825Stheraven static_cast<__node_const_pointer>(__tree_min(__rt->__right_)) 2215227825Stheraven : __result)); 2216227825Stheraven } 2217232950Stheraven return _Pp(const_iterator(__result), const_iterator(__result)); 2218227825Stheraven} 2219227825Stheraven 2220227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2221227825Stheraventemplate <class _Key> 2222227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2223227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::iterator> 2224227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 2225227825Stheraven{ 2226232950Stheraven typedef pair<iterator, iterator> _Pp; 2227227825Stheraven __node_pointer __result = __end_node(); 2228227825Stheraven __node_pointer __rt = __root(); 2229227825Stheraven while (__rt != nullptr) 2230227825Stheraven { 2231227825Stheraven if (value_comp()(__k, __rt->__value_)) 2232227825Stheraven { 2233227825Stheraven __result = __rt; 2234227825Stheraven __rt = static_cast<__node_pointer>(__rt->__left_); 2235227825Stheraven } 2236227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2237227825Stheraven __rt = static_cast<__node_pointer>(__rt->__right_); 2238227825Stheraven else 2239232950Stheraven return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt), 2240227825Stheraven __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2241227825Stheraven } 2242232950Stheraven return _Pp(iterator(__result), iterator(__result)); 2243227825Stheraven} 2244227825Stheraven 2245227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2246227825Stheraventemplate <class _Key> 2247227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2248227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2249227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 2250227825Stheraven{ 2251232950Stheraven typedef pair<const_iterator, const_iterator> _Pp; 2252227825Stheraven __node_const_pointer __result = __end_node(); 2253227825Stheraven __node_const_pointer __rt = __root(); 2254227825Stheraven while (__rt != nullptr) 2255227825Stheraven { 2256227825Stheraven if (value_comp()(__k, __rt->__value_)) 2257227825Stheraven { 2258227825Stheraven __result = __rt; 2259227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2260227825Stheraven } 2261227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2262227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2263227825Stheraven else 2264232950Stheraven return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2265227825Stheraven __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)); 2266227825Stheraven } 2267232950Stheraven return _Pp(const_iterator(__result), const_iterator(__result)); 2268227825Stheraven} 2269227825Stheraven 2270227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2271227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_holder 2272227825Stheraven__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 2273227825Stheraven{ 2274253159Stheraven __node_pointer __np = __p.__ptr_; 2275227825Stheraven if (__begin_node() == __np) 2276227825Stheraven { 2277227825Stheraven if (__np->__right_ != nullptr) 2278227825Stheraven __begin_node() = static_cast<__node_pointer>(__np->__right_); 2279227825Stheraven else 2280227825Stheraven __begin_node() = static_cast<__node_pointer>(__np->__parent_); 2281227825Stheraven } 2282227825Stheraven --size(); 2283227825Stheraven __tree_remove(__end_node()->__left_, 2284227825Stheraven static_cast<__node_base_pointer>(__np)); 2285232950Stheraven return __node_holder(__np, _Dp(__node_alloc())); 2286227825Stheraven} 2287227825Stheraven 2288227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2289227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2290227825Stheravenvoid 2291227825Stheravenswap(__tree<_Tp, _Compare, _Allocator>& __x, 2292227825Stheraven __tree<_Tp, _Compare, _Allocator>& __y) 2293227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2294227825Stheraven{ 2295227825Stheraven __x.swap(__y); 2296227825Stheraven} 2297227825Stheraven 2298227825Stheraven_LIBCPP_END_NAMESPACE_STD 2299227825Stheraven 2300227825Stheraven#endif // _LIBCPP___TREE 2301