Language: C++

const size_t MOD = 10000;


template<class KeyType, class ValueType>
class MyIterator {
 private:
    size_t pos;
    typename std::list<std::pair<const KeyType, ValueType> >::iterator it;
    std::vector<std::list<std::pair<const KeyType, ValueType> > > *_table;

 public:
    MyIterator() :  pos(0) {
    }

    MyIterator(typename std::list<std::pair<const KeyType, ValueType> >::iterator i,
               std::vector<std::list<std::pair<const KeyType, ValueType> > > *table, size_t p)
            : pos(p), it(i), _table(table) {
    }

    std::pair<const KeyType, ValueType> &operator*() {
        return *it;
    }

    std::pair<const KeyType, ValueType> *operator->() {
        return &*it;
    }

    MyIterator &operator++() {
        ++it;
        while (it == (*_table)[pos].end() && pos < MOD - 1) {
            ++pos;
            it = (*_table)[pos].begin();
        }
        return *this;
    }

    bool operator==(const MyIterator &other) const {
        return pos == other.pos && it == other.it;
    }

    bool operator!=(const MyIterator &other) const {
        return !(*this == other);
    }

    MyIterator operator++(int) {
        MyIterator temp(it, _table, pos);
        ++(*this);
        return temp;
    }
};

template<class KeyType, class ValueType>
class MyConstIterator {
 private:
    size_t pos;
    typename std::list<std::pair<const KeyType, ValueType> >::const_iterator it;
    const std::vector<std::list<std::pair<const KeyType, ValueType> > > *_table;

 public:
    MyConstIterator() : pos(0) {
    }

    MyConstIterator(typename std::list<std::pair<const KeyType, ValueType> >::const_iterator i,
                    const std::vector<std::list<std::pair<const KeyType, ValueType> > > *table,
                    const size_t p) : pos(p), it(i), _table(table) {
    }

    const std::pair<const KeyType, ValueType> &operator*() {
        return *it;
    }

    const std::pair<const KeyType, ValueType> *operator->() {
        return &*it;
    }

    MyConstIterator &operator++() {
        ++it;
        while (it == (*_table)[pos].end() && pos < MOD - 1) {
            ++pos;
            it = (*_table)[pos].begin();
        }
        return *this;
    }

    bool operator==(const MyConstIterator &other) const {
        return pos == other.pos && it == other.it;
    }

    bool operator!=(const MyConstIterator &other) const {
        return !(*this == other);
    }

    MyConstIterator operator++(int) {
        MyConstIterator temp(it, _table, pos);
        ++(*this);
        return temp;
    }
};


template<class KeyType, class ValueType, class Hash = std::hash<KeyType> >
class HashMap {
 private:
    std::vector<std::list<std::pair<const KeyType, ValueType> > > hash_table;
    Hash hash;
    size_t size_of_table;

 public:
    HashMap & operator=(const HashMap & s) {
        HashMap temp(s);
        temp.swap(*this);
        return *this;
    }
    void swap(HashMap& s) throw() {
        std::swap(this->size_of_table, s.size_of_table);
        std::swap(this->hash, s.hash);
        std::vector<std::list<std::pair<const KeyType, ValueType> > > temp;
        temp.resize(MOD);
        for (int i = 0; i < MOD; i++) {
            for (auto x : this->hash_table[i]) {
                temp[i].push_back(x);
            }
        }
        for (int i = 0; i < MOD; i++) {
            this->hash_table[i].clear();
        }
        for (int i = 0; i < MOD; i++) {
            for (auto x : s.hash_table[i]) {
                this->hash_table[i].push_back(x);
            }
        }
        for (int i = 0; i < MOD; i++) {
            s.hash_table[i].clear();
        }
        for (int i = 0; i < MOD; i++) {
            for (auto x : temp[i]) {
                s.hash_table[i].push_back(x);
            }
        }
    }
    typedef MyIterator<const KeyType, ValueType> iterator;
    typedef MyConstIterator<const KeyType, ValueType>
            const_iterator;

    HashMap(Hash h = Hash()) : hash(h), size_of_table(0) {
        hash_table.resize(MOD);
    }

    template<class TIterator>
    HashMap(TIterator begin, TIterator end, Hash h = Hash()) : hash(h), size_of_table(0) {
        hash_table.resize(MOD);
        for (TIterator x = begin; x != end; ++x) {
            insert(*x);
        }
    }

