Skip to content

Instantly share code, notes, and snippets.

@akmalm07

akmalm07/compact_map.h

Created January 25, 2026 00:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save akmalm07/c12fd534a0a866933d964cc20ca71d8b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save akmalm07/c12fd534a0a866933d964cc20ca71d8b to your computer and use it in GitHub Desktop.
Download ZIP
This is a cache-friendly, vector-backed associative map for C++ optimized for fast iteration over small to medium datasets. Benchmarks show it achieves over 9× faster iteration than std::unordered_map, while unordered_map remains faster for random key lookups.
Raw
compact_map.h
#pragma once
/*
compact_map — a cache-friendly vector-backed map for C++.
Benchmark results (10,000 integer keys):
| Operation | compact_map | unordered_map |
|------------|-------------------:|-----------------:|
| Lookup | 1,969,399 ns (~508 op/s) | 381,418 ns (~2,622 op/s) |
| Iteration | 10,973 ns (~91,129 op/s) | 91,662 ns (~10,910 op/s) |
Takeaway:
- compact_map is extremely fast for iteration due to contiguous memory layout.
- unordered_map is faster for random lookups, as expected.
*/
namespace smallVecMap
{
template<typename T>
concept Sortable = requires(T a, T b) {
{ a < b } -> std::convertible_to<bool>;
};
template<Sortable Key, typename Value>
class compact_map {
public:
compact_map() = default;
// Find index using binary search
size_t find_index(const Key& key) const;
// Insert or update key-value pair
void insert(const Key& key, const Value& value);
// operator[] inserts default if not found
Value& operator[](const Key& key);
const Value& operator[](const Key& key) const;
void remove(const Key& key);
void clear();
size_t size() const;
bool empty() const;
const std::vector<Key>& keys() const;
const std::vector<Value>& values() const;
struct iterator
{
using self = iterator;
using value_type = std::pair<const Key&, Value&>;
using reference = value_type;
using pointer = void;
using difference_type = std::ptrdiff_t;
using iterator_category = std::random_access_iterator_tag;
iterator(std::vector<Key>& keys, std::vector<Value>& values, size_t index);
reference operator*() const;
self& operator++();
self operator++(int);
bool operator==(const self& other) const;
bool operator!=(const self& other) const;
private:
std::vector<Key>& _keys;
std::vector<Value>& _values;
size_t _index;
};
iterator begin();
iterator end();
static constexpr size_t npos = static_cast<size_t>(-1);
private:
std::vector<Key> _keys;
std::vector<Value> _values;
};
}
#include "compact_map.inl"
Raw
compact_map.inl
#pragma once
#include "compact_map.h"
namespace smallVecMap
{
template<Sortable Key, typename Value>
inline size_t compact_map<Key, Value>::find_index(const Key& key) const
{
auto it = std::lower_bound(_keys.begin(), _keys.end(), key);
if (it != _keys.end() && *it == key)
{
return std::distance(_keys.begin(), it);
}
return npos;
}
template<Sortable Key, typename Value>
inline void compact_map<Key, Value>::insert(const Key& key, const Value& value)
{
auto it = std::lower_bound(_keys.begin(), _keys.end(), key);
size_t index = std::distance(_keys.begin(), it);
if (it != _keys.end() && *it == key)
{
_values[index] = value;
}
else
{
_keys.insert(it, key);
_values.insert(_values.begin() + index, value);
}
}
template<Sortable Key, typename Value>
Value& compact_map<Key, Value>::operator[](const Key& key)
{
auto it = std::lower_bound(_keys.begin(), _keys.end(), key);
size_t index = std::distance(_keys.begin(), it);
if (it != _keys.end() && *it == key)
{
return _values[index];
}
else
{
_keys.insert(it, key);
_values.insert(_values.begin() + index, Value{});
return _values[index];
}
}
template<Sortable Key, typename Value>
inline const Value& compact_map<Key, Value>::operator[](const Key& key) const
{
size_t index = find_index(key);
assert(index != npos && "Key not found in const operator[]");
return _values[index];
}
template<Sortable Key, typename Value>
inline void compact_map<Key, Value>::remove(const Key& key)
{
size_t index = find_index(key);
if (index != npos)
{
_keys.erase(_keys.begin() + index);
_values.erase(_values.begin() + index);
}
}
template<Sortable Key, typename Value>
inline void compact_map<Key, Value>::clear()
{
_keys.clear();
_values.clear();
}
template<Sortable Key, typename Value>
inline size_t compact_map<Key, Value>::size() const
{
return _keys.size();
}
template<Sortable Key, typename Value>
inline bool compact_map<Key, Value>::empty() const
{
return _keys.empty();
}
template<Sortable Key, typename Value>
inline const std::vector<Key>& compact_map<Key, Value>::keys() const
{
return _keys;
}
template<Sortable Key, typename Value>
inline const std::vector<Value>& compact_map<Key, Value>::values() const
{
return _values;
}
template<Sortable Key, typename Value>
inline compact_map<Key, Value>::iterator compact_map<Key, Value>::begin()
{
return iterator(_keys, _values, 0);
}
template<Sortable Key, typename Value>
inline compact_map<Key, Value>::iterator compact_map<Key, Value>::end()
{
return iterator(_keys, _values, _keys.size());
}
template<Sortable Key, typename Value>
inline compact_map<Key, Value>::iterator::iterator(std::vector<Key>& keys, std::vector<Value>& values, size_t index)
: _keys(keys), _values(values), _index(index) {
}
template<Sortable Key, typename Value>
inline compact_map<Key, Value>::iterator::reference compact_map<Key, Value>::iterator::operator*() const
{
return { _keys[_index], _values[_index] };
}
template<Sortable Key, typename Value>
inline compact_map<Key, Value>::iterator::self& compact_map<Key, Value>::iterator::operator++()
{
_index++;
return *this;
}
template<Sortable Key, typename Value>
inline compact_map<Key, Value>::iterator::self compact_map<Key, Value>::iterator::operator++(int)
{
auto tmp = *this;
(*this)++;
return tmp;
}
template<Sortable Key, typename Value>
inline bool compact_map<Key, Value>::iterator::operator==(const self& other) const
{
return _index == other._index;
}
template<Sortable Key, typename Value>
inline bool compact_map<Key, Value>::iterator::operator!=(const self& other) const
{
return !(*this == other);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment