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