#include <iostream>
#include <vector>

using std::vector;

#define element std::pair<const KeyType, ValueType>
#define bucket std::vector<element>
#define pbucket bucket*

template<class KeyType, class ValueType>
class hash_iterator: public std::iterator<std::forward_iterator_tag, element> {
  typedef typename vector<element>::iterator viterator;

 private:
  vector<pbucket> &data_;
  viterator it_;
  size_t index_;

 public:
  hash_iterator(const vector<pbucket> &data, const size_t ind, const viterator x) : data_(data) {
    index_ = ind;
    it_ = x;
  }

  const element operator*(const hash_iterator &x) const {
    return *x.it_;
  }

  friend const hash_iterator operator++(hash_iterator &x, int) {
    hash_iterator y = x;
    x.it_++;
    while (x.it_ == x.data_[x.index_]->end()) {
      (x.index_)++;
    }
    return y;
  }

  friend const hash_iterator& operator++(hash_iterator &x) {
    ++x.it_;
    while (x.it_ == x.data_[x.index_]->end()) {
      ++(x.index_);
    }
    return x;
  }

/*
  const hash_iterator& operator=(const const_hash_iterator &x) : this->data_(x.data_) {
    this->it_ = x.it_;
    this->index_ = x.index_;
  }
*/
};

template<class KeyType, class ValueType>
class const_hash_iterator: public std::iterator<std::forward_iterator_tag, element> {
  typedef typename vector<element>::iterator viterator;

 private:
  vector<pbucket> &data_;
  viterator it_;
  size_t index_;

 public:
  const_hash_iterator(const vector<pbucket> &data, const size_t ind, const viterator x) {
    data_(data);
    index_ = ind;
    it_ = x;
  }

  const element operator*(const const_hash_iterator &x) const {
    return *x.it_;
  }

  const_hash_iterator& operator=(const hash_iterator<KeyType, ValueType> &x) {
    if (this == &x)
      return *this;
    this->data_(x.data_);
    this->it_ = x.it_;
    this->index_ = x.index_;
    return *this;
  }
};

template<class KeyType, class ValueType, class Hash = std::hash<KeyType>>
class HashMap {
 private:
  typedef hash_iterator<const KeyType, ValueType> iterator;
  typedef const_hash_iterator<const KeyType, ValueType> const_iterator;
  const double LOAD_FACTOR = 0.3;

  vector<pbucket> data_;
  size_t size_, tsize_;  // table size = data_.capacity()
  Hash hasher;

  void data_clearing() {
    for (size_t i = 0; i < data_.size(); ++i) {  // mb bug
      (*data_[i]).clear();
      delete (*data_[i]);
    }
  }

  void fix() {
    if (1.0 * size_ / tsize_ < LOAD_FACTOR)
      return;
    iterator it = this->begin();
    iterator end = this->end();
    tsize_ *= 3;
    vector<pbucket> buf;
    buf.reserve(tsize_);
    for (size_t i = 0; i < tsize_; ++i)
      buf[i] = new bucket;
    while (it != end) {
      size_t ind = get_pos(it->first);
      buf[ind]->push_back(*it);
      ++it;
    }
    data_clearing();
    data_ = buf;
  }

  size_t get_pos(KeyType x) const {
    return hasher(x) % tsize_;
  }

  iterator find_in_bucket(size_t ind, KeyType x) const {
    size_t i = 0;
    for (auto it = data_[ind]->begin(); it != data_[ind]->end(); ++it, ++i) {
      if (it->first == x)
        return iterator(data_, ind, it);
    }
    return iterator(data_, ind, data_[ind]->end());
  }

 public:
  HashMap(const Hash& hash = Hash()) {
    size_ = 0;
    tsize_ = 10;
    data_.reserve(10);
    for (size_t i = 0; i < 10; ++i)
      data_[i] = new bucket;
    hasher = hash;
  }

  HashMap(iterator l, iterator r, const Hash& hash = Hash()) {
    (*this) = HashMap(hash);
    while (l != r) {
      insert((*l)++);
    }
  }

  HashMap(std::initializer_list<std::pair<KeyType, ValueType>> x, const Hash& hash = Hash()) {
    (*this) = HashMap(hash);
    for (auto it = x.begin(); it != x.end(); ++it) {
      insert(*x);
    }
  }

  const_iterator begin() const {
    return const_iterator(data_, 0, data_[0].begin());
  }

  const_iterator end() const {
    return const_iterator(data_, tsize_ - 1, data_[tsize_ - 1].end());
  }

  iterator begin() {
    return iterator(data_, 0, data_[0].begin());
  }

  iterator end() {
    return iterator(data_, tsize_ - 1, data_[tsize_ - 1].end());
  }

  const size_t size() const {
    return size_;
  }

  const bool empty() const {
    return !size_;
  }

  const Hash& hash_function() const {
    return hasher;
  }

  void insert(std::pair<KeyType, ValueType> x) {
    size_t ind = get_pos(x.first);
    if (find_in_bucket(ind, x.first) == data_[ind]->end())
      return;
    (*data_[ind]).push_back(x);
    ++size_;
    fix();
  }

  void erase(std::pair<KeyType, ValueType> x) {
    size_t ind = get_pos(x.first);
    iterator it = find_in_bucket(ind, x.first);
    if (it == data_[ind]->end())
      return;
    --size_;
    (*data_[ind]).erase(it);
  }

  iterator find(const KeyType x) {
    size_t ind = get_pos(x);
    iterator it = find_in_bucket(ind, x);
    if (it == data_[ind]->end())
      return this->end();
    return it;
  }

  const_iterator find(const KeyType x) const {
    size_t ind = get_pos(x);
    iterator it = find_in_bucket(ind, x);
    if (it == data_[ind]->end())
      return this->end();
    return it;
  }

  ValueType& operator[](const KeyType x) const {
    size_t ind = get_pos(x);
    iterator it = find(x);
    if (it == this->end()) {
      data_[ind]->push_back(std::make_pair(x, ValueType()));
      return &((*data_[ind]).back().second);
    }
    return &(it->second);
  }

  const ValueType& at(const KeyType x) const {
    size_t ind = get_pos(x);
    iterator it = find(x);
    if (it == this->end()) {
      std::cout << "std::out_of_range\n";  // LEL
    }
    return &(it->second);
  }

  void clear() {
    data_clearing();
    size_ = 0;
    tsize_ = 10;
    data_.reserve(10);
    for (size_t i = 0; i < 10; ++i)
      data_[i] = new bucket;
  }

  ~HashMap() {
    data_clearing();
  }
};

int main() {
}