Map from small integers to values. More...

#include <small_map.h>

Inheritance diagram for small_mapt< T, Ind, Num >:

Classes
class	const_iterator
	Const iterator. More...

class	const_value_iterator
	Const value iterator. More...

Public Types
typedef std::pair< const std::size_t, const T & >	valuet

Public Member Functions
	small_mapt ()

	small_mapt (const small_mapt &m)

	~small_mapt ()

const_iterator	begin () const

const_iterator	end () const

const_value_iterator	value_begin () const

const_value_iterator	value_end () const

T &	operator[] (std::size_t idx)

const_iterator	find (std::size_t idx) const

std::size_t	erase (std::size_t idx)

small_mapt *	copy_and_erase (std::size_t idx) const

small_mapt *	copy_and_insert (std::size_t idx, const T &value) const

std::size_t	size () const

bool	empty () const

Private Types
typedef Ind	index_fieldt

Private Member Functions
void	copy (T dest, const T src, std::size_t n) const

T *	allocate (std::size_t n) const

T *	allocate (T *ptr, std::size_t n) const

std::size_t	get_field (std::size_t field) const

void	set_field (std::size_t field, std::size_t v)

void	shift_indices (std::size_t ii)

Static Private Member Functions
static constexpr std::size_t	num_bits (const std::size_t n)

static constexpr index_fieldt	indicator_mask (const index_fieldt digit=1)

Private Attributes
index_fieldt	ind

T *	p

Static Private Attributes
static const std::size_t	N_BITS = std::numeric_limits<index_fieldt>::digits

static const std::size_t	NUM = Num

static constexpr std::size_t	S_BITS = NUM * num_bits(NUM - 1) + NUM

static const std::size_t	BITS = num_bits(NUM - 1) + 1

static const index_fieldt	IND = indicator_mask()

static const index_fieldt	MASK = ((index_fieldt)1 << BITS) - 1

Friends
void	small_map_test ()

Detailed Description

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
class small_mapt< T, Ind, Num >

Map from small integers to values.

A data structure that maps small integers (in {0, ..., Num-1}) to values. It is designed to be more memory-efficient than std::map for this use case.

In the following we give some data about the memory consumption of small_mapt compared to std::map, on a 64-bit Linux system with GNU STL. It was determined with valgrind/massif. We configured the maps as small_mapt<uint64_t, uint32_t, Num=8> and std::map<uint8_t, uint64_t>. Thus, indices to small_mapt can be in {0, ..., 7} for this configuration.

Below we give the memory consumption (in bytes) of small_mapt and std::map, both for when containing 8 elements, and when being empty. The value for "useful" indicates the number of bytes requested, the value for "total" also includes padding bytes.

small_mapt:

8 elements:
- useful: 80 B
- total: 120 B
empty:
- useful: 16 B
- total: 32 B

std::map:

8 elements:
- useful: 432 B
- total: 512 B
empty:
- useful: 48 B
- total: 64 B

Template Parameters

T	mapped type
Ind	unsigned integer type, used to map integer indices to internal indices that index into the memory block that stores the mapped values
Num	gives range of valid indices, i.e., the valid indices are {0, ..., Num-1}, must satisfy Num * num_bits(Num-1) + Num < sizeof(Ind) * 8, with num_bits(n) denoting the minimum number of bits required to represent integer n

Definition at line 68 of file small_map.h.