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

#include <persistent_map.hpp>

Classes
struct	value_compare

Public Types
using	key_type = TKey

using	mapped_type = TValue

using	value_type = std::pair< const key_type, const 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	version_type = typename tree_type::version_type

Public Member Functions
	persistent_map ()

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

	persistent_map (const allocator_type &allocator)

	persistent_map (const persistent_map &other)

persistent_map &	operator= (const persistent_map &other)

	persistent_map (persistent_map &&other) noexcept

persistent_map &	operator= (persistent_map &&other) noexcept

	~persistent_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.

std::vector< const mapped_type * >	list_in_order (version_type version) const noexcept
	Returns a vector of values sorted by keys.

const mapped_type *	find (const key_type &key, version_type version) const noexcept
	Access specified item.

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

bool	empty (version_type version) const noexcept
	Checks whether the map contains any values in a given version.

size_type	size (version_type version) const noexcept
	Returns the current number of items in the given version.

int	get_height (version_type version) const noexcept
	Returns the height of the underlying tree in the given version.

void	clear () noexcept
	Erases the whole tree with all its versions.

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

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

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

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

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

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

std::pair< bool, version_type >	erase (const key_type &key, version_type version) noexcept
	Erases an item with the given key.

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

version_type	get_current_version () const noexcept
	Returns the current verison.

version_type	get_preceding_version (version_type version) const
	Returns the preceding version to the given version.

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

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

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

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

Detailed Description

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

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

This map type provides immutable updates while preserving access to all previously created versions. Each successful modifying operation creates a new version instead of changing the existing one.

The implementation uses structural sharing, so unchanged parts of the AVL tree are shared between versions and only the path affected by an update is copied.

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

Every version has a unique version ID. Version IDs are assigned sequentially starting from 0, while the initial empty version has the special ID -1. New versions can be based on any existing version, therefore the versions form a tree rather than a simple linear sequence.

References to values belonging to an existing version remain valid as long as the map object itself remains alive and the version is not deleted by .clear_all().

Template Parameters

TKey	Represents the keys in the map, it must support `std::less` comparisons or you must provide a custom one.
TValue	Represents the stored 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 rebound to allocate the nodes themselves.

Member Typedef Documentation

◆ alloc_traits

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

using datastructures::persistent_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, const TValue>>>

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

◆ const_pointer

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

using datastructures::persistent_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, const TValue>>>

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

◆ difference_type

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

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

◆ key_compare

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

using datastructures::persistent_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, const TValue>>>

using datastructures::persistent_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, const TValue>>>

using datastructures::persistent_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, const TValue>>>

using datastructures::persistent_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, const TValue>>>

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

◆ size_type

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

using datastructures::persistent_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, const TValue>>>

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

◆ version_type

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

using datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::version_type = typename tree_type::version_type

Constructor & Destructor Documentation

◆ persistent_map() [1/5]

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

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

◆ persistent_map() [2/5]

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

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

explicit

◆ persistent_map() [3/5]

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

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

explicit

◆ persistent_map() [4/5]

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

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

◆ persistent_map() [5/5]

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

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

noexcept

◆ ~persistent_map()

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

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

noexcept

Member Function Documentation

◆ clear()

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

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

noexcept

Erases the whole tree with all its versions.

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::persistent_map< TKey, TValue, TKeyComp, TAlloc >::contains	(	const key_type &	key,
		version_type	version
	)		const

noexcept

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

Note: Time Complexity: O(log n)

◆ empty()

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

bool datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::empty ( version_type version ) const

noexcept

Checks whether the map contains any values in a given version.

Note: Time Complexity: O(1)

◆ erase()

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

std::pair< bool, typename persistent_map< TKey, TValue, TKeyComp, TAlloc >::version_type > datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::erase	(	const key_type &	key,
		version_type	version
	)

noexcept

Erases an item with the given key.

Does nothing when the key does not exist, the version does not update.

Returns: Whether the deletion occured and the newest version id in this branch.

Note: Time Complexity: O(log n)

◆ find()

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

const persistent_map< TKey, TValue, TKeyComp, TAlloc >::mapped_type * datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::find	(	const key_type &	key,
		version_type	version
	)		const

noexcept

Access specified item.

