The C++ input iterator pitfall · hmpc

15 min read Original article ↗

A tale of three functions

The year is 2005. As part of a parser utility library at your job, you write the following function to read a known-size list of formatted values from a stream into a vector:

template <typename T>
static std::vector<T> read_vector(std::istream& is, std::size_t size)
{
    std::vector<T> out;
    T val;

    while (size-- && is >> val) {
        out.push_back(val);
    }

    return out;
}

You also add a few unit tests as an afterthought:

TEST_CASE("Read whole input", "[read_vector]") {
    std::istringstream input{"26 42 73 0 1312"};
    REQUIRE(read_vector<int>(input, 5) == std::vector<int>{26, 42, 73, 0, 1312});
}

TEST_CASE("Read partial input", "[read_vector]") {
    std::istringstream input{"26 42 73"};
    REQUIRE(read_vector<int>(input, 2) == std::vector<int>{26, 42});
}

TEST_CASE("Read nothing", "[read_vector]") {
    std::istringstream input{"26"};
    REQUIRE(read_vector<int>(input, 0).empty());
}

TEST_CASE("Read two vectors", "[read_vector]") {
    std::istringstream input{"26 42 73 0 1312"};
    REQUIRE(read_vector<int>(input, 2) == std::vector<int>{26, 42});
    REQUIRE(read_vector<int>(input, 3) == std::vector<int>{73, 0, 1312});
}

You call it an early day and hurry home to get in costume before the Revenge of the Sith opening night. Last chance for these prequels to get good.

The year is 2015. After your team adopts C++11, one of your coworkers watches Sean Parent’s exhortation to exorcise raw loops from your codebase and eagerly rewrites the function:

template <typename T>
static auto read_vector(std::istream& is, std::size_t size) -> std::vector<T>
{
    std::vector<T> out;
    std::copy_n(std::istream_iterator<T>(is), size, std::back_inserter(out));
    return out;
}

Clean! Modern! Passing all unit tests! A flawless success. That is, until a downstream application starts crashing in production after receiving some malformed input. You reproduce the issue locally and quickly find the culprit: copy_n() will blindly read past the end of the stream, summoning the nasal demons of undefined behaviour. You revert the change and add a new unit test to cover this scenario, wondering what idiot forgot such an obvious test case but also resenting your colleague who couldn’t leave a perfectly good function alone. You add this to your growing “list of reasons to quit” file and move on to the next ticket.

The year is 2025. You get bitten by the ranges bug. You can now write the definitive version of this function in full C++23 glory:

template <typename T>
static auto read_vector(std::istream& is, std::size_t size) -> std::vector<T>
{
    return ranges::to<std::vector>(views::istream<T>(is) | views::take(size));
}

Isn’t it beautiful? With take_view you even avoid reading past the end of the input, unlike some of your careless colleagues who shall remain unnamed. Days like this you can almost ignore that niggling feeling that you should be learning Rust instead. You run your unit tests before pushing the change and…

-----------------------------------------------------------------
Read two vectors
-----------------------------------------------------------------
test_parsing.cpp:50
.................................................................

test_parsing.cpp:53: FAILED:
  REQUIRE( read_vector<int>(input, 3) == std::vector<int>{73, 0, 1312} )
with expansion:
  { 0, 1312 (0x520) }
  ==
  { 73, 0, 1312 (0x520) }

Wait, what? It looks like the first element of the second vector got discarded entirely. The code couldn’t be more self-explanatory; what’s going on here?

You have unwittingly tripped over a somewhat obscure but long-standing hazard of the standard library. Rooting out its origin will take us on a tour of C++ philosophy, the standardisation process, and implementation compromises, but first let’s get to the bottom of this behaviour. You may already suspect that our first call to read_vector() somehow consumed one too many values from the input. A quick peek at the istream_view specification tells us it reads from the underlying stream in the begin() method and whenever its iterator is incremented; counted_iterator, used by take_view, increments its base iterator whenever it itself is incremented. When we reach the end of this counted range, then, the istream_view holds the next value to process, if any, which is discarded once the function returns and the view is destroyed.

Who’s at fault here: the specification or our own expectations? And how can we fix our code?

What’s in a range?

We’ll start by considering counted_iterator. Should it skip incrementing its base iterator when the count reaches zero?

