#include <cassert>
#include <iterator>
#include <string>
#include <unordered_map>
#include <vector>

template <typename Key, typename Value>
class Sparse_Map
{    
public:

    class iterator
    {
    public:

        using value_type = std::pair<Key, Value>;
        using reference  = std::pair<Key const&, Value&>;
        using pointer    = std::pair<Key const*, Value*>;
        using difference_type = int;
        using iterator_category = std::bidirectional_iterator_tag;

        reference operator*()
        {
            auto&& pair = *current;
            return { pair.first, pair.second };
        }

        iterator& operator++()
        {
            ++current;
            return *this;
        }

        iterator operator++(int)
        {
            iterator tmp { *this };
            ++(*this);
            return tmp;
        }

        iterator& operator--()
        {
            --current;
            return *this;
        }

        iterator operator--(int)
        {
            iterator tmp { *this };
            --(*this);
            return tmp;
        }
        
        bool operator==(iterator const& other) const
        {
            return current == other.current;
        }

        bool operator!=(iterator const& other) const
        {
            return !(*this == other);
        }
        
    private:

        friend class Sparse_Map<Key, Value>;
        iterator(typename std::vector<std::pair<Key, Value>>::iterator current)
            : current { current }
        {
        }
        
        typename std::vector<std::pair<Key, Value>>::iterator current;
        
        
    };
    
    void insert(Key const& key, Value const& value)
    {
        if (lookup.count(key) > 0)
            return;

        std::size_t index { data.size() };
        lookup[key] = index;

        data.push_back({ key, value });
    }

    void erase(Key const& key)
    {
        auto it = lookup.find(key);
        if (it == lookup.end())
            return;

        std::size_t index { it->second };
        std::swap(data[index], data.back());
        
        lookup[data[index].first] = index;
        
        data.pop_back();
        lookup.erase(it);
    }

    Value& at(Key const& key)
    {
        std::size_t index { lookup.at(key) };
        return data[index].second;
    }

    std::size_t size() const
    {
        return data.size();
    }
    
    iterator begin()
    {
        return { data.begin() };
    }

    iterator end()
    {
        return { data.end() };
    }
    
private:

    std::unordered_map<Key, std::size_t> lookup { };
    std::vector<std::pair<Key, Value>> data { };
    
};

int main()
{
    Sparse_Map<std::string, int> map { };
    
    map.insert("def", 2);
    map.insert("abc", 1);
    map.insert("ghi", 3);

    assert( map.at("abc") == 1 );
    assert( map.at("def") == 2 );
    assert( map.at("ghi") == 3 );

    map.erase("def");
    assert( map.size() == 2 );

    map.insert("jkl", 4);

    assert( map.at("abc") == 1 );
    assert( map.at("ghi") == 3 );
    assert( map.at("jkl") == 4 );

    assert( map.size() == 3 );
    
    // looping should work once the iterators have been created
    // note that it should be possible to modify value, but not key
    for (auto&& [key, value] : map)
        ++value;

    // make sure that modifying value in the previous loop worked
    assert( map.at("abc") == 2 );
    assert( map.at("ghi") == 4 );
    assert( map.at("jkl") == 5 );
    
    auto it = map.begin();

    // test that all increments and decrements exist and work
    
    assert( it++ == map.begin() );
    assert( --it == map.begin() );

    it = map.end();
    assert( it-- == map.end() );
    assert( ++it == map.end() );

    --(--(--it));
    assert( it == map.begin() );

    ++(++(++it));
    assert( it == map.end() );

}