A dependency-aware associative container that stores elements in topologically sorted order. More...

#include <aeongames/DependencyMap.hpp>

Inheritance diagram for AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >:

Collaboration diagram for AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >:

Classes
class	iterator
	Mutable bidirectional iterator over topologically sorted entries. More...
class	const_iterator
	Const bidirectional iterator over topologically sorted entries. More...

Public Types
using	triple = typename std::tuple<Key, std::vector<Key>, T>
	Convenience type alias for an insertion tuple: (key, dependencies, payload).

Public Member Functions
void	Reserve (size_t count)
	Reserve storage for a given number of elements.
	DependencyMap ()=default
	Default constructor.
	~DependencyMap ()=default
	Default destructor.
	DependencyMap (std::initializer_list< triple > aList)
	Construct from an initializer list, performing topological sort.
size_t	Insert (const triple &item)
	Insert a new element, maintaining topological order.
void	Erase (const Key &key)
	Remove an element by key.
const T &	operator[] (const std::size_t index) const
	Access element by sorted index (const).
T &	operator[] (const std::size_t index)
	Access element by sorted index (mutable).
const std::size_t	Size () const
	Get the number of elements.
const_iterator	Find (const Key &key) const
	Find an element by key (const).
iterator	Find (const Key &key)
	Find an element by key (mutable).
iterator	begin ()
	Get a mutable iterator to the first element in sorted order.
iterator	end ()
	Get a mutable iterator past the last element in sorted order.
const_iterator	begin () const
	Get a const iterator to the first element in sorted order.
const_iterator	end () const
	Get a const iterator past the last element in sorted order.

Detailed Description

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>
class AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >

A dependency-aware associative container that stores elements in topologically sorted order.

Template Parameters

Key	The key type used to identify nodes.
T	The payload type stored with each node.
Hash	Hash function object type for keys.
KeyEqual	Equality comparison function object type for keys.
MapAllocator	Allocator type for the internal unordered map.
VectorAllocator	Allocator type for the internal sorted vector.

Definition at line 47 of file DependencyMap.hpp.

Member Typedef Documentation

◆ triple

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

using AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::triple = typename std::tuple<Key, std::vector<Key>, T>

Convenience type alias for an insertion tuple: (key, dependencies, payload).

Definition at line 58 of file DependencyMap.hpp.

Constructor & Destructor Documentation

◆ DependencyMap()

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::DependencyMap ( std::initializer_list< triple > aList )

inline

Construct from an initializer list, performing topological sort.

Parameters

aList Initializer list of triples (key, dependencies, payload).

Exceptions

std::runtime_error If a circular dependency is detected.

Definition at line 237 of file DependencyMap.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

iterator AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::begin ( )

inline

Get a mutable iterator to the first element in sorted order.

Returns: An iterator to the beginning.

Definition at line 423 of file DependencyMap.hpp.

◆ begin() [2/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

const_iterator AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::begin ( ) const

inline

Get a const iterator to the first element in sorted order.

Returns: A const_iterator to the beginning.

Definition at line 436 of file DependencyMap.hpp.

◆ end() [1/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

iterator AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::end ( )

inline

Get a mutable iterator past the last element in sorted order.

Returns: An iterator to the end.

Definition at line 429 of file DependencyMap.hpp.

◆ end() [2/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

const_iterator AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::end ( ) const

inline

Get a const iterator past the last element in sorted order.

Returns: A const_iterator to the end.

Definition at line 443 of file DependencyMap.hpp.

◆ Erase()

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

void AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::Erase ( const Key & key )

inline

Remove an element by key.

Parameters

key	The key of the element to remove.

Definition at line 364 of file DependencyMap.hpp.

◆ Find() [1/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

iterator AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::Find ( const Key & key )

inline

Find an element by key (mutable).

Parameters

key	The key to search for.

Returns: An iterator to the element, or end() if not found.

Definition at line 413 of file DependencyMap.hpp.

◆ Find() [2/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

const_iterator AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::Find ( const Key & key ) const

inline

Find an element by key (const).

Parameters

key	The key to search for.

Returns: A const_iterator to the element, or end() if not found.

Definition at line 402 of file DependencyMap.hpp.

◆ Insert()

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

size_t AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::Insert ( const triple & item )

inline

Insert a new element, maintaining topological order.

Parameters

item	A triple (key, dependencies, payload) to insert.

Returns: The index at which the element was inserted in the sorted order.

Exceptions

std::runtime_error If the insertion would create a circular dependency.

Definition at line 291 of file DependencyMap.hpp.

◆ operator[]() [1/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

T & AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::operator[] ( const std::size_t index )

inline

Access element by sorted index (mutable).

Parameters

index Zero-based index into the sorted order.

Returns: A mutable reference to the payload.

Exceptions

std::out_of_range If index is out of range.

Definition at line 387 of file DependencyMap.hpp.

◆ operator[]() [2/2]

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

const T & AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::operator[] ( const std::size_t index ) const

inline

Access element by sorted index (const).

Parameters

index Zero-based index into the sorted order.

Returns: A const reference to the payload.

Exceptions

std::out_of_range If index is out of range.

Definition at line 374 of file DependencyMap.hpp.

◆ Reserve()

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

void AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::Reserve ( size_t count )

inline

Reserve storage for a given number of elements.

Parameters

count Number of elements to reserve space for.

Definition at line 224 of file DependencyMap.hpp.

◆ Size()

template<class Key, class T = Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class MapAllocator = std::allocator< std::pair<const Key, typename std::tuple < Key, size_t, std::vector<Key, std::allocator<Key >>, T >>>, class VectorAllocator = std::allocator<Key>>

const std::size_t AeonGames::DependencyMap< Key, T, Hash, KeyEqual, MapAllocator, VectorAllocator >::Size ( ) const

inline

Get the number of elements.

Returns: The number of stored elements.

Definition at line 394 of file DependencyMap.hpp.

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

include/aeongames/DependencyMap.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ triple

Constructor & Destructor Documentation

◆ DependencyMap()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ Erase()

◆ Find() [1/2]

◆ Find() [2/2]

◆ Insert()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ Reserve()

◆ Size()