Red-Black Tree based implementation of the map interface. More...

#include <maps.h>

Inheritance diagram for original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >:

Collaboration diagram for original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >:

Classes
class	Iterator
	Bidirectional iterator for treeMap. More...

Public Member Functions
	treeMap (Compare comp=Compare{}, ALLOC alloc=ALLOC{})
	Constructs empty treeMap.

	treeMap (const treeMap &other)
	Copy constructor.

treeMap &	operator= (const treeMap &other)
	Copy assignment operator.

	treeMap (treeMap &&other) noexcept
	Move constructor.

treeMap &	operator= (treeMap &&other) noexcept
	Move assignment operator.

u_integer	size () const override
	Gets number of elements.

bool	contains (const couple< const K_TYPE, V_TYPE > &e) const override
	Checks if key-value pair exists.

bool	add (const K_TYPE &k, const V_TYPE &v) override
	Adds new key-value pair.

bool	remove (const K_TYPE &k) override
	Removes key-value pair.

bool	containsKey (const K_TYPE &k) const override
	Checks if key exists.

V_TYPE	get (const K_TYPE &k) const override
	Gets value for key.

bool	update (const K_TYPE &key, const V_TYPE &value) override
	Updates value for existing key.

const V_TYPE &	operator[] (const K_TYPE &k) const override
	Const element access.

V_TYPE &	operator[] (const K_TYPE &k) override
	Non-const element access.

Iterator *	begins () const override
	Gets begin iterator.

Iterator *	ends () const override
	Gets end iterator.

std::string	className () const override
	Gets class name.

std::string	toString (bool enter) const override
	Converts to string representation.

	~treeMap () override
	Destructor.

Public Member Functions inherited from original::iterable< couple< const K_TYPE, V_TYPE > >
auto	forEach (Callback operation) -> void

auto	forEach (const Callback &operation) const -> void

iterAdaptor	begin ()
	Returns an iterator adapter pointing to the beginning of the container.

iterAdaptor	begin () const
	Returns a const iterator adapter pointing to the beginning of the container.

iterAdaptor	end ()
	Returns an iterator adapter pointing to the end sentinel of the container.

iterAdaptor	end () const
	Returns a const iterator adapter pointing to the end sentinel of the container.

iterAdaptor	first ()
	Returns an iterator adapter pointing to the first element.

iterAdaptor	first () const
	Returns a const iterator adapter pointing to the first element.

iterAdaptor	last ()
	Returns an iterator adapter pointing to the last element.

iterAdaptor	last () const
	Returns a const iterator adapter pointing to the last element.

void	forEach (Callback operation=Callback{})
	Applies a given operation to each element in the iterable container.

void	forEach (const Callback &operation=Callback{}) const
	Applies a given operation to each element in the iterable container (const version).

auto	forEach (Callback operation) -> void

auto	forEach (const Callback &operation) const -> void

Public Member Functions inherited from original::printable
	operator std::string () const
	Explicit conversion to std::string.

	operator const char * () const
	Explicit conversion to C-style string.

const char *	toCString (bool enter) const
	Direct C-string access with formatting control.

template<typename TYPE>
auto	formatString (const TYPE &t) -> std::string

template<typename TYPE>
auto	formatCString (const TYPE &t) -> const char *

template<typename TYPE>
auto	formatEnum (const TYPE &t) -> std::string

template<typename TYPE>
auto	formatString (TYPE *const &ptr) -> std::string

Friends
class	Iterator

Additional Inherited Members
Static Public Member Functions inherited from original::printable
template<typename TYPE>
static std::string	formatString (const TYPE &t)
	Universal value-to-string conversion.

template<typename TYPE>
static std::string	formatString (TYPE *const &ptr)
	Pointer-specific formatting.

template<typename TYPE>
static const char *	formatCString (const TYPE &t)
	C-string cache for temporary usage.

template<typename TYPE>
static std::string	formatEnum (const TYPE &t)
	Enum formatting utility.

template<>
auto	formatString (const char &t) -> std::string

template<>
auto	formatString (const bool &t) -> std::string

template<>
auto	formatString (const char *const &ptr) -> std::string

Detailed Description

template<typename K_TYPE, typename V_TYPE, typename Compare = increaseComparator<K_TYPE>, typename ALLOC = allocator<couple<const K_TYPE, V_TYPE>>>
class original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >

Red-Black Tree based implementation of the map interface.

Template Parameters

K_TYPE	Key type (must be comparable)
V_TYPE	Value type
Compare	Comparison function type (default: increaseComparator<K_TYPE>)
ALLOC	Allocator type (default: allocator)

This class provides a concrete implementation of the map interface using a Red-Black Tree. It combines the functionality of:

map (interface)
RBTree (storage)
iterable (iteration support)

Performance Characteristics:

Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)
Traversal: O(n)

The implementation guarantees:

Elements sorted by key according to comparator
Unique keys (no duplicates)
Type safety
Exception safety (basic guarantee)
Iterator validity unless modified

