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