This was the idea behind P2406, originally proposed in 2021 to change the specification of counted_iterator to address, among others, precisely the scenario where istream_view is chained with take_view. It appears to have been dropped in 2023 after Tim Song wrote a counter-proposal defending the current behaviour as the more idiomatic one. The crux of his argument was that C++ ranges are, and have always been, half-open; changing counted_iterator to support closed ranges would be unintuitive and cause more problems than it would solve. He also wrote of our motivating example:

Here, the actual problem is that istream_view expects all access to the stream to happen through its iterators. Nothing is actually lost if its iterator is consistently used. In the example above, we can extract the istream_view iterator out of the past-the-end counted_iterator using the allegedly useless base() function:

    auto iss = std::istringstream("0 1 2");
    auto tv = rn::istream_view<int>(iss)
                  | rv::take(1);
    auto it = tv.begin();
    for(; it != tv.end(); ++it)
        std::cout << *it << '\n';
    auto next = std::move(it).base();
    auto i = *next;
    assert(i == 1); // OK

I find this fix something of a kludge, directly manipulating the range iterators and cutting across abstraction layers. It also ignores other cases where, from a user’s perspective, reading more values than expected from the stream is objectively wrong or has bad performance:

auto input = std::ifstream{path_to_pipe};
const auto batch = read_vector(input, 5);
// hangs until it can read *six* values (or fails) or the pipe closes

Using istream_view consistently (as opposed to carrying the iterator around like it’s 1998) would, alas, also not save us from dropping values:

template <typename T>
static auto
read_vector(ranges::istream_view<T>& rg, std::size_t size) -> std::vector<T>
{
    return ranges::to<std::vector>(ranges::ref_view{rg} | views::take(size));
}

auto rg = views::istream(input);
const auto first = read_vector(rg, 2);
const auto second = read_vector(rg, 3);

The reason this doesn’t work can be understood from our earlier explanation: since istream_view::begin() consumes the next value in the stream, iterating the range again discards the value currently stored in the view just as if we had constructed a new one. Time to take a closer look at istream_view.

Leaky standardisation

The addition of istream_view to the standard library was originally proposed in 2018, back in the heady days of the Ranges TS, with P1035. The initial revision made it clear that the proposed istream_range adaptor was an abstraction over the venerable istream_iterator for a more civilised era, and as such it mimicked its behaviour closely: the initial value was consumed from the stream in the adaptor constructor1, as well as on each iterator increment. This was also the behaviour of the equivalent types in Boost.Range and Eric Niebler’s range-v3. In fact, as early as 2013 Eric explained how this approach avoided otherwise surprising user-visible consequences, much as our last example illustrates2.

By the time P1035R1 rolled around a few months later, however, and despite the addition of a shout-out to range-v3, istream_view was irrevocably altered: the first value was now consumed by begin(), rather than the constructor, rendering our potential solution null and void. It’s unclear where this change came from; the fact that neither range-v3 nor Boost.Range were ever modified to match it seems to indicate it was not widely discussed. This issue also shows that Christopher di Bella, the original author of P1035, was aware of the range-v3 behaviour. The intention may have been to postpone access to the stream until the view was iterated so the constructor would not block execution, for cases where the two are done in different parts of the program. Whatever the reason, we are now unfortunately saddled with a stateful range adaptor which cannot easily be reused.3

The std::copy_n() exception

But wait—what about the overly-optimistic implementation of read_vector() we had to revert, which used istream_iterator:

std::copy_n(std::istream_iterator<T>{is}, size, std::back_inserter(out));

Sure, it failed when there were fewer values than expected, but it did pass our test case with sequential calls despite the fact that the value consumed by the last increment should’ve been discarded. What gives?

It turns out people have, perhaps not surprisingly, been running into (and getting frustrated by) this scenario ever since copy_n() was introduced in C++11. The original libc++ code, the trivial one-liner you might expect, was changed in 2011 to accommodate copies from istream_iterator by skipping the final increment; libstdc++ followed not long after, apparently without debate. Because the standard specifies the exact number of assignments performed by copy_n() but not the number of iterator increments, this is fair game for the implementation.

