Hybrid RB tree with rank and virtual destructor. More...

Inheritance diagram for Aleph::HtdRbTreeRkVtl< Key, Compare >:

Collaboration diagram for Aleph::HtdRbTreeRkVtl< Key, Compare >:

Public Types
using	Base = HtdRbTreeRk< Key, Compare >

using	Node = typename Base::Node

Public Types inherited from Aleph::HtdRbTreeRk< Key, Compare >
using	Color = unsigned char

using	Node = RbNodeRk< Key >

using	key_type = Key

Additional Inherited Members
Public Member Functions inherited from Aleph::HtdRbTreeRk< Key, Compare >
Compare &	key_comp () noexcept

const Compare &	key_comp () const noexcept

Compare &	get_compare () noexcept

constexpr const Compare &	get_compare () const noexcept

	HtdRbTreeRk (Compare __cmp=Compare()) noexcept

void	swap (HtdRbTreeRk &tree) noexcept

	HtdRbTreeRk (HtdRbTreeRk &&tree) noexcept

HtdRbTreeRk &	operator= (HtdRbTreeRk &&tree) noexcept

	HtdRbTreeRk (const HtdRbTreeRk &)=delete

HtdRbTreeRk &	operator= (const HtdRbTreeRk &)=delete

virtual	~HtdRbTreeRk ()=default

constexpr bool	is_empty () const noexcept

size_t	size () const noexcept
	O(1) size using root count.

void	reset () noexcept

Node *	insert (Node *p) noexcept

Node *	search_or_insert (Node *p) noexcept

Node *	insert_dup (Node *p) noexcept

Node *	search (const Key &key) const noexcept

Node *	remove (const Key &key) noexcept

Node *&	getRoot () noexcept

Node *	getRoot () const noexcept

Node *	select (size_t i) const
	Select the i-th smallest element (0-indexed).

std::pair< long, Node * >	position (const Key &key) const noexcept
	Find position of a key.

std::pair< long, Node * >	find_position (const Key &key) const noexcept
	Find position where key would be inserted.

Node *	remove_pos (size_t i)
	Remove element at position i.

void	split_pos (size_t pos, HtdRbTreeRk &t1, HtdRbTreeRk &t2)
	Split tree at position.

bool	verify () const noexcept
	Verify red-black and rank invariants.

Detailed Description

template<class Key, class Compare = Aleph::less<Key>>
class Aleph::HtdRbTreeRkVtl< Key, Compare >

Hybrid RB tree with rank and virtual destructor.

Definition at line 979 of file tpl_hRbTreeRk.H.

Member Typedef Documentation

template<class Key , class Compare = Aleph::less<Key>>

using Aleph::HtdRbTreeRkVtl< Key, Compare >::Base = HtdRbTreeRk<Key, Compare>

Definition at line 982 of file tpl_hRbTreeRk.H.

template<class Key , class Compare = Aleph::less<Key>>

Definition at line 983 of file tpl_hRbTreeRk.H.

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