Overview

template<typename K, typename V>
class pw::containers::internal::AATree< K, V >

An AA tree, as described by Arne Andersson in https://user.it.uu.se/~arneande/ps/simp.pdf. AA trees are simplified red-black which offer almost as much performance with much simpler and smaller code.

The tree provides an ordered collection of keyed items, and is used to implement pw::IntrusiveMap and pw::IntrusiveMultiMap. Keys are retrieved and compared using the functions provided via template parameters.

Template Parameters

K	Key type.
V	Value type.

Inheritance diagram for pw::containers::internal::AATree< K, V >:

Classes
class	Item

class	Pair
	An extension of `Item` that includes storage for a key. More...

Public Types
using	Base = KeyedAATree< K >

using	Key = typename Base::Key

using	Compare = typename Base::Compare

using	GetKey = Function< Key(const V &)>

Public Types inherited from pw::containers::internal::KeyedAATree< K >
using	Key = K

using	Compare = Function< bool(Key, Key)>

using	GetKey = Function< Key(const AATreeItem &)>

using	iterator = AATreeIterator<>

Public Types inherited from pw::containers::internal::GenericAATree
using	iterator = AATreeIterator<>

Public Member Functions
constexpr	AATree (bool unique_keys, Compare &&compare, GetKey &&get_key)

Public Member Functions inherited from pw::containers::internal::KeyedAATree< K >
constexpr	KeyedAATree (bool unique_keys, Compare &&compare, GetKey &&get_key)

void	SetCompare (Compare &&compare)

void	SetGetKey (GetKey &&get_key)

std::pair< iterator, bool >	insert (AATreeItem &item)

template<class Iterator >
void	insert (Iterator first, Iterator last)

size_t	erase_all (Key key)

void	merge (KeyedAATree< K > &other)

size_t	count (Key key)

iterator	find (Key key)

std::pair< iterator, iterator >	equal_range (Key key)

iterator	lower_bound (Key key)

iterator	upper_bound (Key key)

iterator	erase_one (AATreeItem &item)

iterator	erase_range (AATreeItem &first, AATreeItem &last)

Public Member Functions inherited from pw::containers::internal::GenericAATree
constexpr	GenericAATree (bool unique_keys)

	~GenericAATree ()
	Destructor.

	GenericAATree (const GenericAATree &)=delete

GenericAATree &	operator= (const GenericAATree &)=delete

constexpr bool	unique_keys () const

void	SetRoot (AATreeItem *item)
	Sets the tree's root item.

constexpr iterator	begin () noexcept
	Returns a pointer to the first item, if any.

constexpr iterator	end () noexcept
	Returns a pointer to the last item, if any.

constexpr bool	empty () const
	Returns whether the tree has zero items or not.

size_t	size () const
	Returns the number of items in the tree.

constexpr size_t	max_size () const noexcept

void	clear ()

iterator	erase_one (AATreeItem &item)

iterator	erase_range (AATreeItem &first, AATreeItem &last)

void	swap (GenericAATree &other)
	Exchanges this tree's items with the `other` tree's items.

Public Attributes
GetKey	get_key_

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

pw_containers/public/pw_containers/internal/aa_tree.h

Overview

Classes

Public Types

Public Member Functions

Public Attributes