scalable_map.h: pair->flat_map->unordered_map as growth demands

scalable_map.h

#pragma once

template <class K, class V, int bigmap_threshold = 10>
class scalable_map {
  struct Empty {};

  typedef std::pair<K, V> Pair;
  typedef boost::container::flat_map<K, V> SmallMap;
  typedef std::unordered_map<K, V> BigMap;

  std::variant<Empty, Pair, SmallMap, BigMap> data_;
  
public:
  struct iterator {
    std::variant<Empty, Pair, SmallMap::iterator, BigMap::iterator> it_;
    
    Pair& operator->() {
      if (auto pp = std::get<Pair>(&it_) {
        return *pp;
      } else if (auto psmallit = std::get<SmallMap::iterator>(&it_) {
        return **psmallit;
      } else if (auto pbigit = std::get<BigMap::iterator>(&it_) {
        return **pbigit;
      } else {
        throw 0;
      }
    }

    iterator& operator++() {
      if (std::get<Pair>(&it_) {
        it_ = Empty();
      } else if (auto psmallit = std::get<SmallMap::iterator>(&it_) {
        auto &it = *psmallit;
        ++it;
      } else if (auto pbigit = std::get<BigMap::iterator>(&it_) {
        auto &it = *pbigit;
        ++it;
      } else {
        throw 0;
      }
    }
  };

  void insert(const Pair& newPair) {
    if (std::get<Empty>(&data_)) {
      data_ = newPair;
    } else if (auto pp = std::get<Pair>(&data_)) {
      auto existingPair = *pp;
      data_ = SmallMap();
      auto &map = *std::get<SmallMap>();
      map.insert(existingPair);
      map.insert(newPair);
    } else if (auto psmall = std::get<SmallMap>(&data_)) {
      if (psmall->size() < bigmap_threshold - 1) {
        auto &map = *psmall;
        map.insert(newPair);
      } else {
        auto smallMapCopy = *psmall;
        data_.emplace(BigMap(smallMapCopy.begin(), smallMapCopy.end()));
        auto &map = *std::get<BigMap>();
        map.insert(newPair);
      }
    } else if (auto pbigit = std::get<SmallMap>(&data_)) {
      auto &map = *pbigit;
      map.insert(newPair);
    } else {
      throw 0;
    }
  }

  iterator find(const K &key) {
    if (auto pp = std::get<Pair>(&data_)) {
      return { *pp };
    } else if (auto psmallit = std::get<SmallMap>(&data_)) {
      return { psmallit->find(key) };
    } else if (auto pbigit = std::get<SmallMap>(&data_)) {
      return { pbigit->find(key) };
    } else {
      throw 0;
    }
  }

  iterator end() {
    if (auto pp = std::get<Pair>(&data_)) {
      return { false }
    } else if (auto psmallit = std::get<SmallMap>(&data_)) {
      return { psmallit->end() };
    } else if (auto pbigit = std::get<SmallMap>(&data_)) {
      return { pbigit->end() };
    } else {
      throw 0;
    }
  }
}