2
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Neither the title nor the description actually seem to have anything to do with what the code concretely does. Do you want to have the key-value scheme reviewed, or is this a general design question (in which case it's off-topic)? \$\endgroup\$
    – Daniel
    Jul 7, 2018 at 20:40
  • \$\begingroup\$ Did you want an iterator_adaptor? Sounds like you just want a transform_iterator that gives .second. But I think you are better off just using a range adaptor, specifically map_values when you write your loop. \$\endgroup\$
    – JDługosz
    Jul 8, 2018 at 2:23
  • \$\begingroup\$ @JDługosz, did you mean this transform_iterator? :) \$\endgroup\$ Jul 8, 2018 at 3:07
  • \$\begingroup\$ @Incomputable no, I was referring to the one in Boost.Iterator. But any such read-made transform iterator is better than making a special purpose one from scratch. \$\endgroup\$
    – JDługosz
    Jul 8, 2018 at 3:50
  • \$\begingroup\$ @JDługosz, I was just joking. My code in no way is comparable in quality to boost code. But I hope one day it will be of similar quality. \$\endgroup\$ Jul 8, 2018 at 12:55

4 Answers 4

4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.
};
\$\endgroup\$
3
\$\begingroup\$

The first questions when building a custom iterator are:

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.