Intrusive balanced A.Andersson binary tree container. More...

#include <bintree_aa.h>

Classes
struct	Node
	A.Andersson 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< BinTreeAA< T, TCompare >, T >	iterator

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

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

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

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

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

	BinTreeAA (const BinTreeAA &) noexcept=default

	BinTreeAA (BinTreeAA &&) noexcept=default

	~BinTreeAA () noexcept=default

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

BinTreeAA &	operator= (BinTreeAA &&) 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 (BinTreeAA &bintree) noexcept
	Swap two instances. More...

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

Detailed Description

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

Intrusive balanced A.Andersson binary tree container.

Not thread-safe.

Overview
Andersson trees are simple and easy to implement balanced binary search trees that are based on the foundations of red black trees. Consequently, Andersson trees have similar performance and structuring properties as red black trees without the difficult implementation. Red black trees are an abstraction of the symmetric binary B-tree, which is a clever abstraction of a B-tree of order 4. Andersson trees are a simplification of the symmetric binary B-tree that use a B-tree of order 3 to remove several unpleasant cases in the implementation. If the last two sentences meant absolutely nothing to you, that's okay. This background isn't necessary to understand Andersson trees or implement them well. Andersson trees were introduced by Arne Andersson in his paper "Balanced Search Trees Made Simple". They were further studied by a few people, most notably Mark Allen Weiss, who discussed them briefly in his books on data structures and algorithm analysis.

Andersson trees are a very simple alternative to the more traditional balanced binary search trees. The performance properties are very close to that of red black trees, and the effort required in implementing them is minimal for anyone who is comfortable writing basic binary search trees.

Performance
The performance of an AA tree is equivalent to the performance of a red- black tree. While an AA tree makes more rotations than a red-black tree, the simpler algorithms tend to be faster, and all of this balances out to result in similar performance. A red-black tree is more consistent in its performance than an AA tree, but an AA tree tends to be flatter, which results in slightly faster search times.

Usage
When comparisons are expensive but lookups are more frequent than updates, the AA tree might win. AA tree tends to be flatter, which results in slightly faster search times.

Taken from:
AA tree from Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/AA_tree

Definition at line 59 of file bintree_aa.h.

Member Typedef Documentation

◆ const_iterator

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

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

Definition at line 72 of file bintree_aa.h.

◆ const_pointer

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

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

Definition at line 68 of file bintree_aa.h.

◆ const_reference

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

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

Definition at line 66 of file bintree_aa.h.

◆ const_reverse_iterator

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

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

Definition at line 74 of file bintree_aa.h.

◆ difference_type

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

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

Definition at line 69 of file bintree_aa.h.

◆ iterator

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

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

Definition at line 71 of file bintree_aa.h.

◆ pointer

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

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

Definition at line 67 of file bintree_aa.h.

◆ reference

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

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

Definition at line 65 of file bintree_aa.h.

◆ reverse_iterator

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

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

Definition at line 73 of file bintree_aa.h.

◆ size_type

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

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

Definition at line 70 of file bintree_aa.h.

◆ value_compare

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

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

Definition at line 64 of file bintree_aa.h.

◆ value_type

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

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

Definition at line 63 of file bintree_aa.h.

Constructor & Destructor Documentation

◆ BinTreeAA() [1/4]

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

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

inlineexplicitnoexcept

Definition at line 87 of file bintree_aa.h.

◆ BinTreeAA() [2/4]

template<typename T , typename TCompare >

template<class InputIterator >

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

inlinenoexcept

Definition at line 13 of file bintree_aa.inl.

◆ BinTreeAA() [3/4]

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

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

defaultnoexcept

◆ BinTreeAA() [4/4]

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

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

defaultnoexcept

◆ ~BinTreeAA()

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

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

defaultnoexcept

Member Function Documentation

◆ begin() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 71 of file bintree_aa.inl.

