4
\$\begingroup\$

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++.

\$\endgroup\$
  • 1
    \$\begingroup\$ Does not compile. I think it's because the iterator traits are supposed to be discoverable by (standard) algorithms, so you can't make them private. \$\endgroup\$ – nwp Jan 17 '18 at 20:23
  • \$\begingroup\$ @nwp Did on Xcode yet I had to set C++14 in the settings. I will take a look at the issue but not today. \$\endgroup\$ – coderodde Jan 17 '18 at 20:26
6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I’m not sure about calling begin on iterator being wrong. May be you expected dereference first? \$\endgroup\$ – Incomputable Jan 18 '18 at 6:46
  • 1
    \$\begingroup\$ @Incomputable No, this is more of a general idea of iterator design. An iterator is basically a generalization of a pointer, and is usually obtained from a container by calling begin and end. Calling begin and end on the iterator itself doesn't make much sense from a design point of view, because you are not iterating over the iterator but the underlying container(s) instead. \$\endgroup\$ – Ben Steffan Jan 18 '18 at 14:36
  • \$\begingroup\$ Nice one! BTW, I am pretty sure that I can deal with basic C++ syntax, but would it be a good idea to read a standard draft as a "course book"? \$\endgroup\$ – coderodde Apr 29 '18 at 8:52
  • 1
    \$\begingroup\$ @coderodde If you have the dexterity to read a whole draft, then there is probably a lot you can learn from that. I certainly don't, but in any case, I keep a standard draft around just to look up certain things from time to time. It's probably the most invaluable resource for C++ programmers, once you have figured out how to read the somewhat convoluted "standardese". \$\endgroup\$ – Ben Steffan Apr 29 '18 at 8:56
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ BTW, if anyone is wondering - that initial "" is there just to help Emacs line up the rows of s. \$\endgroup\$ – Toby Speight Jan 18 '18 at 14:15

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.