A map type using an AVL tree as the underlying structure. More...

#include <map.hpp>

Classes
struct	value_compare

Public Types
using	key_type = TKey

using	mapped_type = TValue

using	value_type = std::pair< const key_type, mapped_type >

using	reference = value_type &

using	const_reference = const value_type &

using	key_compare = TKeyComp

using	allocator_type = TAlloc

using	alloc_traits = std::allocator_traits< allocator_type >

using	size_type = typename alloc_traits::size_type

using	difference_type = typename alloc_traits::difference_type

using	pointer = typename alloc_traits::pointer

using	const_pointer = typename alloc_traits::const_pointer

using	iterator = detail::avl_iterator< tree_type, false >

using	const_iterator = detail::avl_iterator< tree_type, true >

using	reverse_iterator = std::reverse_iterator< iterator >

using	const_reverse_iterator = std::reverse_iterator< const_iterator >

Public Member Functions
	map ()

	map (const key_compare &comparator, const allocator_type &allocator=allocator_type{})

	map (const allocator_type &allocator)

	map (const map &other)

map &	operator= (const map &other)

	map (map &&other) noexcept

map &	operator= (map &&other) noexcept

	~map () noexcept

allocator_type	get_allocator () const noexcept
	Returns the associated allocator.

key_compare	key_comp () const noexcept
	Returns the function that compares keys.

value_compare	value_comp () const noexcept
	Returns the function that compares keys in the key, value pairs.

mapped_type &	at (const key_type &key)
	Access specified item.

const mapped_type &	at (const key_type &key) const
	Access specified item.

mapped_type &	operator[] (const key_type &key)
	Access specified item or insert.

mapped_type &	operator[] (key_type &&key)
	Access specified item or insert.

iterator	find (const key_type &key) noexcept
	Finds an item with the given key.

const_iterator	find (const key_type &key) const noexcept
	Finds an item with the given key.

bool	contains (const key_type &key) const noexcept
	Checks whether there exists an item with given key in the tree.

size_type	count (const key_type &key) const noexcept
	Returns the number of items with the given key (0 or 1).

iterator	lower_bound (const key_type &key) noexcept
	Returns an iterator to the first item which is not less than the given key.

const_iterator	lower_bound (const key_type &key) const noexcept
	Returns an iterator to the first item which is not less than the given key.

iterator	upper_bound (const key_type &key) noexcept
	Returns an iterator to the first item which is greater that the given key.

const_iterator	upper_bound (const key_type &key) const noexcept
	Returns an iterator to the first item which is greater that the given key.

std::pair< iterator, iterator >	equal_range (const key_type &key) noexcept
	Returns a range containing all the items with the given key.

std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const noexcept
	Returns a range containing all the items with the given key.

iterator	begin () noexcept
	Returns an iterator to the smallest item.

const_iterator	begin () const noexcept
	Returns an iterator to the smallest item, read only.

const_iterator	cbegin () const noexcept
	Returns explicitly a constant iterator to the smallest item.

iterator	end () noexcept
	Returns an iterator to the end.

const_iterator	end () const noexcept
	Returns an iterator to the end, read only.

const_iterator	cend () const noexcept
	Returns explicitly a constant iterator to the end.

reverse_iterator	rbegin () noexcept
	Returns a reverse iterator to the biggest item.

const_reverse_iterator	rbegin () const noexcept
	Returns a reverse iterator to the biggest item, read only.

const_reverse_iterator	crbegin () const noexcept
	Returns explicitly a constant reverse iterator to the biggest item.

reverse_iterator	rend () noexcept
	Returns a reverse iterator to the end.

const_reverse_iterator	rend () const noexcept
	Returns a reverse iterator to the end, read only.

const_reverse_iterator	crend () const noexcept
	Returns explicitly a constant reverse iterator to the end.

bool	empty () const noexcept
	Checks whether the map contains any values.

size_type	size () const noexcept
	Returns the current number of items.

int	get_height () const noexcept
	Returns the height of the underlying tree.

void	clear () noexcept
	Erases the whole tree.

std::pair< iterator, bool >	insert (const value_type &item)
	Inserts an item.

std::pair< iterator, bool >	insert (value_type &&item)
	Inserts an item.

template<class TMapped >
std::pair< iterator, bool >	insert_or_assign (const key_type &key, TMapped &&value)
	Inserts an item or assigns the value.

template<class TMapped >
std::pair< iterator, bool >	insert_or_assign (key_type &&key, TMapped &&value)
	Inserts an item or assigns the value.

