Common::RBTree< ValueType, Key, KeyProj, KeyComp > Class Template Reference

#include <rb_tree.h>

Classes
class	Iterator
struct	Node

Public Types
enum	Color { kRed, kBlack }
using	BasicIterator = Iterator< ValueType &, ValueType * >
using	ConstIterator = Iterator< const ValueType &, const ValueType * >

Public Member Functions
	RBTree (KeyComp comp={})
	RBTree (const RBTree &other)
	RBTree (RBTree &&other)
RBTree &	operator= (const RBTree &rhs)
RBTree &	operator= (RBTree &&rhs)
void	clear ()
BasicIterator	begin ()
ConstIterator	begin () const
BasicIterator	end ()
ConstIterator	end () const
BasicIterator	lowerBound (const Key &key)
ConstIterator	lowerBound (const Key &key) const
BasicIterator	upperBound (const Key &key)
ConstIterator	upperBound (const Key &key) const
BasicIterator	erase (BasicIterator it)
BasicIterator	erase (BasicIterator first, BasicIterator last)
BasicIterator	insert (const ValueType &val)
BasicIterator	insert (BasicIterator start, const ValueType &val)
size_t	size () const
bool	isEmpty () const

Detailed Description

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>
class Common::RBTree< ValueType, Key, KeyProj, KeyComp >

Red-black tree implementation with insertion and deletion algorithms based on the ones found in Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. Used in the implementation of Common::StableMap and Common::MultiMap

Member Typedef Documentation

BasicIterator

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

using Common::RBTree< ValueType, Key, KeyProj, KeyComp >::BasicIterator = Iterator<ValueType &, ValueType *>

RBTree iterator.

ConstIterator

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

using Common::RBTree< ValueType, Key, KeyProj, KeyComp >::ConstIterator = Iterator<const ValueType &, const ValueType *>

Const-qualified RBTree iterator.

Constructor & Destructor Documentation

RBTree() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

Common::RBTree< ValueType, Key, KeyProj, KeyComp >::RBTree ( const RBTree< ValueType, Key, KeyProj, KeyComp > &  other )

inline

Construct an RBTree as a copy of the given tree other .

RBTree() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

Common::RBTree< ValueType, Key, KeyProj, KeyComp >::RBTree ( RBTree< ValueType, Key, KeyProj, KeyComp > &&  other )

inline

Construct an RBTree by moving the contents of the given tree (using the C++11 move semantics).

Member Function Documentation

operator=() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

RBTree& Common::RBTree< ValueType, Key, KeyProj, KeyComp >::operator= ( const RBTree< ValueType, Key, KeyProj, KeyComp > &  rhs )

inline

Assign the given tree to this tree.

operator=() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

RBTree& Common::RBTree< ValueType, Key, KeyProj, KeyComp >::operator= ( RBTree< ValueType, Key, KeyProj, KeyComp > &&  rhs )

inline

Moves the contents of the given tree into this tree (using the C++11 move semantics).

clear()

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

void Common::RBTree< ValueType, Key, KeyProj, KeyComp >::clear ( )

inline

Clears the contents of the tree.

begin() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::begin ( )

inline

Return an iterator pointing to the first element in the tree.

begin() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

ConstIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::begin ( ) const

inline

Return a const iterator pointing to the first element of the tree.

end() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::end ( )

inline

Return an iterator pointing to the last element in the tree.

end() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

ConstIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::end ( ) const

inline

Return a const iterator pointing to the last element of the tree.

lowerBound() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::lowerBound ( const Key &  key )

inline

Returns an iterator to the first item thas is not less than key in the tree (or end() if this cannot be found).

lowerBound() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

ConstIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::lowerBound ( const Key &  key ) const

inline

Returns a const iterator to the first item thas is not less than key in the tree (or end() if this cannot be found).

upperBound() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::upperBound ( const Key &  key )

inline

Returns an iterator to the first item bigger than key in the tree (or end() if this cannot be found).

upperBound() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

ConstIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::upperBound ( const Key &  key ) const

inline

Return a const iterator to the first item bigger than key in the tree (or end() if this cannot be found).

erase() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::erase ( BasicIterator  it )

inline

Erases the item in the tree pointed by it .

erase() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::erase ( BasicIterator  first, BasicIterator  last  )

inline

Erase the elements from first to last and return an iterator pointing to the next element in the tree.

Note

If [first, last) is not a valid range for the tree, the behaviour is undefined.

insert() [1/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::insert ( const ValueType &  val )

inline

Inserts a value val into the tree returning an iterator for the inserted value.

insert() [2/2]

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

BasicIterator Common::RBTree< ValueType, Key, KeyProj, KeyComp >::insert ( BasicIterator  start, const ValueType &  val  )

inline

Inserts the element val starting from start instead of the tree's root. This operations is meant for efficient insertions after a call to lowerBound. For example:

auto it = tree.lowerBound(value);
if (it == tree.end() || *it != value)
   tree.insert(it, value);

inserts 'value' if its not contained in 'tree' (assumes that key and value type are the same)

Note

If start is not the lower bound, or it's not end(), the resulting tree could be unsorted.

size()

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

size_t Common::RBTree< ValueType, Key, KeyProj, KeyComp >::size ( ) const

inline

Returns the number of values in the tree.

isEmpty()

template<class ValueType, class Key, class KeyProj, class KeyComp = Common::Less<Key>>

bool Common::RBTree< ValueType, Key, KeyProj, KeyComp >::isEmpty ( ) const

inline

Returns true if the tree is empty. Shorthand for:

tree.size() == 0

---

The documentation for this class was generated from the following file:

• common/rb_tree.h