cprover
|
Map from small integers to values. More...
#include <small_map.h>
Classes | |
class | const_iterator |
Const iterator. More... | |
class | const_value_iterator |
Const value iterator. More... | |
Public Types | |
typedef std::pair< const unsigned, const T & > | value_type |
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 |
unsigned | get_field (std::size_t field) const |
void | set_field (std::size_t field, unsigned v) |
void | shift_indices (std::size_t ii) |
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 const std::size_t | S_BITS = NUM * num_bitst<NUM - 1>::value + NUM |
static const std::size_t | BITS = num_bitst<NUM - 1>::value + 1 |
static const index_fieldt | IND = indicator_maskt<index_fieldt, BITS>::value |
static const index_fieldt | MASK = ((index_fieldt)1 << BITS) - 1 |
Friends | |
void | small_map_test () |
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.
std::map:
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 107 of file small_map.h.
|
private |
Definition at line 115 of file small_map.h.
typedef std::pair<const unsigned, const T &> small_mapt< T, Ind, Num >::value_type |
Definition at line 287 of file small_map.h.
|
inline |
Definition at line 110 of file small_map.h.
|
inline |
Definition at line 172 of file small_map.h.
|
inline |
Definition at line 187 of file small_map.h.
|
inlineprivate |
Definition at line 131 of file small_map.h.
|
inlineprivate |
Definition at line 144 of file small_map.h.
|
inline |
Definition at line 368 of file small_map.h.
|
inlineprivate |
Definition at line 123 of file small_map.h.
|
inline |
Definition at line 515 of file small_map.h.
|
inline |
Definition at line 549 of file small_map.h.
|
inline |
Definition at line 582 of file small_map.h.
|
inline |
Definition at line 373 of file small_map.h.
|
inline |
Definition at line 478 of file small_map.h.
|
inline |
Definition at line 464 of file small_map.h.
|
inlineprivate |
Definition at line 248 of file small_map.h.
|
inline |
Definition at line 443 of file small_map.h.
|
inlineprivate |
Definition at line 256 of file small_map.h.
|
inlineprivate |
Definition at line 267 of file small_map.h.
|
inline |
Definition at line 576 of file small_map.h.
|
inline |
Definition at line 431 of file small_map.h.
|
inline |
Definition at line 436 of file small_map.h.
|
friend |
|
staticprivate |
Definition at line 216 of file small_map.h.
|
staticprivate |
Definition at line 218 of file small_map.h.
|
private |
Definition at line 593 of file small_map.h.
|
staticprivate |
Definition at line 240 of file small_map.h.
|
staticprivate |
Definition at line 205 of file small_map.h.
|
staticprivate |
Definition at line 207 of file small_map.h.
|
private |
Definition at line 594 of file small_map.h.
|
staticprivate |
Definition at line 214 of file small_map.h.