36 #ifndef EASTL_RED_BLACK_TREE_H 37 #define EASTL_RED_BLACK_TREE_H 41 #include <stk_util/util/config_eastl.h> 42 #include <stk_util/util/type_traits_eastl.h> 43 #include <stk_util/util/allocator_eastl.h> 44 #include <stk_util/util/iterator_eastl.h> 45 #include <stk_util/util/utility_eastl.h> 46 #include <stk_util/util/algorithm_eastl.h> 49 #pragma warning(push, 0) 61 #pragma warning(disable: 4512) // 'class' : assignment operator could not be generated 62 #pragma warning(disable: 4530) // C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc 73 #ifndef EASTL_RBTREE_DEFAULT_NAME 74 #define EASTL_RBTREE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " rbtree" // Unless the user overrides something, this is "EASTL rbtree". 80 #ifndef EASTL_RBTREE_DEFAULT_ALLOCATOR 81 #define EASTL_RBTREE_DEFAULT_ALLOCATOR allocator_type(EASTL_RBTREE_DEFAULT_NAME) 130 template <
typename Value>
166 template <
typename T,
typename Po
inter,
typename Reference>
172 typedef eastl_size_t size_type;
173 typedef ptrdiff_t difference_type;
174 typedef T value_type;
177 typedef Pointer pointer;
178 typedef Reference reference;
179 typedef EASTL_ITC_NS::bidirectional_iterator_tag iterator_category;
189 reference operator*()
const;
190 pointer operator->()
const;
225 template <
typename Key,
typename Value,
typename Compare,
typename ExtractKey,
bool bUniqueKeys,
typename RBTree>
228 typedef ExtractKey extract_key;
235 rb_base(
const Compare& compare) : mCompare(compare) {}
244 template <
typename Key,
typename Value,
typename Compare,
typename ExtractKey,
typename RBTree>
245 struct rb_base<Key, Value, Compare, ExtractKey, false, RBTree>
247 typedef ExtractKey extract_key;
254 rb_base(
const Compare& compare) : mCompare(compare) {}
261 template <
typename Key,
typename Pair,
typename Compare,
typename RBTree>
271 rb_base(
const Compare& compare) : mCompare(compare) {}
278 template <
typename Key,
typename Pair,
typename Compare,
typename RBTree>
288 rb_base(
const Compare& compare) : mCompare(compare) {}
343 template <
typename Key,
typename Value,
typename Compare,
typename Allocator,
344 typename ExtractKey,
bool bMutableIterators,
bool bUniqueKeys>
346 :
public rb_base<Key, Value, Compare, ExtractKey, bUniqueKeys,
347 rbtree<Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys> >
350 typedef ptrdiff_t difference_type;
351 typedef eastl_size_t size_type;
352 typedef Key key_type;
353 typedef Value value_type;
355 typedef value_type& reference;
356 typedef const value_type& const_reference;
357 typedef typename type_select<bMutableIterators,
364 typedef Allocator allocator_type;
365 typedef Compare key_compare;
367 typedef rbtree<Key, Value, Compare, Allocator,
368 ExtractKey, bMutableIterators, bUniqueKeys>
this_type;
370 typedef integral_constant<bool, bUniqueKeys> has_unique_keys_type;
371 typedef typename base_type::extract_key extract_key;
373 using base_type::mCompare;
377 kKeyAlignment = EASTL_ALIGN_OF(key_type),
378 kKeyAlignmentOffset = 0,
379 kValueAlignment = EASTL_ALIGN_OF(value_type),
380 kValueAlignmentOffset = 0
392 rbtree(
const Compare& compare,
const allocator_type&
allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR);
395 template <
typename InputIterator>
396 rbtree(InputIterator first, InputIterator last,
const Compare& compare,
const allocator_type&
allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR);
402 allocator_type& get_allocator();
403 void set_allocator(
const allocator_type&
allocator);
405 const key_compare& key_comp()
const {
return mCompare; }
406 key_compare& key_comp() {
return mCompare; }
408 this_type& operator=(
const this_type& x);
410 void swap(this_type& x);
415 const_iterator begin()
const;
417 const_iterator end()
const;
419 reverse_iterator rbegin();
420 const_reverse_iterator rbegin()
const;
421 reverse_iterator rend();
422 const_reverse_iterator rend()
const;
426 size_type size()
const;
430 insert_return_type
insert(
const value_type& value);
441 iterator
insert(iterator position,
const value_type& value);
443 template <
typename InputIterator>
444 void insert(InputIterator first, InputIterator last);
446 iterator erase(iterator position);
447 iterator erase(iterator first, iterator last);
449 reverse_iterator erase(reverse_iterator position);
450 reverse_iterator erase(reverse_iterator first, reverse_iterator last);
458 void erase(
const key_type* first,
const key_type* last);
463 iterator find(
const key_type& key);
464 const_iterator find(
const key_type& key)
const;
477 template <
typename U,
typename Compare2>
478 iterator
find_as(
const U& u, Compare2 compare2);
480 template <
typename U,
typename Compare2>
481 const_iterator
find_as(
const U& u, Compare2 compare2)
const;
483 iterator lower_bound(
const key_type& key);
484 const_iterator lower_bound(
const key_type& key)
const;
486 iterator upper_bound(
const key_type& key);
487 const_iterator upper_bound(
const key_type& key)
const;
489 bool validate()
const;
490 int validate_iterator(const_iterator i)
const;
493 node_type* DoAllocateNode();
494 void DoFreeNode(node_type* pNode);
496 node_type* DoCreateNodeFromKey(
const key_type& key);
497 node_type* DoCreateNode(
const value_type& value);
498 node_type* DoCreateNode(
const node_type* pNodeSource, node_type* pNodeParent);
500 node_type* DoCopySubtree(
const node_type* pNodeSource, node_type* pNodeDest);
501 void DoNukeSubtree(node_type* pNode);
506 iterator DoInsertValue(
const value_type& value, false_type);
509 iterator DoInsertKey(
const key_type& key, false_type);
511 iterator DoInsertValue(iterator position,
const value_type& value, true_type);
512 iterator DoInsertValue(iterator position,
const value_type& value, false_type);
514 iterator DoInsertKey(iterator position,
const key_type& key, true_type);
515 iterator DoInsertKey(iterator position,
const key_type& key, false_type);
517 iterator DoInsertValueImpl(node_type* pNodeParent,
const value_type& value,
bool bForceToLeft);
518 iterator DoInsertKeyImpl(node_type* pNodeParent,
const key_type& key,
bool bForceToLeft);
530 EASTL_API
inline rbtree_node_base* RBTreeGetMinChild(
const rbtree_node_base* pNodeBase)
532 while(pNodeBase->mpNodeLeft)
533 pNodeBase = pNodeBase->mpNodeLeft;
534 return const_cast<rbtree_node_base*
>(pNodeBase);
537 EASTL_API
inline rbtree_node_base* RBTreeGetMaxChild(
const rbtree_node_base* pNodeBase)
539 while(pNodeBase->mpNodeRight)
540 pNodeBase = pNodeBase->mpNodeRight;
541 return const_cast<rbtree_node_base*
>(pNodeBase);
553 template <
typename T,
typename Po
inter,
typename Reference>
554 rbtree_iterator<T, Pointer, Reference>::rbtree_iterator()
558 template <
typename T,
typename Po
inter,
typename Reference>
559 rbtree_iterator<T, Pointer, Reference>::rbtree_iterator(
const node_type* pNode)
560 : mpNode(static_cast<node_type*>(const_cast<node_type*>(pNode))) { }
563 template <
typename T,
typename Po
inter,
typename Reference>
564 rbtree_iterator<T, Pointer, Reference>::rbtree_iterator(
const iterator& x)
565 : mpNode(x.mpNode) { }
568 template <
typename T,
typename Po
inter,
typename Reference>
569 typename rbtree_iterator<T, Pointer, Reference>::reference
570 rbtree_iterator<T, Pointer, Reference>::operator*()
const 571 {
return mpNode->mValue; }
574 template <
typename T,
typename Po
inter,
typename Reference>
575 typename rbtree_iterator<T, Pointer, Reference>::pointer
576 rbtree_iterator<T, Pointer, Reference>::operator->()
const 577 {
return &mpNode->mValue; }
580 template <
typename T,
typename Po
inter,
typename Reference>
581 typename rbtree_iterator<T, Pointer, Reference>::this_type&
582 rbtree_iterator<T, Pointer, Reference>::operator++()
589 template <
typename T,
typename Po
inter,
typename Reference>
590 typename rbtree_iterator<T, Pointer, Reference>::this_type
591 rbtree_iterator<T, Pointer, Reference>::operator++(
int)
593 this_type temp(*
this);
599 template <
typename T,
typename Po
inter,
typename Reference>
600 typename rbtree_iterator<T, Pointer, Reference>::this_type&
601 rbtree_iterator<T, Pointer, Reference>::operator--()
608 template <
typename T,
typename Po
inter,
typename Reference>
609 typename rbtree_iterator<T, Pointer, Reference>::this_type
610 rbtree_iterator<T, Pointer, Reference>::operator--(
int)
612 this_type temp(*
this);
621 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB>
622 inline bool operator==(
const rbtree_iterator<T, PointerA, ReferenceA>& a,
623 const rbtree_iterator<T, PointerB, ReferenceB>& b)
625 return a.mpNode == b.mpNode;
629 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB>
630 inline bool operator!=(
const rbtree_iterator<T, PointerA, ReferenceA>& a,
631 const rbtree_iterator<T, PointerB, ReferenceB>& b)
633 return a.mpNode != b.mpNode;
639 template <
typename T,
typename Po
inter,
typename Reference>
640 inline bool operator!=(
const rbtree_iterator<T, Pointer, Reference>& a,
641 const rbtree_iterator<T, Pointer, Reference>& b)
643 return a.mpNode != b.mpNode;
653 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
654 inline rbtree<K, V, C, A, E, bM, bU>::rbtree()
657 mAllocator(EASTL_RBTREE_DEFAULT_NAME)
663 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
664 inline rbtree<K, V, C, A, E, bM, bU>::rbtree(
const allocator_type& allocator)
667 mAllocator(allocator)
673 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
674 inline rbtree<K, V, C, A, E, bM, bU>::rbtree(
const C& compare,
const allocator_type& allocator)
675 : base_type(compare),
678 mAllocator(allocator)
684 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
685 inline rbtree<K, V, C, A, E, bM, bU>::rbtree(
const this_type& x)
686 : base_type(x.mCompare),
689 mAllocator(x.mAllocator)
693 if(x.mAnchor.mpNodeParent)
695 mAnchor.mpNodeParent = DoCopySubtree((
const node_type*)x.mAnchor.mpNodeParent, (node_type*)&mAnchor);
696 mAnchor.mpNodeRight = RBTreeGetMaxChild(mAnchor.mpNodeParent);
697 mAnchor.mpNodeLeft = RBTreeGetMinChild(mAnchor.mpNodeParent);
703 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
704 template <
typename InputIterator>
705 inline rbtree<K, V, C, A, E, bM, bU>::rbtree(InputIterator first, InputIterator last,
const C& compare,
const allocator_type& allocator)
706 : base_type(compare),
709 mAllocator(allocator)
713 #if EASTL_EXCEPTIONS_ENABLED 717 for(; first != last; ++first)
719 #if EASTL_EXCEPTIONS_ENABLED 730 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
731 inline rbtree<K, V, C, A, E, bM, bU>::~rbtree()
735 DoNukeSubtree((node_type*)mAnchor.mpNodeParent);
739 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
740 inline typename rbtree<K, V, C, A, E, bM, bU>::allocator_type&
741 rbtree<K, V, C, A, E, bM, bU>::get_allocator()
747 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
748 inline void rbtree<K, V, C, A, E, bM, bU>::set_allocator(
const allocator_type& allocator)
750 mAllocator = allocator;
754 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
755 inline typename rbtree<K, V, C, A, E, bM, bU>::size_type
756 rbtree<K, V, C, A, E, bM, bU>::size()
const 760 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
761 inline bool rbtree<K, V, C, A, E, bM, bU>::empty()
const 762 {
return (mnSize == 0); }
765 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
766 inline typename rbtree<K, V, C, A, E, bM, bU>::iterator
767 rbtree<K, V, C, A, E, bM, bU>::begin()
768 {
return iterator(static_cast<node_type*>(mAnchor.mpNodeLeft)); }
771 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
772 inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
773 rbtree<K, V, C, A, E, bM, bU>::begin()
const 774 {
return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(mAnchor.mpNodeLeft))); }
777 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
778 inline typename rbtree<K, V, C, A, E, bM, bU>::iterator
779 rbtree<K, V, C, A, E, bM, bU>::end()
780 {
return iterator(static_cast<node_type*>(&mAnchor)); }
783 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
784 inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
785 rbtree<K, V, C, A, E, bM, bU>::end()
const 786 {
return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(&mAnchor))); }
789 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
790 inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
791 rbtree<K, V, C, A, E, bM, bU>::rbegin()
792 {
return reverse_iterator(end()); }
795 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
796 inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator
797 rbtree<K, V, C, A, E, bM, bU>::rbegin()
const 798 {
return const_reverse_iterator(end()); }
801 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
802 inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
803 rbtree<K, V, C, A, E, bM, bU>::rend()
804 {
return reverse_iterator(begin()); }
807 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
808 inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator
809 rbtree<K, V, C, A, E, bM, bU>::rend()
const 810 {
return const_reverse_iterator(begin()); }
813 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
814 inline typename rbtree<K, V, C, A, E, bM, bU>::this_type&
815 rbtree<K, V, C, A, E, bM, bU>::operator=(
const this_type& x)
821 #if EASTL_ALLOCATOR_COPY_ENABLED 822 mAllocator = x.mAllocator;
825 base_type::mCompare = x.mCompare;
827 if(x.mAnchor.mpNodeParent)
829 mAnchor.mpNodeParent = DoCopySubtree((
const node_type*)x.mAnchor.mpNodeParent, (node_type*)&mAnchor);
830 mAnchor.mpNodeRight = RBTreeGetMaxChild(mAnchor.mpNodeParent);
831 mAnchor.mpNodeLeft = RBTreeGetMinChild(mAnchor.mpNodeParent);
839 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
840 void rbtree<K, V, C, A, E, bM, bU>::swap(this_type& x)
842 if(mAllocator == x.mAllocator)
856 if(mAnchor.mpNodeParent && x.mAnchor.mpNodeParent)
858 eastl::swap(mAnchor.mpNodeRight, x.mAnchor.mpNodeRight);
859 eastl::swap(mAnchor.mpNodeLeft, x.mAnchor.mpNodeLeft);
860 eastl::swap(mAnchor.mpNodeParent, x.mAnchor.mpNodeParent);
863 mAnchor.mpNodeParent->mpNodeParent = &mAnchor;
864 x.mAnchor.mpNodeParent->mpNodeParent = &x.mAnchor;
866 else if(mAnchor.mpNodeParent)
868 x.mAnchor.mpNodeRight = mAnchor.mpNodeRight;
869 x.mAnchor.mpNodeLeft = mAnchor.mpNodeLeft;
870 x.mAnchor.mpNodeParent = mAnchor.mpNodeParent;
871 x.mAnchor.mpNodeParent->mpNodeParent = &x.mAnchor;
874 mAnchor.mpNodeRight = &mAnchor;
875 mAnchor.mpNodeLeft = &mAnchor;
876 mAnchor.mpNodeParent = NULL;
878 else if(x.mAnchor.mpNodeParent)
880 mAnchor.mpNodeRight = x.mAnchor.mpNodeRight;
881 mAnchor.mpNodeLeft = x.mAnchor.mpNodeLeft;
882 mAnchor.mpNodeParent = x.mAnchor.mpNodeParent;
883 mAnchor.mpNodeParent->mpNodeParent = &mAnchor;
886 x.mAnchor.mpNodeRight = &x.mAnchor;
887 x.mAnchor.mpNodeLeft = &x.mAnchor;
888 x.mAnchor.mpNodeParent = NULL;
893 const this_type temp(*
this);
900 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
901 inline typename rbtree<K, V, C, A, E, bM, bU>::insert_return_type
903 {
return DoInsertValue(value, has_unique_keys_type()); }
906 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
909 {
return DoInsertValue(position, value, has_unique_keys_type()); }
912 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
914 rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(
const value_type& value, true_type)
919 extract_key extractKey;
921 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
922 node_type* pLowerBound = (node_type*)&mAnchor;
925 bool bValueLessThanNode =
true;
930 while(EASTL_LIKELY(pCurrent))
932 bValueLessThanNode = mCompare(extractKey(value), extractKey(pCurrent->mValue));
933 pLowerBound = pCurrent;
935 if(bValueLessThanNode)
937 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), extractKey(value)));
938 pCurrent = (node_type*)pCurrent->mpNodeLeft;
941 pCurrent = (node_type*)pCurrent->mpNodeRight;
944 pParent = pLowerBound;
946 if(bValueLessThanNode)
948 if(EASTL_LIKELY(pLowerBound != (node_type*)mAnchor.mpNodeLeft))
956 const iterator itResult(DoInsertValueImpl(pLowerBound, value,
false));
957 return pair<iterator, bool>(itResult,
true);
962 if(mCompare(extractKey(pLowerBound->mValue), extractKey(value)))
964 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(value), extractKey(pLowerBound->mValue)));
965 const iterator itResult(DoInsertValueImpl(pParent, value,
false));
966 return pair<iterator, bool>(itResult,
true);
970 return pair<iterator, bool>(iterator(pLowerBound),
false);
974 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
975 typename rbtree<K, V, C, A, E, bM, bU>::iterator
976 rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(
const value_type& value, false_type)
979 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
980 node_type* pRangeEnd = (node_type*)&mAnchor;
981 extract_key extractKey;
985 pRangeEnd = pCurrent;
987 if(mCompare(extractKey(value), extractKey(pCurrent->mValue)))
989 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), extractKey(value)));
990 pCurrent = (node_type*)pCurrent->mpNodeLeft;
993 pCurrent = (node_type*)pCurrent->mpNodeRight;
996 return DoInsertValueImpl(pRangeEnd, value,
false);
1000 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1002 rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(
const key_type& key, true_type)
1006 extract_key extractKey;
1008 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
1009 node_type* pLowerBound = (node_type*)&mAnchor;
1012 bool bValueLessThanNode =
true;
1017 while(EASTL_LIKELY(pCurrent))
1019 bValueLessThanNode = mCompare(key, extractKey(pCurrent->mValue));
1020 pLowerBound = pCurrent;
1022 if(bValueLessThanNode)
1024 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), key));
1025 pCurrent = (node_type*)pCurrent->mpNodeLeft;
1028 pCurrent = (node_type*)pCurrent->mpNodeRight;
1031 pParent = pLowerBound;
1033 if(bValueLessThanNode)
1035 if(EASTL_LIKELY(pLowerBound != (node_type*)mAnchor.mpNodeLeft))
1043 const iterator itResult(DoInsertKeyImpl(pLowerBound, key,
false));
1044 return pair<iterator, bool>(itResult,
true);
1049 if(mCompare(extractKey(pLowerBound->mValue), key))
1051 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(pLowerBound->mValue)));
1052 const iterator itResult(DoInsertKeyImpl(pParent, key,
false));
1053 return pair<iterator, bool>(itResult,
true);
1057 return pair<iterator, bool>(iterator(pLowerBound),
false);
1061 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1062 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1063 rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(
const key_type& key, false_type)
1066 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
1067 node_type* pRangeEnd = (node_type*)&mAnchor;
1068 extract_key extractKey;
1072 pRangeEnd = pCurrent;
1074 if(mCompare(key, extractKey(pCurrent->mValue)))
1076 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), key));
1077 pCurrent = (node_type*)pCurrent->mpNodeLeft;
1080 pCurrent = (node_type*)pCurrent->mpNodeRight;
1083 return DoInsertKeyImpl(pRangeEnd, key,
false);
1087 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1088 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1089 rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(iterator position,
const value_type& value, true_type)
1095 extract_key extractKey;
1097 if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor))
1099 iterator itNext(position);
1105 const bool bPositionLessThanValue = mCompare(extractKey(position.mpNode->mValue), extractKey(value));
1107 if(bPositionLessThanValue)
1109 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(value), extractKey(position.mpNode->mValue)));
1111 const bool bValueLessThanNext = mCompare(extractKey(value), extractKey(itNext.mpNode->mValue));
1113 if(bValueLessThanNext)
1115 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(itNext.mpNode->mValue), extractKey(value)));
1117 if(position.mpNode->mpNodeRight)
1118 return DoInsertValueImpl(itNext.mpNode, value,
true);
1119 return DoInsertValueImpl(position.mpNode, value,
false);
1123 return DoInsertValue(value, has_unique_keys_type()).first;
1126 if(mnSize && mCompare(extractKey(((node_type*)mAnchor.mpNodeRight)->mValue), extractKey(value)))
1128 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(value), extractKey(((node_type*)mAnchor.mpNodeRight)->mValue)));
1129 return DoInsertValueImpl((node_type*)mAnchor.mpNodeRight, value,
false);
1132 return DoInsertValue(value, has_unique_keys_type()).first;
1136 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1137 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1138 rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(iterator position,
const value_type& value, false_type)
1144 extract_key extractKey;
1146 if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor))
1148 iterator itNext(position);
1155 if(!mCompare(extractKey(value), extractKey(position.mpNode->mValue)) &&
1156 !mCompare(extractKey(itNext.mpNode->mValue), extractKey(value)))
1158 if(position.mpNode->mpNodeRight)
1159 return DoInsertValueImpl(itNext.mpNode, value,
true);
1160 return DoInsertValueImpl(position.mpNode, value,
false);
1163 return DoInsertValue(value, has_unique_keys_type());
1169 if(mnSize && !mCompare(extractKey(value), extractKey(((node_type*)mAnchor.mpNodeRight)->mValue)))
1170 return DoInsertValueImpl((node_type*)mAnchor.mpNodeRight, value,
false);
1172 return DoInsertValue(value, has_unique_keys_type());
1176 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1177 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1178 rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(iterator position,
const key_type& key, true_type)
1184 extract_key extractKey;
1186 if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor))
1188 iterator itNext(position);
1194 const bool bPositionLessThanValue = mCompare(extractKey(position.mpNode->mValue), key);
1196 if(bPositionLessThanValue)
1198 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(position.mpNode->mValue)));
1200 const bool bValueLessThanNext = mCompare(key, extractKey(itNext.mpNode->mValue));
1202 if(bValueLessThanNext)
1204 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(itNext.mpNode->mValue), key));
1206 if(position.mpNode->mpNodeRight)
1207 return DoInsertKeyImpl(itNext.mpNode, key,
true);
1208 return DoInsertKeyImpl(position.mpNode, key,
false);
1212 return DoInsertKey(key, has_unique_keys_type()).first;
1215 if(mnSize && mCompare(extractKey(((node_type*)mAnchor.mpNodeRight)->mValue), key))
1217 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(((node_type*)mAnchor.mpNodeRight)->mValue)));
1218 return DoInsertKeyImpl((node_type*)mAnchor.mpNodeRight, key,
false);
1221 return DoInsertKey(key, has_unique_keys_type()).first;
1225 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1226 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1227 rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(iterator position,
const key_type& key, false_type)
1233 extract_key extractKey;
1235 if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor))
1237 iterator itNext(position);
1243 if(!mCompare(key, extractKey(position.mpNode->mValue)) &&
1244 !mCompare(extractKey(itNext.mpNode->mValue), key))
1246 if(position.mpNode->mpNodeRight)
1247 return DoInsertKeyImpl(itNext.mpNode, key,
true);
1248 return DoInsertKeyImpl(position.mpNode, key,
false);
1251 return DoInsertKey(key, has_unique_keys_type());
1256 if(mnSize && !mCompare(key, extractKey(((node_type*)mAnchor.mpNodeRight)->mValue)))
1257 return DoInsertKeyImpl((node_type*)mAnchor.mpNodeRight, key,
false);
1259 return DoInsertKey(key, has_unique_keys_type());
1263 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1264 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1265 rbtree<K, V, C, A, E, bM, bU>::DoInsertValueImpl(node_type* pNodeParent,
const value_type& value,
bool bForceToLeft)
1268 extract_key extractKey;
1273 if(bForceToLeft || (pNodeParent == &mAnchor) || mCompare(extractKey(value), extractKey(pNodeParent->mValue)))
1274 side = kRBTreeSideLeft;
1276 side = kRBTreeSideRight;
1278 node_type*
const pNodeNew = DoCreateNode(value);
1282 return iterator(pNodeNew);
1286 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1287 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1288 rbtree<K, V, C, A, E, bM, bU>::DoInsertKeyImpl(node_type* pNodeParent,
const key_type& key,
bool bForceToLeft)
1291 extract_key extractKey;
1296 if(bForceToLeft || (pNodeParent == &mAnchor) || mCompare(key, extractKey(pNodeParent->mValue)))
1297 side = kRBTreeSideLeft;
1299 side = kRBTreeSideRight;
1301 node_type*
const pNodeNew = DoCreateNodeFromKey(key);
1305 return iterator(pNodeNew);
1309 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1310 template <
typename InputIterator>
1313 for( ; first != last; ++first)
1314 DoInsertValue(*first, has_unique_keys_type());
1318 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1319 inline void rbtree<K, V, C, A, E, bM, bU>::clear()
1323 DoNukeSubtree((node_type*)mAnchor.mpNodeParent);
1328 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1329 inline void rbtree<K, V, C, A, E, bM, bU>::reset()
1335 mAnchor.mpNodeRight = &mAnchor;
1336 mAnchor.mpNodeLeft = &mAnchor;
1337 mAnchor.mpNodeParent = NULL;
1338 mAnchor.mColor = kRBTreeColorRed;
1343 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1344 inline typename rbtree<K, V, C, A, E, bM, bU>::iterator
1345 rbtree<K, V, C, A, E, bM, bU>::erase(iterator position)
1347 const iterator iErase(position);
1351 DoFreeNode(iErase.mpNode);
1356 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1357 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1358 rbtree<K, V, C, A, E, bM, bU>::erase(iterator first, iterator last)
1361 if(EASTL_LIKELY((first.mpNode != mAnchor.mpNodeLeft) || (last.mpNode != &mAnchor)))
1364 while(first != last)
1365 first = erase(first);
1383 return iterator((node_type*)&mAnchor);
1387 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1388 inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
1389 rbtree<K, V, C, A, E, bM, bU>::erase(reverse_iterator position)
1391 return reverse_iterator(erase((++position).base()));
1395 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1396 typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
1397 rbtree<K, V, C, A, E, bM, bU>::erase(reverse_iterator first, reverse_iterator last)
1406 return reverse_iterator(erase((++last).base(), (++first).base()));
1410 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1411 inline void rbtree<K, V, C, A, E, bM, bU>::erase(
const key_type* first,
const key_type* last)
1416 while(first != last)
1421 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1422 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1423 rbtree<K, V, C, A, E, bM, bU>::find(
const key_type& key)
1431 extract_key extractKey;
1433 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
1434 node_type* pRangeEnd = (node_type*)&mAnchor;
1436 while(EASTL_LIKELY(pCurrent))
1438 if(EASTL_LIKELY(!mCompare(extractKey(pCurrent->mValue), key)))
1440 pRangeEnd = pCurrent;
1441 pCurrent = (node_type*)pCurrent->mpNodeLeft;
1445 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(pCurrent->mValue)));
1446 pCurrent = (node_type*)pCurrent->mpNodeRight;
1450 if(EASTL_LIKELY((pRangeEnd != &mAnchor) && !mCompare(key, extractKey(pRangeEnd->mValue))))
1451 return iterator(pRangeEnd);
1452 return iterator((node_type*)&mAnchor);
1456 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1457 inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
1458 rbtree<K, V, C, A, E, bM, bU>::find(
const key_type& key)
const 1460 typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
1461 return const_iterator(const_cast<rbtree_type*>(
this)->
find(key));
1465 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1466 template <
typename U,
typename Compare2>
1467 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1470 extract_key extractKey;
1475 while(EASTL_LIKELY(pCurrent))
1477 if(EASTL_LIKELY(!compare2(extractKey(pCurrent->mValue), u)))
1479 pRangeEnd = pCurrent;
1480 pCurrent = (
node_type*)pCurrent->mpNodeLeft;
1484 EASTL_VALIDATE_COMPARE(!compare2(u, extractKey(pCurrent->mValue)));
1485 pCurrent = (
node_type*)pCurrent->mpNodeRight;
1489 if(EASTL_LIKELY((pRangeEnd != &mAnchor) && !compare2(u, extractKey(pRangeEnd->mValue))))
1495 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1496 template <
typename U,
typename Compare2>
1501 return const_iterator(const_cast<rbtree_type*>(
this)->find_as(u, compare2));
1505 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1506 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1507 rbtree<K, V, C, A, E, bM, bU>::lower_bound(
const key_type& key)
1509 extract_key extractKey;
1511 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
1512 node_type* pRangeEnd = (node_type*)&mAnchor;
1514 while(EASTL_LIKELY(pCurrent))
1516 if(EASTL_LIKELY(!mCompare(extractKey(pCurrent->mValue), key)))
1518 pRangeEnd = pCurrent;
1519 pCurrent = (node_type*)pCurrent->mpNodeLeft;
1523 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(pCurrent->mValue)));
1524 pCurrent = (node_type*)pCurrent->mpNodeRight;
1528 return iterator(pRangeEnd);
1532 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1533 inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
1534 rbtree<K, V, C, A, E, bM, bU>::lower_bound(
const key_type& key)
const 1536 typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
1537 return const_iterator(const_cast<rbtree_type*>(
this)->
lower_bound(key));
1541 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1542 typename rbtree<K, V, C, A, E, bM, bU>::iterator
1543 rbtree<K, V, C, A, E, bM, bU>::upper_bound(
const key_type& key)
1545 extract_key extractKey;
1547 node_type* pCurrent = (node_type*)mAnchor.mpNodeParent;
1548 node_type* pRangeEnd = (node_type*)&mAnchor;
1550 while(EASTL_LIKELY(pCurrent))
1552 if(EASTL_LIKELY(mCompare(key, extractKey(pCurrent->mValue))))
1554 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), key));
1555 pRangeEnd = pCurrent;
1556 pCurrent = (node_type*)pCurrent->mpNodeLeft;
1559 pCurrent = (node_type*)pCurrent->mpNodeRight;
1562 return iterator(pRangeEnd);
1566 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1567 inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
1568 rbtree<K, V, C, A, E, bM, bU>::upper_bound(
const key_type& key)
const 1570 typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
1571 return const_iterator(const_cast<rbtree_type*>(
this)->
upper_bound(key));
1576 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1577 bool rbtree<K, V, C, A, E, bM, bU>::validate()
const 1589 extract_key extractKey;
1597 if(mAnchor.mpNodeLeft != RBTreeGetMinChild(mAnchor.mpNodeParent))
1600 if(mAnchor.mpNodeRight != RBTreeGetMaxChild(mAnchor.mpNodeParent))
1604 size_type nIteratedSize = 0;
1606 for(const_iterator it = begin(); it != end(); ++it, ++nIteratedSize)
1608 const node_type*
const pNode = (
const node_type*)it.mpNode;
1609 const node_type*
const pNodeRight = (
const node_type*)pNode->mpNodeRight;
1610 const node_type*
const pNodeLeft = (
const node_type*)pNode->mpNodeLeft;
1613 if(pNodeRight && mCompare(extractKey(pNodeRight->mValue), extractKey(pNode->mValue)) && mCompare(extractKey(pNode->mValue), extractKey(pNodeRight->mValue)))
1617 if(pNodeLeft && mCompare(extractKey(pNodeLeft->mValue), extractKey(pNode->mValue)) && mCompare(extractKey(pNode->mValue), extractKey(pNodeLeft->mValue)))
1621 if((pNode->mColor != kRBTreeColorRed) && (pNode->mColor != kRBTreeColorBlack))
1625 if(pNode->mColor == kRBTreeColorRed)
1627 if((pNodeRight && (pNodeRight->mColor == kRBTreeColorRed)) ||
1628 (pNodeLeft && (pNodeLeft->mColor == kRBTreeColorRed)))
1633 if(pNodeRight && mCompare(extractKey(pNodeRight->mValue), extractKey(pNode->mValue)))
1636 if(pNodeLeft && mCompare(extractKey(pNode->mValue), extractKey(pNodeLeft->mValue)))
1639 if(!pNodeRight && !pNodeLeft)
1648 if(nIteratedSize != mnSize)
1655 if((mAnchor.mpNodeLeft != &mAnchor) || (mAnchor.mpNodeRight != &mAnchor))
1663 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1664 inline int rbtree<K, V, C, A, E, bM, bU>::validate_iterator(const_iterator i)
const 1668 for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
1681 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1682 inline typename rbtree<K, V, C, A, E, bM, bU>::node_type*
1683 rbtree<K, V, C, A, E, bM, bU>::DoAllocateNode()
1685 return (node_type*)
allocate_memory(mAllocator,
sizeof(node_type), kValueAlignment, kValueAlignmentOffset);
1689 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1690 inline void rbtree<K, V, C, A, E, bM, bU>::DoFreeNode(node_type* pNode)
1692 pNode->~node_type();
1693 EASTLFree(mAllocator, pNode,
sizeof(node_type));
1697 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1698 typename rbtree<K, V, C, A, E, bM, bU>::node_type*
1699 rbtree<K, V, C, A, E, bM, bU>::DoCreateNodeFromKey(
const key_type& key)
1704 node_type*
const pNode = DoAllocateNode();
1706 #if EASTL_EXCEPTIONS_ENABLED 1710 ::new(&pNode->mValue) value_type(key);
1712 #if EASTL_EXCEPTIONS_ENABLED 1722 pNode->mpNodeRight = NULL;
1723 pNode->mpNodeLeft = NULL;
1724 pNode->mpNodeParent = NULL;
1725 pNode->mColor = kRBTreeColorBlack;
1732 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1733 typename rbtree<K, V, C, A, E, bM, bU>::node_type*
1734 rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(
const value_type& value)
1739 node_type*
const pNode = DoAllocateNode();
1741 #if EASTL_EXCEPTIONS_ENABLED 1745 ::new(&pNode->mValue) value_type(value);
1746 #if EASTL_EXCEPTIONS_ENABLED 1756 pNode->mpNodeRight = NULL;
1757 pNode->mpNodeLeft = NULL;
1758 pNode->mpNodeParent = NULL;
1759 pNode->mColor = kRBTreeColorBlack;
1766 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1767 typename rbtree<K, V, C, A, E, bM, bU>::node_type*
1768 rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(
const node_type* pNodeSource, node_type* pNodeParent)
1770 node_type*
const pNode = DoCreateNode(pNodeSource->mValue);
1772 pNode->mpNodeRight = NULL;
1773 pNode->mpNodeLeft = NULL;
1774 pNode->mpNodeParent = pNodeParent;
1775 pNode->mColor = pNodeSource->mColor;
1781 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1782 typename rbtree<K, V, C, A, E, bM, bU>::node_type*
1783 rbtree<K, V, C, A, E, bM, bU>::DoCopySubtree(
const node_type* pNodeSource, node_type* pNodeDest)
1785 node_type*
const pNewNodeRoot = DoCreateNode(pNodeSource, pNodeDest);
1787 #if EASTL_EXCEPTIONS_ENABLED 1792 if(pNodeSource->mpNodeRight)
1793 pNewNodeRoot->mpNodeRight = DoCopySubtree((
const node_type*)pNodeSource->mpNodeRight, pNewNodeRoot);
1795 node_type* pNewNodeLeft;
1797 for(pNodeSource = (node_type*)pNodeSource->mpNodeLeft, pNodeDest = pNewNodeRoot;
1799 pNodeSource = (node_type*)pNodeSource->mpNodeLeft, pNodeDest = pNewNodeLeft)
1801 pNewNodeLeft = DoCreateNode(pNodeSource, pNodeDest);
1803 pNodeDest->mpNodeLeft = pNewNodeLeft;
1806 if(pNodeSource->mpNodeRight)
1807 pNewNodeLeft->mpNodeRight = DoCopySubtree((
const node_type*)pNodeSource->mpNodeRight, pNewNodeLeft);
1809 #if EASTL_EXCEPTIONS_ENABLED 1813 DoNukeSubtree(pNewNodeRoot);
1818 return pNewNodeRoot;
1822 template <
typename K,
typename V,
typename C,
typename A,
typename E,
bool bM,
bool bU>
1823 void rbtree<K, V, C, A, E, bM, bU>::DoNukeSubtree(node_type* pNode)
1827 DoNukeSubtree((node_type*)pNode->mpNodeRight);
1829 node_type*
const pNodeLeft = (node_type*)pNode->mpNodeLeft;
1841 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1842 inline bool operator==(
const rbtree<K, V, C, A, E, bM, bU>& a,
const rbtree<K, V, C, A, E, bM, bU>& b)
1844 return (a.size() == b.size()) &&
eastl::equal(a.begin(), a.end(), b.begin());
1854 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1855 inline bool operator<(const rbtree<K, V, C, A, E, bM, bU>& a,
const rbtree<K, V, C, A, E, bM, bU>& b)
1861 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1862 inline bool operator!=(
const rbtree<K, V, C, A, E, bM, bU>& a,
const rbtree<K, V, C, A, E, bM, bU>& b)
1868 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1869 inline bool operator>(
const rbtree<K, V, C, A, E, bM, bU>& a,
const rbtree<K, V, C, A, E, bM, bU>& b)
1875 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1876 inline bool operator<=(const rbtree<K, V, C, A, E, bM, bU>& a,
const rbtree<K, V, C, A, E, bM, bU>& b)
1882 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1883 inline bool operator>=(
const rbtree<K, V, C, A, E, bM, bU>& a,
const rbtree<K, V, C, A, E, bM, bU>& b)
1889 template <
typename K,
typename V,
typename A,
typename C,
typename E,
bool bM,
bool bU>
1890 inline void swap(rbtree<K, V, C, A, E, bM, bU>& a, rbtree<K, V, C, A, E, bM, bU>& b)
1900 #pragma warning(pop) 1904 #endif // Header include guard
EASTL_API void RBTreeErase(rbtree_node_base *pNode, rbtree_node_base *pNodeAnchor)
allocator_type mAllocator
Stores the count of nodes in the tree (not counting the anchor node).
EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base *pNodeTop, const rbtree_node_base *pNodeBottom)
The iterator is valid and points to the same element it did when created. For example, if an iterator points to vector::begin() but an element is inserted at the front, the iterator is valid but not current. Modification of elements in place do not make iterators non-current.
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T &value)
EASTL_API rbtree_node_base * RBTreeIncrement(const rbtree_node_base *pNode)
size_type mnSize
This node acts as end() and its mpLeft points to begin(), and mpRight points to rbegin() (the last no...
insert_return_type insert(const value_type &value)
EASTL_API void RBTreeInsert(rbtree_node_base *pNode, rbtree_node_base *pNodeParent, rbtree_node_base *pNodeAnchor, RBTreeSide insertionSide)
iterator find_as(const U &u, Compare2 compare2)
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &value)
InputIterator find(InputIterator first, InputIterator last, const T &value)
The iterator is valid, which means it is in the range of [begin, end].
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
This is called none and not called invalid because it is not strictly the opposite of invalid...
void reset(MPI_Comm new_comm)
Function reset determines new parallel_size and parallel_rank. Flushes, closes, and reopens log files...
void * allocate_memory(Allocator &a, size_t n, size_t alignment, size_t alignmentOffset)
EASTL_API rbtree_node_base * RBTreeDecrement(const rbtree_node_base *pNode)
EA Standard Template Library.
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)