template<class... Args>
std::pair< iterator, bool >	try_emplace (const key_type &key, Args &&...args)
	Construct an item in-place.

template<class... Args>
std::pair< iterator, bool >	try_emplace (key_type &&key, Args &&...args)
	Construct an item in-place.

iterator	erase (iterator pos) noexcept
	Erases an item.

iterator	erase (const_iterator pos) noexcept
	Erases an item.

size_type	erase (const key_type &key) noexcept
	Erases an item with the given key.

void	swap (map &other) noexcept
	Swaps the content.

std::string	to_dot (bool print_invis) const
	Returns the dot representation of the tree.

template<class TMapped >
std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool >	insert_or_assign (const key_type &key, TMapped &&value)

template<class TMapped >
std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool >	insert_or_assign (key_type &&key, TMapped &&value)

template<class... Args>
std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool >	try_emplace (const key_type &key, Args &&...args)

template<class... Args>
std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool >	try_emplace (key_type &&key, Args &&...args)

Detailed Description

template<class TKey, class TValue, class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>
class datastructures::map< TKey, TValue, TKeyComp, TAlloc >

A map type using an AVL tree as the underlying structure.

This map type is mostly compatible with the std::map, but is based on an AVL tree.

When the equivalence relation derived from the TKeyComp has an equivalence class with more than one element, then the first one to be inserted stays there until deleted, in other words the keys are immutable and aren't changed even by assigmnets.

All the references to the items are valid until erased, balancing and inserting new values wont invalidate them.

Template Parameters

TKey	Represents the keys in the map, it must support `std::less` comparisons or you must provide custom one.
TValue	Represents the values, can be anything.
TKeyComp	The comparison struct, it must contain `operator()` which takes two keys as parameters and creates a weak ordering on them.
TAlloc	The allocator that can allocate the key, value pairs, must comply with the standard allocators, so that `std::allocator_traits` works on it. Internally it is rebinded to allocate the nodes themself.

Member Typedef Documentation

◆ alloc_traits

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::alloc_traits = std::allocator_traits<allocator_type>

◆ allocator_type

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::allocator_type = TAlloc

◆ const_iterator

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::const_iterator = detail::avl_iterator<tree_type, true>

◆ const_pointer

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::const_pointer = typename alloc_traits::const_pointer

◆ const_reference

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::const_reference = const value_type &

◆ const_reverse_iterator

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::const_reverse_iterator = std::reverse_iterator<const_iterator>

◆ difference_type

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::difference_type = typename alloc_traits::difference_type

◆ iterator

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::iterator = detail::avl_iterator<tree_type, false>

◆ key_compare

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::key_compare = TKeyComp

◆ key_type

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::key_type = TKey

◆ mapped_type

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::mapped_type = TValue

◆ pointer

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::pointer = typename alloc_traits::pointer

◆ reference

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::reference = value_type &

◆ reverse_iterator

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::reverse_iterator = std::reverse_iterator<iterator>

◆ size_type

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::size_type = typename alloc_traits::size_type

◆ value_type

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

using datastructures::map< TKey, TValue, TKeyComp, TAlloc >::value_type = std::pair<const key_type, mapped_type>

Constructor & Destructor Documentation

◆ map() [1/5]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

datastructures::map< TKey, TValue, TKeyComp, TAlloc >::map ( )

◆ map() [2/5]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

datastructures::map< TKey, TValue, TKeyComp, TAlloc >::map	(	const key_compare &	comparator,
		const allocator_type &	allocator = `allocator_type{}`
	)

explicit

◆ map() [3/5]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

datastructures::map< TKey, TValue, TKeyComp, TAlloc >::map ( const allocator_type & allocator )

explicit

◆ map() [4/5]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

datastructures::map< TKey, TValue, TKeyComp, TAlloc >::map ( const map< TKey, TValue, TKeyComp, TAlloc > & other )

◆ map() [5/5]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

datastructures::map< TKey, TValue, TKeyComp, TAlloc >::map ( map< TKey, TValue, TKeyComp, TAlloc > && other )

noexcept

◆ ~map()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

datastructures::map< TKey, TValue, TKeyComp, TAlloc >::~map ( )

noexcept

Member Function Documentation

◆ at() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::mapped_type & datastructures::map< TKey, TValue, TKeyComp, TAlloc >::at ( const key_type & key )

Access specified item.

When there is no item with the specified key throws std::out_of_range.

Note: Time Complexity: O(log n)

◆ at() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

