HashMap-iterator.cpp

    friend class iterator;
    class iterator :
        public std::iterator<std::forward_iterator_tag, pair_t> {
        private:
            std::list<size_t>::iterator lit;
            typename std::vector<Element>::iterator it;
        public:
            iterator(HashMap& h, std::list<size_t>::iterator _lit) :
                lit(_lit), it(h.elements.begin()) {}
            iterator(HashMap& h, size_t position) :
                iterator(h, h.elements[position].it) {}
            bool operator==(const iterator& other) const {
                return (it == other.it) && (lit == other.lit);
            }
            bool operator!=(const iterator& other) const {
                return !(*this == other);
            }
            pair_t& operator*() {
                return (it + *lit)->pair;
            }
            pair_t* operator->() {
                return &(operator*());
            }
            iterator& operator++() {
                ++lit;
                return *this;
            }
            iterator operator++(int) {
                iterator tmp(*this);
                operator++();
                return tmp;
            }
    };

Код Element:

using pair_t = std::pair<KeyType, ValueType>;
using elem_list_t = std::list<size_t>;
static const size_t default_size = 2 * 1000 * 1000 + 3;
enum State {NONE, DELETED, USED};
struct Element {
    elem_list_t::iterator it;
    pair_t pair;
    State state = NONE;
    size_t hash;
};

StackOverflow:
http://stackoverflow.com/questions/3582608/how-to-correctly-implement-custom-iterators-and-const-iterators