Untitled

#include "bits/stdc++.h"

using namespace std;

enum OPERATION
{
    ADD,
    DELETE
};

class Record
{
public:
    OPERATION operation;
    int key;
    int value;
    int snap_id;
    Record(OPERATION operation, int key, int value, int snap_id)
    {
        this->operation = operation;
        this->key = key;
        this->value = value;
        this->snap_id = snap_id;
    }
};

class KeyValueStore
{
private:
    unordered_map<int, vector<Record>> keys_to_records;
    int current_snapshot;
    int find_record(vector<Record> &vec, int snap_id)
    {
        int left = 0;
        int right = vec.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (vec[mid].snap_id == snap_id)
            {
                return mid;
            }
            else if (vec[mid].snap_id > snap_id)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return -1;
    }

    int lower_bound_record(vector<Record> &vec, int snap_id)
    {
        int left = 0;
        int right = vec.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (vec[mid].snap_id >= snap_id)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        if (left < vec.size() - 1 && vec[left].snap_id < snap_id)
        {
            left++;
        }
        return left;
    }

public:
    KeyValueStore()
    {
        keys_to_records.clear();
        current_snapshot = 0;
    }
    KeyValueStore(KeyValueStore const &other) = delete;
    KeyValueStore operator&=(KeyValueStore const &other) = delete;

    int get_key_value(int key, int snap_id)
    {
        int pos = -1;
        if (keys_to_records.find(key) == keys_to_records.end())
        {
            throw "Key not found in store";
        }
        else
        {
            pos = find_record(keys_to_records[key], snap_id);
            if (pos == -1)
            {
                pos = lower_bound_record(keys_to_records[key], snap_id);
            }
        }
        if (pos == -1)
        {
            throw "Error in Getting Value";
        }
        if (keys_to_records[key][pos].operation == DELETE)
        {
            throw "Key not found in store";
        }
        return keys_to_records[key][pos].value;
    }

    void put_key_value(int key, int value)
    {
        Record r(ADD, key, value, current_snapshot);
        if (keys_to_records.find(key) != keys_to_records.end())
        {
            int pos = find_record(keys_to_records[key], current_snapshot);
            if (pos != -1)
            {
                keys_to_records[key].push_back(r);
                return;
            }
        }
        keys_to_records[key].push_back(r);
    }

    int take_snap_shot()
    {
        int res = current_snapshot;
        current_snapshot++;
        return res;
    }

    void erase_snap_shot(int snap_id)
    {
        for (auto &&key_to_records : keys_to_records)
        {
            int pos = find_record(key_to_records.second, snap_id);
            if (pos != -1)
            {
                key_to_records.second[pos].operation = DELETE;
            }
        }
    }
};

int main()
{
    KeyValueStore kvs;
    kvs.put_key_value(1, 10);
    int snap_id = kvs.take_snap_shot();
    cout << "Key: " << 1 << " Value: " << kvs.get_key_value(1, snap_id) << "\n";
    kvs.erase_snap_shot(snap_id);
    kvs.put_key_value(1, 100);
    snap_id = kvs.take_snap_shot();
    cout << "Key: " << 1 << " Value: " << kvs.get_key_value(1, snap_id) << "\n";
    return 0;
}