Map
The Map template class provides a hash table implementation for arbitrary key-value pairs.
Template parameters
H
typename
default:"Hash<K>"
Hash functor type
E
typename
default:"Equal<K>"
Equality comparator type
Nested types
Contains K key and D data members representing a key-value pair
Constructors
Map()
Map(const H& h, const E& e)
Equality comparator instance
Core operations
operator[]
D& operator[](const K& k)
const D& operator[](const K& k) const
Key to look up (must already exist)
This operator requires the key to already exist. Use insert() first or check with has().
insert
void insert(const K& k, const D& d)
Key to insert (must not exist)
Data to associate with the key
The map automatically rehashes when needed to maintain performance.
has
bool has(const K& k) const
peek
bool peek(const K& k, D& d) const
Reference to store the value if found
true if the key exists, false otherwise
remove
Removes a key-value pair. Precondition: The key must exist.
Key to remove (must exist)
Utility operations
elems
Returns the number of elements in the map.
bucket_count
Returns the number of hash table buckets.
clear
Removes all elements and deallocates the hash table.
moveTo
Moves this map’s contents to another map, leaving this map empty.
The hash and equality objects are not moved by this method.
bucket
const vec<Pair>& bucket(int i) const
Hash and equality functors
MiniSat provides default hash functions for integer types:
static inline uint32_t hash(uint32_t x) { return x; }
static inline uint32_t hash(uint64_t x) { return (uint32_t)x; }
static inline uint32_t hash(int32_t x) { return (uint32_t)x; }
static inline uint32_t hash(int64_t x) { return (uint32_t)x; }
DeepHash<K> and DeepEqual<K> to hash/compare pointed-to values.
Usage example
#include "minisat/mtl/Map.h"
using namespace Minisat;
Map<int, const char*> names;
names.insert(1, "Alice");
names.insert(2, "Bob");
names.insert(3, "Charlie");
if (names.has(2)) {
printf("Name: %s\n", names[2]); // Prints: Name: Bob
}
names.remove(2);
IntMap
The IntMap template class provides an efficient map for keys that can be converted to small integers. It uses a vector for O(1) access.
Template parameters
Key type (must be convertible to integer index)
MkIndex
typename
default:"MkIndexDefault<K>"
Functor that converts keys to vector indices
Constructor
explicit IntMap(MkIndex _index = MkIndex())
_index
MkIndex
default:"MkIndex()"
Index conversion functor
Operations
has
Checks whether a key exists (has been reserved).
operator[]
V& operator[](K k)
const V& operator[](K k) const
Key to access (must exist)
reserve
void reserve(K key)
void reserve(K key, V pad)
Value to use for any new slots created
insert
void insert(K key, V val)
void insert(K key, V val, V pad)
Padding value for intermediate slots
Iteration
const V* begin() const
const V* end() const
V* begin()
V* end()
Utility methods
void clear(bool dispose = false)
void moveTo(IntMap& to)
void copyTo(IntMap& to) const
Whether to deallocate storage
Destination map for move/copy
Usage example
#include "minisat/mtl/IntMap.h"
using namespace Minisat;
// Map from Var (which is just an int) to activity scores
IntMap<Var, double> activity;
Var v0 = 0, v1 = 1, v2 = 2;
activity.insert(v0, 1.0);
activity.insert(v1, 2.5);
activity.insert(v2, 0.8);
if (activity.has(v1)) {
activity[v1] += 0.5; // Increase activity
}
IntSet
The IntSet template class provides a set implementation for integer-indexable keys.
Template parameters
MkIndex
typename
default:"MkIndexDefault<K>"
Index conversion functor
Operations
insert
Adds a key to the set (no effect if already present).
has
Checks whether a key is in the set.
size
Returns the number of elements in the set.
clear
void clear(bool free = false)
toVec
const vec<K>& toVec() const
operator[]
K operator[](int index) const
Map
- Insert: O(1) amortized
- Lookup: O(1) average case
- Remove: O(1) average case
- Space: O(n) plus overhead for hash table buckets
IntMap
- Insert: O(1) amortized
- Lookup: O(1)
- Remove: Not supported
- Space: O(max_key) - sparse for large key ranges