    HashMap(std::initializer_list<std::pair<KeyType, ValueType> > data,
            Hash h = Hash()) : hash(h), size_of_table(0) {
        hash_table.resize(MOD);
        for (typename std::initializer_list<std::pair<KeyType, ValueType> >::const_iterator it
                = data.begin(); it != data.end(); ++it) {
            insert(*it);
        }
    }

    size_t size() const {
        return size_of_table;
    }

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

    Hash hash_function() const {
        return hash;
    }

    void insert(const std::pair<KeyType, ValueType> &data) {
        bool have = false;
        size_t pos = hash(data.first) % MOD;
        for (auto it = hash_table[pos].begin(); it != hash_table[pos].end(); ++it) {
            if (it->first == data.first) {
                have = true;
            }
        }
        if (!have) {
            hash_table[pos].insert(hash_table[pos].begin(),
                                   std::make_pair(data.first, data.second));
            ++size_of_table;
        }
    }

    void erase(const KeyType &key) {
        if (size_of_table == 0) {
            return;
        }
        size_t pos = hash(key) % MOD;
        for (auto it = hash_table[pos].begin(); it != hash_table[pos].end(); ++it) {
            if (it->first == key) {
                hash_table[pos].erase(it);
                --size_of_table;
                return;
            }
        }
    }

    iterator begin() {
        if (size_of_table == 0) {
            return (this->end());
        }
        size_t pos = 0;
        while (hash_table[pos].empty() && pos < MOD)
            ++pos;
        if (pos == MOD) {
            return this->end();
        } else {
            iterator ans(hash_table[pos].begin(), &hash_table, pos);
            return ans;
        }
    }

    iterator end() {
        iterator ans((*this).hash_table[MOD - 1].end(), &hash_table, MOD - 1);
        return ans;
    }

    const_iterator begin() const {
        if (size_of_table == 0) {
            return (this->end());
        }
        size_t pos = 0;
        while (hash_table[pos].empty() && pos < MOD)
            ++pos;
        return (pos == MOD ? this->end() :
                const_iterator(this->hash_table[pos].cbegin(), &hash_table, pos));
    }

    const_iterator end() const {
        return const_iterator(this->hash_table[MOD - 1].cend(), &hash_table, MOD - 1);
    }

    iterator find(const KeyType &key) {
        if (size_of_table == 0)
            return this->end();
        size_t pos = hash(key) % MOD;
        for (auto it = hash_table[pos].begin(); it != hash_table[pos].end(); ++it) {
            if (it->first == key) {
                return iterator(it, &hash_table, pos);
            }
        }
        return this->end();
    }

    const_iterator find(const KeyType &key) const {
        if (size_of_table == 0)
            return this->end();
        size_t pos = hash(key) % MOD;
        for (auto it = hash_table[pos].begin(); it != hash_table[pos].end(); ++it) {
            if (it->first == key) {
                return const_iterator(it, &hash_table, pos);
            }
        }
        return this->end();
    }

    ValueType &operator[](const KeyType &k) {
        auto it = this->find(k);
        if (it != this->end()) {
            return it->second;
        } else {
            ValueType p;
            if (strncmp(typeid(p).name(), "i", 1) == 0) {
                insert(std::make_pair(k, static_cast<ValueType>(0)));
            } else {
                insert(std::make_pair(k, p));
            }
            return this->operator[](k);
        }
    }

    const ValueType &at(const KeyType &k) const {
        auto it = this->find(k);
        if (it != this->end()) {
            return it->second;
        } else {
            throw std::out_of_range("");
        }
    }

    void clear() {
        if (size_of_table == 0) {
            return;
        }
        for (int i = 0; i < MOD; ++i) {
            hash_table[i].clear();
        }
        size_of_table = 0;
    }
};


Compiler output:
a.cc:1:7: error: 'size_t' does not name a type
    1 | const size_t MOD = 10000;
      |       ^~~~~~
a.cc:1:1: note: 'size_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
  +++ |+#include <cstddef>
    1 | const size_t MOD = 10000;
a.cc:7:5: error: 'size_t' does not name a type
    7 |     size_t pos;
      |     ^~~~~~
a.cc:7:5: note: 'size_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:8:19: error: 'list' in namespace 'std' does not name a template type
    8 |     typename std::list<std::pair<const KeyType, ValueType> >::iterator it;
      |                   ^~~~
a.cc:1:1: note: 'std::list' is defined in header '<list>'; this is probably fixable by adding '#include <list>'
  +++ |+#include <list>
    1 | const size_t MOD = 10000;
a.cc:8:23: error: expected unqualified-id before '<' token
    8 |     typename std::list<std::pair<const KeyType, ValueType> >::iterator it;
      |                       ^
