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.