I’ve been digging into ranges recently, and I’m finding them to be more than just a pair of iterators. In a series of posts, I’ll be expanding the notion of what a range is to cover some kinds of ranges not easily or efficiently expressible within the STL today: delimited ranges and infinite ranges. This post deals with the problems of representing delimited ranges with STL iterators.

Delimited Ranges

When groping about for concepts, it’s essential to have some concrete examples in mind. So when I say “delimited range,” think: null-terminated C-style string. The end of the sequence is not some known position; rather, it’s an unknown position at which we expect to find some delimiter, or more generally, at which some predicate becomes true. Another example, interestingly, is an istream range. The delimiter in that case is when the istream extractor fails. And yet, the standard has std::istream_iterator, so clearly it’s not impossible to shoehorn delimited ranges into the STL. I’ll show how, and explain why I use the term “shoehorn.”

Delimited Ranges in the STL

To prove my “shoehorn” allegation, here is a delimited range over a C-style string with fully STL-compliant iterators:

#include <cassert>
#include <iostream>
#include <boost/iterator/iterator_facade.hpp>

struct c_string_range
{
private:
    char const *str_;
public:
    using const_iterator = struct iterator
      : boost::iterator_facade<
            iterator
          , char const
          , std::forward_iterator_tag
        >
    {
    private:
        friend class boost::iterator_core_access;
        friend struct c_string_range;
        char const * str_;
        iterator(char const * str)
          : str_(str)
        {}
        bool equal(iterator that) const
        {
            return str_
                ? (that.str_ == str_ ||
                     (!that.str_ && !*str_))
                : (!that.str_ || !*that.str_);
        }
        void increment()
        {
            assert(str_ && *str_);
            ++str_;
        }
        char const& dereference() const
        {
            assert(str_ && *str_);
            return *str_;
        }
    public:
        iterator()
          : str_(nullptr)
        {}
    };
    c_string_range(char const * str)
      : str_(str)
    {
        assert(str_);
    }
    iterator begin() const
    {
        return iterator{str_};
    }
    iterator end() const
    {
        return iterator{};
    }
    explicit operator bool() const
    {
        return !!*str_;
    }
};

int main()
{
    for(char c : c_string_range("hello world!"))
        std::cout << c;
    std::cout << 'n';
}

The code traverses the sequence of characters without first computing its end. It does it by creating a dummy end iterator — a sentinel — such that any time a real iterator is compared to it, it checks to see if the real iterator points to the null terminator. All the gross logic is there in the c_string_range::iterator::equal member function. Nobody would call this code beautiful or elegant.

In the STL today, ranges are specified with two iterators: the begin and the end. For iterators like std::istream_iterator or c_string_range::iterator where an iterator can be a sentinel, it adds branches to the iterator equality test since you first have to determine if one or both of the iterators are sentinels. The expression a == b is evaluated according to the following truth table:

The above tests must be evaluated at runtime! There’s no way to know a priori whether an iterator is a real iterator or a dummy one. And all that checking is expensive. That’s what I mean when I say that delimited ranges can be “shoehorned” into the STL. It’s not a comfortable fit.

The Compiler Agrees

And when I say it’s an uncomfortable fit, that’s not just my opinion. I generated code for the following two functions:

int c_strlen(char const *sz)
{
    int i = 0;
    for(; *sz; ++sz)
        ++i;
    return i;
}

