A C++ custom iterator for indirection iteration

Question

This program does not quite conform to the previous related question, yet does basically the same thing: given a collection of elements and a collection of indices, return via an iterator collection elements according to the sequence of indices. Here it goes:

#include <exception>
#include <iostream>
#include <iterator>
#include <list>
#include <sstream>
#include <vector>

template<typename ForwardIterator, typename IndexIterator>
class indirection_iterator {
public:
    indirection_iterator(ForwardIterator element_begin,
                         ForwardIterator element_end,
                         IndexIterator index_begin,
                         IndexIterator index_end)
    :
    m_element_begin{element_begin},
    m_element_end{element_end},
    m_index_begin{index_begin},
    m_index_end{index_end},
    m_index_current{index_begin},
    m_elements{std::distance(element_begin, element_end)}
    {}

    indirection_iterator begin()
    {
        return indirection_iterator{m_element_begin,
                                    m_element_end,
                                    m_index_begin,
                                    m_index_end,
                                    m_index_begin};
    }

    indirection_iterator end()
    {
        return indirection_iterator{m_element_begin,
                                    m_element_end,
                                    m_index_begin,
                                    m_index_end,
                                    m_index_end};
    }

    auto operator*()
    {
        auto index = *m_index_current;
        check_index(index, m_elements);
        auto element_iterator = m_element_begin;
        std::advance(element_iterator, index);
        return *element_iterator;
    }

    void operator++()
    {
        std::advance(m_index_current, 1);
    }

    bool operator!=(indirection_iterator const& other)
    {
        return m_index_current != other.m_index_current;
    }

private:

    indirection_iterator(ForwardIterator element_begin,
                         ForwardIterator element_end,
                         IndexIterator index_begin,
                         IndexIterator index_end,
                         IndexIterator index_current)
    :
    m_element_begin{element_begin},
    m_element_end{element_end},
    m_index_begin{index_begin},
    m_index_end{index_end},
    m_index_current{index_current},
    m_elements{std::distance(element_begin, element_end)}
    {}

    template<typename IndexIter>
    using index_type = typename std::iterator_traits<IndexIter>::value_type;

    ForwardIterator m_element_begin;
    ForwardIterator m_element_end;
    IndexIterator m_index_begin;
    IndexIterator m_index_end;
    IndexIterator m_index_current;
    typename std::iterator_traits<ForwardIterator>::difference_type m_elements;

    template<typename index_type>
    void check_index(index_type index, size_t elements)
    {
        if (index < 0)
        {
            std::stringstream ss;
            ss << "index(" << index << ") < 0";
            throw std::runtime_error{ss.str()};
        }

        if (index >= elements)
        {
            std::stringstream ss;
            ss << "index(" << index << ") >= elements(" << elements << ")";
            throw std::runtime_error{ss.str()};
        }
    }
};


static std::vector<char> get_alphabet() {
    std::vector<char> alphabet;

    for (char ch = 'a'; ch <= 'z'; ch++)
    {
        alphabet.push_back(ch);
    }

    for (char ch = 'A'; ch <= 'Z'; ch++)
    {
        alphabet.push_back(ch);
    }

    alphabet.push_back(',');
    alphabet.push_back(' ');
    alphabet.push_back('!');
    alphabet.push_back('\n');

    return alphabet;
}

int main(int argc, const char * argv[]) {
    std::vector<char> alphabet = get_alphabet();
    std::list<int> char_indices =
    { 33, 4, 11, 11, 14, 52, 53, 48, 14, 17, 11, 3, 54, 55 };

    indirection_iterator<decltype(alphabet.cbegin()),
                         decltype(char_indices.cbegin())> indirection_iter {
        alphabet.cbegin(),
        alphabet.cend(),
        char_indices.cbegin(),
        char_indices.cend()
    };

    std::copy(indirection_iter.begin(),
              indirection_iter.end(),
              std::ostream_iterator<char>{std::cout});
    return 0;
}

Critique request

I would like to hear how to make it more usable and how to make it more idiomatic C++.

Answer 1

You are missing the iterator_traits types

If there were only one big tip I could give you, it would be to add the required type aliases for compatibility with the standard iterator interface. Citing from working draft N 4296 of the C++ standard (the last working draft before C++14), section 24.4.1 [iterator.traits]:

To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type. Accordingly, it is required that if Iterator is the type of an iterator, the types

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category 

be defined as the iterator’s difference type, value type and iterator category, respectively. In addition, the types

iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

shall be defined as the iterator’s reference and pointer types, that is, for an iterator object a, the same type as the type of *a and a->, respectively. In the case of an output iterator, the types

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

may be defined as void.

Thus, your implementation is currently not a valid iterator in the STL sense (which was also already noticed by nwp in the comments).

