RedBlackTree<KeyType, ValueType, KeyOfValue, Compare> Class

Template Parameters | Constraint | Constructors & Destructor | Member Functions | Type Aliases | Member Variables

A red-black tree.

Model of BidirectionalContainer .

Definition

Line 529 of System.Base/RedBlackTree.cm

Template Parameters

KeyType
ValueType
KeyOfValue
Compare

Constraint

KeyType  is  Semiregular  and  ValueType  is  Semiregular  and  KeySelectionFunction <KeyOfValue , KeyType , ValueType > and  Compare  is  Relation  and  Compare .Domain is  KeyType

Constructors & Destructor

public RedBlackTree()
public RedBlackTree(RedBlackTree&& that)
public RedBlackTree(const RedBlackTree& that)
public ~RedBlackTree()

Member Functions

public inline RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Begin()
public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> Begin() const
public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CBegin() const
public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CEnd() const
public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CFind(const KeyType& key) const
public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CLowerBound(const KeyType& key) const
public void Clear()
private RedBlackTreeNode<ValueType>* CloneNode(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p) const
private inline bool Comp(const KeyType& left, const KeyType& right) const
private RedBlackTreeNode<ValueType>* Copy(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p)
private void CopyFrom(const RedBlackTree& that)
public inline long Count() const
public inline RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> End()
public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> End() const
public RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Find(const KeyType& key)
public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> Find(const KeyType& key) const
public void Init()
private RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Insert(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p, ValueType&& value)
private RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Insert(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p, const ValueType& value)
public Pair<RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*>, bool> Insert(ValueType&& value)
public Pair<RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*>, bool> Insert(const ValueType& value)
public inline bool IsEmpty() const
private inline const KeyType& KeyOf(const ValueType& value) const
private inline RedBlackTreeNode<ValueType>* Leftmost()
private inline RedBlackTreeNodeBase*& LeftmostRef()
public RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> LowerBound(const KeyType& key)
public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> LowerBound(const KeyType& key) const
public void Remove(RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> pos)
public bool Remove(const KeyType& key)
private inline RedBlackTreeNode<ValueType>* Rightmost()
private inline RedBlackTreeNodeBase*& RightmostRef()
private inline RedBlackTreeNode<ValueType>* Root()
private inline RedBlackTreeNodeBase*& RootRef()
private inline void SetLeftmost(RedBlackTreeNode<ValueType>* lm)
private inline void SetRightmost(RedBlackTreeNode<ValueType>* rm)
private inline void SetRoot(RedBlackTreeNode<ValueType>* root)
public void operator=(RedBlackTree&& that)
public void operator=(const RedBlackTree& that)

Type Aliases

public typedef ConstIterator RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*>
public typedef Iterator RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*>
private typedef Self RedBlackTree

Member Variables

private Compare comp
private long count
private UniquePtr<RedBlackTreeNode<ValueType>> header
private KeyOfValue keyOf

Constructor& Destructor Details

RedBlackTree Constructor

public RedBlackTree()

Definition
Line 537 of System.Base/RedBlackTree.cm

RedBlackTree Constructor

public RedBlackTree(RedBlackTree&& that)

Definition
Line 547 of System.Base/RedBlackTree.cm

RedBlackTree Constructor

public RedBlackTree(const RedBlackTree& that)

Definition
Line 541 of System.Base/RedBlackTree.cm

~RedBlackTree Destructor

public ~RedBlackTree()

Definition
Line 567 of System.Base/RedBlackTree.cm

Member Function Details

Begin Member Function

public inline RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Begin()

Definition
Line 582 of System.Base/RedBlackTree.cm

Begin Member Function

public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> Begin()

Definition
Line 571 of System.Base/RedBlackTree.cm

CBegin Member Function

public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CBegin()

Definition
Line 593 of System.Base/RedBlackTree.cm

CEnd Member Function

public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CEnd()

Definition
Line 612 of System.Base/RedBlackTree.cm

CFind Member Function

public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CFind(const KeyType& key)

Definition
Line 702 of System.Base/RedBlackTree.cm

CLowerBound Member Function

public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> CLowerBound(const KeyType& key)

Definition
Line 776 of System.Base/RedBlackTree.cm

Clear Member Function

public void Clear()

Definition
Line 626 of System.Base/RedBlackTree.cm

CloneNode Member Function

private RedBlackTreeNode<ValueType>* CloneNode(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p)

Definition
Line 1032 of System.Base/RedBlackTree.cm

Comp Member Function

