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> 28262801Sdim class _LIBCPP_TYPE_VIS_ONLY __tree_iterator; 29227825Stheraventemplate <class _Tp, class _ConstNodePtr, class _DiffType> 30262801Sdim class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator; 31227825Stheraventemplate <class _Key, class _Tp, class _Compare, class _Allocator> 32262801Sdim class _LIBCPP_TYPE_VIS_ONLY map; 33227825Stheraventemplate <class _Key, class _Tp, class _Compare, class _Allocator> 34262801Sdim class _LIBCPP_TYPE_VIS_ONLY multimap; 35227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 36262801Sdim class _LIBCPP_TYPE_VIS_ONLY set; 37227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 38262801Sdim class _LIBCPP_TYPE_VIS_ONLY 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 617262801Sdimtemplate <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator; 618262801Sdimtemplate <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; 619227825Stheraven 620227825Stheraventemplate <class _Tp, class _NodePtr, class _DiffType> 621262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __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 644262801Sdim _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT 645262801Sdim#if _LIBCPP_STD_VER > 11 646262801Sdim : __ptr_(nullptr) 647262801Sdim#endif 648262801Sdim {} 649227825Stheraven 650227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 651253222Sdim _LIBCPP_INLINE_VISIBILITY pointer operator->() const 652253222Sdim {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 653227825Stheraven 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655227825Stheraven __tree_iterator& operator++() 656227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); 657227825Stheraven return *this;} 658227825Stheraven _LIBCPP_INLINE_VISIBILITY 659227825Stheraven __tree_iterator operator++(int) 660227825Stheraven {__tree_iterator __t(*this); ++(*this); return __t;} 661227825Stheraven 662227825Stheraven _LIBCPP_INLINE_VISIBILITY 663227825Stheraven __tree_iterator& operator--() 664227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); 665227825Stheraven return *this;} 666227825Stheraven _LIBCPP_INLINE_VISIBILITY 667227825Stheraven __tree_iterator operator--(int) 668227825Stheraven {__tree_iterator __t(*this); --(*this); return __t;} 669227825Stheraven 670227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 671227825Stheraven bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 672227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 673227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 674227825Stheraven bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 675227825Stheraven {return !(__x == __y);} 676227825Stheraven 677227825Stheravenprivate: 678227825Stheraven _LIBCPP_INLINE_VISIBILITY 679227825Stheraven explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 680227825Stheraven template <class, class, class> friend class __tree; 681262801Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator; 682262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator; 683262801Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 684262801Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 685262801Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set; 686262801Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset; 687227825Stheraven}; 688227825Stheraven 689227825Stheraventemplate <class _Tp, class _ConstNodePtr, class _DiffType> 690262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator 691227825Stheraven{ 692227825Stheraven typedef _ConstNodePtr __node_pointer; 693227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type __node; 694253222Sdim typedef typename __node::base __node_base; 695227825Stheraven typedef typename pointer_traits<__node_pointer>::template 696227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 697227825Stheraven rebind<__node_base> 698227825Stheraven#else 699227825Stheraven rebind<__node_base>::other 700227825Stheraven#endif 701227825Stheraven __node_base_pointer; 702227825Stheraven 703227825Stheraven __node_pointer __ptr_; 704227825Stheraven 705227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 706227825Stheravenpublic: 707227825Stheraven typedef bidirectional_iterator_tag iterator_category; 708227825Stheraven typedef _Tp value_type; 709227825Stheraven typedef _DiffType difference_type; 710227825Stheraven typedef const value_type& reference; 711227825Stheraven typedef typename pointer_traits<__node_pointer>::template 712227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 713227825Stheraven rebind<const value_type> 714227825Stheraven#else 715227825Stheraven rebind<const value_type>::other 716227825Stheraven#endif 717227825Stheraven pointer; 718227825Stheraven 719262801Sdim _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT 720262801Sdim#if _LIBCPP_STD_VER > 11 721262801Sdim : __ptr_(nullptr) 722262801Sdim#endif 723262801Sdim {} 724262801Sdim 725227825Stheravenprivate: 726227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 727227825Stheraven typedef typename pointer_traits<__node_pointer>::template 728227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 729227825Stheraven rebind<__non_const_node> 730227825Stheraven#else 731227825Stheraven rebind<__non_const_node>::other 732227825Stheraven#endif 733227825Stheraven __non_const_node_pointer; 734227825Stheraven typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> 735227825Stheraven __non_const_iterator; 736227825Stheravenpublic: 737227825Stheraven _LIBCPP_INLINE_VISIBILITY 738227825Stheraven __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 739227825Stheraven : __ptr_(__p.__ptr_) {} 740227825Stheraven 741227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 742253222Sdim _LIBCPP_INLINE_VISIBILITY pointer operator->() const 743253222Sdim {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 744227825Stheraven 745227825Stheraven _LIBCPP_INLINE_VISIBILITY 746227825Stheraven __tree_const_iterator& operator++() 747227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); 748227825Stheraven return *this;} 749227825Stheraven _LIBCPP_INLINE_VISIBILITY 750227825Stheraven __tree_const_iterator operator++(int) 751227825Stheraven {__tree_const_iterator __t(*this); ++(*this); return __t;} 752227825Stheraven 753227825Stheraven _LIBCPP_INLINE_VISIBILITY 754227825Stheraven __tree_const_iterator& operator--() 755227825Stheraven {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); 756227825Stheraven return *this;} 757227825Stheraven _LIBCPP_INLINE_VISIBILITY 758227825Stheraven __tree_const_iterator operator--(int) 759227825Stheraven {__tree_const_iterator __t(*this); --(*this); return __t;} 760227825Stheraven 761227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 762227825Stheraven bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 763227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 764227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 765227825Stheraven bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 766227825Stheraven {return !(__x == __y);} 767227825Stheraven 768227825Stheravenprivate: 769227825Stheraven _LIBCPP_INLINE_VISIBILITY 770227825Stheraven explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 771227825Stheraven : __ptr_(__p) {} 772227825Stheraven template <class, class, class> friend class __tree; 773262801Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 774262801Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 775262801Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set; 776262801Sdim template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset; 777262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; 778227825Stheraven}; 779227825Stheraven 780227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 781227825Stheravenclass __tree 782227825Stheraven{ 783227825Stheravenpublic: 784227825Stheraven typedef _Tp value_type; 785227825Stheraven typedef _Compare value_compare; 786227825Stheraven typedef _Allocator allocator_type; 787227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 788227825Stheraven typedef typename __alloc_traits::pointer pointer; 789227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 790227825Stheraven typedef typename __alloc_traits::size_type size_type; 791227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 792227825Stheraven 793253222Sdim typedef typename __alloc_traits::void_pointer __void_pointer; 794253222Sdim 795253222Sdim typedef __tree_node<value_type, __void_pointer> __node; 796253222Sdim typedef __tree_node_base<__void_pointer> __node_base; 797227825Stheraven typedef typename __alloc_traits::template 798227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 799227825Stheraven rebind_alloc<__node> 800227825Stheraven#else 801227825Stheraven rebind_alloc<__node>::other 802227825Stheraven#endif 803227825Stheraven __node_allocator; 804227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 805227825Stheraven typedef typename __node_traits::pointer __node_pointer; 806253222Sdim typedef typename __node_traits::pointer __node_const_pointer; 807227825Stheraven typedef typename __node_base::pointer __node_base_pointer; 808253222Sdim typedef typename __node_base::pointer __node_base_const_pointer; 809227825Stheravenprivate: 810227825Stheraven typedef typename __node_base::base __end_node_t; 811227825Stheraven typedef typename pointer_traits<__node_pointer>::template 812227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 813227825Stheraven rebind<__end_node_t> 814227825Stheraven#else 815227825Stheraven rebind<__end_node_t>::other 816227825Stheraven#endif 817227825Stheraven __end_node_ptr; 818227825Stheraven typedef typename pointer_traits<__node_pointer>::template 819227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 820253222Sdim rebind<__end_node_t> 821227825Stheraven#else 822253222Sdim rebind<__end_node_t>::other 823227825Stheraven#endif 824227825Stheraven __end_node_const_ptr; 825227825Stheraven 826227825Stheraven __node_pointer __begin_node_; 827227825Stheraven __compressed_pair<__end_node_t, __node_allocator> __pair1_; 828227825Stheraven __compressed_pair<size_type, value_compare> __pair3_; 829227825Stheraven 830227825Stheravenpublic: 831227825Stheraven _LIBCPP_INLINE_VISIBILITY 832227825Stheraven __node_pointer __end_node() _NOEXCEPT 833227825Stheraven { 834227825Stheraven return static_cast<__node_pointer> 835227825Stheraven ( 836227825Stheraven pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 837227825Stheraven ); 838227825Stheraven } 839227825Stheraven _LIBCPP_INLINE_VISIBILITY 840227825Stheraven __node_const_pointer __end_node() const _NOEXCEPT 841227825Stheraven { 842227825Stheraven return static_cast<__node_const_pointer> 843227825Stheraven ( 844253222Sdim pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first())) 845227825Stheraven ); 846227825Stheraven } 847227825Stheraven _LIBCPP_INLINE_VISIBILITY 848227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 849227825Stheravenprivate: 850227825Stheraven _LIBCPP_INLINE_VISIBILITY 851227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 852227825Stheraven {return __pair1_.second();} 853227825Stheraven _LIBCPP_INLINE_VISIBILITY 854227825Stheraven __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 855227825Stheraven _LIBCPP_INLINE_VISIBILITY 856227825Stheraven const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 857227825Stheravenpublic: 858227825Stheraven _LIBCPP_INLINE_VISIBILITY 859227825Stheraven allocator_type __alloc() const _NOEXCEPT 860227825Stheraven {return allocator_type(__node_alloc());} 861227825Stheravenprivate: 862227825Stheraven _LIBCPP_INLINE_VISIBILITY 863227825Stheraven size_type& size() _NOEXCEPT {return __pair3_.first();} 864227825Stheravenpublic: 865227825Stheraven _LIBCPP_INLINE_VISIBILITY 866227825Stheraven const size_type& size() const _NOEXCEPT {return __pair3_.first();} 867227825Stheraven _LIBCPP_INLINE_VISIBILITY 868227825Stheraven value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 869227825Stheraven _LIBCPP_INLINE_VISIBILITY 870227825Stheraven const value_compare& value_comp() const _NOEXCEPT 871227825Stheraven {return __pair3_.second();} 872227825Stheravenpublic: 873227825Stheraven _LIBCPP_INLINE_VISIBILITY 874227825Stheraven __node_pointer __root() _NOEXCEPT 875227825Stheraven {return static_cast<__node_pointer> (__end_node()->__left_);} 876227825Stheraven _LIBCPP_INLINE_VISIBILITY 877227825Stheraven __node_const_pointer __root() const _NOEXCEPT 878227825Stheraven {return static_cast<__node_const_pointer>(__end_node()->__left_);} 879227825Stheraven 880227825Stheraven typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 881253222Sdim typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 882227825Stheraven 883227825Stheraven explicit __tree(const value_compare& __comp) 884227825Stheraven _NOEXCEPT_( 885227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 886227825Stheraven is_nothrow_copy_constructible<value_compare>::value); 887227825Stheraven explicit __tree(const allocator_type& __a); 888227825Stheraven __tree(const value_compare& __comp, const allocator_type& __a); 889227825Stheraven __tree(const __tree& __t); 890227825Stheraven __tree& operator=(const __tree& __t); 891227825Stheraven template <class _InputIterator> 892227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 893227825Stheraven template <class _InputIterator> 894227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 895227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 896227825Stheraven __tree(__tree&& __t) 897227825Stheraven _NOEXCEPT_( 898227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 899227825Stheraven is_nothrow_move_constructible<value_compare>::value); 900227825Stheraven __tree(__tree&& __t, const allocator_type& __a); 901227825Stheraven __tree& operator=(__tree&& __t) 902227825Stheraven _NOEXCEPT_( 903227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 904227825Stheraven is_nothrow_move_assignable<value_compare>::value && 905227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 906227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 907227825Stheraven 908227825Stheraven ~__tree(); 909227825Stheraven 910227825Stheraven _LIBCPP_INLINE_VISIBILITY 911227825Stheraven iterator begin() _NOEXCEPT {return iterator(__begin_node());} 912227825Stheraven _LIBCPP_INLINE_VISIBILITY 913227825Stheraven const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 914227825Stheraven _LIBCPP_INLINE_VISIBILITY 915227825Stheraven iterator end() _NOEXCEPT {return iterator(__end_node());} 916227825Stheraven _LIBCPP_INLINE_VISIBILITY 917227825Stheraven const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 918227825Stheraven 919227825Stheraven _LIBCPP_INLINE_VISIBILITY 920227825Stheraven size_type max_size() const _NOEXCEPT 921227825Stheraven {return __node_traits::max_size(__node_alloc());} 922227825Stheraven 923227825Stheraven void clear() _NOEXCEPT; 924227825Stheraven 925227825Stheraven void swap(__tree& __t) 926227825Stheraven _NOEXCEPT_( 927227825Stheraven __is_nothrow_swappable<value_compare>::value && 928227825Stheraven (!__node_traits::propagate_on_container_swap::value || 929227825Stheraven __is_nothrow_swappable<__node_allocator>::value)); 930227825Stheraven 931227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 932227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 933227825Stheraven template <class... _Args> 934227825Stheraven pair<iterator, bool> 935227825Stheraven __emplace_unique(_Args&&... __args); 936227825Stheraven template <class... _Args> 937227825Stheraven iterator 938227825Stheraven __emplace_multi(_Args&&... __args); 939227825Stheraven 940227825Stheraven template <class... _Args> 941227825Stheraven iterator 942227825Stheraven __emplace_hint_unique(const_iterator __p, _Args&&... __args); 943227825Stheraven template <class... _Args> 944227825Stheraven iterator 945227825Stheraven __emplace_hint_multi(const_iterator __p, _Args&&... __args); 946227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 947227825Stheraven 948232950Stheraven template <class _Vp> 949232950Stheraven pair<iterator, bool> __insert_unique(_Vp&& __v); 950232950Stheraven template <class _Vp> 951232950Stheraven iterator __insert_unique(const_iterator __p, _Vp&& __v); 952232950Stheraven template <class _Vp> 953232950Stheraven iterator __insert_multi(_Vp&& __v); 954232950Stheraven template <class _Vp> 955232950Stheraven iterator __insert_multi(const_iterator __p, _Vp&& __v); 956227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 957227825Stheraven 958227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __v); 959227825Stheraven iterator __insert_unique(const_iterator __p, const value_type& __v); 960227825Stheraven iterator __insert_multi(const value_type& __v); 961227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __v); 962227825Stheraven 963227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 964227825Stheraven iterator __node_insert_unique(const_iterator __p, 965227825Stheraven __node_pointer __nd); 966227825Stheraven 967227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 968227825Stheraven iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 969227825Stheraven 970227825Stheraven iterator erase(const_iterator __p); 971227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 972227825Stheraven template <class _Key> 973227825Stheraven size_type __erase_unique(const _Key& __k); 974227825Stheraven template <class _Key> 975227825Stheraven size_type __erase_multi(const _Key& __k); 976227825Stheraven 977227825Stheraven void __insert_node_at(__node_base_pointer __parent, 978227825Stheraven __node_base_pointer& __child, 979227825Stheraven __node_base_pointer __new_node); 980227825Stheraven 981227825Stheraven template <class _Key> 982227825Stheraven iterator find(const _Key& __v); 983227825Stheraven template <class _Key> 984227825Stheraven const_iterator find(const _Key& __v) const; 985227825Stheraven 986227825Stheraven template <class _Key> 987227825Stheraven size_type __count_unique(const _Key& __k) const; 988227825Stheraven template <class _Key> 989227825Stheraven size_type __count_multi(const _Key& __k) const; 990227825Stheraven 991227825Stheraven template <class _Key> 992227825Stheraven _LIBCPP_INLINE_VISIBILITY 993227825Stheraven iterator lower_bound(const _Key& __v) 994227825Stheraven {return __lower_bound(__v, __root(), __end_node());} 995227825Stheraven template <class _Key> 996227825Stheraven iterator __lower_bound(const _Key& __v, 997227825Stheraven __node_pointer __root, 998227825Stheraven __node_pointer __result); 999227825Stheraven template <class _Key> 1000227825Stheraven _LIBCPP_INLINE_VISIBILITY 1001227825Stheraven const_iterator lower_bound(const _Key& __v) const 1002227825Stheraven {return __lower_bound(__v, __root(), __end_node());} 1003227825Stheraven template <class _Key> 1004227825Stheraven const_iterator __lower_bound(const _Key& __v, 1005227825Stheraven __node_const_pointer __root, 1006227825Stheraven __node_const_pointer __result) const; 1007227825Stheraven template <class _Key> 1008227825Stheraven _LIBCPP_INLINE_VISIBILITY 1009227825Stheraven iterator upper_bound(const _Key& __v) 1010227825Stheraven {return __upper_bound(__v, __root(), __end_node());} 1011227825Stheraven template <class _Key> 1012227825Stheraven iterator __upper_bound(const _Key& __v, 1013227825Stheraven __node_pointer __root, 1014227825Stheraven __node_pointer __result); 1015227825Stheraven template <class _Key> 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven const_iterator upper_bound(const _Key& __v) const 1018227825Stheraven {return __upper_bound(__v, __root(), __end_node());} 1019227825Stheraven template <class _Key> 1020227825Stheraven const_iterator __upper_bound(const _Key& __v, 1021227825Stheraven __node_const_pointer __root, 1022227825Stheraven __node_const_pointer __result) const; 1023227825Stheraven template <class _Key> 1024227825Stheraven pair<iterator, iterator> 1025227825Stheraven __equal_range_unique(const _Key& __k); 1026227825Stheraven template <class _Key> 1027227825Stheraven pair<const_iterator, const_iterator> 1028227825Stheraven __equal_range_unique(const _Key& __k) const; 1029227825Stheraven 1030227825Stheraven template <class _Key> 1031227825Stheraven pair<iterator, iterator> 1032227825Stheraven __equal_range_multi(const _Key& __k); 1033227825Stheraven template <class _Key> 1034227825Stheraven pair<const_iterator, const_iterator> 1035227825Stheraven __equal_range_multi(const _Key& __k) const; 1036227825Stheraven 1037232950Stheraven typedef __tree_node_destructor<__node_allocator> _Dp; 1038232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1039227825Stheraven 1040227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 1041227825Stheravenprivate: 1042227825Stheraven typename __node_base::pointer& 1043227825Stheraven __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v); 1044227825Stheraven typename __node_base::pointer& 1045227825Stheraven __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v); 1046227825Stheraven typename __node_base::pointer& 1047227825Stheraven __find_leaf(const_iterator __hint, 1048227825Stheraven typename __node_base::pointer& __parent, const value_type& __v); 1049227825Stheraven template <class _Key> 1050227825Stheraven typename __node_base::pointer& 1051227825Stheraven __find_equal(typename __node_base::pointer& __parent, const _Key& __v); 1052227825Stheraven template <class _Key> 1053227825Stheraven typename __node_base::pointer& 1054227825Stheraven __find_equal(const_iterator __hint, typename __node_base::pointer& __parent, 1055227825Stheraven const _Key& __v); 1056227825Stheraven 1057227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1058227825Stheraven template <class ..._Args> 1059227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1060227825Stheraven#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1061227825Stheraven __node_holder __construct_node(const value_type& __v); 1062227825Stheraven#endif 1063227825Stheraven 1064227825Stheraven void destroy(__node_pointer __nd) _NOEXCEPT; 1065227825Stheraven 1066227825Stheraven _LIBCPP_INLINE_VISIBILITY 1067227825Stheraven void __copy_assign_alloc(const __tree& __t) 1068227825Stheraven {__copy_assign_alloc(__t, integral_constant<bool, 1069227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1070227825Stheraven 1071227825Stheraven _LIBCPP_INLINE_VISIBILITY 1072227825Stheraven void __copy_assign_alloc(const __tree& __t, true_type) 1073227825Stheraven {__node_alloc() = __t.__node_alloc();} 1074227825Stheraven _LIBCPP_INLINE_VISIBILITY 1075227825Stheraven void __copy_assign_alloc(const __tree& __t, false_type) {} 1076227825Stheraven 1077227825Stheraven void __move_assign(__tree& __t, false_type); 1078227825Stheraven void __move_assign(__tree& __t, true_type) 1079227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1080227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 1081227825Stheraven 1082227825Stheraven _LIBCPP_INLINE_VISIBILITY 1083227825Stheraven void __move_assign_alloc(__tree& __t) 1084227825Stheraven _NOEXCEPT_( 1085227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1086227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1087227825Stheraven {__move_assign_alloc(__t, integral_constant<bool, 1088227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1089227825Stheraven 1090227825Stheraven _LIBCPP_INLINE_VISIBILITY 1091227825Stheraven void __move_assign_alloc(__tree& __t, true_type) 1092227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1093227825Stheraven {__node_alloc() = _VSTD::move(__t.__node_alloc());} 1094227825Stheraven _LIBCPP_INLINE_VISIBILITY 1095227825Stheraven void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {} 1096227825Stheraven 1097227825Stheraven _LIBCPP_INLINE_VISIBILITY 1098227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 1099227825Stheraven _NOEXCEPT_( 1100227825Stheraven !__node_traits::propagate_on_container_swap::value || 1101227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 1102227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 1103227825Stheraven __node_traits::propagate_on_container_swap::value>());} 1104227825Stheraven _LIBCPP_INLINE_VISIBILITY 1105227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) 1106227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 1107227825Stheraven { 1108227825Stheraven using _VSTD::swap; 1109227825Stheraven swap(__x, __y); 1110227825Stheraven } 1111227825Stheraven _LIBCPP_INLINE_VISIBILITY 1112227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) 1113227825Stheraven _NOEXCEPT 1114227825Stheraven {} 1115227825Stheraven 1116227825Stheraven __node_pointer __detach(); 1117227825Stheraven static __node_pointer __detach(__node_pointer); 1118253222Sdim 1119262801Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 1120262801Sdim template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 1121227825Stheraven}; 1122227825Stheraven 1123227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1124227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 1125227825Stheraven _NOEXCEPT_( 1126227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 1127227825Stheraven is_nothrow_copy_constructible<value_compare>::value) 1128227825Stheraven : __pair3_(0, __comp) 1129227825Stheraven{ 1130227825Stheraven __begin_node() = __end_node(); 1131227825Stheraven} 1132227825Stheraven 1133227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1134227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1135227825Stheraven : __pair1_(__node_allocator(__a)), 1136227825Stheraven __begin_node_(__node_pointer()), 1137227825Stheraven __pair3_(0) 1138227825Stheraven{ 1139227825Stheraven __begin_node() = __end_node(); 1140227825Stheraven} 1141227825Stheraven 1142227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1143227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 1144227825Stheraven const allocator_type& __a) 1145227825Stheraven : __pair1_(__node_allocator(__a)), 1146227825Stheraven __begin_node_(__node_pointer()), 1147227825Stheraven __pair3_(0, __comp) 1148227825Stheraven{ 1149227825Stheraven __begin_node() = __end_node(); 1150227825Stheraven} 1151227825Stheraven 1152227825Stheraven// Precondition: size() != 0 1153227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1154227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1155227825Stheraven__tree<_Tp, _Compare, _Allocator>::__detach() 1156227825Stheraven{ 1157227825Stheraven __node_pointer __cache = __begin_node(); 1158227825Stheraven __begin_node() = __end_node(); 1159227825Stheraven __end_node()->__left_->__parent_ = nullptr; 1160227825Stheraven __end_node()->__left_ = nullptr; 1161227825Stheraven size() = 0; 1162227825Stheraven // __cache->__left_ == nullptr 1163227825Stheraven if (__cache->__right_ != nullptr) 1164227825Stheraven __cache = static_cast<__node_pointer>(__cache->__right_); 1165227825Stheraven // __cache->__left_ == nullptr 1166227825Stheraven // __cache->__right_ == nullptr 1167227825Stheraven return __cache; 1168227825Stheraven} 1169227825Stheraven 1170227825Stheraven// Precondition: __cache != nullptr 1171227825Stheraven// __cache->left_ == nullptr 1172227825Stheraven// __cache->right_ == nullptr 1173227825Stheraven// This is no longer a red-black tree 1174227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1175227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1176227825Stheraven__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache) 1177227825Stheraven{ 1178227825Stheraven if (__cache->__parent_ == nullptr) 1179227825Stheraven return nullptr; 1180253222Sdim if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 1181227825Stheraven { 1182227825Stheraven __cache->__parent_->__left_ = nullptr; 1183227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1184227825Stheraven if (__cache->__right_ == nullptr) 1185227825Stheraven return __cache; 1186227825Stheraven return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); 1187227825Stheraven } 1188227825Stheraven // __cache is right child 1189227825Stheraven __cache->__parent_->__right_ = nullptr; 1190227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1191227825Stheraven if (__cache->__left_ == nullptr) 1192227825Stheraven return __cache; 1193227825Stheraven return static_cast<__node_pointer>(__tree_leaf(__cache->__left_)); 1194227825Stheraven} 1195227825Stheraven 1196227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1197227825Stheraven__tree<_Tp, _Compare, _Allocator>& 1198227825Stheraven__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 1199227825Stheraven{ 1200227825Stheraven if (this != &__t) 1201227825Stheraven { 1202227825Stheraven value_comp() = __t.value_comp(); 1203227825Stheraven __copy_assign_alloc(__t); 1204227825Stheraven __assign_multi(__t.begin(), __t.end()); 1205227825Stheraven } 1206227825Stheraven return *this; 1207227825Stheraven} 1208227825Stheraven 1209227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1210227825Stheraventemplate <class _InputIterator> 1211227825Stheravenvoid 1212227825Stheraven__tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last) 1213227825Stheraven{ 1214227825Stheraven if (size() != 0) 1215227825Stheraven { 1216227825Stheraven __node_pointer __cache = __detach(); 1217227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1218227825Stheraven try 1219227825Stheraven { 1220227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1221227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1222227825Stheraven { 1223227825Stheraven __cache->__value_ = *__first; 1224227825Stheraven __node_pointer __next = __detach(__cache); 1225227825Stheraven __node_insert_unique(__cache); 1226227825Stheraven __cache = __next; 1227227825Stheraven } 1228227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1229227825Stheraven } 1230227825Stheraven catch (...) 1231227825Stheraven { 1232227825Stheraven while (__cache->__parent_ != nullptr) 1233227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1234227825Stheraven destroy(__cache); 1235227825Stheraven throw; 1236227825Stheraven } 1237227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1238227825Stheraven if (__cache != nullptr) 1239227825Stheraven { 1240227825Stheraven while (__cache->__parent_ != nullptr) 1241227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1242227825Stheraven destroy(__cache); 1243227825Stheraven } 1244227825Stheraven } 1245227825Stheraven for (; __first != __last; ++__first) 1246227825Stheraven __insert_unique(*__first); 1247227825Stheraven} 1248227825Stheraven 1249227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1250227825Stheraventemplate <class _InputIterator> 1251227825Stheravenvoid 1252227825Stheraven__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 1253227825Stheraven{ 1254227825Stheraven if (size() != 0) 1255227825Stheraven { 1256227825Stheraven __node_pointer __cache = __detach(); 1257227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1258227825Stheraven try 1259227825Stheraven { 1260227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1261227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1262227825Stheraven { 1263227825Stheraven __cache->__value_ = *__first; 1264227825Stheraven __node_pointer __next = __detach(__cache); 1265227825Stheraven __node_insert_multi(__cache); 1266227825Stheraven __cache = __next; 1267227825Stheraven } 1268227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1269227825Stheraven } 1270227825Stheraven catch (...) 1271227825Stheraven { 1272227825Stheraven while (__cache->__parent_ != nullptr) 1273227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1274227825Stheraven destroy(__cache); 1275227825Stheraven throw; 1276227825Stheraven } 1277227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1278227825Stheraven if (__cache != nullptr) 1279227825Stheraven { 1280227825Stheraven while (__cache->__parent_ != nullptr) 1281227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1282227825Stheraven destroy(__cache); 1283227825Stheraven } 1284227825Stheraven } 1285227825Stheraven for (; __first != __last; ++__first) 1286227825Stheraven __insert_multi(*__first); 1287227825Stheraven} 1288227825Stheraven 1289227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1290227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1291227825Stheraven : __begin_node_(__node_pointer()), 1292227825Stheraven __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1293227825Stheraven __pair3_(0, __t.value_comp()) 1294227825Stheraven{ 1295227825Stheraven __begin_node() = __end_node(); 1296227825Stheraven} 1297227825Stheraven 1298227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1299227825Stheraven 1300227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1301227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 1302227825Stheraven _NOEXCEPT_( 1303227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 1304227825Stheraven is_nothrow_move_constructible<value_compare>::value) 1305227825Stheraven : __begin_node_(_VSTD::move(__t.__begin_node_)), 1306227825Stheraven __pair1_(_VSTD::move(__t.__pair1_)), 1307227825Stheraven __pair3_(_VSTD::move(__t.__pair3_)) 1308227825Stheraven{ 1309227825Stheraven if (size() == 0) 1310227825Stheraven __begin_node() = __end_node(); 1311227825Stheraven else 1312227825Stheraven { 1313253222Sdim __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1314227825Stheraven __t.__begin_node() = __t.__end_node(); 1315227825Stheraven __t.__end_node()->__left_ = nullptr; 1316227825Stheraven __t.size() = 0; 1317227825Stheraven } 1318227825Stheraven} 1319227825Stheraven 1320227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1321227825Stheraven__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1322227825Stheraven : __pair1_(__node_allocator(__a)), 1323227825Stheraven __pair3_(0, _VSTD::move(__t.value_comp())) 1324227825Stheraven{ 1325227825Stheraven if (__a == __t.__alloc()) 1326227825Stheraven { 1327227825Stheraven if (__t.size() == 0) 1328227825Stheraven __begin_node() = __end_node(); 1329227825Stheraven else 1330227825Stheraven { 1331227825Stheraven __begin_node() = __t.__begin_node(); 1332227825Stheraven __end_node()->__left_ = __t.__end_node()->__left_; 1333253222Sdim __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1334227825Stheraven size() = __t.size(); 1335227825Stheraven __t.__begin_node() = __t.__end_node(); 1336227825Stheraven __t.__end_node()->__left_ = nullptr; 1337227825Stheraven __t.size() = 0; 1338227825Stheraven } 1339227825Stheraven } 1340227825Stheraven else 1341227825Stheraven { 1342227825Stheraven __begin_node() = __end_node(); 1343227825Stheraven } 1344227825Stheraven} 1345227825Stheraven 1346227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1347227825Stheravenvoid 1348227825Stheraven__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1349227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1350227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1351227825Stheraven{ 1352227825Stheraven destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1353227825Stheraven __begin_node_ = __t.__begin_node_; 1354227825Stheraven __pair1_.first() = __t.__pair1_.first(); 1355227825Stheraven __move_assign_alloc(__t); 1356227825Stheraven __pair3_ = _VSTD::move(__t.__pair3_); 1357227825Stheraven if (size() == 0) 1358227825Stheraven __begin_node() = __end_node(); 1359227825Stheraven else 1360227825Stheraven { 1361253222Sdim __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1362227825Stheraven __t.__begin_node() = __t.__end_node(); 1363227825Stheraven __t.__end_node()->__left_ = nullptr; 1364227825Stheraven __t.size() = 0; 1365227825Stheraven } 1366227825Stheraven} 1367227825Stheraven 1368227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1369227825Stheravenvoid 1370227825Stheraven__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 1371227825Stheraven{ 1372227825Stheraven if (__node_alloc() == __t.__node_alloc()) 1373227825Stheraven __move_assign(__t, true_type()); 1374227825Stheraven else 1375227825Stheraven { 1376227825Stheraven value_comp() = _VSTD::move(__t.value_comp()); 1377227825Stheraven const_iterator __e = end(); 1378227825Stheraven if (size() != 0) 1379227825Stheraven { 1380227825Stheraven __node_pointer __cache = __detach(); 1381227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1382227825Stheraven try 1383227825Stheraven { 1384227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1385227825Stheraven while (__cache != nullptr && __t.size() != 0) 1386227825Stheraven { 1387227825Stheraven __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 1388227825Stheraven __node_pointer __next = __detach(__cache); 1389227825Stheraven __node_insert_multi(__cache); 1390227825Stheraven __cache = __next; 1391227825Stheraven } 1392227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1393227825Stheraven } 1394227825Stheraven catch (...) 1395227825Stheraven { 1396227825Stheraven while (__cache->__parent_ != nullptr) 1397227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1398227825Stheraven destroy(__cache); 1399227825Stheraven throw; 1400227825Stheraven } 1401227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1402227825Stheraven if (__cache != nullptr) 1403227825Stheraven { 1404227825Stheraven while (__cache->__parent_ != nullptr) 1405227825Stheraven __cache = static_cast<__node_pointer>(__cache->__parent_); 1406227825Stheraven destroy(__cache); 1407227825Stheraven } 1408227825Stheraven } 1409227825Stheraven while (__t.size() != 0) 1410227825Stheraven __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_)); 1411227825Stheraven } 1412227825Stheraven} 1413227825Stheraven 1414227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1415227825Stheraven__tree<_Tp, _Compare, _Allocator>& 1416227825Stheraven__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 1417227825Stheraven _NOEXCEPT_( 1418227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1419227825Stheraven is_nothrow_move_assignable<value_compare>::value && 1420227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1421227825Stheraven 1422227825Stheraven{ 1423227825Stheraven __move_assign(__t, integral_constant<bool, 1424227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1425227825Stheraven return *this; 1426227825Stheraven} 1427227825Stheraven 1428227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1429227825Stheraven 1430227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1431227825Stheraven__tree<_Tp, _Compare, _Allocator>::~__tree() 1432227825Stheraven{ 1433227825Stheraven destroy(__root()); 1434227825Stheraven} 1435227825Stheraven 1436227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1437227825Stheravenvoid 1438227825Stheraven__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 1439227825Stheraven{ 1440227825Stheraven if (__nd != nullptr) 1441227825Stheraven { 1442227825Stheraven destroy(static_cast<__node_pointer>(__nd->__left_)); 1443227825Stheraven destroy(static_cast<__node_pointer>(__nd->__right_)); 1444227825Stheraven __node_allocator& __na = __node_alloc(); 1445227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_)); 1446227825Stheraven __node_traits::deallocate(__na, __nd, 1); 1447227825Stheraven } 1448227825Stheraven} 1449227825Stheraven 1450227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1451227825Stheravenvoid 1452227825Stheraven__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1453227825Stheraven _NOEXCEPT_( 1454227825Stheraven __is_nothrow_swappable<value_compare>::value && 1455227825Stheraven (!__node_traits::propagate_on_container_swap::value || 1456227825Stheraven __is_nothrow_swappable<__node_allocator>::value)) 1457227825Stheraven{ 1458227825Stheraven using _VSTD::swap; 1459227825Stheraven swap(__begin_node_, __t.__begin_node_); 1460227825Stheraven swap(__pair1_.first(), __t.__pair1_.first()); 1461227825Stheraven __swap_alloc(__node_alloc(), __t.__node_alloc()); 1462227825Stheraven __pair3_.swap(__t.__pair3_); 1463227825Stheraven if (size() == 0) 1464227825Stheraven __begin_node() = __end_node(); 1465227825Stheraven else 1466253222Sdim __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1467227825Stheraven if (__t.size() == 0) 1468227825Stheraven __t.__begin_node() = __t.__end_node(); 1469227825Stheraven else 1470253222Sdim __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node()); 1471227825Stheraven} 1472227825Stheraven 1473227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1474227825Stheravenvoid 1475227825Stheraven__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 1476227825Stheraven{ 1477227825Stheraven destroy(__root()); 1478227825Stheraven size() = 0; 1479227825Stheraven __begin_node() = __end_node(); 1480227825Stheraven __end_node()->__left_ = nullptr; 1481227825Stheraven} 1482227825Stheraven 1483227825Stheraven// Find lower_bound place to insert 1484227825Stheraven// Set __parent to parent of null leaf 1485227825Stheraven// Return reference to null leaf 1486227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1487227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1488227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent, 1489227825Stheraven const value_type& __v) 1490227825Stheraven{ 1491227825Stheraven __node_pointer __nd = __root(); 1492227825Stheraven if (__nd != nullptr) 1493227825Stheraven { 1494227825Stheraven while (true) 1495227825Stheraven { 1496227825Stheraven if (value_comp()(__nd->__value_, __v)) 1497227825Stheraven { 1498227825Stheraven if (__nd->__right_ != nullptr) 1499227825Stheraven __nd = static_cast<__node_pointer>(__nd->__right_); 1500227825Stheraven else 1501227825Stheraven { 1502253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1503227825Stheraven return __parent->__right_; 1504227825Stheraven } 1505227825Stheraven } 1506227825Stheraven else 1507227825Stheraven { 1508227825Stheraven if (__nd->__left_ != nullptr) 1509227825Stheraven __nd = static_cast<__node_pointer>(__nd->__left_); 1510227825Stheraven else 1511227825Stheraven { 1512253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1513227825Stheraven return __parent->__left_; 1514227825Stheraven } 1515227825Stheraven } 1516227825Stheraven } 1517227825Stheraven } 1518253222Sdim __parent = static_cast<__node_base_pointer>(__end_node()); 1519227825Stheraven return __parent->__left_; 1520227825Stheraven} 1521227825Stheraven 1522227825Stheraven// Find upper_bound place to insert 1523227825Stheraven// Set __parent to parent of null leaf 1524227825Stheraven// Return reference to null leaf 1525227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1526227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1527227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent, 1528227825Stheraven const value_type& __v) 1529227825Stheraven{ 1530227825Stheraven __node_pointer __nd = __root(); 1531227825Stheraven if (__nd != nullptr) 1532227825Stheraven { 1533227825Stheraven while (true) 1534227825Stheraven { 1535227825Stheraven if (value_comp()(__v, __nd->__value_)) 1536227825Stheraven { 1537227825Stheraven if (__nd->__left_ != nullptr) 1538227825Stheraven __nd = static_cast<__node_pointer>(__nd->__left_); 1539227825Stheraven else 1540227825Stheraven { 1541253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1542227825Stheraven return __parent->__left_; 1543227825Stheraven } 1544227825Stheraven } 1545227825Stheraven else 1546227825Stheraven { 1547227825Stheraven if (__nd->__right_ != nullptr) 1548227825Stheraven __nd = static_cast<__node_pointer>(__nd->__right_); 1549227825Stheraven else 1550227825Stheraven { 1551253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1552227825Stheraven return __parent->__right_; 1553227825Stheraven } 1554227825Stheraven } 1555227825Stheraven } 1556227825Stheraven } 1557253222Sdim __parent = static_cast<__node_base_pointer>(__end_node()); 1558227825Stheraven return __parent->__left_; 1559227825Stheraven} 1560227825Stheraven 1561227825Stheraven// Find leaf place to insert closest to __hint 1562227825Stheraven// First check prior to __hint. 1563227825Stheraven// Next check after __hint. 1564227825Stheraven// Next do O(log N) search. 1565227825Stheraven// Set __parent to parent of null leaf 1566227825Stheraven// Return reference to null leaf 1567227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1568227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1569227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 1570227825Stheraven typename __node_base::pointer& __parent, 1571227825Stheraven const value_type& __v) 1572227825Stheraven{ 1573227825Stheraven if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1574227825Stheraven { 1575227825Stheraven // __v <= *__hint 1576227825Stheraven const_iterator __prior = __hint; 1577227825Stheraven if (__prior == begin() || !value_comp()(__v, *--__prior)) 1578227825Stheraven { 1579227825Stheraven // *prev(__hint) <= __v <= *__hint 1580227825Stheraven if (__hint.__ptr_->__left_ == nullptr) 1581227825Stheraven { 1582253222Sdim __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1583227825Stheraven return __parent->__left_; 1584227825Stheraven } 1585227825Stheraven else 1586227825Stheraven { 1587253222Sdim __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1588227825Stheraven return __parent->__right_; 1589227825Stheraven } 1590227825Stheraven } 1591227825Stheraven // __v < *prev(__hint) 1592227825Stheraven return __find_leaf_high(__parent, __v); 1593227825Stheraven } 1594227825Stheraven // else __v > *__hint 1595227825Stheraven return __find_leaf_low(__parent, __v); 1596227825Stheraven} 1597227825Stheraven 1598227825Stheraven// Find place to insert if __v doesn't exist 1599227825Stheraven// Set __parent to parent of null leaf 1600227825Stheraven// Return reference to null leaf 1601227825Stheraven// If __v exists, set parent to node of __v and return reference to node of __v 1602227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1603227825Stheraventemplate <class _Key> 1604227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1605227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent, 1606227825Stheraven const _Key& __v) 1607227825Stheraven{ 1608227825Stheraven __node_pointer __nd = __root(); 1609227825Stheraven if (__nd != nullptr) 1610227825Stheraven { 1611227825Stheraven while (true) 1612227825Stheraven { 1613227825Stheraven if (value_comp()(__v, __nd->__value_)) 1614227825Stheraven { 1615227825Stheraven if (__nd->__left_ != nullptr) 1616227825Stheraven __nd = static_cast<__node_pointer>(__nd->__left_); 1617227825Stheraven else 1618227825Stheraven { 1619253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1620227825Stheraven return __parent->__left_; 1621227825Stheraven } 1622227825Stheraven } 1623227825Stheraven else if (value_comp()(__nd->__value_, __v)) 1624227825Stheraven { 1625227825Stheraven if (__nd->__right_ != nullptr) 1626227825Stheraven __nd = static_cast<__node_pointer>(__nd->__right_); 1627227825Stheraven else 1628227825Stheraven { 1629253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1630227825Stheraven return __parent->__right_; 1631227825Stheraven } 1632227825Stheraven } 1633227825Stheraven else 1634227825Stheraven { 1635253222Sdim __parent = static_cast<__node_base_pointer>(__nd); 1636227825Stheraven return __parent; 1637227825Stheraven } 1638227825Stheraven } 1639227825Stheraven } 1640253222Sdim __parent = static_cast<__node_base_pointer>(__end_node()); 1641227825Stheraven return __parent->__left_; 1642227825Stheraven} 1643227825Stheraven 1644227825Stheraven// Find place to insert if __v doesn't exist 1645227825Stheraven// First check prior to __hint. 1646227825Stheraven// Next check after __hint. 1647227825Stheraven// Next do O(log N) search. 1648227825Stheraven// Set __parent to parent of null leaf 1649227825Stheraven// Return reference to null leaf 1650227825Stheraven// If __v exists, set parent to node of __v and return reference to node of __v 1651227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1652227825Stheraventemplate <class _Key> 1653227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1654227825Stheraven__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, 1655227825Stheraven typename __node_base::pointer& __parent, 1656227825Stheraven const _Key& __v) 1657227825Stheraven{ 1658227825Stheraven if (__hint == end() || value_comp()(__v, *__hint)) // check before 1659227825Stheraven { 1660227825Stheraven // __v < *__hint 1661227825Stheraven const_iterator __prior = __hint; 1662227825Stheraven if (__prior == begin() || value_comp()(*--__prior, __v)) 1663227825Stheraven { 1664227825Stheraven // *prev(__hint) < __v < *__hint 1665227825Stheraven if (__hint.__ptr_->__left_ == nullptr) 1666227825Stheraven { 1667253222Sdim __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1668227825Stheraven return __parent->__left_; 1669227825Stheraven } 1670227825Stheraven else 1671227825Stheraven { 1672253222Sdim __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1673227825Stheraven return __parent->__right_; 1674227825Stheraven } 1675227825Stheraven } 1676227825Stheraven // __v <= *prev(__hint) 1677227825Stheraven return __find_equal(__parent, __v); 1678227825Stheraven } 1679227825Stheraven else if (value_comp()(*__hint, __v)) // check after 1680227825Stheraven { 1681227825Stheraven // *__hint < __v 1682227825Stheraven const_iterator __next = _VSTD::next(__hint); 1683227825Stheraven if (__next == end() || value_comp()(__v, *__next)) 1684227825Stheraven { 1685227825Stheraven // *__hint < __v < *_VSTD::next(__hint) 1686227825Stheraven if (__hint.__ptr_->__right_ == nullptr) 1687227825Stheraven { 1688253222Sdim __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1689227825Stheraven return __parent->__right_; 1690227825Stheraven } 1691227825Stheraven else 1692227825Stheraven { 1693253222Sdim __parent = static_cast<__node_base_pointer>(__next.__ptr_); 1694227825Stheraven return __parent->__left_; 1695227825Stheraven } 1696227825Stheraven } 1697227825Stheraven // *next(__hint) <= __v 1698227825Stheraven return __find_equal(__parent, __v); 1699227825Stheraven } 1700227825Stheraven // else __v == *__hint 1701253222Sdim __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1702227825Stheraven return __parent; 1703227825Stheraven} 1704227825Stheraven 1705227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1706227825Stheravenvoid 1707227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent, 1708227825Stheraven __node_base_pointer& __child, 1709227825Stheraven __node_base_pointer __new_node) 1710227825Stheraven{ 1711227825Stheraven __new_node->__left_ = nullptr; 1712227825Stheraven __new_node->__right_ = nullptr; 1713227825Stheraven __new_node->__parent_ = __parent; 1714227825Stheraven __child = __new_node; 1715227825Stheraven if (__begin_node()->__left_ != nullptr) 1716227825Stheraven __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_); 1717227825Stheraven __tree_balance_after_insert(__end_node()->__left_, __child); 1718227825Stheraven ++size(); 1719227825Stheraven} 1720227825Stheraven 1721227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1722227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1723227825Stheraven 1724227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1725227825Stheraventemplate <class ..._Args> 1726227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_holder 1727227825Stheraven__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 1728227825Stheraven{ 1729227825Stheraven __node_allocator& __na = __node_alloc(); 1730232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1731227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1732227825Stheraven __h.get_deleter().__value_constructed = true; 1733227825Stheraven return __h; 1734227825Stheraven} 1735227825Stheraven 1736227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1737227825Stheraventemplate <class... _Args> 1738227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1739227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args) 1740227825Stheraven{ 1741227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1742227825Stheraven __node_base_pointer __parent; 1743227825Stheraven __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 1744227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1745227825Stheraven bool __inserted = false; 1746227825Stheraven if (__child == nullptr) 1747227825Stheraven { 1748253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1749227825Stheraven __r = __h.release(); 1750227825Stheraven __inserted = true; 1751227825Stheraven } 1752227825Stheraven return pair<iterator, bool>(iterator(__r), __inserted); 1753227825Stheraven} 1754227825Stheraven 1755227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1756227825Stheraventemplate <class... _Args> 1757227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1758227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args) 1759227825Stheraven{ 1760227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1761227825Stheraven __node_base_pointer __parent; 1762227825Stheraven __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_); 1763227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1764227825Stheraven if (__child == nullptr) 1765227825Stheraven { 1766253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1767227825Stheraven __r = __h.release(); 1768227825Stheraven } 1769227825Stheraven return iterator(__r); 1770227825Stheraven} 1771227825Stheraven 1772227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1773227825Stheraventemplate <class... _Args> 1774227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1775227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 1776227825Stheraven{ 1777227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1778227825Stheraven __node_base_pointer __parent; 1779227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1780253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1781227825Stheraven return iterator(static_cast<__node_pointer>(__h.release())); 1782227825Stheraven} 1783227825Stheraven 1784227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1785227825Stheraventemplate <class... _Args> 1786227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1787227825Stheraven__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 1788227825Stheraven _Args&&... __args) 1789227825Stheraven{ 1790227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1791227825Stheraven __node_base_pointer __parent; 1792227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1793253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1794227825Stheraven return iterator(static_cast<__node_pointer>(__h.release())); 1795227825Stheraven} 1796227825Stheraven 1797227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1798227825Stheraven 1799227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1800232950Stheraventemplate <class _Vp> 1801227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1802232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) 1803227825Stheraven{ 1804232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1805227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1806227825Stheraven if (__r.second) 1807227825Stheraven __h.release(); 1808227825Stheraven return __r; 1809227825Stheraven} 1810227825Stheraven 1811227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1812232950Stheraventemplate <class _Vp> 1813227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1814232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v) 1815227825Stheraven{ 1816232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1817227825Stheraven iterator __r = __node_insert_unique(__p, __h.get()); 1818227825Stheraven if (__r.__ptr_ == __h.get()) 1819227825Stheraven __h.release(); 1820227825Stheraven return __r; 1821227825Stheraven} 1822227825Stheraven 1823227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1824232950Stheraventemplate <class _Vp> 1825227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1826232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) 1827227825Stheraven{ 1828232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1829227825Stheraven __node_base_pointer __parent; 1830227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1831253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1832227825Stheraven return iterator(__h.release()); 1833227825Stheraven} 1834227825Stheraven 1835227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1836232950Stheraventemplate <class _Vp> 1837227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1838232950Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v) 1839227825Stheraven{ 1840232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1841227825Stheraven __node_base_pointer __parent; 1842227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1843253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1844227825Stheraven return iterator(__h.release()); 1845227825Stheraven} 1846227825Stheraven 1847227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1848227825Stheraven 1849227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1850227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_holder 1851227825Stheraven__tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v) 1852227825Stheraven{ 1853227825Stheraven __node_allocator& __na = __node_alloc(); 1854232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1855227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1856227825Stheraven __h.get_deleter().__value_constructed = true; 1857262801Sdim return _VSTD::move(__h); // explicitly moved for C++03 1858227825Stheraven} 1859227825Stheraven 1860227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1861227825Stheraven 1862227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1863227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1864227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v) 1865227825Stheraven{ 1866227825Stheraven __node_base_pointer __parent; 1867227825Stheraven __node_base_pointer& __child = __find_equal(__parent, __v); 1868227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1869227825Stheraven bool __inserted = false; 1870227825Stheraven if (__child == nullptr) 1871227825Stheraven { 1872227825Stheraven __node_holder __h = __construct_node(__v); 1873253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1874227825Stheraven __r = __h.release(); 1875227825Stheraven __inserted = true; 1876227825Stheraven } 1877227825Stheraven return pair<iterator, bool>(iterator(__r), __inserted); 1878227825Stheraven} 1879227825Stheraven 1880227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1881227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1882227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v) 1883227825Stheraven{ 1884227825Stheraven __node_base_pointer __parent; 1885227825Stheraven __node_base_pointer& __child = __find_equal(__p, __parent, __v); 1886227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1887227825Stheraven if (__child == nullptr) 1888227825Stheraven { 1889227825Stheraven __node_holder __h = __construct_node(__v); 1890253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1891227825Stheraven __r = __h.release(); 1892227825Stheraven } 1893227825Stheraven return iterator(__r); 1894227825Stheraven} 1895227825Stheraven 1896227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1897227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1898227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v) 1899227825Stheraven{ 1900227825Stheraven __node_base_pointer __parent; 1901227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __v); 1902227825Stheraven __node_holder __h = __construct_node(__v); 1903253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1904227825Stheraven return iterator(__h.release()); 1905227825Stheraven} 1906227825Stheraven 1907227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1908227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1909227825Stheraven__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v) 1910227825Stheraven{ 1911227825Stheraven __node_base_pointer __parent; 1912227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __v); 1913227825Stheraven __node_holder __h = __construct_node(__v); 1914253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1915227825Stheraven return iterator(__h.release()); 1916227825Stheraven} 1917227825Stheraven 1918227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1919227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1920227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd) 1921227825Stheraven{ 1922227825Stheraven __node_base_pointer __parent; 1923227825Stheraven __node_base_pointer& __child = __find_equal(__parent, __nd->__value_); 1924227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1925227825Stheraven bool __inserted = false; 1926227825Stheraven if (__child == nullptr) 1927227825Stheraven { 1928253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1929227825Stheraven __r = __nd; 1930227825Stheraven __inserted = true; 1931227825Stheraven } 1932227825Stheraven return pair<iterator, bool>(iterator(__r), __inserted); 1933227825Stheraven} 1934227825Stheraven 1935227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1936227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1937227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p, 1938227825Stheraven __node_pointer __nd) 1939227825Stheraven{ 1940227825Stheraven __node_base_pointer __parent; 1941227825Stheraven __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_); 1942227825Stheraven __node_pointer __r = static_cast<__node_pointer>(__child); 1943227825Stheraven if (__child == nullptr) 1944227825Stheraven { 1945253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1946227825Stheraven __r = __nd; 1947227825Stheraven } 1948227825Stheraven return iterator(__r); 1949227825Stheraven} 1950227825Stheraven 1951227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1952227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1953227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) 1954227825Stheraven{ 1955227825Stheraven __node_base_pointer __parent; 1956227825Stheraven __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_); 1957253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1958227825Stheraven return iterator(__nd); 1959227825Stheraven} 1960227825Stheraven 1961227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1962227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1963227825Stheraven__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, 1964227825Stheraven __node_pointer __nd) 1965227825Stheraven{ 1966227825Stheraven __node_base_pointer __parent; 1967227825Stheraven __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_); 1968253222Sdim __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1969227825Stheraven return iterator(__nd); 1970227825Stheraven} 1971227825Stheraven 1972227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1973227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1974227825Stheraven__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) 1975227825Stheraven{ 1976253222Sdim __node_pointer __np = __p.__ptr_; 1977227825Stheraven iterator __r(__np); 1978227825Stheraven ++__r; 1979227825Stheraven if (__begin_node() == __np) 1980227825Stheraven __begin_node() = __r.__ptr_; 1981227825Stheraven --size(); 1982227825Stheraven __node_allocator& __na = __node_alloc(); 1983227825Stheraven __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p))); 1984227825Stheraven __tree_remove(__end_node()->__left_, 1985227825Stheraven static_cast<__node_base_pointer>(__np)); 1986227825Stheraven __node_traits::deallocate(__na, __np, 1); 1987227825Stheraven return __r; 1988227825Stheraven} 1989227825Stheraven 1990227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 1991227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 1992227825Stheraven__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) 1993227825Stheraven{ 1994227825Stheraven while (__f != __l) 1995227825Stheraven __f = erase(__f); 1996253222Sdim return iterator(__l.__ptr_); 1997227825Stheraven} 1998227825Stheraven 1999227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2000227825Stheraventemplate <class _Key> 2001227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2002227825Stheraven__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) 2003227825Stheraven{ 2004227825Stheraven iterator __i = find(__k); 2005227825Stheraven if (__i == end()) 2006227825Stheraven return 0; 2007227825Stheraven erase(__i); 2008227825Stheraven return 1; 2009227825Stheraven} 2010227825Stheraven 2011227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2012227825Stheraventemplate <class _Key> 2013227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2014227825Stheraven__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) 2015227825Stheraven{ 2016227825Stheraven pair<iterator, iterator> __p = __equal_range_multi(__k); 2017227825Stheraven size_type __r = 0; 2018227825Stheraven for (; __p.first != __p.second; ++__r) 2019227825Stheraven __p.first = erase(__p.first); 2020227825Stheraven return __r; 2021227825Stheraven} 2022227825Stheraven 2023227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2024227825Stheraventemplate <class _Key> 2025227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 2026227825Stheraven__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) 2027227825Stheraven{ 2028227825Stheraven iterator __p = __lower_bound(__v, __root(), __end_node()); 2029227825Stheraven if (__p != end() && !value_comp()(__v, *__p)) 2030227825Stheraven return __p; 2031227825Stheraven return end(); 2032227825Stheraven} 2033227825Stheraven 2034227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2035227825Stheraventemplate <class _Key> 2036227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2037227825Stheraven__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const 2038227825Stheraven{ 2039227825Stheraven const_iterator __p = __lower_bound(__v, __root(), __end_node()); 2040227825Stheraven if (__p != end() && !value_comp()(__v, *__p)) 2041227825Stheraven return __p; 2042227825Stheraven return end(); 2043227825Stheraven} 2044227825Stheraven 2045227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2046227825Stheraventemplate <class _Key> 2047227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2048227825Stheraven__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const 2049227825Stheraven{ 2050227825Stheraven __node_const_pointer __result = __end_node(); 2051227825Stheraven __node_const_pointer __rt = __root(); 2052227825Stheraven while (__rt != nullptr) 2053227825Stheraven { 2054227825Stheraven if (value_comp()(__k, __rt->__value_)) 2055227825Stheraven { 2056227825Stheraven __result = __rt; 2057227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2058227825Stheraven } 2059227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2060227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2061227825Stheraven else 2062227825Stheraven return 1; 2063227825Stheraven } 2064227825Stheraven return 0; 2065227825Stheraven} 2066227825Stheraven 2067227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2068227825Stheraventemplate <class _Key> 2069227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::size_type 2070227825Stheraven__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const 2071227825Stheraven{ 2072232950Stheraven typedef pair<const_iterator, const_iterator> _Pp; 2073227825Stheraven __node_const_pointer __result = __end_node(); 2074227825Stheraven __node_const_pointer __rt = __root(); 2075227825Stheraven while (__rt != nullptr) 2076227825Stheraven { 2077227825Stheraven if (value_comp()(__k, __rt->__value_)) 2078227825Stheraven { 2079227825Stheraven __result = __rt; 2080227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2081227825Stheraven } 2082227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2083227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2084227825Stheraven else 2085227825Stheraven return _VSTD::distance( 2086227825Stheraven __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2087227825Stheraven __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result) 2088227825Stheraven ); 2089227825Stheraven } 2090227825Stheraven return 0; 2091227825Stheraven} 2092227825Stheraven 2093227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2094227825Stheraventemplate <class _Key> 2095227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 2096227825Stheraven__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2097227825Stheraven __node_pointer __root, 2098227825Stheraven __node_pointer __result) 2099227825Stheraven{ 2100227825Stheraven while (__root != nullptr) 2101227825Stheraven { 2102227825Stheraven if (!value_comp()(__root->__value_, __v)) 2103227825Stheraven { 2104227825Stheraven __result = __root; 2105227825Stheraven __root = static_cast<__node_pointer>(__root->__left_); 2106227825Stheraven } 2107227825Stheraven else 2108227825Stheraven __root = static_cast<__node_pointer>(__root->__right_); 2109227825Stheraven } 2110227825Stheraven return iterator(__result); 2111227825Stheraven} 2112227825Stheraven 2113227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2114227825Stheraventemplate <class _Key> 2115227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2116227825Stheraven__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2117227825Stheraven __node_const_pointer __root, 2118227825Stheraven __node_const_pointer __result) const 2119227825Stheraven{ 2120227825Stheraven while (__root != nullptr) 2121227825Stheraven { 2122227825Stheraven if (!value_comp()(__root->__value_, __v)) 2123227825Stheraven { 2124227825Stheraven __result = __root; 2125227825Stheraven __root = static_cast<__node_const_pointer>(__root->__left_); 2126227825Stheraven } 2127227825Stheraven else 2128227825Stheraven __root = static_cast<__node_const_pointer>(__root->__right_); 2129227825Stheraven } 2130227825Stheraven return const_iterator(__result); 2131227825Stheraven} 2132227825Stheraven 2133227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2134227825Stheraventemplate <class _Key> 2135227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::iterator 2136227825Stheraven__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2137227825Stheraven __node_pointer __root, 2138227825Stheraven __node_pointer __result) 2139227825Stheraven{ 2140227825Stheraven while (__root != nullptr) 2141227825Stheraven { 2142227825Stheraven if (value_comp()(__v, __root->__value_)) 2143227825Stheraven { 2144227825Stheraven __result = __root; 2145227825Stheraven __root = static_cast<__node_pointer>(__root->__left_); 2146227825Stheraven } 2147227825Stheraven else 2148227825Stheraven __root = static_cast<__node_pointer>(__root->__right_); 2149227825Stheraven } 2150227825Stheraven return iterator(__result); 2151227825Stheraven} 2152227825Stheraven 2153227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2154227825Stheraventemplate <class _Key> 2155227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2156227825Stheraven__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2157227825Stheraven __node_const_pointer __root, 2158227825Stheraven __node_const_pointer __result) const 2159227825Stheraven{ 2160227825Stheraven while (__root != nullptr) 2161227825Stheraven { 2162227825Stheraven if (value_comp()(__v, __root->__value_)) 2163227825Stheraven { 2164227825Stheraven __result = __root; 2165227825Stheraven __root = static_cast<__node_const_pointer>(__root->__left_); 2166227825Stheraven } 2167227825Stheraven else 2168227825Stheraven __root = static_cast<__node_const_pointer>(__root->__right_); 2169227825Stheraven } 2170227825Stheraven return const_iterator(__result); 2171227825Stheraven} 2172227825Stheraven 2173227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2174227825Stheraventemplate <class _Key> 2175227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2176227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::iterator> 2177227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 2178227825Stheraven{ 2179232950Stheraven typedef pair<iterator, iterator> _Pp; 2180227825Stheraven __node_pointer __result = __end_node(); 2181227825Stheraven __node_pointer __rt = __root(); 2182227825Stheraven while (__rt != nullptr) 2183227825Stheraven { 2184227825Stheraven if (value_comp()(__k, __rt->__value_)) 2185227825Stheraven { 2186227825Stheraven __result = __rt; 2187227825Stheraven __rt = static_cast<__node_pointer>(__rt->__left_); 2188227825Stheraven } 2189227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2190227825Stheraven __rt = static_cast<__node_pointer>(__rt->__right_); 2191227825Stheraven else 2192232950Stheraven return _Pp(iterator(__rt), 2193227825Stheraven iterator( 2194227825Stheraven __rt->__right_ != nullptr ? 2195227825Stheraven static_cast<__node_pointer>(__tree_min(__rt->__right_)) 2196227825Stheraven : __result)); 2197227825Stheraven } 2198232950Stheraven return _Pp(iterator(__result), iterator(__result)); 2199227825Stheraven} 2200227825Stheraven 2201227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2202227825Stheraventemplate <class _Key> 2203227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2204227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2205227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 2206227825Stheraven{ 2207232950Stheraven typedef pair<const_iterator, const_iterator> _Pp; 2208227825Stheraven __node_const_pointer __result = __end_node(); 2209227825Stheraven __node_const_pointer __rt = __root(); 2210227825Stheraven while (__rt != nullptr) 2211227825Stheraven { 2212227825Stheraven if (value_comp()(__k, __rt->__value_)) 2213227825Stheraven { 2214227825Stheraven __result = __rt; 2215227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2216227825Stheraven } 2217227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2218227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2219227825Stheraven else 2220232950Stheraven return _Pp(const_iterator(__rt), 2221227825Stheraven const_iterator( 2222227825Stheraven __rt->__right_ != nullptr ? 2223227825Stheraven static_cast<__node_const_pointer>(__tree_min(__rt->__right_)) 2224227825Stheraven : __result)); 2225227825Stheraven } 2226232950Stheraven return _Pp(const_iterator(__result), const_iterator(__result)); 2227227825Stheraven} 2228227825Stheraven 2229227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2230227825Stheraventemplate <class _Key> 2231227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2232227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::iterator> 2233227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 2234227825Stheraven{ 2235232950Stheraven typedef pair<iterator, iterator> _Pp; 2236227825Stheraven __node_pointer __result = __end_node(); 2237227825Stheraven __node_pointer __rt = __root(); 2238227825Stheraven while (__rt != nullptr) 2239227825Stheraven { 2240227825Stheraven if (value_comp()(__k, __rt->__value_)) 2241227825Stheraven { 2242227825Stheraven __result = __rt; 2243227825Stheraven __rt = static_cast<__node_pointer>(__rt->__left_); 2244227825Stheraven } 2245227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2246227825Stheraven __rt = static_cast<__node_pointer>(__rt->__right_); 2247227825Stheraven else 2248232950Stheraven return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt), 2249227825Stheraven __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2250227825Stheraven } 2251232950Stheraven return _Pp(iterator(__result), iterator(__result)); 2252227825Stheraven} 2253227825Stheraven 2254227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2255227825Stheraventemplate <class _Key> 2256227825Stheravenpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2257227825Stheraven typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2258227825Stheraven__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 2259227825Stheraven{ 2260232950Stheraven typedef pair<const_iterator, const_iterator> _Pp; 2261227825Stheraven __node_const_pointer __result = __end_node(); 2262227825Stheraven __node_const_pointer __rt = __root(); 2263227825Stheraven while (__rt != nullptr) 2264227825Stheraven { 2265227825Stheraven if (value_comp()(__k, __rt->__value_)) 2266227825Stheraven { 2267227825Stheraven __result = __rt; 2268227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__left_); 2269227825Stheraven } 2270227825Stheraven else if (value_comp()(__rt->__value_, __k)) 2271227825Stheraven __rt = static_cast<__node_const_pointer>(__rt->__right_); 2272227825Stheraven else 2273232950Stheraven return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2274227825Stheraven __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)); 2275227825Stheraven } 2276232950Stheraven return _Pp(const_iterator(__result), const_iterator(__result)); 2277227825Stheraven} 2278227825Stheraven 2279227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2280227825Stheraventypename __tree<_Tp, _Compare, _Allocator>::__node_holder 2281227825Stheraven__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 2282227825Stheraven{ 2283253222Sdim __node_pointer __np = __p.__ptr_; 2284227825Stheraven if (__begin_node() == __np) 2285227825Stheraven { 2286227825Stheraven if (__np->__right_ != nullptr) 2287227825Stheraven __begin_node() = static_cast<__node_pointer>(__np->__right_); 2288227825Stheraven else 2289227825Stheraven __begin_node() = static_cast<__node_pointer>(__np->__parent_); 2290227825Stheraven } 2291227825Stheraven --size(); 2292227825Stheraven __tree_remove(__end_node()->__left_, 2293227825Stheraven static_cast<__node_base_pointer>(__np)); 2294232950Stheraven return __node_holder(__np, _Dp(__node_alloc())); 2295227825Stheraven} 2296227825Stheraven 2297227825Stheraventemplate <class _Tp, class _Compare, class _Allocator> 2298227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2299227825Stheravenvoid 2300227825Stheravenswap(__tree<_Tp, _Compare, _Allocator>& __x, 2301227825Stheraven __tree<_Tp, _Compare, _Allocator>& __y) 2302227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2303227825Stheraven{ 2304227825Stheraven __x.swap(__y); 2305227825Stheraven} 2306227825Stheraven 2307227825Stheraven_LIBCPP_END_NAMESPACE_STD 2308227825Stheraven 2309227825Stheraven#endif // _LIBCPP___TREE 2310