Intrusive balanced Red-Black binary tree container. More...

#include <bintree_rb.h>

Classes
struct	Node
	Red-Black binary tree node. More...

Public Types
typedef T	value_type

typedef TCompare	value_compare

typedef value_type &	reference

typedef const value_type &	const_reference

typedef value_type *	pointer

typedef const value_type *	const_pointer

typedef ptrdiff_t	difference_type

typedef size_t	size_type

typedef BinTreeIterator< BinTreeRB< T, TCompare >, T >	iterator

typedef BinTreeConstIterator< BinTreeRB< T, TCompare >, T >	const_iterator

typedef BinTreeReverseIterator< BinTreeRB< T, TCompare >, T >	reverse_iterator

typedef BinTreeConstReverseIterator< BinTreeRB< T, TCompare >, T >	const_reverse_iterator

Public Member Functions
	BinTreeRB (const TCompare &compare=TCompare()) noexcept

template<class InputIterator >
	BinTreeRB (InputIterator first, InputIterator last, const TCompare &compare=TCompare()) noexcept

	BinTreeRB (const BinTreeRB &) noexcept=default

	BinTreeRB (BinTreeRB &&) noexcept=default

	~BinTreeRB () noexcept=default

BinTreeRB &	operator= (const BinTreeRB &) noexcept=default

BinTreeRB &	operator= (BinTreeRB &&) noexcept=default

	operator bool () const noexcept
	Check if the binary tree is not empty. More...

bool	empty () const noexcept
	Is the binary tree empty? More...

size_t	size () const noexcept
	Get the binary tree size. More...

T *	root () noexcept
	Get the root binary tree item. More...

const T *	root () const noexcept

T *	lowest () noexcept
	Get the lowest binary tree item. More...

const T *	lowest () const noexcept

T *	highest () noexcept
	Get the highest binary tree item. More...

const T *	highest () const noexcept

bool	compare (const T &item1, const T &item2) const noexcept
	Compare two items: if the first item is less than the second one? More...

iterator	begin () noexcept
	Get the begin binary tree iterator. More...

const_iterator	begin () const noexcept

const_iterator	cbegin () const noexcept

iterator	end () noexcept
	Get the end binary tree iterator. More...

const_iterator	end () const noexcept

const_iterator	cend () const noexcept

reverse_iterator	rbegin () noexcept
	Get the reverse begin binary tree iterator. More...

const_reverse_iterator	rbegin () const noexcept

const_reverse_iterator	crbegin () const noexcept

reverse_iterator	rend () noexcept
	Get the reverse end binary tree iterator. More...

const_reverse_iterator	rend () const noexcept

const_reverse_iterator	crend () const noexcept

iterator	find (const T &item) noexcept
	Find the iterator which points to the first equal item in the binary tree or return end iterator. More...

const_iterator	find (const T &item) const noexcept

iterator	lower_bound (const T &item) noexcept
	Find the iterator which points to the first item that not less than the given item in the binary tree or return end iterator. More...

const_iterator	lower_bound (const T &item) const noexcept

iterator	upper_bound (const T &item) noexcept
	Find the iterator which points to the first item that greater than the given item in the binary tree or return end iterator. More...

const_iterator	upper_bound (const T &item) const noexcept

std::pair< iterator, bool >	insert (T &item) noexcept
	Insert a new item into the binary tree. More...

std::pair< iterator, bool >	insert (const const_iterator &position, T &item) noexcept
	Insert a new item into the binary tree with a position hint. More...

T *	erase (const T &item) noexcept
	Erase the given item from the binary tree. More...

iterator	erase (const iterator &it) noexcept
	Erase the given item from the binary tree. More...

void	clear () noexcept
	Clear the binary tree. More...

void	swap (BinTreeRB &bintree) noexcept
	Swap two instances. More...