Returns a constant pointer to the value associated with the key, when such value does not exist returns a nullptr. The value cannot be changed this way, because all updates are immutable, if you want to update the value, use insert_or_assign with the same key and version.

Note: Time Complexity: O(log n)

◆ get_allocator()

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

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

noexcept

Returns the associated allocator.

◆ get_current_version()

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

version_type datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::get_current_version ( ) const

inlinenoexcept

Returns the current verison.

◆ get_height()

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

int datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::get_height ( version_type version ) const

noexcept

Returns the height of the underlying tree in the given version.

Note: Time Complexity: O(log n)

◆ get_preceding_version()

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

version_type datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::get_preceding_version ( version_type version ) const

inline

Returns the preceding version to the given version.

◆ insert() [1/2]

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

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

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: whether the new value was inserted or not and the newest version id in this branch.

Note: Time Complexity: O(log n)

◆ insert() [2/2]

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

std::pair< bool, typename persistent_map< TKey, TValue, TKeyComp, TAlloc >::version_type > datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::insert	(	value_type &&	item,
		version_type	version
	)

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: whether the new value was inserted or not and the newest version id in this branch.

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, const TValue>>>

template<class TMapped >

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

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: true if the item was inserted, false if it was updated. And the newest version id in this branch.

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, const TValue>>>

template<class TMapped >

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

◆ insert_or_assign() [3/4]

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

template<class TMapped >

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

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: true if the item was inserted, false if it was updated. And the newest version id in this branch.

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, const TValue>>>

template<class TMapped >

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

◆ key_comp()

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

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

noexcept

Returns the function that compares keys.

◆ list_in_order()

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

std::vector< const typename persistent_map< TKey, TValue, TKeyComp, TAlloc >::mapped_type * > datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::list_in_order ( version_type version ) const

noexcept

Returns a vector of values sorted by keys.

The values are returned as const pointers since they are immutable.

For an empty tree or invalid version returns an empty vector.

Returns: The sorted vector.

Note: Time Complexity: O(n); Newly allocated space: O(n)

◆ operator=() [1/2]

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

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

◆ operator=() [2/2]

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

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

noexcept

◆ size()

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

persistent_map< TKey, TValue, TKeyComp, TAlloc >::size_type datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::size ( version_type version ) const

noexcept

Returns the current number of items in the given version.

Note: Time Complexity: O(1)

◆ swap()

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

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

noexcept

Swaps the content.

Parameters

◆ try_emplace() [1/4]

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

template<class... Args>

std::pair< bool, version_type > datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::try_emplace	(	const key_type &	key,
		version_type	version,
		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: Whether the new value was inserted or not and the newest version id in this branch.

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, const TValue>>>

template<class... Args>

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

◆ try_emplace() [3/4]

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

template<class... Args>

std::pair< bool, version_type > datastructures::persistent_map< TKey, TValue, TKeyComp, TAlloc >::try_emplace	(	key_type &&	key,
		version_type	version,
		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: Whether the new value was inserted or not and the newest version id in this branch.

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, const TValue>>>

template<class... Args>

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

◆ value_comp()

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

persistent_map< TKey, TValue, TKeyComp, TAlloc >::value_compare datastructures::persistent_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/persistent_map.hpp
include/datastructures/persistent_map.ipp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ alloc_traits

◆ allocator_type

◆ const_pointer

◆ const_reference

◆ difference_type

◆ key_compare

◆ key_type

◆ mapped_type

◆ pointer

◆ reference

◆ size_type

◆ value_type

◆ version_type

Constructor & Destructor Documentation

◆ persistent_map() [1/5]

◆ persistent_map() [2/5]

◆ persistent_map() [3/5]

◆ persistent_map() [4/5]

◆ persistent_map() [5/5]

◆ ~persistent_map()

Member Function Documentation

◆ clear()

◆ contains()

◆ empty()

◆ erase()

◆ find()

◆ get_allocator()

◆ get_current_version()

◆ get_height()

◆ get_preceding_version()

◆ 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()

◆ list_in_order()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()

◆ swap()

◆ try_emplace() [1/4]

◆ try_emplace() [2/4]

◆ try_emplace() [3/4]

◆ try_emplace() [4/4]

◆ value_comp()