#include <algorithm>
#include <vector>
#include <iostream>
#include <initializer_list>
#include <iterator>
#include <list>
#include <exception>
#include <string>
#include <ctime>
#include <unordered_map>
#include <utility>

template<class KeyType, class ValueType, class Hash = std::hash<KeyType>>
class HashMap {
public:
    typedef typename std::list<std::pair<const KeyType, ValueType>>::iterator iterator;
    typedef typename std::list<std::pair<const KeyType, ValueType>>::const_iterator const_iterator;

private:
    std::vector<std::vector<iterator>> Data;
    std::list<std::pair<const KeyType, ValueType>> Pairs;
    std::list<size_t> NotEmptyCells;
    Hash hasher;
    std::vector<bool> isEmpty;
    std::vector<std::list<size_t>::iterator> NotEmptyPtr;
public:
    HashMap(Hash hasher_init = Hash()) : hasher(hasher_init),
        isEmpty(std::vector<bool>(765322, true)) {
        Data.resize(765322);
        NotEmptyPtr.resize(765322);
    }

    Hash hash_function() const {
        return hasher;
    }

    HashMap(const std::initializer_list<std::pair<const KeyType, ValueType>>& l,
        Hash hasher_init = Hash()) : hasher(hasher_init),
        isEmpty(std::vector<bool>(765322, true)) {
        Data.resize(765322);
        NotEmptyPtr.resize(765322);
        for (auto el : l) {
            insert(el);
        }
    }

    template <class iterate>
    HashMap(iterate begin, iterate end, Hash hasher_init = Hash()) : hasher(hasher_init),
        isEmpty(std::vector<bool>(765322, true)) {
        Data.resize(765322);
        NotEmptyPtr.resize(765322);
        for (iterate it = begin; it != end; ++it) {
            insert(*it);
        }
    }

    const_iterator begin() const {
        return const_iterator(Pairs.cbegin());
    }

    iterator begin() {
        return iterator(Pairs.begin());
    }

    const_iterator end() const {
        return const_iterator(Pairs.cend());
    }

    iterator end() {
        return iterator(Pairs.end());
    }

    void insert(const std::pair<const KeyType, ValueType>& key) {
        size_t hash = hasher(key.first) % 765322;
        if (find(key.first) == Pairs.end()) {
            Pairs.push_back(key);
            Data[hash].push_back(--Pairs.end());
            if (isEmpty[hash]) {
                NotEmptyCells.push_back(hash);
                isEmpty[hash] = true;
                NotEmptyPtr[hash] = --NotEmptyCells.end();
            }
        }
    }

    void erase(const KeyType& key) {
        size_t hash = hasher(key) % 765322;
        auto it = Data[hash].begin();
        for (it = Data[hash].begin(); it != Data[hash].end(); ++it) {
            if ((*it)->first == key) {
                break;
            }
        }
        if (it != Data[hash].end()) {
            Pairs.erase(*it);
            Data[hash].erase(it);
            if (Data[hash].empty()) {
                isEmpty[hash] = true;
                NotEmptyCells.erase(NotEmptyPtr[hash]);
            }
        }
    }

    size_t size() const {
        return Pairs.size();
    }

    bool empty() const {
        return Pairs.empty();
    }

    void clear() {
        Pairs.clear();
        for (auto empty : NotEmptyCells) {
            Data[empty].clear();
            isEmpty[empty] = true;
        }
    }

    ValueType& operator[](const KeyType& key) {
        if (find(key) != Pairs.end()) {
            size_t hash = hasher(key) % 765322;
            for (auto i : Data[hash]) {
                if (i->first == key) {
                    return i->second;
                }
            }
        }
        else {
            insert(std::make_pair(key, ValueType()));
            return (--Pairs.end())->second;
        }
    }

    const ValueType& at(const KeyType& key) const {
        if (find(key) != Pairs.end()) {
            size_t hash = hasher(key) % 765322;
            for (auto i : Data[hash]) {
                if ((*i).first == key) {
                    return (*i).second;
                }
            }
        }
        else {
            throw std::out_of_range("I HATE PCFS");
        }
    }

    iterator find(const KeyType& key) {
        size_t hash = hasher(key) % 765322;
        for (auto it : Data[hash]) {
            if ((*it).first == key)
                return it;
        }
        return Pairs.end();
    }

    const_iterator find(const KeyType& key) const {
        size_t hash = hasher(key) % 765322;
        for (auto it : Data[hash]) {
            if ((*it).first == key)
                return it;
        }
        return Pairs.cend();
    }
};

std::string check(HashMap<int, int> a, std::unordered_map<int, int> b) {
    if (a.empty() && !b.empty()) {
        return "a is empty, b is not";
    }
    if (!a.empty() && b.empty()) {
        return "b is empty, a is not";
    }
    if (a.size() > b.size()) {
        return "a is bigger than b";
    }
    if (b.size() > a.size()) {
        return "b is bigger than a";
    }
    for (auto i : a) {
        if (b.find(i.first) == b.end()) {
            std::string err = "b does not have ";
            err += i.first;
        }
        if (b[i.first] != i.second) {
            std::string err = "b has another value for ";
            err += i.first;
        }
    }
    for (auto i : b) {
        if (a.find(i.first) == a.end()) {
            std::string err = "a does not have ";
            err += i.first;
        }
        if (a[i.first] != i.second) {
            std::string err = "a has another value for ";
            err += i.first;
        }
    }
    return "OK!";
}



int main() {
    const size_t commands = 1001;
    const size_t maxrand = 603;
    const size_t maxnum = 200;
    srand(time(0));
    clock_t timer = clock();
    HashMap<int, int> a{ { 1,3 },{ 4,2 },{ 3,5 } };
    std::unordered_map<int, int> b{ { 1,3 },{ 4,2 },{ 3,5 } };
    for (size_t i = 0; i < commands; ++i) {
        size_t num = i;
        if (num < 100) {
            int key = rand() % maxnum - maxnum / 2;
            int value = rand() % maxnum - maxnum / 2;
            //std::cout << "Adding " << key << " " << value << std::endl;
            a[key] = value;
            //std::cout << a[key];
            b[key] = value;
        }
        else if (num < 500) {
            int key = rand() % maxnum - maxnum / 2;
            int value = rand() % maxnum - maxnum / 2;
            //std::cout << "Inserting " << key << " " << value << std::endl;
            a.insert(std::pair<int, int>(key, value));
            b.insert(std::pair<int, int>(key, value));
        }
        else if (num < 1000) {
            int key = rand() % maxnum - maxnum / 2;
            std::cout << "Erasing " << key << std::endl;
            a.erase(key);
            b.erase(key);
        }
        else {
            std::cout << "Clearing ";
            a.clear();
            b.clear();
        }
        std::string s = check(a, b);
        //std::cout << s << std::endl;
        if (s != "OK!") { throw(-1); }
    }
    std::cout << (float)(clock() - timer) / CLOCKS_PER_SEC;
    std::cout << std::endl;
    return 0;
}