private inline bool Comp(const KeyType& left, const KeyType& right)

Definition
Line 1043 of System.Base/RedBlackTree.cm

Copy Member Function

private RedBlackTreeNode<ValueType>* Copy(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p)

Definition
Line 1009 of System.Base/RedBlackTree.cm

CopyFrom Member Function

private void CopyFrom(const RedBlackTree& that)

Constraint
ValueType  is  Copyable
Definition
Line 997 of System.Base/RedBlackTree.cm

Count Member Function

public inline long Count()

Definition
Line 616 of System.Base/RedBlackTree.cm

End Member Function

public inline RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> End()

Definition
Line 608 of System.Base/RedBlackTree.cm

End Member Function

public inline RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> End()

Definition
Line 604 of System.Base/RedBlackTree.cm

Find Member Function

public RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Find(const KeyType& key)

Definition
Line 642 of System.Base/RedBlackTree.cm

Find Member Function

public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> Find(const KeyType& key)

Definition
Line 672 of System.Base/RedBlackTree.cm

Init Member Function

public void Init()

Definition
Line 990 of System.Base/RedBlackTree.cm

Insert Member Function

private RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Insert(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p, ValueType&& value)

Constraint
ValueType  is  Movable
Definition
Line 913 of System.Base/RedBlackTree.cm

Insert Member Function

private RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Insert(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p, const ValueType& value)

Constraint
ValueType  is  Copyable
Definition
Line 880 of System.Base/RedBlackTree.cm

Insert Member Function

public Pair<RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*>, bool> Insert(ValueType&& value)

Constraint
ValueType  is  Movable
Definition
Line 839 of System.Base/RedBlackTree.cm

Insert Member Function

public Pair<RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*>, bool> Insert(const ValueType& value)

Constraint
ValueType  is  Copyable
Definition
Line 798 of System.Base/RedBlackTree.cm

IsEmpty Member Function

public inline bool IsEmpty()

Definition
Line 621 of System.Base/RedBlackTree.cm

KeyOf Member Function

private inline const KeyType& KeyOf(const ValueType& value)

Definition
Line 1039 of System.Base/RedBlackTree.cm

Leftmost Member Function

private inline RedBlackTreeNode<ValueType>* Leftmost()

Definition
Line 1059 of System.Base/RedBlackTree.cm

LeftmostRef Member Function

private inline RedBlackTreeNodeBase*& LeftmostRef()

Definition
Line 1063 of System.Base/RedBlackTree.cm

LowerBound Member Function

public RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> LowerBound(const KeyType& key)

Definition
Line 732 of System.Base/RedBlackTree.cm

LowerBound Member Function

public RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> LowerBound(const KeyType& key)

Definition
Line 754 of System.Base/RedBlackTree.cm

Remove Member Function

public void Remove(RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> pos)

Definition
Line 982 of System.Base/RedBlackTree.cm

Remove Member Function

public bool Remove(const KeyType& key)

Definition
Line 946 of System.Base/RedBlackTree.cm

Rightmost Member Function

private inline RedBlackTreeNode<ValueType>* Rightmost()

Definition
Line 1071 of System.Base/RedBlackTree.cm

RightmostRef Member Function

private inline RedBlackTreeNodeBase*& RightmostRef()

Definition
Line 1075 of System.Base/RedBlackTree.cm

Root Member Function

private inline RedBlackTreeNode<ValueType>* Root()

Definition
Line 1047 of System.Base/RedBlackTree.cm

RootRef Member Function

private inline RedBlackTreeNodeBase*& RootRef()

Definition
Line 1051 of System.Base/RedBlackTree.cm

SetLeftmost Member Function

private inline void SetLeftmost(RedBlackTreeNode<ValueType>* lm)

Definition
Line 1067 of System.Base/RedBlackTree.cm

SetRightmost Member Function

private inline void SetRightmost(RedBlackTreeNode<ValueType>* rm)

Definition
Line 1079 of System.Base/RedBlackTree.cm

SetRoot Member Function

private inline void SetRoot(RedBlackTreeNode<ValueType>* root)

Definition
Line 1055 of System.Base/RedBlackTree.cm

operator= Member Function

public void operator=(RedBlackTree&& that)

Constraint
ValueType  is  Movable
Definition
Line 559 of System.Base/RedBlackTree.cm

operator= Member Function

public void operator=(const RedBlackTree& that)

Constraint
ValueType  is  Copyable
Definition
Line 552 of System.Base/RedBlackTree.cm