const map< TKey, TValue, TKeyComp, TAlloc >::mapped_type & datastructures::map< TKey, TValue, TKeyComp, TAlloc >::at ( const key_type & key ) const

Access specified item.

A constant overload. When there is no item with the specified key throws std::out_of_range.

Note: Time Complexity: O(log n)

◆ begin() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::begin ( ) const

noexcept

Returns an iterator to the smallest item, read only.

Note: Time Complexity: O(log n)

◆ begin() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::begin ( )

noexcept

Returns an iterator to the smallest item.

Note: Time Complexity: O(log n)

◆ cbegin()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::cbegin ( ) const

noexcept

Returns explicitly a constant iterator to the smallest item.

Note: Time Complexity: O(log n)

◆ cend()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::cend ( ) const

noexcept

Returns explicitly a constant iterator to the end.

Note: Time Complexity: O(1)

◆ clear()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

void datastructures::map< TKey, TValue, TKeyComp, TAlloc >::clear ( )

noexcept

Erases the whole tree.

Erases every node without allocating any more space and thus cannot throw an exception.

Note: Time Complexity: O(n).; Space Complexity: O(1) including the stack size.

◆ contains()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

bool datastructures::map< TKey, TValue, TKeyComp, TAlloc >::contains ( const key_type & key ) const

noexcept

Checks whether there exists an item with given key in the tree.

Note: Time Complexity: O(log n)

◆ count()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::size_type datastructures::map< TKey, TValue, TKeyComp, TAlloc >::count ( const key_type & key ) const

noexcept

Returns the number of items with the given key (0 or 1).

Note: Time Complexity: O(log n)

◆ crbegin()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_reverse_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::crbegin ( ) const

noexcept

Returns explicitly a constant reverse iterator to the biggest item.

Note: Time Complexity: O(log n)

◆ crend()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_reverse_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::crend ( ) const

noexcept

Returns explicitly a constant reverse iterator to the end.

Note: Time Complexity: O(log n)

◆ empty()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

bool datastructures::map< TKey, TValue, TKeyComp, TAlloc >::empty ( ) const

noexcept

Checks whether the map contains any values.

Note: Time Complexity: O(1)

◆ end() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::end ( ) const

noexcept

Returns an iterator to the end, read only.

Note: Time Complexity: O(1)

◆ end() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::end ( )

noexcept

Returns an iterator to the end.

Note: Time Complexity: O(1)

◆ equal_range() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::const_iterator, typename map< TKey, TValue, TKeyComp, TAlloc >::const_iterator > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::equal_range ( const key_type & key ) const

noexcept

Returns a range containing all the items with the given key.

Returns a pair containing the lower and upper bounds.

Returns: A std::pair constaining a pair of iterator. For each element of the pair, if there is no such item present a past-the-end iterator is returned at its place.

Note: Time Complexity: O(log n)

◆ equal_range() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, typename map< TKey, TValue, TKeyComp, TAlloc >::iterator > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::equal_range ( const key_type & key )

noexcept

Returns a range containing all the items with the given key.

Returns a pair containing the lower and upper bounds.

Returns: A std::pair constaining a pair of iterator. For each element of the pair, if there is no such item present a past-the-end iterator is returned at its place.

Note: Time Complexity: O(log n)

◆ erase() [1/3]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::size_type datastructures::map< TKey, TValue, TKeyComp, TAlloc >::erase ( const key_type & key )

noexcept

Erases an item with the given key.

Does nothing when the key does not exist.

Returns: Number of elements erased (0 or 1)

Note: Time Complexity: O(log n)

◆ erase() [2/3]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::erase ( const_iterator pos )

noexcept

Erases an item.

Invalidates only the references to this item. Erasing invalid iterator and .end() is UB.

Returns: Iterator pointing to the next item.

Note: Time Complexity: O(log n)

◆ erase() [3/3]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::erase ( iterator pos )

noexcept

Erases an item.

Invalidates only the references to this item. Erasing invalid iterator and .end() is UB.

Returns: Iterator pointing to the next item.

Note: Time Complexity: O(log n)

◆ find() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::find ( const key_type & key ) const

noexcept

Finds an item with the given key.

Returns: Iterator pointing to the found item or to the end when the key is not present.

Note: Time Complexity: O(log n)

◆ find() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::find ( const key_type & key )

noexcept

Finds an item with the given key.

Returns: Iterator pointing to the found item or to the end when the key is not present.

Note: Time Complexity: O(log n)

◆ get_allocator()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::allocator_type datastructures::map< TKey, TValue, TKeyComp, TAlloc >::get_allocator ( ) const

