dense_map.h

#ifndef __VECS_STORAGE_DENSE_MAP_H__
#define __VECS_STORAGE_DENSE_MAP_H__
 
#include <algorithm>
#include <vector>
 
namespace vecs::storage {

template<
    typename Key,
    typename Value,
    typename = std::enable_if_t<std::is_integral_v<Key>>>
class dense_map {
  public:
    using pair_type = std::pair<Key, Value>;
    using iterator = typename std::vector<pair_type>::iterator;
    using const_iterator = typename std::vector<pair_type>::const_iterator;
 
    void insert(const Key& key, const Value& value) {
        auto it = std::lower_bound(
            m_data.begin(),
            m_data.end(),
            key,
            [](const pair_type& lhs, const Key& rhs) { return lhs.first < rhs; }
        );
        if (it != m_data.end() && it->first == key) {
            // Key already exists; update the value
            it->second = value;
        } else {
            // Insert the new key and value at the correct position
            m_data.insert(it, pair_type {key, value});
        }
    }
 
    iterator find(const Key& key) {
        auto it = std::lower_bound(
            m_data.begin(),
            m_data.end(),
            key,
            [](const pair_type& lhs, const Key& rhs) { return lhs.first < rhs; }
        );
        if (it != m_data.end() && it->first == key) {
            return it;
        }
        return m_data.end();
    }
 
    const_iterator find(const Key& key) const {
        auto it = std::lower_bound(
            m_data.begin(),
            m_data.end(),
            key,
            [](const pair_type& lhs, const Key& rhs) { return lhs.first < rhs; }
        );
        if (it != m_data.end() && it->first == key) {
            return it;
        }
        return m_data.end();
    }
 
    Value& operator[](const Key& key) {
        auto it = std::lower_bound(
            m_data.begin(),
            m_data.end(),
            key,
            [](const pair_type& lhs, const Key& rhs) { return lhs.first < rhs; }
        );
        if (it != m_data.end() && it->first == key) {
            return it->second;
        } else {
            // Key does not exist; insert default value
            return m_data.insert(it, pair_type {key, Value {}})->second;
        }
    }
 
    void clear() {
        m_data.clear();
    }
 
    void erase(const Key& key) {
        auto it = std::lower_bound(
            m_data.begin(),
            m_data.end(),
            key,
            [](const pair_type& lhs, const Key& rhs) { return lhs.first < rhs; }
        );
        if (it != m_data.end() && it->first == key) {
            m_data.erase(it);
        }
    }
 
    iterator erase(iterator it) {
        return m_data.erase(it);
    }
 
    size_t size() const {
        return m_data.size();
    }
 
    bool empty() const {
        return m_data.empty();
    }
 
    iterator begin() {
        return m_data.begin();
    }
 
    const_iterator begin() const {
        return m_data.begin();
    }
 
    iterator end() {
        return m_data.end();
    }
 
    const_iterator end() const {
        return m_data.end();
    }
 
  private:
    std::vector<pair_type>
        m_data;  // Stores pairs of keys and values in sorted order
};
 
}  // namespace vecs::storage
 
#endif