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

using namespace std;

template<class KeyType, class ValueType, class Hash = std::hash<KeyType>>
class HashMap {
public:

    //1
    HashMap(const Hash& hash = Hash()) : Hasher(hash) {
            clear();
        }

    //2
    template<class Iter>
    HashMap(Iter begin, Iter end, const Hash& hasher = Hash()) :
        HashMap(hasher)
    {
        while (begin != end) {
            insert(*begin);
            ++begin;
        }
    }

    //3 , 4
    HashMap(const std::initializer_list<std::pair<KeyType, ValueType> >& list,
            const Hash& hasher = Hash()) :
        HashMap(hasher)
    {
        for (auto now : list) {
            insert(now);
        }
    }

    //5
    size_t size() const {
        return Elements;
    }

    bool empty() const {
        return !Elements;
    }

    //6
    Hash hash_function() const {
        return Hasher;
    }

    //7
    void insert(const pair<KeyType, ValueType>& a) {
        if (5* static_cast<long long>(Elements + 1) > 3*static_cast<long long>(Size)) {
            expand();
        }
        size_t i = hash_count(a.first);
        if (Table[i].first == Data.end()) {
            Data.push_front(a);
            Table[i].first = Data.begin();
            ++Table[i].second;
            ++Elements;
        } else {
            auto it = Table[i].first;
            while (it != Data.end() && hash_count(it->first) == i) {
                if (it->first == a.first) {
                    return;
                }
                ++it;
            }
            Data.insert(it, a);
            ++Table[i].second;
            ++Elements;
        }
    }

    //8
    void erase(const KeyType& x) {
        size_t i = hash_count(x);
        auto it = Table[i].first;
        if (it != Data.end()) {
            while (it != Data.end() && hash_count(it->first) == i) {
                if (it->first == x) {
                    if (Table[i].second == 1) {
                        Table[i].first = Data.end();
                        Table[i].second = 0;
                    }
                    Data.erase(it);
                    --Elements;
                    return;
                }
                ++it;
            }
        }
    }

    //9
    using iterator = typename list<pair<const KeyType, ValueType>>::iterator;
    using const_iterator = typename list<pair<const KeyType, ValueType>>::const_iterator;

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

    const_iterator begin() const {
        return Data.begin();
    }

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

    const_iterator end() const {
        return Data.end();
    }

    //10
    iterator find(const KeyType& x) {
        size_t i = hash_count(x);
        iterator it = Table[i].first;
        if (Table[i].first != Data.end()) {
            while (it != Data.end() && hash_count(it->first) == i) {
                if (it->first == x) {
                    return it;
                }
                ++it;
            }
        }
        return (Data.end());
    }

    const_iterator find(const KeyType& x) const {
        size_t i = hash_count(x);
        const_iterator it = Table[i].first;
        if (Table[i].first != Data.end()) {
            while (it != Data.end() && hash_count(it->first) == i) {
                if (it->first == x) {
                    return it;
                }
                ++it;
            }
        }
        return (Data.end());
    }

    //11
    ValueType& operator [] (const KeyType& x) {
        auto it = find(x);
        if (it == Data.end()) {
            insert({x, ValueType()});

            return find(x)->second;
        } else {
            return it->second;
        }
    }

    //12
    const ValueType& at(const KeyType& x) const {
        auto it = find(x);
        if (it == Data.end()) {
            throw std::out_of_range("I do not have dis key\n");
        } else {
            return it->second;
        }
    }

    //13
    void clear() {
        Data.clear();
        Data.resize(0);
        Table.clear();
        Table.resize(1,make_pair(Data.end(), 0));
        Size = 1;
        Elements = 0;
    }


   HashMap& operator = (const HashMap other) {
        clear();
        for (auto now : other) {
            insert(now);
        }
        return *this;
    }

    void print() {
        cout << "Таблица содержит:\n";
        for (auto now : Data) {
            cout <<"элемент " << now.first << " " << now.second << "\n";
        }
    }


    vector<pair <typename list< pair<const KeyType, ValueType>>::iterator,size_t>> Table;
    list<pair<const KeyType, ValueType>> Data;
    Hash Hasher;
    size_t Size, Elements;



    void expand() {
        vector<pair<const KeyType, ValueType> > CurPairs;
        for (auto a : Data) {
                CurPairs.emplace_back(a);
        }
        size_t nSize = 2*Size;
        clear();
        Table.resize(nSize, make_pair(Data.end(),0));
        Size = nSize;
        for (auto now : CurPairs) {
            insert(now);
        }
    }



    size_t hash_count(const KeyType& key) const {
        return Hasher(key)%Size;
    }


};