When the issue was formally raised a few years later, LEWG appears to have thrown up its hands in disgust. It’s hard to blame the library authors though: because copy_n() returns the next output iterator but not the input one, there is no good way to continue from where it left off. ranges::copy_n(), on the other hand, does return the final value of the input iterator, and both libc++ and libstdc++ increment it N times.

Trapdoor iterators

Here’s another situation where we run into our original problem in a different guise. Say we have a non-blocking concurrent queue, perhaps something like:

template <typename T>
class concurrent_queue
{
public:
    void put(T&&);
    std::optional<T> get();

    // ...
};

We can design an adaptor over this container similar to istream_view: store the last consumed value in the adaptor, use a sentinel for the end of the range, and read the first value in the constructor4. If we’re using this queue to distribute work over multiple threads, for example, and each thread processes items in batches, we might naturally write (calling our adaptor concurrent_view):

template <typename T>
void worker(concurrent_queue<T>& queue)
{
    auto items = concurrent_view{queue};

    while (true) {
        ranges::for_each(items | views::take(batch_size), process_item);

        // ...
    }
}

There is a subtle issue here though. After processing a batch of items, the thread will presumably go off to do something else. Meanwhile, any item it might’ve pulled from the queue in the last for_each increment will languish inside the concurrent_view, unavailable to any other worker, to be processed when the event loop restarts. Not great for our latency tails! And that’s if the thread doesn’t terminate in the meantime, at which point the item would simply be lost in the ether.

But maybe you don’t particularly care about this; after all, developers writing low-latency code are already used to some loss of ergonomics in pursuit of performance. Can we just agree that reusing the adaptor and reading the initial value in its constructor would solve all of our problems?

Not so fast. Let’s look at a different scenario involving our modified istream_view with a no-op begin(), where we repeatedly read lists of integers of bounded size followed by an optional boolean flag (this example is somewhat contorted, but it demonstrates the more general point):

auto values = views::istream<int>(stream);

stream.setf(std::ios_base::boolalpha); // don't parse integers as booleans

while (const auto vs = ranges::to<std::vector>(values | views::take(max_size));
       !vs.empty()) {
    bool flag = false;
    if (!(stream >> flag)) stream.clear();

    // ...
}

Does this work as expected? No integers are discarded, and we are careful to handle the case where the flag is absent by clearing the stream’s failbit before continuing. However, the curse of the final increment strikes again: if the flag is present, the last read from the counted range will leave the stream in failed state (since it expects an integer) and operator>> will refuse to read from it. What’s worse, because we only read from the stream when incrementing the iterator, we’ll also process the wrong values in the next loop even if we clear the stream state.

The shared characteristic of istream_view and concurrent_view is that advancing the range iterator requires reading from the underlying sequence5, and reading it mutates its state. This is a common property of weakly-incrementable types, particularly input iterators, which are suitable only for single-pass algorithms because their increment operators are not necessarily equality-preserving. When combined with any adaptor that might “truncate” the range rather than iterating it through its end (such as take_view, take_while_view, or zip), we always risk running into a situation of the sort we have described.

A new hope

Let’s return to Tim Song’s critique of the proposal for lazy_counted_iterator and associated range adaptors. Although I have some quibbles with his overall argument, the idea of a generic close_view adaptor from closed to half-open ranges is promising. For example, some ranges could easily provide an ending() iterator method relying on internal details—such as the current count of a take_view or the value of a iota_view—to know whether the next increment might be past the end, and the adaptor iterator would only forward increments if this method returned false. Our code might then look something like:

for (auto value : views::istream<int>(input) | views::take(5) | views::close) {
    // ...
}

This would elegantly solve our original use case! It would even satisfyingly resolve our constructor-or-begin() conundrum to read the first value from an input range: whether the adaptor is reused or not, the proper place to initialise the value would now be in the begin() method.

Unfortunately, this is still not a general solution for input ranges; in fact, such a solution cannot exist. To see why, consider the following example that zips together multiple ranges and an index:

static auto enumerate_up_to(std::size_t n, auto&&... rgs)
{
    return views::zip(views::iota(0, n), rgs...) | views::close;
}

for (auto [i, x, s] : enumerate_up_to(10,
                                      views::istream<int>(a),
                                      views::istream<std::string>(b))) {
    // ...
}

