File two-dimensional-map.hh

Implementation of a two-dimensional map from pairs to single values.

namespace mata

Main namespace including structs and algorithms for all automata.

In particular, this includes:

  1. Alphabets,

  2. Formula graphs and nodes,

  3. Mintermization,

  4. Closed sets.

namespace utils

SparseSet.h Implements a class template of a sparse set of unsigned integers.

Non-automata-related structures and algorithms.

In particular, this includes:

  1. Predicates,

  2. Ordered Vectors,

  3. Iterators,

  4. Printers,

  5. Other helper functions.

Author

Sam Griffiths www.computist.xyz https://gist.github.com/sjgriffiths/06732c6076b9db8a7cf4dfe3a7aed43a

template<typename T, bool track_inverted = true, size_t MAX_MATRIX_SIZE = 50'000'000>
class TwoDimensionalMap
#include <two-dimensional-map.hh>

A two-dimensional map that can be used to store pairs of values and their associated value.

This class can handle both small and large maps efficiently.

The largest matrix of pairs of we are brave enough to allocate is 50’000’000 for 8 Byte values. So ten million cells is close to 100 MB. If the number is larger, then we do not allocate a matrix, but use a vector of unordered maps (vec_map_storage). The unordered_map seems to be about twice slower.

Template Parameters:

  • T – Type of the values stored in the map. Must be an unsigned type.

  • track_inverted – Whether to track inverted indices for the first and second dimensions. To use this feature correctly, the mapping has to be reversible.

  • MAX_MATRIX_SIZE – Maximum size of the matrix before switching to vector of unordered maps.

Public Types

using Map = std::unordered_map<std::pair<T, T>, T>
using MatrixStorage = std::vector<std::vector<T>>
using VecMapStorage = std::vector<std::unordered_map<T, T>>
using InvertedStorage = std::vector<T>

Public Functions

inline TwoDimensionalMap(const size_t first_dim_size, const size_t second_dim_size)

Constructor for TwoDimensionalMap.

Parameters:

  • first_dim_size – Size of the first dimension.

  • second_dim_size – Size of the second dimension.

inline T get(const T first, const T second) const

Get the value associated with a pair of keys.

Parameters:

  • first – First key.

  • second – Second key.

Returns:

The value associated with the pair, or std::numeric_limits<T>::max() if not found.

inline void insert(const T first, const T second, const T value)

Insert a value associated with a pair of keys.

Parameters:

  • first – First key.

  • second – Second key.

  • value – Value to associate with the pair.

inline T get_first_inverted(const T value) const

Get the first inverted index for a value.

This is only available if track_inverted is true.

inline T get_second_inverted(const T value) const

Get the second inverted index for a value.

This is only available if track_inverted is true.

Private Members

const bool is_large
const size_t first_dim_size
const size_t second_dim_size
MatrixStorage matrix_storage = {}
std::vector<std::unordered_map<T, T>> vec_map_storage = {}
InvertedStorage first_dim_inverted = {}
InvertedStorage second_dim_inverted = {}