a.cc:9:10: error: 'vector' in namespace 'std' does not name a template type
    9 |     std::vector<std::list<std::pair<const KeyType, ValueType> > > *_table;
      |          ^~~~~~
a.cc:1:1: note: 'std::vector' is defined in header '<vector>'; this is probably fixable by adding '#include <vector>'
  +++ |+#include <vector>
    1 | const size_t MOD = 10000;
a.cc:15:30: error: 'list' in namespace 'std' does not name a template type
   15 |     MyIterator(typename std::list<std::pair<const KeyType, ValueType> >::iterator i,
      |                              ^~~~
a.cc:15:30: note: 'std::list' is defined in header '<list>'; this is probably fixable by adding '#include <list>'
a.cc:15:34: error: expected ',' or '...' before '<' token
   15 |     MyIterator(typename std::list<std::pair<const KeyType, ValueType> >::iterator i,
      |                                  ^
a.cc:20:10: error: 'pair' in namespace 'std' does not name a template type
   20 |     std::pair<const KeyType, ValueType> &operator*() {
      |          ^~~~
a.cc:1:1: note: 'std::pair' is defined in header '<utility>'; this is probably fixable by adding '#include <utility>'
  +++ |+#include <utility>
    1 | const size_t MOD = 10000;
a.cc:24:10: error: 'pair' in namespace 'std' does not name a template type
   24 |     std::pair<const KeyType, ValueType> *operator->() {
      |          ^~~~
a.cc:24:5: note: 'std::pair' is defined in header '<utility>'; this is probably fixable by adding '#include <utility>'
   24 |     std::pair<const KeyType, ValueType> *operator->() {
      |     ^~~
a.cc: In constructor 'MyIterator<KeyType, ValueType>::MyIterator()':
a.cc:12:21: error: class 'MyIterator<KeyType, ValueType>' does not have any field named 'pos'
   12 |     MyIterator() :  pos(0) {
      |                     ^~~
a.cc: In constructor 'MyIterator<KeyType, ValueType>::MyIterator(int)':
a.cc:17:15: error: class 'MyIterator<KeyType, ValueType>' does not have any field named 'pos'
   17 |             : pos(p), it(i), _table(table) {
      |               ^~~
a.cc:17:19: error: 'p' was not declared in this scope
   17 |             : pos(p), it(i), _table(table) {
      |                   ^
a.cc:17:23: error: class 'MyIterator<KeyType, ValueType>' does not have any field named 'it'
   17 |             : pos(p), it(i), _table(table) {
      |                       ^~
a.cc:17:26: error: 'i' was not declared in this scope
   17 |             : pos(p), it(i), _table(table) {
      |                          ^
a.cc:17:30: error: class 'MyIterator<KeyType, ValueType>' does not have any field named '_table'
   17 |             : pos(p), it(i), _table(table) {
      |                              ^~~~~~
a.cc:17:37: error: 'table' was not declared in this scope; did you mean 'mutable'?
   17 |             : pos(p), it(i), _table(table) {
      |                                     ^~~~~
      |                                     mutable
a.cc: In member function 'MyIterator<KeyType, ValueType>& MyIterator<KeyType, ValueType>::operator++()':
a.cc:29:11: error: 'it' was not declared in this scope; did you mean 'int'?
   29 |         ++it;
      |           ^~
      |           int
a.cc:30:24: error: '_table' was not declared in this scope; did you mean 'mutable'?
   30 |         while (it == (*_table)[pos].end() && pos < MOD - 1) {
      |                        ^~~~~~
      |                        mutable
a.cc:30:32: error: 'pos' was not declared in this scope
   30 |         while (it == (*_table)[pos].end() && pos < MOD - 1) {
      |                                ^~~
a.cc:30:52: error: 'MOD' was not declared in this scope
   30 |         while (it == (*_table)[pos].end() && pos < MOD - 1) {
      |                                                    ^~~
a.cc: In member function 'bool MyIterator<KeyType, ValueType>::operator==(const MyIterator<KeyType, ValueType>&) const':
a.cc:38:16: error: 'pos' was not declared in this scope
   38 |         return pos == other.pos && it == other.it;
      |                ^~~
a.cc:38:36: error: 'it' was not declared in this scope; did you mean 'int'?
   38 |         return pos == other.pos && it == other.it;
      |                                    ^~
      |                                    int
a.cc: In member function 'MyIterator<KeyType, ValueType> MyIterator<KeyType, ValueType>::operator++(int)':
a.cc:46:25: error: 'it' was not declared in this scope; did you mean 'int'?
   46 |         MyIterator temp(it, _table, pos);
      |                         ^~
      |                         int
a.cc:46:29: error: '_table' was not declared in this scope; did you mean 'mutable'?
   46 |         MyIterator temp(it, _table, pos);
      |                             ^~~~~~
      |                             mutable
a.cc:46:37: error: 'pos' was not declared in this scope
   46 |         MyIterator temp(it, _table, pos);
      |                                     ^~~
a.cc: At global scope:
a.cc:55:5: error: 'size_t' does not name a type
   55 |     size_t pos;
      |     ^~~~~~
a.cc:55:5: note: 'size_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:56:19: error: 'list' in namespace 'std' does not name a template type
   56 |     typename std::list<std::pair<const KeyType, ValueType> >::const_iterator it;
      |                   ^~~~
a.cc:56:19: note: 'std::list' is defined in header '<list>'; this is probably fixable by adding '#include <list>'
a.cc:56:23: error: expected unqualified-id before '<' token
   56 |     typename std::list<std::pair<const KeyType, ValueType> >::const_iterator it;
      |                       ^
a.cc:57:16: error: 'vector' in namespace 'std' does not name a template type
   57 |     const std::vector<std::list<std::pair<const KeyType, ValueType> > > *_table;
      |                ^~~~~~
a.cc:57:11: note: 'std::vector' is defined in header '<vector>'; this is probably fixable by adding '#include <vector>'
   57 |     const std::vector<std::list<std::pair<const KeyType, ValueType> > > *_table;
      |           ^~~
a.cc:63:35: error: 'list' in namespace 'std' does not name a template type
   63 |     MyConstIterator(typename std::list<std::pair<const KeyType, ValueType> >::const_iterator i,
      |                                   ^~~~
a.cc:63:35: note: 'std::list' is defined in header '<list>'; this is probably fixable by adding '#include <list>'
a.cc:63:39: error: expected ',' or '...' before '<' token
   63 |     MyConstIterator(typename std::list<std::pair<const KeyType, ValueType> >::const_iterator i,
      |                                       ^
a.cc:68:16: error: 'pair' in namespace 'std' does not name a template type
   68 |     const std::pair<const KeyType, ValueType> &operator*() {
      |                ^~~~
a.cc:68:11: note: 'std::pair' is defined in header '<utility>'; this is probably fixable by adding '#include <utility>'
   68 |     const std::pair<const KeyType, ValueType> &operator*() {
      |           ^~~
a.cc:72:16: error: 'pair' in namespace 'std' does not name a template type
   72 |     const std::pair<const KeyType, ValueType> *operator->() {
      |                ^~~~
a.cc:72:11: note: 'std::pair' is defined in header '<utility>'; this is probably fixable by adding '#include <utility>'
   72 |     const std::pair<const KeyType, ValueType> *operator->() {
      |           ^~~
a.cc: In constructor 'MyConstIterator<KeyType, ValueType>::MyConstIterator()':
a.cc:60:25: error: class 'MyConstIterator<KeyType, ValueType>' does not have any field named 'pos'
   60 |     MyConstIterator() : pos(0) {
      |                         ^~~
a.cc: In constructor 'MyConstIterator<KeyType, ValueType>::MyConstIterator(int)':
a.cc:65:39: error: class 'MyConstIterator<KeyType, ValueType>' does not have any field named 'pos'
   65 |                     const size_t p) : pos(p), it(i), _table(table) {
      |                                       ^~~
a.cc:65:43: error: 'p' was not declared in this scope
   65 |                     const size_t p) : pos(p), it(i), _table(table) {
      |                                           ^
a.cc:65:47: error: class 'MyConstIterator<KeyType, ValueType>' does not have any field named 'it'
   65 |                     const size_t p) : pos(p), it(i), _table(table) {
      |                                               ^~
a.cc:65:50: error: 'i' was not declared in this scope
   65 |                     const size_t p) : pos(p), it(i), _table(table) {
      |                                                  ^
a.cc:65:54: error: class 'MyConstIterator<KeyType, ValueType>' does not have any field named '_table'
   65 |                     const size_t p) : pos(p), it(i), _table(table) {
      |                                                      ^~~~~~
a.cc:65:61: error: 'table' was not declared in this scope; did you mean 'mutable'?
   65 |                     const size_t p) : pos(p), it(i), _table(table) {
      |                                                             ^~~~~
      |                                                             mutable
a.cc: In member function 'MyConstIterator<KeyType, ValueType>& MyConstIterator<KeyType,