Endless stream: stream a range and return default value if the range is exhausted

Question

Introduction:

Motivation

Sometimes there is a need to merge N > 1 ranges, and they don't have equal length, but there is a value which can be used in case the range is already exhausted. It is especially apparent in this question, in which most of the complexity comes from handling the nullness of either or both lists.

Solution

The solution constitutes a parody to std::optional's value_or(), but being the only option to retrieve a value. The idea is that users don't care if it is value from the range or it is default value. The stream will keep issuing values from range, until iterator hits end iterator, then it will return default value.

Problems by design

• Not modelled after standard library iterator

The problem lies in the ValueType. I don't want to apply greater constraints on it, other than being constructible and destructible. One would think that since there is next(), the value should copy/move constructible.

• No support for std::vector<bool>

std::vector<bool> for C++ is like older versions of IE for javascript. To return dereferenced value from iterator, the reference must be constructible from outside of std::vector<bool>, but that is not possible, so no, no support for std::vector<bool>.

• Not compatible with standard library at all

The reason is that I didn't see much usage and discussion about this, thus I decided to take opportunity to look at more usage examples, before making more concrete interface.

---

Code

#include <utility>
#include <iterator>

namespace shino {
template <typename InputIterator, 
          typename Sentinel = InputIterator,
          typename ValueType = typename std::iterator_traits<InputIterator>::value_type>
class endless_stream {
    InputIterator first;
    Sentinel last;
    ValueType default_value;
public:
    template <typename ... ArgTypes>
    endless_stream(InputIterator first, Sentinel last, ArgTypes&& ... args) :
        first(first),
        last(last),
        default_value(std::forward<ArgTypes>(args)...)
    {}

    ValueType& next() {
        if (first == last) {
            return default_value;
        } else {
            return *first++;
        }
    }

    bool has_next() const {
        return first != last;
    }

    InputIterator current_position() const {
        return first;
    }

    Sentinel end() const {
        return last;
    }
};
}

---

Usage example

As it was born from this question, I thought that it would be only natural to target the problem in the demo on Wandbox:

using iterator = std::list<int>::iterator;
void add_digit_lists(shino::endless_stream<iterator> left, 
                     shino::endless_stream<iterator> right,
                     std::list<int>& output) {
    bool has_carry = false;
    std::stack<int, std::vector<int>> prev_sums; //default is std::deque, not desired
    while (left.has_next() || right.has_next() || has_carry) {
        auto sum = left.next() + right.next() + has_carry;
        has_carry = false;
        if (sum > 9) {
            sum -= 10;
            has_carry = true;
        }
        prev_sums.push(sum);
    }

    while (not prev_sums.empty()) {
        output.push_back(prev_sums.top());
        prev_sums.pop();
    }
}

---

Concerns

• Non-descriptive name of the class

One would need to read the docs to figure out the exact behavior of the facility. Is there a better one?

• Is it C++14 compatible?

I tried to keep the code C++14 friendly, but still allow C++17 users to not type too much.

• Is implicit class template argument deduction from constructor sufficient?

I'm worried that in some cases compiler won't be able to deduce some of the types if they are not provided and C++17 mechanism is used.

Any other suggestions are welcome.

Answer 1

Design

• Iterator categories: You try to make sure to support InputIterator, but then expose current_position(). Since callers of that function can do anything with the returned iterator, including dereferencing and/or advancing it, for pure InputIterators this can invalidate first.

  To support this, you'd need at least ForwardIterators, since they have to provide a multipass guarantee. As a side effect, it would fix the std::vector<bool> issue, since its iterator isn't complying to one of the ForwardIterator requirements: reference must be equal to value_type& or const value_type&.

  Note: Just removing current_position wouldn't fix this, you'd also need to disable copying (same issue).

• endless_stream interface: This is neither a range (doesn't contain begin() and end() member functions) nor an iterator. Instead, it looks like some range-like construct (maybe inspired from other languages?). As mentioned, this doesn't fit in well with usual standard library constructs.

  Is there any specific reason this implementation doesn't orient itself on usual iterator semantics?

• Is there any specific reason for allowing output operations, i.e. allowing modification of default_value? I'd think it wouldn't be too much of a restriction to only return const ValueType& from next (basically adhering to const_iterator semantics).

Implementation

• Most member functions can be made conditionally noexcept.

• Some names are off:

  • has_next: I'd expect that one to always return true for an infinte range. From the implementation, I guess something like end_reached or fully_traversed was meant.

  • end suggests there should be an begin, which there isn't (usually expected iterator semantics). I'd suggest renaming to end_iterator (or maybe last_iterator), or removing this function entirely.

  • current_position: The position irks me a bit, as an iterator doesn't always conceptually represent a position (e.g. in a generator). current_iterator might be better.

  • endless_stream isn't a stream as it would usually be understood in C++. Maybe it could be reworked into an infinite_filler_range (when matching the range criteria)?

• There is no way to get the same value multiple times (since next always advances first, if possible). I'd suggest splitting this operation into two parts: advance() and value() (or current_value()).

• member initializer list: The general advice is to prefer aggregate initialization (using {}) over direct initialization (using ()), unless the latter is absolutely required. So, first and last can and should use aggregate initialization, and default_value can go either way (though I prefer direct initialization in this case).

Usage example

I don't think an implementation detail like endless_stream should leak into the interface. Instead, it might be better to create those endless_stream instances inside of add_digit_lists, taking either iterators or const std::list<int>& as parameters.

Also, the output is in normal order, whereas the inputs are reversed. This might not be intended.

Answer 2

Is it C++14 compatible? - it compiles successfully with -std=C++14, and I don't see anything else to give me concern in that respect.

---

I'm assuming it's intentional that default_value can be written; users need to be aware that writing to the iterator at this stage will affect all future values, which may be surprising.

It's not as easy as I'd like to make a const version: when I tried instantiating with a std::list::const_iterator, I got an error from return *first++;:

201933.cpp:24:30: error: binding reference of type ‘int&’ to ‘const int’ discards qualifiers
                 return *first++;
                              ^~

I didn't expect that, but a simple fix is:

    using reference = typename std::iterator_traits<InputIterator>::reference;

    reference next() {
        if (first == last) {
            return default_value;
        } else {
            return *first++;
        }
    }

However, this makes it no longer useful to specify a non-default ValueType template argument.

---

In the constructor, we can move the start and sentinel values:

    template <typename ... ArgTypes>
    endless_stream(InputIterator first, Sentinel last, ArgTypes&& ... args) :
        first{std::move(first)},
        last{std::move(last)},
        default_value(std::forward<ArgTypes>(args)...)
    {}

Although iterators are generally cheap to copy, this seems a good habit to have in general.

Answer 3

Perhaps it makes more sense to declare adaptor's interface more C++-, rather than Java-, idiomatic. I mean, define operator* and increment rather than next() etc. You'll need, however, to define a helper sentinel structure to compare against, to get rid of has_next().