Friends
template<typename U , typename UCompare >
void	swap (BinTreeRB< U, UCompare > &bintree1, BinTreeRB< U, UCompare > &bintree2) noexcept

Detailed Description

template<typename T, typename TCompare = std::less<T>>
class CppCommon::BinTreeRB< T, TCompare >

Intrusive balanced Red-Black binary tree container.

Not thread-safe.

Overview
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is the number of elements in the tree.

Background and terminology
A red-black tree is a special type of binary tree, which is a structure used in computer science to organize pieces of comparable data, such as numbers. Each piece of data is stored in a node. One of the nodes always functions as our starting place, and is not the child of any node; we call this the root node or root. It has up to two "children", other nodes to which it connects. Each of these children can have up to two children of its own, and so on. The root node thus has a path connecting it to any other node in the tree.

If a node has no children, we call it a leaf node, since intuitively it is at the periphery of the tree. A subtree is the portion of the tree that can be reached from a certain node, considered as a tree itself. In red-black trees, the leaves are assumed to be null, that is, they do not contain any data.

As red-black trees are also binary search trees, they satisfy the constraint that every node contains a value less than or equal to all nodes in its right subtree, and greater than or equal to all nodes in its left subtree. This makes it quick to search the tree for a given value, and allows efficient in-order traversal of elements.

Uses and advantages.
Red-black trees, along with AVL trees, offer the best possible worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees; for example, many data structures used in computational geometry can be based on red-black trees.

Red-black trees are also particularly valuable in functional programming, where they are one of the most common persistent data structures, used to construct associative arrays and sets which can retain previous versions after mutations. The persistent version of red-black trees requires O(log n) space for each insertion or deletion, in addition to time.

Red-black trees are an isometry of 2-3-4 trees. In other words, for every 2-3-4 tree, there exists at least one red-black tree with data elements in the same order. The insertion and deletion operations on 2-3-4 trees are also equivalent to color-flipping and rotations in red-black trees. This makes 2-3-4 trees an important tool for understanding the logic behind red-black trees, and this is why many introductory algorithm texts introduce 2-3-4 trees just before red-black trees, even though 2-3-4 trees are not often used in practice.

Properties

Red-Black binary tree

A red-black tree is a binary search tree where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, we make the following additional requirements of any valid red-black tree:

1. A node is either red or black.
2. The root is black.
3. All leaves are black. (This includes the NIL children)
4. Both children of every red node are black. (i.e. Every red node must have a black parent.)
5. All paths from any given node to its leaf nodes contain the same number of black nodes.

These constraints enforce a critical property of red-black trees: that the longest possible path from the root to a leaf is no more than twice as long as the shortest possible path. The result is that the tree is roughly balanced. Since operations such as inserting, deleting, and finding values requires worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red-black trees to be efficient in the worst-case, unlike ordinary binary search trees.

To see why these properties guarantee this, it suffices to note that no path can have two red nodes in a row, due to property 4. The shortest possible path has all black nodes, and the longest possible path alternates between red and black nodes. Since all maximal paths have the same number of black nodes, by property 5, this shows that no path is more than twice as long as any other path.

In many presentations of tree data structures, it is possible for a node to have only one child, and leaf nodes contain data. It is possible to present red-black trees in this paradigm, but it changes several of the properties and complicates the algorithms. For this reason, in this article we use "nil leaves" or "null leaves", which contain no data and merely serve to indicate where the tree ends, as shown above. These nodes are often omitted in drawings, resulting in a tree which seems to contradict the above principles, but which in fact does not. A consequence of this is that all internal (non-leaf) nodes have two children, although one or more of those children may be a null leaf.

Some explain a red-black tree as a binary search tree whose edges, instead of nodes, are colored in red or black, but this does not make any difference. The color of a node in our terminology corresponds to the color of the edge connecting the node to its parent, except that the root node is always black in our terminology (property 2) whereas the corresponding edge does not exist.