Your interface is a little confusing

The class that you wrote, indirection_iterator, does not only serve as an iterator, but also as a kind of iterator factory. Code such as

indirection_iterator<decltype(alphabet.cbegin()),
                     decltype(char_indices.cbegin())> indirection_iter {
    alphabet.cbegin(),
    alphabet.cend(),
    char_indices.cbegin(),
    char_indices.cend()
};

std::copy(indirection_iter.begin(),
          indirection_iter.end(),
          std::ostream_iterator<char>{std::cout});

makes me feel really uneasy because it goes against how iterators are used by the STL. Calling begin and end on an iterator just feels wrong.

I suggest splitting up the functionality into two classes instead: One class which is used to make indirection iterators from a given set of value and index iterators (called indirection_iterator_factory, for example) and an indirection_iterator class which encapsulates only the iterator functionality.

De-cluttering

An added benefit of this method would be that you could reduce your actual iterator class by a few members. Another point which makes me uneasy is the fact that you have six different members in what is basically a simple iterator class, some of which are unnecessary as far as I can see. For example, you never make use of m_index_begin, so that should be the first variable to go. The same is true for m_index_end, as for m_element_end.

Before we go on removing stuff, let's talk a bit about iterator design here. In particular, I want to talk about check_index. So far, you are evaluating whether a particular index is in bounds for every access and, if it is not, throw an exception. That last part is going to make some people angry, because throwing exceptions is something a not negligible part of C++ developers disapprove of, and on some platforms, exceptions are not even usable at all. This does not mean that you should never rely on exceptions, but in my opinion, you should make everything relying on exceptions opt-in.

In your case, that basically means extracting the index check into a public interface method that the user can call if he wants, but doesn't have to. This is akin to how this issue is usually dealt with in the standard library: For example, std::vector offers both an unchecked operator[] as well as a checked (and exception-throwing) method at.

Having said that, I do actually believe that iterators should be as minimalistic as possible and only offer what they were designed to do, which is, in most cases, iterating a certain range of objects. If I had to rewrite your indirection_iterator, I would certainly leave out range checking as a whole, and require that all the indices in the underlying container be valid (again, it does seem to me that this largely reflects how the iterators in the STL were designed). This is a matter of opinion, however, so don't take this as a must-do.

Adding to the interface

The interface of indirection_iterator is currently kind of meager. For example, operator-> is missing, which is a requirement for input iterators; an iterator category you could easily fulfill. The same is true for pre-increment, and having operator==, although not strictly required, would probably be reasonable. Another thing which I would definitely add is a way to retrieve the current index, since this opens up a wide variety of possible use cases for your users, ranging from logging elements with their index to doing bounds checking manually.

Then there is a whole group of methods which are difficult to provide, but oftentimes very reasonable, e.g. operator--. The difficulty here arises from the fact that what you have written is less of an actual iterator and more of an iterator adapter.

Optimizing functionality for different iterators could definitely be beneficial to usability as well as speed, but the big downside is that it will be a lot of work to implement. Ultimately, it depends on your use case, but if you really wanted to make this iterator part of a publicly available library, you should do that step. Otherwise, it is purely up to you whether you want to invest that much time and effort.

Little things and nitpicks

1. The name of the type parameter to check_index, index_type, is the same as an alias template you defined before. This could possibly lead to name shadowing or worse, so I would suggest you change either of those two names.
2. The template typename parameter IndexIterator does not convey what type of iterator you require. I would suggest IndexForwardIterator.
3. operator!= is currently somewhat dysfunctional, the reason being that you only check for index equality, but not whether both of the iterators are iterators over the same container. Thus, if I had an iterator over container a with indices i and an iterator over container b with indices i, both iterators could still compare equal, which is likely not what you want.

Answer 2

A portability problem

I know this is just the test code, rather than the real subject of the review, but it's worth mentioning.

for (char ch = 'a'; ch <= 'z'; ch++)
{
    alphabet.push_back(ch);
}

This doesn't necessarily do what you think it does; it depends on the target's character coding. In EBCDIC locales, this will insert 41 values, which will throw your indexing off.

It's safer and clearer to initialize from a string literal:

static std::vector<char> get_alphabet() {
    static char const s[] = ""
        "abcdefghijklmnopqrstuvwxyz"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        ", !\n";

    return {std::begin(s), std::end(s)};
}

Iterator interface

GCC warns (with -Weffc++) that operator++() should conventionally return a reference to *this, not void. Many of the methods could/should be declared const, too (at least begin, end, operator*, operator!= and check_index, per my testing).

User Incomputable recommended that I point you at operator overloading (on cppreference.com) as a useful list of the usual function signatures.