◆ begin() [2/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Get the begin binary tree iterator.

Definition at line 65 of file bintree_aa.inl.

◆ cbegin()

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 77 of file bintree_aa.inl.

◆ cend()

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 95 of file bintree_aa.inl.

◆ clear()

template<typename T , typename TCompare >

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

inlinenoexcept

Clear the binary tree.

Definition at line 494 of file bintree_aa.inl.

◆ compare()

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

bool CppCommon::BinTreeAA< 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 121 of file bintree_aa.h.

◆ crbegin()

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 113 of file bintree_aa.inl.

◆ crend()

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 131 of file bintree_aa.inl.

◆ empty()

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

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

inlinenoexcept

Is the binary tree empty?

Definition at line 105 of file bintree_aa.h.

◆ end() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 89 of file bintree_aa.inl.

◆ end() [2/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Get the end binary tree iterator.

Definition at line 83 of file bintree_aa.inl.

◆ erase() [1/2]

template<typename T , typename TCompare >

BinTreeAA< T, TCompare >::iterator CppCommon::BinTreeAA< 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 343 of file bintree_aa.inl.

◆ erase() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeAA< 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 337 of file bintree_aa.inl.

◆ find() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 143 of file bintree_aa.inl.

◆ find() [2/2]

template<typename T , typename TCompare >

BinTreeAA< T, TCompare >::iterator CppCommon::BinTreeAA< 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_aa.inl.

◆ highest() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 49 of file bintree_aa.inl.

◆ highest() [2/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Get the highest binary tree item.

Definition at line 43 of file bintree_aa.inl.

◆ insert() [1/2]

template<typename T , typename TCompare >

std::pair< typename BinTreeAA< T, TCompare >::iterator, bool > CppCommon::BinTreeAA< 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_aa.inl.

◆ insert() [2/2]

template<typename T , typename TCompare >

std::pair< typename BinTreeAA< T, TCompare >::iterator, bool > CppCommon::BinTreeAA< 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_aa.inl.

◆ lower_bound() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 185 of file bintree_aa.inl.

◆ lower_bound() [2/2]

template<typename T , typename TCompare >

BinTreeAA< T, TCompare >::iterator CppCommon::BinTreeAA< 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_aa.inl.

◆ lowest() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 27 of file bintree_aa.inl.

◆ lowest() [2/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Get the lowest binary tree item.

Definition at line 21 of file bintree_aa.inl.

◆ operator bool()

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

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

inlineexplicitnoexcept

Check if the binary tree is not empty.

Definition at line 102 of file bintree_aa.h.

◆ operator=() [1/2]

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

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

defaultnoexcept

◆ operator=() [2/2]

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

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

defaultnoexcept

◆ rbegin() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 107 of file bintree_aa.inl.

◆ rbegin() [2/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Get the reverse begin binary tree iterator.

Definition at line 101 of file bintree_aa.inl.

◆ rend() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 125 of file bintree_aa.inl.

◆ rend() [2/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Get the reverse end binary tree iterator.

Definition at line 119 of file bintree_aa.inl.

◆ root() [1/2]

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

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

inlinenoexcept

Definition at line 112 of file bintree_aa.h.

◆ root() [2/2]

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

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

inlinenoexcept

Get the root binary tree item.

Definition at line 111 of file bintree_aa.h.

◆ size()

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

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

inlinenoexcept

Get the binary tree size.

Definition at line 108 of file bintree_aa.h.

◆ swap()

template<typename T , typename TCompare >

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

inlinenoexcept

Swap two instances.

Definition at line 501 of file bintree_aa.inl.

◆ upper_bound() [1/2]

template<typename T , typename TCompare >

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

inlinenoexcept

Definition at line 229 of file bintree_aa.inl.

◆ upper_bound() [2/2]

template<typename T , typename TCompare >

BinTreeAA< T, TCompare >::iterator CppCommon::BinTreeAA< 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_aa.inl.

Friends And Related Function Documentation

◆ swap

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

template<typename U , typename UCompare >

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

friend

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

include/containers/bintree_aa.h
include/containers/bintree_aa.inl

Classes

Public Types

Public Member Functions

Friends

Detailed Description

template<typename T, typename TCompare = std::less<T>> class CppCommon::BinTreeAA< 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

◆ BinTreeAA() [1/4]

◆ BinTreeAA() [2/4]

◆ BinTreeAA() [3/4]

◆ BinTreeAA() [4/4]

◆ ~BinTreeAA()

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::BinTreeAA< T, TCompare >