noexcept

Returns the associated allocator.

◆ get_height()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

int datastructures::map< TKey, TValue, TKeyComp, TAlloc >::get_height ( ) const

noexcept

Returns the height of the underlying tree.

Note: Time Complexity: O(log n)

◆ insert() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::insert ( const value_type & item )

Inserts an item.

Tries to insert an item into the tree, when there already is an item with the given key does nothing. Returns true if and only if the insertion was performed. Copies the key, value pair.

Returns: An iterator to an item with the given key, either inserted or the one that was already there and whether the new value was inserted or not.

Note: Time Complexity: O(log n)

◆ insert() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::insert ( value_type && item )

Inserts an item.

Tries to insert an item into the tree, when there already is an item with the given key does nothing. Returns true if and only if the insertion was performed. Moves the key, value pair, if the insertion does not happen the values data are not invalidated.

Returns: An iterator to an item with the given key, either inserted or the one that was already there and whether the new value was inserted or not.

Note: Time Complexity: O(log n)

◆ insert_or_assign() [1/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class TMapped >

std::pair< iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::insert_or_assign	(	const key_type &	key,
		TMapped &&	value
	)

Inserts an item or assigns the value.

If a key equivalent to key already exists, assigns std::forward<M>(value) to the value belonging to key. Otherwise inserts a new value, constructing it from value_type(key, std::forward<M>(value)).

Returns: The iterator to the item updated or inserted, and the true if the item was inserted, false if it was updated.

Note: Time Complexity: O(log n)

◆ insert_or_assign() [2/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class TMapped >

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::insert_or_assign	(	const key_type &	key,
		TMapped &&	value
	)

◆ insert_or_assign() [3/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class TMapped >

std::pair< iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::insert_or_assign	(	key_type &&	key,
		TMapped &&	value
	)

Inserts an item or assigns the value.

If a key equivalent to key already exists, assigns std::forward<M>(value) to the value belonging to key and the keys data are not invalidated. Otherwise inserts a new value, constructing it from value_type(std::move(key), std::forward<M>(value)).

Returns: The iterator to the item updated or inserted, and the true if the item was inserted, false if it was updated.

Note: Time Complexity: O(log n)

◆ insert_or_assign() [4/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class TMapped >

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::insert_or_assign	(	key_type &&	key,
		TMapped &&	value
	)

◆ key_comp()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::key_compare datastructures::map< TKey, TValue, TKeyComp, TAlloc >::key_comp ( ) const

noexcept

Returns the function that compares keys.

◆ lower_bound() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::lower_bound ( const key_type & key ) const

noexcept

Returns an iterator to the first item which is not less than the given key.

The key doesn't have to be in the tree.

Returns: The first item that is not less than the key. If no such item is present, returns a past-the-end iterator.

Note: Time Complexity: O(log n)

◆ lower_bound() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::lower_bound ( const key_type & key )

noexcept

Returns an iterator to the first item which is not less than the given key.

The key doesn't have to be in the tree.

Returns: The first item that is not less than the key. If no such item is present, returns a past-the-end iterator.

Note: Time Complexity: O(log n)

◆ operator=() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc > & datastructures::map< TKey, TValue, TKeyComp, TAlloc >::operator= ( const map< TKey, TValue, TKeyComp, TAlloc > & other )

◆ operator=() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc > & datastructures::map< TKey, TValue, TKeyComp, TAlloc >::operator= ( map< TKey, TValue, TKeyComp, TAlloc > && other )

noexcept

◆ operator[]() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::mapped_type & datastructures::map< TKey, TValue, TKeyComp, TAlloc >::operator[] ( const key_type & key )

Access specified item or insert.

Returns a reference to the mapped value performing an insertion when the specified key isn't present.

Note: Time Complexity: O(log n)

◆ operator[]() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::mapped_type & datastructures::map< TKey, TValue, TKeyComp, TAlloc >::operator[] ( key_type && key )

Access specified item or insert.

Returns a reference to the mapped value performing an insertion when the specified key isn't present. In this overload the key will be moved in the case of a new insertion.

Note: Time Complexity: O(log n)

◆ rbegin() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_reverse_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::rbegin ( ) const

noexcept

Returns a reverse iterator to the biggest item, read only.

Note: Time Complexity: O(log n)

◆ rbegin() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::reverse_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::rbegin ( )

noexcept

Returns a reverse iterator to the biggest item.

Note: Time Complexity: O(log n)

◆ rend() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_reverse_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::rend ( ) const

noexcept

Returns a reverse iterator to the end, read only.

Note: Time Complexity: O(log n)

◆ rend() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::reverse_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::rend ( )

noexcept

Returns a reverse iterator to the end.

Note: Time Complexity: O(log n)

◆ size()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::size_type datastructures::map< TKey, TValue, TKeyComp, TAlloc >::size ( ) const

noexcept

Returns the current number of items.

Note: Time Complexity: O(1)

◆ swap()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

void datastructures::map< TKey, TValue, TKeyComp, TAlloc >::swap ( map< TKey, TValue, TKeyComp, TAlloc > & other )

noexcept

Swaps the content.

Parameters

◆ to_dot()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

std::string datastructures::map< TKey, TValue, TKeyComp, TAlloc >::to_dot ( bool print_invis ) const

Returns the dot representation of the tree.

◆ try_emplace() [1/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class... Args>

std::pair< iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::try_emplace	(	const key_type &	key,
		Args &&...	args
	)

Construct an item in-place.

If there is no item with the given key, inserts a new item into the tree constructed in-place with the given args, otherwise does nothing.

The arguments are forwarded using std::forward<Args>(args)... into the constructor to retain their original types.

Returns: An iterator to an item with the given key, either inserted or the one that was already there and whether the new value was inserted or not.

Note: Time Complexity: O(log n)

◆ try_emplace() [2/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class... Args>

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::try_emplace	(	const key_type &	key,
		Args &&...	args
	)

◆ try_emplace() [3/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class... Args>

std::pair< iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::try_emplace	(	key_type &&	key,
		Args &&...	args
	)

Construct an item in-place.

If there is no item with the given key, inserts a new item into the tree constructed in-place with the given args, otherwise does nothing.

The arguments are forwarded using std::forward<Args>(args)... into the constructor to retain their original types. The key is also moved in this overload.

Returns: An iterator to an item with the given key, either inserted or the one that was already there and whether the new value was inserted or not.

Note: Time Complexity: O(log n)

◆ try_emplace() [4/4]

template<class TKey , class TValue , class TKeyComp = std::less<TKey>, class TAlloc = std::allocator<std::pair<const TKey, TValue>>>

template<class... Args>

std::pair< typename map< TKey, TValue, TKeyComp, TAlloc >::iterator, bool > datastructures::map< TKey, TValue, TKeyComp, TAlloc >::try_emplace	(	key_type &&	key,
		Args &&...	args
	)

◆ upper_bound() [1/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::const_iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::upper_bound ( const key_type & key ) const

noexcept

Returns an iterator to the first item which is greater that the given key.

The key doesn't have to be in the tree.

Returns: The first item that is greater than the key. If no such item is present, returns a past-the-end iterator.

Note: Time Complexity: O(log n)

◆ upper_bound() [2/2]

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::iterator datastructures::map< TKey, TValue, TKeyComp, TAlloc >::upper_bound ( const key_type & key )

noexcept

Returns an iterator to the first item which is greater that the given key.

The key doesn't have to be in the tree.

Returns: The first item that is greater than the key. If no such item is present, returns a past-the-end iterator.

Note: Time Complexity: O(log n)

◆ value_comp()

template<class TKey , class TValue , class TKeyComp , class TAlloc >

map< TKey, TValue, TKeyComp, TAlloc >::value_compare datastructures::map< TKey, TValue, TKeyComp, TAlloc >::value_comp ( ) const

noexcept

Returns the function that compares keys in the key, value pairs.

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

include/datastructures/_avl_iterator.hpp
include/datastructures/map.hpp
include/datastructures/map.ipp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ alloc_traits

◆ allocator_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ difference_type

◆ iterator

◆ key_compare

◆ key_type

◆ mapped_type

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ map() [1/5]

◆ map() [2/5]

◆ map() [3/5]

◆ map() [4/5]

◆ map() [5/5]

◆ ~map()

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ contains()

◆ count()

◆ crbegin()

◆ crend()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ get_allocator()

◆ get_height()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_or_assign() [1/4]

◆ insert_or_assign() [2/4]

◆ insert_or_assign() [3/4]

◆ insert_or_assign() [4/4]

◆ key_comp()

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ swap()

◆ to_dot()

◆ try_emplace() [1/4]

◆ try_emplace() [2/4]

◆ try_emplace() [3/4]

◆ try_emplace() [4/4]

◆ upper_bound() [1/2]

◆ upper_bound() [2/2]

◆ value_comp()