int range_strlen(
    c_string_range::iterator begin,
    c_string_range::iterator end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

The two functions do exactly the same thing, so in theory they should generate the same code. Our Spidey-sense should be tingling though after seeing the complicated conditional logic in c_string_range::iterator::equal. Indeed, the code they generate is far from comparable:

    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    xorl    %eax, %eax
    cmpb    $0, (%ecx)
    je  LBB1_3
    xorl    %eax, %eax
    .align  16, 0x90
LBB1_2:
    cmpb    $0, 1(%ecx,%eax)
    leal    1(%eax), %eax
    jne LBB1_2
LBB1_3:
    popl    %ebp
    ret
        

    pushl   %ebp
    movl    %esp, %ebp
    pushl   %esi
    leal    8(%ebp), %ecx
    movl    12(%ebp), %esi
    xorl    %eax, %eax
    testl   %esi, %esi
    movl    8(%ebp), %edx
    jne LBB2_4
    jmp LBB2_1
    .align  16, 0x90
LBB2_8:
    incl    %eax
    incl    %edx
    movl    %edx, (%ecx)
LBB2_4:
    testl   %edx, %edx
    jne LBB2_5
    cmpb    $0, (%esi)
    jne LBB2_8
    jmp LBB2_6
    .align  16, 0x90
LBB2_5:
    cmpl    %edx, %esi
    jne LBB2_8
    jmp LBB2_6
    .align  16, 0x90
LBB2_3:
    leal    1(%edx,%eax), %esi
    incl    %eax
    movl    %esi, (%ecx)
LBB2_1:
    movl    %edx, %esi
    addl    %eax, %esi
    je  LBB2_6
    cmpb    $0, (%esi)
    jne LBB2_3
LBB2_6:
    popl    %esi
    popl    %ebp
    ret
        

Oh my! Look at all those tests and branches! The above code was generated with clang 3.4 with -O3 -DNDEBUG. I should add that in practice, the compiler can often generate better code for range_strlen. If the compiler can infer statically that end is in fact a sentinel, and if the definition of range_strlen is available for inlining, then the compiler will generate better code. Near-optimal, in fact. But those are some big “If”s.

Besides, people generally don’t contort themselves by writing the c_string_range class when dealing with delimited strings. They call strlen and then some algorithm, traversing the range twice instead of once. But consider the case of the istream range. You can’t do the same trick with an input range because merely finding the end iterator consumes the range! Now we see why std::istream_iterator has a dummy sentinel. There’s simply no other way.

And as a final note, observe that c_string_range::iterator is a forward iterator, despite the fact that the raw char const* it wraps is random-access. That’s because the sentinel cannot be decremented. The range’s iterator can only be as powerful as its sentinel, which is pretty darn weak.

So What?

So we can’t efficiently use STL algorithms on C-style strings. Big deal, right? Actually, it is. It means that pretty much all generic string algorithms cannot be used on C-style strings. Look at all the juicy string algorithms in Boost.String_algo. The docs say this about the string types it supports:

“Definition: A string is a range of characters accessible in sequential ordered fashion. […] First requirement of string-type is that it must accessible using Boost.Range. This facility allows to access the elements inside the string in a uniform iterator-based fashion.”

No love for C-style strings from Boost.String_algo. And by the way, what do you think happens when you call std::regex_search with a C-style string? It first calls strlen! So even if your string is megabytes long and the match is at the very front, you first have to traverse the entire string just so that you know where the end is. Which is all totally pointless.

“You shouldn’t be using C-style strings anyway,” you say. But the problem is bigger than C-style string. All delimited ranges have this problem. Just within the standard library, there are istream_iterator, istreambuf_iterator, regex_iterator, and regex_token_iterator, all of which have dummy sentinels, all of which have been shoehorned in like I’ve shown above. I’m sure you can think of others.

Dietmar Kuehl alerted me to another interesting case. Have you ever wanted to call a generic algorithm but couldn’t because you wanted to break out of the loop early under some condition? Imagine that you could build a delimited range with that predicate and the end iterator. Now you can pass that range to an algorithm and it would stop either when the predicate becomes true or when you reach the end of the sequence. Voila! Standard algorithms just got a lot more useful. But this iterator type would have to be shoehorned in like the others, and you wouldn’t be able to call any algorithm that required more than forward iterators since you can’t decrement the sentinel.

Conclusion, For Now…

What’s my point? My point is this: the pair-of-iterators range abstraction that we are familiar with and that was designed to have low abstraction cost has real abstraction cost that cannot be avoided for delimited ranges. It also forces delimited ranges to model weaker concepts than they might otherwise, and makes their implementation awkward. What’s the solution? I do have a concrete suggestion, but we’re not there yet. First I want to talk about infinite ranges, and then we’ll see how delimited, infinite and pair-o’-iterators ranges can all be subsumed into a larger Range concept. Tune in next time…

Acknowledgements

I’d like to Dietmar Kuehl and Andrew Sutton for helping me formulate my range ideas and for reviewing this article.

x

x