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.
static_map<PointType, Point, 5> map;
map[PointType::b] = {2, 3};
map[PointType::c] = {7, 8};
Then I wanted more features found in a map. I wanted to know if a key was set, if the map is empty, to iterate the map and use it with STD algorithms, to remove all the elements, and so on.
Knowing all the memory size from the start and not reallocating new one, it was all about knowing at what offset in memory I have some data or if I have something there at all. Being static and initialized memory, there is always something there, so I need to mark somewhere that I consider having a value set for a key or not. My approach is to have multiple arrays (keys, values, flags to know if a key is set) and, for any key, to find the appropriate index that I will use for those arrays.
For iterating the map, I needed a custom iterator that knows how to skip values that were not set. What is worth mentioning about this iterator is the advance method (operator++): if you have 4 keys that you are storing into the map, and only some of them are set, while iterating you have to skip all keys that are not set.
The code shows it all. I compiled it with C++11, gcc.
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <numeric>
#include <stdexcept>
namespace msd {
template <typename Key, typename Value, typename ValuesIterator, typename Values, typename Keys, typename Set>
struct static_map_iterator {
ValuesIterator it_;
Values& values_;
Keys& keys_;
Set& set_;
void operator++() noexcept
{
do {
++it_;
const auto idx = static_cast<std::size_t>(std::distance(values_.begin(), it_));
auto stop = idx >= set_.size() || set_[idx];
if (stop) {
break;
}
} while (true);
}
std::pair<Key&, Value&> operator*()
{
const auto idx = std::distance(values_.begin(), it_);
auto& key = keys_[idx];
auto& element = *it_;
return {key, element};
}
bool operator==(const static_map_iterator&) const noexcept { return it_ == values_.end(); }
bool operator!=(const static_map_iterator&) const noexcept { return !(operator==(*this)); }
};
struct static_map_default_indexer {
template <typename Key>
std::size_t operator()(const Key& key) const noexcept
{
return static_cast<std::size_t>(key);
}
};
template <typename Key, typename Value, std::size_t Size, typename Indexer = static_map_default_indexer>
class static_map {
static_assert(Size > 0, "Size must be at least one");
using keys_type = std::array<Key, Size>;
using values_type = std::array<Value, Size>;
using set_type = std::array<bool, Size>;
public:
using iterator = static_map_iterator<Key, Value, typename values_type::iterator, values_type, keys_type, set_type>;
static_map() = default;
static_map(static_map&) = default;
static_map(static_map&&) noexcept = default;
static_map& operator=(const static_map&) = default;
static_map& operator=(static_map&&) noexcept = default;
static_map(std::initializer_list<std::pair<Key, Value>> list)
{
std::for_each(list.begin(), list.end(), [this](const std::pair<Key, Value>& element) {
this->operator[](element.first) = element.second;
});
}
Value& at(const Key& key)
{
const auto idx = index_(key);
try {
if (!set_.at(idx)) {
throw std::out_of_range{"out of range at map.at()"};
}
return values_.at(idx);
}
catch (const std::out_of_range&) {
throw std::out_of_range{"out of range at map.at()"};
}
}
Value& operator[](const Key& key)
{
const auto idx = index_(key);
keys_[idx] = key;
set_[idx] = true;
return values_[idx];
}
bool empty() const noexcept
{
return std::none_of(set_.cbegin(), set_.cend(), [](bool set) noexcept { return set; });
}
bool contains(const Key& key) const noexcept
{
const auto idx = index_(key);
return set_[idx];
}
std::size_t size() const noexcept { return std::count(set_.cbegin(), set_.cend(), true); }
constexpr std::size_t max_size() const noexcept { return Size; }
iterator begin() noexcept { return iterator{values_.begin(), values_, keys_, set_}; }
iterator end() noexcept { return iterator{values_.end(), values_, keys_, set_}; }
void clear() noexcept { set_.fill(false); }
iterator find(const Key& key)
{
const auto k = std::find(keys_.cbegin(), keys_.cend(), key);
const auto idx = std::distance(keys_.cbegin(), k);
return iterator{std::next(values_.begin(), idx), values_, keys_, set_};
}
private:
values_type values_{};
keys_type keys_{};
set_type set_{};
Indexer index_;
};
} // namespace msd
enum class PointType {
a,
b,
c,
d,
e,
};
struct Point {
int x;
int y;
};
int main()
{
msd::static_map<PointType, Point, 5> init = {
{PointType::a, {1, 0}},
};
msd::static_map<PointType, Point, 5> map;
map = std::move(init);
map[PointType::b] = {2, 3};
map[PointType::b] = {5, 6};
map[PointType::c] = {7, 8};
map[PointType::e] = {99, 98};
assert(map.at(PointType::b).x == 5);
try {
map.at(PointType::d);
throw std::runtime_error{"should have thrown"};
}
catch (const std::out_of_range&) {
}
assert(map[PointType::b].x == 5);
for (auto item : map) {
std::cout << static_cast<int>(item.first) << ": ";
std::cout << "(" << item.second.x << ", " << item.second.y << ")\n";
}
assert(!map.empty());
auto item = map.find(PointType::b);
assert(item != map.end());
assert((*item).first == PointType::b);
assert((*item).second.x == 5);
assert((*item).second.y == 6);
auto missing_item = map.find(PointType::d);
assert(missing_item == map.end());
static_assert(map.max_size() == 5, "max size failed");
assert(map.size() == 4);
assert(map.contains(PointType::b));
assert(!map.contains(PointType::d));
const auto x_sum = std::accumulate(
map.begin(), map.end(), 0,
[](int accumulator, const std::pair<PointType, Point>& item) noexcept { return accumulator + item.second.x; });
assert(x_sum == 112);
std::fill(map.begin(), map.end(), std::make_pair(PointType::b, Point{1, 2}));
for (auto item2 : map) {
std::cout << static_cast<int>(item2.first) << ": ";
std::cout << "(" << item2.second.x << ", " << item2.second.y << ")\n";
}
map.clear();
assert(map.empty());
assert(map.size() == 0);
assert(!map.contains(PointType::b));
}