11
\$\begingroup\$

Today, I will require your help to improve an iterator adapter. The goal of the adapter (I called it get_iterator) is to adapt std::map iterators for example: map iterators return std::pair instances, a get_iterator<0, std::map<...>::iterator> will provide an iterator which iterates through the keys while a get_iterator<1, std::map<...>::iterator> will provide an iterator which iterates through the values. Here is my implementation:

Here is the header file:

template<std::size_t N, typename Iterator>
class get_iterator:
    public std::iterator<
        typename std::iterator_traits<Iterator>::iterator_category,
        typename std::remove_reference<decltype(std::get<N>(*Iterator{}))>::type,
        typename std::iterator_traits<Iterator>::difference_type>
{
    private:

        Iterator _current;

    public:

        using iterator_type     = Iterator;
        using value_type        = typename std::remove_reference<decltype(std::get<N>(*_current))>::type;
        using pointer           = value_type*;
        using reference         = value_type&;

        get_iterator();
        explicit get_iterator(Iterator it);
        template<typename U>
        get_iterator(const get_iterator<N, U>& other);

        template<typename U>
        auto operator=(const get_iterator<N, U>& other)
            -> get_iterator&;

        auto base() const
            -> Iterator;

        auto operator*() const
            -> reference;
        auto operator->() const
            -> pointer;

        auto operator++()
            -> get_iterator&;
        auto operator++(int)
            -> get_iterator&;

        auto operator--()
            -> get_iterator&;
        auto operator--(int)
            -> get_iterator&;
};

And here is the implementation file:

template<std::size_t N, typename Iterator>
get_iterator<N, Iterator>::get_iterator()
    = default;

template<std::size_t N, typename Iterator>
get_iterator<N, Iterator>::get_iterator(Iterator it):
    _current(it)
{}

template<std::size_t N, typename Iterator>
template<typename U>
get_iterator<N, Iterator>::get_iterator(const get_iterator<N, U>& other):
    _current(other.base())
{}

template<std::size_t N, typename Iterator>
template<typename U>
auto get_iterator<N, Iterator>::operator=(const get_iterator<N, U>& other)
    -> get_iterator&
{
    if (&other != this)
    {
        _current = other.base();
    }
    return *this;
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::base() const
    -> Iterator
{
    return _current;
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::operator*() const
    -> reference
{
    return std::get<N>(*_current);
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::operator->() const
    -> pointer
{
    return &(operator*());
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::operator++()
    -> get_iterator&
{
    ++_current;
    return *this;
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::operator++(int)
    -> get_iterator&
{
    auto tmp = *this;
    ++_current;
    return tmp;
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::operator--()
    -> get_iterator&
{
    --_current;
    return *this;
}

template<std::size_t N, typename Iterator>
auto get_iterator<N, Iterator>::operator--(int)
    -> get_iterator&
{
    auto tmp = *this;
    --_current;
    return tmp;
}

I don't provide operator==, operator< and their friends in this question since their implementation is trivial and mimicks this of std::reverse_iterator. Are there functions lacking in the interface or things to be improved in the implementation? Also, do you have any idea of a more suitable name for such an iterator adaptor?

\$\endgroup\$
  • \$\begingroup\$ Still getting used to the new syntax for the return type. Not sure why you are using it here. The normal syntax should work and is much clearer (in my opinion). \$\endgroup\$ – Martin York Jan 2 '14 at 20:34
  • \$\begingroup\$ @LokiAstari I personally find it clearer: it allows to split the return type and the rest of the function in one glance. Moreover, it resembles the functions notation in type theory. Well, it also allows me to always use one and only one return type syntax everywhere. \$\endgroup\$ – Morwenn Jan 3 '14 at 14:57
  • \$\begingroup\$ Remember you are not writing code for you to understand. You wrote it, thus you should quickly pick it up again. You really need to write code for the next person that is not you. As they have to maintain it. \$\endgroup\$ – Martin York Jan 3 '14 at 22:07
  • \$\begingroup\$ @LokiAstari Well, at least I try to be consistent when writing it. I don't see what's the big deal with this syntax; I do not see how the old syntax is clearer. \$\endgroup\$ – Morwenn Jan 3 '14 at 22:25
  • 1
    \$\begingroup\$ If you're actually planning on using this in a project, I feel like I need to point out boost has a transform_iterator that's quite a bit more flexible. \$\endgroup\$ – Yuushi Jan 9 '14 at 23:54
5
\$\begingroup\$

Define get_iterator in terms of transform_iterator

As pointed by @Yuushi, Boost has a transform_iterator class which will apply a function to the return value of operator*. Therefore, get_iterator could be define as an alias template:

struct getter
{
    template<typename T>
    auto operator()(T&& value)
        -> decltype(auto)
    {
        return std::get<N>(std::forward<T>(arg));
    }
};

template<std::size_t N, typename Iterator>
using = boost::iterators::transform_iterator<getter<N>, Iterator>;

The function object would have had another advantage had Boost allowed its transform_iterator to take advantage of the empty base optimization. Unfortunately, this is not the case right now, but using a function object may trigger a free improvement when Boost finally implements EBO in transform_iterator.

I would have loved to use ADL to find the most suitable get to use, but get always need an integer template parameter. And ADL is not triggered when a template parameter is provided by hand instead of being deduced.

Add a construction function

Let's assume that we still want to write a get_iterator by hand. While the integer template parameter is always provided by hand, the ability to deduce the Iterator template parameter is still something we want to have. Therefore, we will add a construction function:

template<std::size_t N, typename Iterator>
auto make_get_iterator(Iterator it)
    -> get_iterator<N, Iterator>
{
    return get_iterator<N, Iterator>(it);
}

Moreover, adding such a construction function is consistent with the standard library. After all, std::make_reverse_iterator was added to C++14 for consistency.

Miscellaneous tidbits

There are more things that could be improved, but they are more subtle and less interesting:

  • The check &other != this in operator= seems pretty useless. It is almost always a pessimization and I cannot think of a scenario where assigning base() to itself would go wrong.

  • operator++(int) and operator--(int) shoud return get_iterator instead of get_iterator&. Currently they return references to temporary variables, which is plain wrong. That proves that I didn't write proper tests.

  • More iterator-related functions could have been overloaded to support the requirements of a [RandomAccessIterator][5] when needed since nothing prevents it and supporting more iterators is better than support fewer. The functions that could have been added are operator+, operator-, operator+=, opperator-= and opeator[].

  • It would be better to put = default on its first declaration instead of separating the declaration and the definition of the default constructor. The rationale is that Iterator it{} can zero-initialize the iterator instead of dedault-initializing it if = default appears on the first declaration. I have no idea whether this can change something for any iterator, but initializing memory with zero cannot be worse than initializing it with garbage.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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