Implementing a custom iterator by inheriting from an existing iterator class and overriding operator*

Question

My goal is to write very little code and I want a custom iterator that only changes the behavior of the dereference operator* but copies the rest of the behavior from the underlying container iterator.

The following code works but is it correct?

#include <iostream>
#include <unordered_map>

using namespace std;

template <typename K, typename V>
class KeyValueStore
{
    using base_iterator = typename unordered_map<K, V>::iterator;

public:
    struct iterator : public base_iterator
    {
        iterator(base_iterator it) : base_iterator(it)
        { }

        // The custom behavior for the dereference operator.
        V& operator*()
        {
            return base_iterator::operator*().second;
        }
    };

    V& get(const K& key)
    {
        return store.at(key);
    }

    void put(K key, V value)
    {
        store[key] = value;
    }

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

    iterator end() { return iterator {store.end()}; }
private:
    unordered_map<K, V> store;
};


int main()
{
    KeyValueStore<string, int> store;
    store.put("aa", 5);
    store.put("vf", 4);

    for (auto item : store)
        cout << item << endl;

    return 0;
}

Answer 1

Use of public inheritance in this case strikes me as problematic.

Public inheritance means that a pointer/reference to an object of the derived class can be converted implicitly to a pointer/reference to the base class. Worse, it also means that an object of the derived class can be implicitly converted ("sliced") to an instance of the base class.

If that happens, you quickly run into a problematic situation: since operator * isn't defined as virtual in the base class, invoking it via a pointer/reference to base will invoke the base version of the operator. Your operator overload isn't really overriding the base class'--it's just hiding it.

This isn't saving a whole lot of work either--you're using an unordered associative container, which only provides forward iterators, so all your inheritance is saving is implementing operator++.

I suppose to be fair, I should add that people rarely pass iterators by reference, so it's not particularly likely that you'll trigger the problems outlined above. On the other hand, history teaches us that idiots can be surprising crafty in figuring out ways to shoot themselves in the feet.

Answer 2

Don’t write using namespace std;.

---

Prefer using \n over std::endl

---

some of the functions should be const member functions.

---

Use existing well-known library features instead of writing something from scratch.

Answer 3

I would also point out that iterators have a bunch of types defined as part of their definition (that are not directly inherited). You need to forward these type definitions into your class. Most importantly value_type.

struct iterator : public base_iterator
{
    // To be a valid iterator you need to define these types:

    // These two you can inherit from base_iterator
    using iterator_category = typename base_iterator::iterator_category;
    using difference_type   = typename base_iterator::difference_type;

    // These three you have changed from the base_iterator
    // so must provide your own definition.
    using value_type        = V:
    using pointer           = V*;
    using reference         = V&;

    iterator(base_iterator it) : base_iterator(it)
    { }

    // The custom behavior for the dereference operator.
    V& operator*()
    {
        return base_iterator::operator*().second;
    }

    // What about `operator->`
    // Currently your iterator has different behaviors for:
    //
    //    (*iter).value   and   iter->value
    //
    // This makes a confusing inconsistency.
};

Answer 4

The first questions when building a custom iterator are:

• is my container a true container for the data referenced by my iterator? ( When Is a Container Not a Container?)
• what is the actual category of my iterator and is it a true iterator? (To Be or Not to Be (an Iterator))

Here all is fine: the underlying map does contain the values you want to iterate, and your iterator will return true references. But you are supposed to declare them so that std::iterator_traits<KeyValueStore::iterator> will find them: your iterator class shall contain declarations for value_type, reference_type, pointer_type, difference_type, iterator_tag.

In addition you are using a public derivation from the underlying iterator. It does save you some boiler plate code, but is wrong: your iterator is not a map iterator, and no polymorphism is to be expected. As the underlying iterator is not required to have a virtual destructor, using a base pointer on a derived object could lead to incorrect destruction.

That means that you will have to write more code, but here the delegate pattern is better than the derivation.

And you should wonder whether is would not make sense to add const iterators...

Code would be:

...
class iterator {
    base_iterator base;

public:
    using value_type = V;
    using reference_type = V&;
    using pointer_type = V*;
    using difference_type = base_iterator::difference_type;
    using iterator_category = base_iterator::iterator_category;

    // ctors:
    iterator() {}
    iterator(const base_iterator& base) base(base) {}

    // Iterators requirements:
    V operator *() {
        return base_iterator::operator*().second;
    }
    iterator& operator ++() {
        ++base;
        return *this;
    }

    // Input iterator:
    iterator operator++(int) {
        iterator tmp = *this;
        ++base;
        return tmp;
    }
    pointer operator ->() {
        return &(operator *());  // or since c++ 2014 return std::addressof(operator *());
    }

You would still have to implement equality, advance, next and distance, as well as conversion from an iterator to a const_iterator.