Operations
Read-only operations on a red-black tree require no modification from those used for binary search trees, because every red-black tree is a specialization of a simple binary search tree. However, the immediate result of an insertion or removal may violate the properties of a red-black tree. Restoring the red-black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion). Although insert and delete operations are complicated, their times remain O(log n).

Proof of asymptotic bounds
A red black tree which contains n internal nodes has a height of O(log(n)).

Definitions:

h(v) = height of subtree rooted at node v
bh(v) = the number of black nodes (not counting v if it is black) from v to any leaf in the subtree (called the black-height).

Lemma: A subtree rooted at node v has at least 2bh(v) ? 1 internal nodes.

Proof of Lemma (by induction height):

Basis: h(v) = 0

If v has a height of zero then it must be nil, therefore bh(v) = 0. So:

$2^{bh(v)} - 1 = 20 - 1 = 1 - 1 = 0$

Inductive Hypothesis: v such that h(v) = k, has $2^{bh(v)} - 1$ internal nodes implies that v' such that h(v') = k+1 has $2^{bh(v')} - 1$ internal nodes.

Since v' has h(v') > 0 it is an internal node. As such it has two children which have a black-height of either bh(v') or bh(v')-1 (depending on whether v' is red or black). By the inductive hypothesis each child has at least $2^{bh(v)} - 1 - 1$ internal nodes, so v' has:

$2^{bh(v)} - 1 - 1 + 2^{bh(v')} - 1 - 1 + 1 = 2^{bh(v')} - 1$

internal nodes.

Using this lemma we can now show that the height of the tree is logarithmic. Since at least half of the nodes on any path from the root to a leaf are black (property 4 of a red black tree), the black- height of the root is at least $h(root) \over 2$ . By the lemma we get:

$n \geq 2^{{h(root) \over 2}} - 1 \leftrightarrow \; \log{(n+1)} \geq {h(root) \over 2} \leftrightarrow \; h(root) \leq 2\log{(n+1)}$

Therefore the height of the root is O(log(n)).

Usage
Reb-Black trees have as a first advantage that their performance is easier to predict, making them a good data structure for libraries. Reb-Black tree win AVL trees in cases when there are lots of inserts / deletes and comparisons are chap. Reb-Black tree will be faster because on average Reb-Black tree use less rotation.

References

Mathworld: Red-Black Tree
San Diego State University: CS 660: Red-Black tree notes, by Roger Whitney
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 13: Red-Black Trees, pp.273-301.

Taken from:
Red-black tree from Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/Red-black_tree

Definition at line 201 of file bintree_rb.h.

Member Typedef Documentation

◆ const_iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeConstIterator<BinTreeRB<T, TCompare>, T> CppCommon::BinTreeRB< T, TCompare >::const_iterator

Definition at line 214 of file bintree_rb.h.

◆ const_pointer

template<typename T , typename TCompare = std::less<T>>

typedef const value_type* CppCommon::BinTreeRB< T, TCompare >::const_pointer

Definition at line 210 of file bintree_rb.h.

◆ const_reference

template<typename T , typename TCompare = std::less<T>>

typedef const value_type& CppCommon::BinTreeRB< T, TCompare >::const_reference

Definition at line 208 of file bintree_rb.h.

◆ const_reverse_iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeConstReverseIterator<BinTreeRB<T, TCompare>, T> CppCommon::BinTreeRB< T, TCompare >::const_reverse_iterator

Definition at line 216 of file bintree_rb.h.

◆ difference_type

template<typename T , typename TCompare = std::less<T>>

typedef ptrdiff_t CppCommon::BinTreeRB< T, TCompare >::difference_type

Definition at line 211 of file bintree_rb.h.

◆ iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeIterator<BinTreeRB<T, TCompare>, T> CppCommon::BinTreeRB< T, TCompare >::iterator

Definition at line 213 of file bintree_rb.h.

◆ pointer

template<typename T , typename TCompare = std::less<T>>

typedef value_type* CppCommon::BinTreeRB< T, TCompare >::pointer

Definition at line 209 of file bintree_rb.h.

◆ reference

template<typename T , typename TCompare = std::less<T>>

typedef value_type& CppCommon::BinTreeRB< T, TCompare >::reference

Definition at line 207 of file bintree_rb.h.

◆ reverse_iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeReverseIterator<BinTreeRB<T, TCompare>, T> CppCommon::BinTreeRB< T, TCompare >::reverse_iterator

Definition at line 215 of file bintree_rb.h.

◆ size_type

template<typename T , typename TCompare = std::less<T>>

typedef size_t CppCommon::BinTreeRB< T, TCompare >::size_type

Definition at line 212 of file bintree_rb.h.

◆ value_compare

template<typename T , typename TCompare = std::less<T>>

typedef TCompare CppCommon::BinTreeRB< T, TCompare >::value_compare

Definition at line 206 of file bintree_rb.h.

◆ value_type

template<typename T , typename TCompare = std::less<T>>

typedef T CppCommon::BinTreeRB< T, TCompare >::value_type

Definition at line 205 of file bintree_rb.h.

Constructor & Destructor Documentation

◆ BinTreeRB() [1/4]

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeRB< T, TCompare >::BinTreeRB ( const TCompare & compare = TCompare() )

inlineexplicitnoexcept

Definition at line 229 of file bintree_rb.h.

◆ BinTreeRB() [2/4]

template<typename T , typename TCompare >

template<class InputIterator >

CppCommon::BinTreeRB< T, TCompare >::BinTreeRB	(	InputIterator	first,
		InputIterator	last,
		const TCompare &	compare = `TCompare()`
	)

inlinenoexcept

Definition at line 13 of file bintree_rb.inl.

◆ BinTreeRB() [3/4]

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeRB< T, TCompare >::BinTreeRB ( const BinTreeRB< T, TCompare > & )

defaultnoexcept

◆ BinTreeRB() [4/4]

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeRB< T, TCompare >::BinTreeRB ( BinTreeRB< T, TCompare > && )

defaultnoexcept

◆ ~BinTreeRB()

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeRB< T, TCompare >::~BinTreeRB ( )

defaultnoexcept

Member Function Documentation

◆ begin() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::begin

inlinenoexcept

Definition at line 71 of file bintree_rb.inl.

◆ begin() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::iterator CppCommon::BinTreeRB< T, TCompare >::begin

inlinenoexcept

Get the begin binary tree iterator.

Definition at line 65 of file bintree_rb.inl.

◆ cbegin()

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::cbegin

inlinenoexcept

Definition at line 77 of file bintree_rb.inl.

◆ cend()

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::cend

inlinenoexcept

Definition at line 95 of file bintree_rb.inl.

◆ clear()

template<typename T , typename TCompare >

void CppCommon::BinTreeRB< T, TCompare >::clear

inlinenoexcept

Clear the binary tree.

Definition at line 648 of file bintree_rb.inl.

◆ compare()

template<typename T , typename TCompare = std::less<T>>

bool CppCommon::BinTreeRB< T, TCompare >::compare	(	const T &	item1,
		const T &	item2
	)		const

inlinenoexcept

Compare two items: if the first item is less than the second one?

Definition at line 263 of file bintree_rb.h.

◆ crbegin()

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_reverse_iterator CppCommon::BinTreeRB< T, TCompare >::crbegin

inlinenoexcept

Definition at line 113 of file bintree_rb.inl.

◆ crend()

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_reverse_iterator CppCommon::BinTreeRB< T, TCompare >::crend

inlinenoexcept

Definition at line 131 of file bintree_rb.inl.

◆ empty()

template<typename T , typename TCompare = std::less<T>>

bool CppCommon::BinTreeRB< T, TCompare >::empty ( ) const

inlinenoexcept

Is the binary tree empty?

Definition at line 247 of file bintree_rb.h.

◆ end() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::end

inlinenoexcept

Definition at line 89 of file bintree_rb.inl.

◆ end() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::iterator CppCommon::BinTreeRB< T, TCompare >::end

inlinenoexcept

Get the end binary tree iterator.

Definition at line 83 of file bintree_rb.inl.

◆ erase() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::iterator CppCommon::BinTreeRB< T, TCompare >::erase ( const iterator & it )

inlinenoexcept

Erase the given item from the binary tree.

Parameters

it	- Iterator to the erased item

Returns: Erased item iterator

Definition at line 391 of file bintree_rb.inl.

◆ erase() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeRB< T, TCompare >::erase ( const T & item )

inlinenoexcept

Erase the given item from the binary tree.

Parameters

item	- Item to erase

Returns: Erased item

Definition at line 385 of file bintree_rb.inl.

◆ find() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::find ( const T & item ) const

inlinenoexcept

Definition at line 143 of file bintree_rb.inl.

◆ find() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::iterator CppCommon::BinTreeRB< T, TCompare >::find ( const T & item )

inlinenoexcept

Find the iterator which points to the first equal item in the binary tree or return end iterator.

Definition at line 137 of file bintree_rb.inl.

◆ highest() [1/2]

template<typename T , typename TCompare >

const T * CppCommon::BinTreeRB< T, TCompare >::highest

inlinenoexcept

Definition at line 49 of file bintree_rb.inl.

◆ highest() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeRB< T, TCompare >::highest

inlinenoexcept

Get the highest binary tree item.

Definition at line 43 of file bintree_rb.inl.

◆ insert() [1/2]

template<typename T , typename TCompare >

std::pair< typename BinTreeRB< T, TCompare >::iterator, bool > CppCommon::BinTreeRB< T, TCompare >::insert	(	const const_iterator &	position,
		T &	item
	)

inlinenoexcept

Insert a new item into the binary tree with a position hint.

Parameters

position	- Iterator position to the inserted item
item	- Item to insert

Returns: Pair with the iterator to the inserted item and success flag

Definition at line 266 of file bintree_rb.inl.

◆ insert() [2/2]

template<typename T , typename TCompare >

std::pair< typename BinTreeRB< T, TCompare >::iterator, bool > CppCommon::BinTreeRB< T, TCompare >::insert ( T & item )

inlinenoexcept

Insert a new item into the binary tree.

Parameters

item	- Item to insert

Returns: Pair with the iterator to the inserted item and success flag

Definition at line 260 of file bintree_rb.inl.

◆ lower_bound() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::lower_bound ( const T & item ) const

inlinenoexcept

Definition at line 185 of file bintree_rb.inl.

◆ lower_bound() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::iterator CppCommon::BinTreeRB< T, TCompare >::lower_bound ( const T & item )

inlinenoexcept

Find the iterator which points to the first item that not less than the given item in the binary tree or return end iterator.

Definition at line 179 of file bintree_rb.inl.

◆ lowest() [1/2]

template<typename T , typename TCompare >

const T * CppCommon::BinTreeRB< T, TCompare >::lowest

inlinenoexcept

Definition at line 27 of file bintree_rb.inl.

◆ lowest() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeRB< T, TCompare >::lowest

inlinenoexcept

Get the lowest binary tree item.

Definition at line 21 of file bintree_rb.inl.

◆ operator bool()

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeRB< T, TCompare >::operator bool ( ) const

inlineexplicitnoexcept

Check if the binary tree is not empty.

Definition at line 244 of file bintree_rb.h.

◆ operator=() [1/2]

template<typename T , typename TCompare = std::less<T>>

BinTreeRB& CppCommon::BinTreeRB< T, TCompare >::operator= ( BinTreeRB< T, TCompare > && )

defaultnoexcept

◆ operator=() [2/2]

template<typename T , typename TCompare = std::less<T>>

BinTreeRB& CppCommon::BinTreeRB< T, TCompare >::operator= ( const BinTreeRB< T, TCompare > & )

defaultnoexcept

◆ rbegin() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_reverse_iterator CppCommon::BinTreeRB< T, TCompare >::rbegin

inlinenoexcept

Definition at line 107 of file bintree_rb.inl.

◆ rbegin() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::reverse_iterator CppCommon::BinTreeRB< T, TCompare >::rbegin

inlinenoexcept

Get the reverse begin binary tree iterator.

Definition at line 101 of file bintree_rb.inl.

◆ rend() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_reverse_iterator CppCommon::BinTreeRB< T, TCompare >::rend

inlinenoexcept

Definition at line 125 of file bintree_rb.inl.

◆ rend() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::reverse_iterator CppCommon::BinTreeRB< T, TCompare >::rend

inlinenoexcept

Get the reverse end binary tree iterator.

Definition at line 119 of file bintree_rb.inl.

◆ root() [1/2]

template<typename T , typename TCompare = std::less<T>>

const T* CppCommon::BinTreeRB< T, TCompare >::root ( ) const

inlinenoexcept

Definition at line 254 of file bintree_rb.h.

◆ root() [2/2]

template<typename T , typename TCompare = std::less<T>>

T* CppCommon::BinTreeRB< T, TCompare >::root ( )

inlinenoexcept

Get the root binary tree item.

Definition at line 253 of file bintree_rb.h.

◆ size()

template<typename T , typename TCompare = std::less<T>>

size_t CppCommon::BinTreeRB< T, TCompare >::size ( ) const

inlinenoexcept

Get the binary tree size.

Definition at line 250 of file bintree_rb.h.

◆ swap()

template<typename T , typename TCompare >

void CppCommon::BinTreeRB< T, TCompare >::swap ( BinTreeRB< T, TCompare > & bintree )

inlinenoexcept

Swap two instances.

Definition at line 655 of file bintree_rb.inl.

◆ upper_bound() [1/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::const_iterator CppCommon::BinTreeRB< T, TCompare >::upper_bound ( const T & item ) const

inlinenoexcept

Definition at line 229 of file bintree_rb.inl.

◆ upper_bound() [2/2]

template<typename T , typename TCompare >

BinTreeRB< T, TCompare >::iterator CppCommon::BinTreeRB< T, TCompare >::upper_bound ( const T & item )

inlinenoexcept

Find the iterator which points to the first item that greater than the given item in the binary tree or return end iterator.

Definition at line 223 of file bintree_rb.inl.

Friends And Related Function Documentation

◆ swap

template<typename T , typename TCompare = std::less<T>>

template<typename U , typename UCompare >

void swap	(	BinTreeRB< U, UCompare > &	bintree1,
		BinTreeRB< U, UCompare > &	bintree2
	)

friend

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

include/containers/bintree_rb.h
include/containers/bintree_rb.inl

Classes

Public Types

Public Member Functions

Friends

Detailed Description

template<typename T, typename TCompare = std::less<T>> class CppCommon::BinTreeRB< T, TCompare >

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_compare

◆ value_type

Constructor & Destructor Documentation

◆ BinTreeRB() [1/4]

◆ BinTreeRB() [2/4]

◆ BinTreeRB() [3/4]

◆ BinTreeRB() [4/4]

◆ ~BinTreeRB()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ compare()

◆ crbegin()

◆ crend()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ highest() [1/2]

◆ highest() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ lowest() [1/2]

◆ lowest() [2/2]

◆ operator bool()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ root() [1/2]

◆ root() [2/2]

◆ size()

◆ swap()

◆ upper_bound() [1/2]

◆ upper_bound() [2/2]

Friends And Related Function Documentation

◆ swap

template<typename T, typename TCompare = std::less<T>>
class CppCommon::BinTreeRB< T, TCompare >