#include <iostream>
#include <vector>

using namespace std;


template <class KeyType, class ValueType, class Hash = std::hash<KeyType> >
class HashMap {
public:
    using KV = pair<KeyType, ValueType>;

    template <class flag, class type> class add_const_if;

    template <class type>
    class add_const_if<true_type, type> {
        using value = const type;
    };

    template <class type>
    class add_const_if<false_type, type> {
        using value = type;
    };

    template <class KV>
    class iter : public std::iterator<std::input_iterator_tag, KV, long, const KV*, long> {
        using buckets_type = add_const_if<is_const<KV>, vector<vector<KV>>>;
    public:
        iter(buckets_type &buckets): buckets(buckets) {
            while (bucketIndex < buckets.size() && buckets[bucketIndex].empty()) {
                bucketIndex++;
            }
            if (bucketIndex == buckets.size()) {
                bucketIndex = -1; // end
                valueIndex = -1;
            }
        }

        iter(size_t bucketIndex, size_t valueIndex, buckets_type &buckets)
        : bucketIndex(bucketIndex)
        , valueIndex(valueIndex)
        , buckets(buckets) {
        }

        KV& operator*() {
            return buckets[bucketIndex][valueIndex];
        }

//        KV* operator->() {
//            return &buckets[bucketIndex][valueIndex];
//        }

        iter& operator++() {
            if (valueIndex == buckets[bucketIndex].size() - 1) {
                bucketIndex++;
                while (bucketIndex < buckets.size() && buckets[bucketIndex].empty()) {
                    bucketIndex++;
                }
                valueIndex = 0;
                if (bucketIndex == buckets.size()) {
                    bucketIndex = -1; // end
                    valueIndex = -1;
                }
            }
            else {
                valueIndex++;
            }
            return *this;
        }

        iter operator++(int) {
            return ++*this;
        }

        bool operator==(const iter& another) {
            return another.bucketIndex == bucketIndex && another.valueIndex == valueIndex;
        }

        bool operator!=(const iter& another) {
            return !this->operator==(another);
        }

        buckets_type &buckets;
        size_t bucketIndex = 0, valueIndex = 0;
    };

    using iterator = iter<KV>;
    using const_iterator = iter<const KV>;

    HashMap();
    HashMap(const iterator& begin, const iterator& end, const Hash& hasher = Hash()): hasher(hasher) {
        buckets.resize(8);
        for (; begin < end; begin++) {
            insert(*begin);
        }
    }

    HashMap(const initializer_list<KV>& list, const Hash& hasher = Hash()): hasher(hasher) {
        buckets.resize(8);
        for (auto& kv : list) {
            insert(kv);
        }
    }

    iterator begin() {
        return iterator(buckets);
    }

    iterator end() {
        return iterator(-1, -1, buckets);
    }

    void insert(const KV& kv) {
        vector<KV>& hashValues = buckets[hasher(kv.first) % buckets.size()];
        auto ptr = find_if(hashValues.begin(), hashValues.end(), [&kv](const KV& x) -> bool {return x.first == kv.first;});
        if (ptr != hashValues.end())
            return;
        hashValues.push_back(kv);
        sizeOfTable++;
    }

    size_t size() const {
        return sizeOfTable;
    }

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

    Hash hash_function() const {
        return hasher;
    }

    void erase(const KeyType& key) {
        size_t index = hasher(key) % buckets.size();
        vector<KV> hashValues = buckets[index];
        buckets[index].clear();
        copy_if(hashValues.begin(), hashValues.end(), back_inserter(buckets[index]), [&key](const KV& x) -> bool {return x.first != key;});
    }

    ValueType& operator[](const KeyType& key) {
        vector<KV>& hashValues = buckets[hasher(key) % buckets.size()];
        auto ptr = find_if(hashValues.begin(), hashValues.end(), [&key](const KV& x) -> bool {return x.first == key;});
        if (ptr == hashValues.end()) {
            hashValues.push_back({key, ValueType()});
            return hashValues.back().second;
        }
        return ptr->second;
    }
    iterator find(const KeyType& key) {
        size_t index = hasher(key) % buckets.size();
        vector<KV>& hashValues = buckets[index];
        auto ptr = find_if(hashValues.begin(), hashValues.end(), [&key](const KV& x) -> bool {return x.first == key;});
        if (ptr == hashValues.end())
            return iterator(-1, -1, buckets);
        return iterator(index, ptr - hashValues.begin());
    }
    const_iterator find(const KeyType& key) const {
        size_t index = hasher(key) % buckets.size();
        const vector<KV>& hashValues = buckets[index];
        auto ptr = find_if(hashValues.begin(), hashValues.end(), [&key](const KV& x) -> bool {return x.first == key;});
        if (ptr == hashValues.end())
            return const_iterator(-1, -1, buckets);
        return const_iterator(index, ptr - hashValues.begin());
    }

    const ValueType& at(const KeyType& key)const {
        const vector<KV>& hashValues = buckets[hasher(key) % buckets.size()];
        auto iter = find(key);
        if (iter == this->end()) {
            throw out_of_range("Key wasn't found");
        }
        return iter->second;
    }

    void clear() {
        buckets.assign(8);
    }

    vector<vector<KV>> buckets;
    Hash hasher;
    size_t sizeOfTable = 0;
};




int main() {

    HashMap<string, int> hah({make_pair("a", 1), make_pair("b", 2)});
    hah["kek"] = 13;
    cout << hah.at("a");
    //    for (auto x = hah.begin(); x != hah.end(); x++) {
    //        cout << x->first << " " << x->second << "\n";
    //    }
    return 0;
}