A map dynamically allocates memory on the heap for stored objects. When new objects are added to the map, new allocations are made. Not for every added object, but there are moments when the allocated memory is not enough and more is needed.
There are systems where runtime allocations are not preferred or even forbidden because they are not predictable (they depend on how data is inserted or removed) and they take time. In these cases, an approach is to use static memory, known at compile time. For this, you need to know the size of your data.
The two approaches above are the main difference between a vector (dynamic) and an array (static) of the C++ standard library.
C++ does not provide a map that uses static memory. And I started writing one for learning purposes. It’s a concept, not ready for production, with missing features, not optimized for speed and size. I just wanted a map with static memory that would help me achieve constant lookup complexity in some algorithms. And I added some map-like features.
I started by defining the need. I have some 2D points and some types of points.
enum class PointType {
a,
b,
c,
d,
e,
};
struct Point {
int x;
int y;
};
And I want a list of those points, each of them associated with a type, so I can easily find a point by a given type.
PointType::a -> Point{0, 0}
PointType::b -> Point{1, 3}
PointType::c -> Point{10, 5}
I could have reached for simple approaches like an array of points and a switch on the given type. And that’s what I kind of did but in a generalized way. I’m storing the values (Point) into an array. Then, for each map access by key, I need to find the corresponding index; this would be the hash function, which I called an indexer because it generates an index for the storage array. The default indexer that I provide does a static_cast from the key to std::size_t; a custom one can be passed.
At this point, I have a simple map that receives a Key type and a Value type, just like the standard map. Using static memory, it also needs to know the size. Continue reading Map with static memory