How many values will we read from each stream, if the zip_view iterator is endowed with a brand-new ending() method capable of telling close_view when the iota_view range is about to run past its end? The answer, of course, is that it depends: if we have fewer than ten values in one of the streams, the closed-range adaptor won’t be able to prevent incrementing the iterators for all ranges, reading an extra value from the longer stream and leaving us right back where we started.6 There is no way to work around this, since it’s the same fundamental limitation of input ranges as we discussed in the previous section.

Embracing state

Let’s take stock of the situation. Our original problem was that, when reading from an input stream multiple times through a range, we lost the last value implicitly pulled from the stream, either because we destroyed the view or, if we reused it, because its begin() method immediately reads the next value. We also saw that even with a reusable view that consumes the stream in its constructor we can run into subtle performance and correctness issues, in addition to potentially blocking execution unexpectedly. Finally, it’s now clear that we can never fully avoid reading past the end of a truncated (counted or otherwise) input range in a general scenario.

If we are willing to let go of the requirement to skip the last increment, focusing only on preventing discarded values with reasonable semantics, we can get the best of both remaining worlds: a stateful range adaptor that keeps track of the last iterator value we’ve seen, initialised in begin() if one doesn’t exist, updated on increment, and cleared when past the end of the adapted range. This makes begin() idempotent between increments but capable of handling transient errors in underlying streams, while ensuring the user always sees every retrieved value and program execution does not block on construction. Here’s a bare-bones implementation:

template <ranges::view V> requires ranges::input_range<V>
class input_cache_view : public ranges::view_interface<input_cache_view<V>>
{
    V base_;
    std::optional<ranges::iterator_t<V>> cur_{};

public:
    class iterator
    {
        input_cache_view<V>* parent_;

    public:
        using difference_type = std::ptrdiff_t;
        using value_type = ranges::range_value_t<V>;

        constexpr explicit iterator(input_cache_view<V>& parent)
        : parent_{std::addressof(parent)} {}

        iterator& operator++()
        {
            if (++*parent_->cur_ == parent_->base_.end()) parent_->cur_.reset();
            return *this;
        }

        void operator++(int) { ++*this; }
        value_type& operator*() const { return **parent_->cur_; }

        friend bool operator==(const iterator& it, std::default_sentinel_t)
        { return !it.parent_->cur_; }
    };

    constexpr explicit input_cache_view(V view) : base_{view} {}

    constexpr auto begin()
    { if (!cur_) cur_ = base_.begin(); return iterator{*this}; }

    constexpr std::default_sentinel_t end() const noexcept
    { return std::default_sentinel; }
};

And here’s what our earlier parsing example would look like with this new adaptor:

auto values = views::istream<int>(stream) | input_cache;

stream.setf(std::ios_base::boolalpha); // don't parse integers as booleans

while (const auto vs = ranges::to<std::vector>(values | views::take(max_size));
       !vs.empty()) {
    stream.clear();

    bool flag = false;
    if (!(stream >> flag)) stream.clear();

    // ...
}

Notice that we still need to clear failbit before reading the flag, but unlike last time the adaptor happily chugs along afterwards. The extra check on increment is essentially free since it gets rolled up with the loop condition. And unlike lazy_take_view, this solution can also handle adaptors like take_while_view:

auto values = views::istream<int>(stream) | input_cache;

for (auto small : values | views::take_while([](auto x) { return x < 100; })) {
    // handle initial small values
}

for (auto large : values) {
    // handle the rest
}

Conclusion

I like the idea of a close_view, despite its shortcomings, but I have some doubts about whether such a proposal (in whatever form) would ever be accepted by LEWG, given the somewhat niche purpose and potentially complex edge cases. Then again, what is C++ for if not to come up with ever more baroque and destructive footguns?

In our current world, however, and with input ranges in general, we must pick our poison. If avoiding that last increment is critical to you, you can write your own lazy_take_view; otherwise, if you just want less error-prone semantics, you can wrap your input range in our input cache adaptor or, if that doesn’t work for whatever reason, maybe a very basic eager constructor adaptor. You can also use functions like ranges::copy which return the next input iterator, at the cost of having to manually build sub-ranges for subsequent operations.

Or, of course, you can swallow your pride, accept that ranges might not be the best hammer for every nail, and welcome back the humble while loop.