Constructor & Destructor Documentation

◆ treeMap() [1/3]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::treeMap	(	Compare	comp = Compare{},
		ALLOC	alloc = ALLOC{} )

explicit

Constructs empty treeMap.

Parameters

comp	Comparison function to use
alloc	Allocator to use

◆ treeMap() [2/3]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::treeMap ( const treeMap< K_TYPE, V_TYPE, Compare, ALLOC > & other )

Copy constructor.

Parameters

other treeMap to copy

Performs deep copy of all elements and tree structure

Note: Allocator is copied if propagate_on_container_copy_assignment is true

◆ treeMap() [3/3]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::treeMap ( treeMap< K_TYPE, V_TYPE, Compare, ALLOC > && other )

noexcept

Move constructor.

Parameters

other treeMap to move from

Transfers ownership of resources from other

Note: Leaves other in valid but unspecified state

◆ ~treeMap()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::~treeMap ( )

overridedefault

Destructor.

Cleans up all tree nodes and allocated memory

Member Function Documentation

◆ add()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

bool original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::add	(	const K_TYPE &	k,
		const V_TYPE &	v )

override

Adds new key-value pair.

Parameters

k	Key to add
v	Value to associate

Returns: true if added, false if key existed

◆ begins()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::Iterator * original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::begins ( ) const

overridevirtual

Gets begin iterator.

Returns: New iterator at first element (minimum key)

Implements original::iterable< couple< const K_TYPE, V_TYPE > >.

◆ className()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

std::string original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::className ( ) const

nodiscardoverridevirtual

Gets class name.

Returns: "treeMap"

Reimplemented from original::printable.

◆ contains()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

bool original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::contains ( const couple< const K_TYPE, V_TYPE > & e ) const

override

Checks if key-value pair exists.

Parameters

e	Pair to check

Returns: true if both key exists and value matches

◆ containsKey()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

bool original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::containsKey ( const K_TYPE & k ) const

nodiscardoverride

Checks if key exists.

Parameters

k	Key to check

Returns: true if key exists

◆ ends()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::Iterator * original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::ends ( ) const

overridevirtual

Gets end iterator.

Returns: New iterator at last element (maximum key)

Implements original::iterable< couple< const K_TYPE, V_TYPE > >.

◆ get()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

V_TYPE original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::get ( const K_TYPE & k ) const

override

Gets value for key.

Parameters

k	Key to lookup

Returns: Associated value

Exceptions

noElementError if key doesn't exist

◆ operator=() [1/2]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC > & original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::operator= ( const treeMap< K_TYPE, V_TYPE, Compare, ALLOC > & other )

Copy assignment operator.

Parameters

other treeMap to copy

Returns: Reference to this treeMap

Performs deep copy of all elements and tree structure

Note: Allocator is copied if propagate_on_container_copy_assignment is true

◆ operator=() [2/2]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC > & original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::operator= ( treeMap< K_TYPE, V_TYPE, Compare, ALLOC > && other )

noexcept

Move assignment operator.

Parameters

other treeMap to move from

Returns: Reference to this treeMap

Transfers ownership of resources from other

Note: Leaves other in valid but unspecified state; Allocator is moved if propagate_on_container_move_assignment is true

◆ operator[]() [1/2]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

const V_TYPE & original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::operator[] ( const K_TYPE & k ) const

override

Const element access.

Parameters

k	Key to access

Returns: const reference to value

Exceptions

noElementError if key doesn't exist

◆ operator[]() [2/2]

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

V_TYPE & original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::operator[] ( const K_TYPE & k )

override

Non-const element access.

Parameters

k	Key to access

Returns: reference to value

Note: Inserts default-constructed value if key doesn't exist

◆ remove()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

bool original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::remove ( const K_TYPE & k )

override

Removes key-value pair.

Parameters

k	Key to remove

Returns: true if removed, false if key didn't exist

◆ size()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

original::u_integer original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::size ( ) const

nodiscardoverride

Gets number of elements.

Returns: Current size

◆ toString()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

std::string original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::toString ( bool enter ) const

nodiscardoverridevirtual

Converts to string representation.

Parameters

enter Add newline if true

Returns: String representation of key-value pairs

Reimplemented from original::printable.

◆ update()

template<typename K_TYPE, typename V_TYPE, typename Compare, typename ALLOC>

bool original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::update	(	const K_TYPE &	key,
		const V_TYPE &	value )

override

Updates value for existing key.

Parameters

key	Key to update
value	New value

Returns: true if updated, false if key didn't exist

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

src/core/maps.h

Classes

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ treeMap() [1/3]

◆ treeMap() [2/3]

◆ treeMap() [3/3]

◆ ~treeMap()

Member Function Documentation

◆ add()

◆ begins()

◆ className()

◆ contains()

◆ containsKey()

◆ ends()

◆ get()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ remove()

◆ size()

◆ toString()

◆ update()