#include <iostream>
#include <vector>
#include <list>
#include <utility>
#include <initializer_list>


template<class KeyType, class ValueType>
class Cell {
public:
    typedef std::pair<const KeyType, ValueType& > Pair;
    KeyType key;
    ValueType value;
    Pair pair;
    typename std::list<std::pair<const KeyType, ValueType& >>::iterator iterPointer; //  pointer to this cell but in iterList
    Cell() {};
    Cell(KeyType inputKey, ValueType inputValue):
            key(inputKey),
            value(inputValue),
            pair(inputKey, value) {}
    Cell(std::pair<const KeyType, ValueType> inputPair):
            key(inputPair.first),
            value(inputPair.second),
            pair(inputPair) {}
};

template<class KeyType, class ValueType>
bool operator== (const Cell<KeyType, ValueType>& cellA, const Cell<KeyType, ValueType>& cellB) {
    return cellA.key == cellB.key && cellA.key == cellB.value;
}

template<class KeyType, class ValueType, class Hash = std::hash<KeyType> >
class HashMap {
private:
    typedef Cell<const KeyType, ValueType> HashCell;
    typedef std::pair<const KeyType, ValueType> Pair;
    std::list<Pair> iterList;
    std::list<size_t> indexList;
    const size_t tableSize = 10*10*10*10*10*10;
    size_t elemsNum;
    size_t hashFunc(size_t num) const {
        return num % tableSize;
    }
    Hash hasher;
    std::vector<std::list<HashCell>> data;

public:
    typedef typename std::list<Pair>::iterator iterator;
    typedef typename std::list<Pair>::const_iterator const_iterator;
    void insert(Pair input) {
        HashCell cell(input);
        KeyType key = cell.key;
        size_t index = hashFunc(hasher(key));
        ++elemsNum;
        for (HashCell& bucketCell : data[index]) {
            if (bucketCell.key == key) {
                return;
            }
        }
        data[index].push_back(cell);
        data[index].back().iterPointer = iterList.insert(iterList.end(), cell.pair);
        //data[index].back().iterPointer = iter;
        iterList.back().second = cell.value;
    }

    HashMap(Hash hasher = Hash()):
            data(tableSize),
            hasher(hasher),
            elemsNum(0) {}
    template <class InputIt>
    HashMap(InputIt begin,
            InputIt end,
            const Hash hasher = Hash()):
            data(tableSize),
            hasher(hasher),
            elemsNum(0)
    {
        for ( ; begin != end; ++begin ) {
            insert(*begin);
        }
    }

    HashMap(std::initializer_list<std::pair<const KeyType, ValueType>> input,
            const Hash hasher = Hash()):
            data(tableSize),
            hasher(hasher),
            elemsNum(0)
    {
        for (auto& pair : input) {
            insert(pair);
        }
    }

    void erase(KeyType key) {
        size_t index = hashFunc(hasher(key));
        for (HashCell& cell : data[index]) {
            if (cell.key == key) {
                --elemsNum;
                iterList.erase(cell.iterPointer); // удаление из списка итераторов
                data[index].remove(cell); // удаление из HashMap
                break;
            }
        }
    }

    bool empty() const {
        return (elemsNum == 0);
    }

    size_t size() const {
        return elemsNum;
    }

    typename std::list<Pair>::iterator begin() {
        return iterList.begin();
    }

    typename std::list<Pair>::iterator end() {
        return iterList.end();
    }

    typename std::list<Pair>::const_iterator begin() const {
        return iterList.cbegin();
    }

    typename std::list<Pair>::const_iterator end() const {
        return iterList.cend();
    }

    Hash hash_function() const {
         return hasher;
    }

    typename std::list<Pair>::iterator find(KeyType key) {
        size_t index = hashFunc(hasher(key));
        for (HashCell& cell : data[index]) {
            if (cell.key == key) {
                return cell.iterPointer;
            }
        }
        return (*this).end();
    }

    typename std::list<Pair>::const_iterator find(KeyType key) const {
        size_t index = hashFunc(hasher(key));
        for (HashCell cell : data[index]) {
            if (cell.key == key) {
                return static_cast<typename std::list<Pair>::const_iterator>(cell.iterPointer);
            }
        }
        return (*this).end();
    }
    ValueType& operator[] (KeyType key) {
        size_t index = hashFunc(hasher(key));
        for (HashCell &cell : data[index]) {
            if (cell.key == key) {
                return cell.value;
            }
        }
        HashCell cell(key, ValueType());

        ++elemsNum;
        data[index].push_back(cell);
        auto iter = iterList.insert(iterList.end(), cell.pair);
        data[index].back().iterPointer = iter;
        return data[index].back().value;
    }

    const ValueType& at(KeyType key) const {
        size_t index = hashFunc(hasher(key));
        for (auto iter = data[index].begin(); iter != data[index].end(); ++iter) {
            if (iter->key == key) {
                return iter->value;
            }
        }
        throw;
    }

    void clear() {
        for (Pair& pair : iterList) {
            KeyType key = pair.first;
            size_t index = hashFunc(hasher(key));
            data[index].clear();
        }
        iterList.clear();
        elemsNum = 0;
    }
};


typedef std::pair<const int, int> Pair;
int main() {
    HashMap<int, int> test1({Pair(1,1),Pair(2,2), Pair(3,3)});
    test1.insert(Pair(4,2));
    test1.insert(Pair(4,0));
    test1.erase(1);
    test1.insert(Pair(7,22));
    test1.erase(3);
    std::cout << test1.empty() << std::endl;
    std::cout<< test1.size() << std::endl;
    std::cout << (test1.find(3) == test1.end()) << std::endl;
    std::cout << (test1.find(4) == test1.end()) << std::endl;
    test1[4] = 4;
    test1[6] = 8;
    test1.clear();

    std::vector<Pair> input = { Pair(2, 7), Pair(3, 8) };
    const HashMap<int, int> test2(input.begin(), input.end());
    std::cout << test2.empty() << std::endl;
    std::cout<< test2.size() << std::endl;
    std::cout << (test2.find(3) == test2.end()) << std::endl;
    std::cout << (test2.find(4) == test2.end()) << std::endl;
    std::cout << test2.at(2) << std::endl;
    //std::cout << test2.at(5) << std::endl;

    HashMap<int, int> test3;
    test3[3] = 5;
    test3[2] = 1;
    test3[0] = 7;
    std::cout << (test3.find(0) == test3.end()) << std::endl;
    test3.erase(0);
    std::cout << (test3.find(0) == test3.end()) << std::endl;
    std::cout << (test3.find(2) == test3.end()) << std::endl;
    test3[8] = -4;
    for (auto iter = test3.begin(); iter != test3.end(); ++iter) {
        std::cout << iter->first << " " << iter->second << std::endl;
    }
    test3.clear();
    std::cout << (test3.find(3) == test3.end()) << std::endl;
    test3[3] = 3;
    std::cout << (test3.find(3) == test3.end()) << std::endl;
    return 0;
}