How can I write an iterator wrapper that combines groups of sequential values from the underlying iterator?

Question

Consider the following sequence:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

I have input iterators for that sequence. I want to wrap those iterators on iterators that produce the following sequence instead:

(1,2), (3,4), (5,6), (7,8), (9,10)

If it's not clear, this sequence is a sequence of consecutive pairs of consecutive elements from the original one. While the original has 10 elements this one has 5: each one is obtained from two from the original sequence.

I'm using Boost's iterator_facade to implement this, and I have this wrong attempt at this:

    template <typename Iterator>
    struct pairing_iterator
    : boost::iterator_facade<
        pairing_iterator<Iterator>,
        std::array<typename std::iterator_traits<Iterator>::value_type, 2>,
        std::input_iterator_category
        // I should probably customize reference too, but it's not relevant
    > {
        pairing_iterator(Iterator it) : it(it) {
            increment(); // A
        }
        pairing_iterator::value_type dereference() const {
            return pair;
        }
        bool equal(pairing_iterator const& that) const {
            return it == that.it; // B
        }
        void increment() {
            pair = { { *it++, *it++ } };
        }
        Iterator it;
        pairing_iterator::value_type pair;
    };

One problem I'm facing is on the line marked with A: when the iterator passed in is an end iterator, this will result in incrementing it, which I can't do.

Another is on the line marked with B: I'm keeping the underlying iterator always ahead of the "current" pair, so if the iterator is at the last pair, the underlying iterator will be an end iterator, and thus compare true against an end pairing_iterator.

If the underlying iterator was a forward iterator, I could simply read the pair every time on dereferencing, and simply advance twice on increment. But with input iterators I can only read once.

Am I reinventing a wheel that already exists somewhere? I didn't find anything like this in Boost, which surprises me a bit. But I'd love to find a ready-made solution.

If this wheel is not out there already, how can I get it to actually roll?

Answer 1

I have two suggestions you already shot down in chat, one with a wierd but relatively safe limitation, and one with an ugly workaround for the limitation:

First idea is very simple, but requires exactly one dereference before each advance

template <typename Iterator>
struct pairing_iterator
: boost::iterator_facade<
    pairing_iterator<Iterator>,
    std::array<typename std::iterator_traits<Iterator>::value_type, 2>,
    std::input_iterator_category
    // I should probably customize reference too, but it's not relevant
> {
    pairing_iterator(Iterator it) : it(it) {
    }
    pairing_iterator::value_type dereference() const {
        auto t = *it++;
        return { { std::move(t), *it } };
    }
    bool equal(pairing_iterator const& that) const {
        return it == that.it;
    }
    void increment() {
        ++it;
    }
    Iterator it;
};

Second idea removes the exactly one dereference limitation, but is ugly and strange:

template <typename Iterator>
struct pairing_iterator
: boost::iterator_facade<
    pairing_iterator<Iterator>,
    std::array<typename std::iterator_traits<Iterator>::value_type, 2>,
    std::input_iterator_category
    // I should probably customize reference too, but it's not relevant
> {
    pairing_iterator(Iterator it) : it(it), dereferenced(false) {
    }
    pairing_iterator::value_type dereference() const {
        if (!dereferenced) {
            auto t = *it++;
            pair = { { std::move(t), *it } };
            dereferenced = true;
        }
        return pair;
    }
    bool equal(pairing_iterator const& that) const {
        return it == that.it;
    }
    void increment() {
        if (!dereferenced)
            dereference();
        dereferenced = false;
        ++it;
    }
    Iterator it;
    pairing_iterator::value_type pair;
    bool dereferenced;
};

I probably made several errors, but hopefully this is enough to portray the concepts.