Range Concepts, Part 3 of 4: Introducing Iterables

In the last two blog posts, I describes the challenges I’ve encountered while building a next-generation range library. In this post, I’ll sketch for you my proposed solution: refinements of the range concepts that allow delimited, infinite, and pair-o’-iterator-style ranges to fit comfortably within the concept hierarchy without loss of performance or expressive power and with increased safety. I’ve built a range library around these concepts that subsumes and extends all of the C++98 STL algorithms and the Boost.Range adaptors, so I can say with confidence that these concepts lead to a useful and consistent generic range library.

Recap

At the end of my last post, I summed up the issues of pair-o’-iterators (PoI)-style ranges as follows:

  • Delimited and infinite ranges generate poor code
  • These range types are sometimes forced to model weaker concepts than they might otherwise
  • Use of infinite ranges with some algorithms is unsafe
  • Delimited and infinite ranges are harder to implement than they need to be
  • Ranges that are possibly infinite can overflow their difference_type

The first issue is particularly hard to swallow, so it’s where I’ll focus my energy in this post.

The Range Concept

Before I go any further, let’s be a little more formal about what “range” means. The C++ standard uses the word “range” all over the place without formally defining it. But we can infer from the section [iterator.range] that a range is something on which you can call begin and end to get back a pair of iterators where the end is reachable from begin. In the language of the current “Concepts Lite” proposal, we can formalize the Range concept as follows:

using std::begin;
using std::end;

template<typename T>
using Iterator_type =
    decltype(begin(std::declval<T>()));

template<typename T>
concept bool Range =
    requires(T range) {
        { begin(range) } -> Iterator_type<T>;
        { end(range) }  -> Iterator_type<T>;
        requires Iterator<Iterator_type<T>>;
    };

This basically says that you can call begin and end on a range and that you get back iterators. There are refinements of the Range concept (not shown) called InputRange, ForwardRange, etc. that merely require more of their iterators. The refinement hierarchy is shown below. It’s fairly straightforward. (The above syntax was given to me by Andrew Sutton, the author of the Concepts Lite proposal, shortly after the February 2014 standardization committee meeting, so it’s guaranteed fresh. He warns me that the syntax may yet change in the future.)

Range Concept Hierarchy

Range Concept Hierarchy

These concepts are the foundation of the Boost.Range library.

Problem 1: Poor Code Generation

If you recall, to implement delimited and infinite ranges as a pair of iterators, the end iterator must be some sort of sentinel iterator. A sentinel represents a conceptual position rather than a physical one. You can still think of it as the last-plus-one position, the only difference is that you won’t know the physical position until you reach it. Since the sentinel has the same type as the iterator, it requires a runtime test to determine whether a given iterator is the sentinel or not. This leads to slow iterator comparisons and awkward range implementations.

The Iterable Concept

Think of the things you do with iterators. You increment them, you dereference them, and you compare them for equality, right? What can you do with a sentinel iterator? Not much. You can’t change its position since it represents a conceptual position, not a physical one. You can’t dereference them, because they always stand in for the last-plus-one position, which is not dereferencable. But you can compare it to an iterator. In other words, a sentinel is a very weak iterator.

The trouble with delimited and infinite ranges comes from trying to make a sentinel iterator into a regular iterator. It just isn’t one, and making it so causes problems. So just let it be. In other words:

Let range sentinels have different types than their ranges’ iterators.

The Range concept requires the begin and end iterator have the same type. If I allow the types to differ, I’m talking about something weaker than Range: the Iterable concept. Iterables are just like Ranges except the begin and end types differ. Here’s the Iterable concept:

template<typename T>
using Sentinel_type =
    decltype(end(std::declval<T>()));

template<typename T>
concept bool Iterable =
    requires(T range) {
        { begin(range) } -> Iterator_type<T>;
        { end(range) }  -> Sentinel_type<T>;
        requires Iterator<Iterator_type<T>>;
        requires EqualityComparable<
            Iterator_type<T>, Sentinel_type<T>>;
    };

template<typename T>
concept bool Range =
    Iteratable<T> &&
    Same<Iterator_type<T>, Sentinel_type<T>>;

All Ranges are Iterables trivially. That is, the Range concept refines Iterable by adding one additional constraint: that begin and end have the same type. In fact, the Iterable concept hierarchy parallels the Range hierarchy nicely:

Iterable Concept Hierarchy

Iterable Concept Hierarchy

This is what the hierarchy looks like when considering Ranges, Iterables, and Iterators, but it’s not necessarily the way we would actually define these concepts in our code. Notice that “rangeyness” — that is, whether begin and end have the same type — is orthogonal to the strength of the begin iterator. When we want to require that a type model RandomAccessRange, we can say requires RandomAccessIterable<T> && Range<T> and do away with the other Range concepts entirely.

The difference between, say, a BidirectionalIterable and a ForwardIterable is in the concept modeled by the Iterable’s begin iterator. If the EqualityComparable constraint in the Iterable concept gives you pause, read on. I justify it below.

Iterables and the STL Algorithms

“But wait,” you say. “No STL algorithms will work with Iterables because they expect begin and end to have the same type!” That’s sadly true. So I went through all the STL algorithm to see which could be re-implemented in terms of the weaker concept. Take std::find for example:

template<class InputIterator, class Value>
InputIterator
find(InputIterator first, InputIterator last,
     Value const & value)
{
    for (; first != last; ++first)
        if (*first == value)
            break;
    return first;
}

Today, std::find requires Ranges. But notice how this algorithm never tries to change the position of the end iterator. The find algorithm can very easily be changed to work with Iterables instead of Ranges:

template<class InputIterator, class Sentinel, class Value>
InputIterator
find(InputIterator first, Sentinel last,
     Value const & value)
{
    for (; first != last; ++first)
        if (*first == value)
            break;
    return first;
}

That’s it. The change is so minor, you might even have a hard time spotting it!

So, which C++98 algorithms can be made to work with Iterables instead of Ranges? Nearly all of them, it turns out. In fact, it’s easier to list the ones that don’t work with Iterables. They are:

  • copy_backward
  • The heap algorithms (push_heap, pop_heap, make_heap, sort_heap)
  • inplace_merge
  • nth_element
  • partial_sort and partial_sort_copy
  • next_permutation and prev_permutation
  • random_shuffle
  • reverse and reverse_copy
  • sort and stable_sort
  • stable_partition

For the 50 or so others, getting them to work with Iterables is mostly a mechanical source code transformation. By defining the Iterable concept such that Range refines it, any algorithm implemented in terms of Iterable automatically works with Ranges, which lets us reuse code. And that’s super important. There’s too much code written for iterators to think about picking an incompatible abstraction now.

The Proof is in the Perf

But what do we gain? Let’s revisit our old friend, the C-style null-terminated string. In a previous post, I defined a c_string_range class and found that iterating through the characters generated very bad code. Let’s try again, this time using my range_facade helper to build an Iterable instead of a Range. The code looks like this:

using namespace ranges;
struct c_string_iterable
  : range_facade<c_string_iterable>
{
private:
    friend range_core_access;
    char const *sz_;
    char const & current() const { return *sz_; }
    void next() { ++sz_; }
    bool done() const { return *sz_ == 0; }
    bool equal(c_string_iterable const &that) const
    { return sz_ == that.sz_; }
public:
    c_string_iterable(char const *sz)
        : sz_(sz) {}
};

The first thing we notice is that this code is a lot simpler than the old c_string_range class. The range_facade helper does all the heavy lifting here. The iterator and the sentinel are all implemented in terms of the primitives shown. Gone is the awkward and complicated equality comparison. But how does it perform? To test it, I generated the optimized assembly for the following two functions, one which used the old c_string_range class, and one that uses the new c_string_iterable:

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

// Iterable-based
int iterable_strlen(
    range_iterator_t<c_string_iterable> begin,
    range_sentinel_t<c_string_iterable> end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

Even if you don’t know much about assembly code, the following should speak to you:

Range-based strlen Iterable-based strlen
    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
        
    pushl    %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    xorl    %eax, %eax
    cmpb    $0, (%ecx)
    je    LBB1_4
    leal    8(%ebp), %edx
    .align    16, 0x90
LBB1_2:
    cmpb    $0, 1(%ecx,%eax)
    leal    1(%eax), %eax
    jne    LBB1_2
    addl    %eax, %ecx
    movl    %ecx, (%edx)
LBB1_4:
    popl    %ebp
    ret
        

The code generated from the Iterable algorithm is far superior to that generated from the pair of iterators. In fact, if you check it against the assembly for the raw C-style iteration, you’ll find it’s almost identical.

Iterators, Sentinels, and Equality

But what does it mean to compare two objects of different types for equality? Or put in more formal terms, can the requirement that an Iterable’s iterator and sentinel satisfy the cross-type EqualityComparable concept be satisfied? I believe the answer is yes.

Some background for the uninitiated: N3351 defines precisely when and how cross-type equality comparisons are meaningful. It’s not enough for the syntax “x==y” to be valid and yield a bool. If x and y have different types, the types of both x and y must themselves be EqualityComparable, and there must be a common type to which they can both be converted, and that type must also be EqualityComparable. Think of comparing a char with a short. It works because both char and short are EqualityComparable, and because they can both be converted to an int which is also EqualityComparable.

Iterators are comparable, and sentinels are trivially comparable (they always compare equal). The tricky part is the common type requirement. Logically, every iterator and sentinel has a common type that can be constructed as follows: assume the existence of a new iterator type I that is a tagged union that contains either an iterator or a sentinel. When an iterator is compared to a sentinel, it behaves semantically as if both the iterator and the sentinel were first converted to two objects of type I — call them lhs and rhs — and then compared according to the following truth table:

lhs is sentinel ? rhs is sentinel ? lhs == rhs ?
true true true
true false done(rhs.iter)
false true done(lhs.iter)
false false lhs.iter == rhs.iter

If you’ve been following this series, the above truth table should ring a bell. It’s pretty much exactly the table we got when figuring out how c_string_range::iterator‘s equality operator should behave, and that’s no coincidence; that was a special case of this more general construction. This construction validates an intuition you might have after seeing the two classes I wrote, c_string_range and c_string_iterable. One is a pair of iterators, the other an iterator/sentinel pair, but they implement equivalent procedures for computing equality. We know they’re the same, and we feel in our guts we could build an equivalent Range out of every Iterable if we’re willing to sacrifice some performance. And now we know that’s true.

Allowing direct comparison of iterators and sentinels lets us use the C++ type system to optimize a large category of iterations by eliminating branches from the equality comparison operator.

Objections

The idea of allowing begin and end iterators to have different types is not new, and it’s not mine. (In fact, many of you who have commented on the first two posts, either here or on reddit.com, have made precisely this suggestion.) I first heard about it from Dave Abrahams years ago. More recently, Dietmar Kuehl floated a similar idea on the Ranges mailing list. Sean Parent raised the following objection in a follow-up message:

Again, I think this is putting too much on iterators. Algorithms that act with a sentinel termination or with a count are different beasts. See copy_n() and copy_sentinel()

http://stlab.adobe.com/copy_8hpp.html

For ranges – I certainly thing you should be able to construct a range with:

  1. a pair of iterators
  2. an iterator and a count
  3. an iterator and a sentinel value

In which case, copy(r, out) can dispatch to the correct algorithm.

If I’m understanding Sean correctly, he is arguing for 3 parallel range concept hierarchies: IteratorRange, CountedRange, and SentinelRange. These hierarchies would have no refinement relationships between them. The copy algorithm would have three underlying implementations, one for each concept hierarchy. There are 50 some odd algorithms that would need to be triplicated in this way. That’s a lot of code duplication.

In fact, it’s worse than that because some algorithms are specialized to take advantage of more refined concepts. For instance, in libc++, the rotate algorithm dispatches to one of three implementations depending on whether you pass it forward, bidirectional, or random-access iterators. To accommodate Iterator, Counted, and SentinelRanges, we would need a grand total of 9 rotate algorithm implementations! I have nothing but respect for Sean Parent, but that’s madness. With the Iterable concept, Sean’s three separate hierarchies get unified under a single syntax that lets us write general algorithms while preserving performance characteristics. In other words, with Iterables, 3 implementations of rotate suffice.

(Incidentally, the Iterable concept can neatly accommodate counted ranges. If you want to turn an iterator and a count into an Iterable, you can bundle the iterator and the count together into a new iterator type that decrements the count whenever the iterator is incremented. When comparing the iterator to the sentinel, it merely checks whether the count is zero.)

Summary, For Now…

At the beginning of this post I summarized some of the problems with pair-o’-iterator ranges. I showed how a new concept, Iterable, addresses the performance issues, and touched a bit on the issue of range implementation complexity. I haven’t yet covered how the Iterable concept helps with infinite ranges, or how to address the safety issue of passing an infinite range to an algorithm that can’t handle them. This post has run a bit long, so I’ll stop for now and address the other issues in the fourth and final installment. Hopefully, this has given you a few things to think about until then.

If you want to download and play with the code, you can find it in the range-v3 repository on github. I’m happy to take suggestions and bug reports, but please don’t use this code for anything real. It’s untested and still evolving.

Acknowledgements

I’d like to thank Andrew Sutton for helping with the Concept Lite syntax and also for explaining the requirements of the cross-type EqualityComparable concept and generally improving and formalizing many of the ideas presented here. The article is immeasurably better for his many contributions.

x
x

50 Replies to “Range Concepts, Part 3 of 4: Introducing Iterables”

    • Because I want to leverage the vast amount of iterator-based code already written, and because in my experience, I don’t find that ranges as primitives solve all the problems that iterators do.

      • It’s basically possible to have iterators on top of a range as a compatibility layer. But I haven’t explored any non-trivial cases yet.

        Could you elaborate on the limitations of ranges you experienced, i.e. give some examples?
        Andrei mentions some in the “Weaknesses” section of his article as well but comes to the conclusion that you don’t really lose much. And considering how powerful D’s ranges and algorithms are by now I think that’s true.

        • A few reasons, two practical, one aesthetic, and one political. First, I don’t believe it’s possible in general to implement iterators on top of ranges since, as Andrei himself says in the article you reference, iterators are a lower-level abstraction.

          Next, Andrei talks about the return type of find. In the STL, it returns the position of the found element. With that position, you can make any range you want. In D, find has to return a range, since positions don’t exist. Which range? It picks one for you — the subrange starting at the found element. If you’re interested in a different subrange, you’re out of luck. D provides Until — a lazy range adapter — if you’re interested in the front subrange. Andrei touts this solution, but to me it demonstrates the weakness of ranges. Until and find do essentially the same thing. They both exist solely because find can’t return a position.

          Also, Until is unsatisfying. I couldn’t find its category described in the docs, but since it’s lazy I’m assuming it’s Forward. If Until is adapting a RandomAccess range, why should I be satisfied with getting only a Forward range back from Until? What if I want to sort the subrange specified by Until?

          With the STL, it’s easy: the is one find algorithm, and if I pass it random-access iterators, I get a random-access iterator back, and I can build a random-access range from it and sort if I want to.

          This is just a representative example, of course. Many algorithms return positions. These all suffer the same problem as find. One algorithm implementation isn’t sufficient; you need bunches of differently-named algorithms that differ only in the subrange they return.

          Or, you have an algorithm like D’s findSplit, that can’t make up its mind and returns three subranges. That’s not necessary if you have a way to represent position.

          For the aesthetic argument, I just find it easier to think of algorithms that identify positions in a sequence rather than subsequences. When I’m looking for a needle in a haystack, I want the needle, not the part of the haystack with the needle in the front. This is just my personal taste.

          As for the political argument: I want ranges in the standard. There is just no way the C++ standardization committee would ever consider a range-only interface. I think this is for very good reasons (see above), but also because iterators are the dominant paradigm, and there is just too much code out there to even think about switching to a different abstraction now.

          I firmly believe that the concepts I’ve presented in this blog post are the best way to get ranges into a future C++ standard. With the proper library support, the vast majority of users of the STL will have all the convenience of a range-based interface with none of the shortcomings. We don’t need to abandon iterators.

          • I was just going to write similar questions. My two cents, without disregarding your fantastic work, which I see as a big improvement already.

            1.- ranges, IMHO, shouldn´t be based on underlying old or new iterators at all, just independent from them, because having to implement iterators in the first place is really difficult. And this is coming from someone using c++ a few years already (since 2002).

            2.- Finding a simpler abstraction for positions could be good (maybe?). I think that these positions should be easier, way easier (I don´t know how, or if possible) to define.
            I like, for example, the solution that was given with polymorphic memory resources: Now mere humans can use it! Just implement do_allocate and do_deallocate. It´s not the same, but you can see the reference here: http://isocpp.org/files/papers/N3916.pdf. They provided a new abstraction and adaptors for making it compatible with allocators and for making allocators compatible with memory resources.

            Defining new iterators is a HELL. I think the 2 main points for ranges, should be:

            Make usage simpler. If we infect ranges with iterators, this goal cannot be met.
            Provide a compatibility layer (adaptors) for iterators-range interoperability. Maybe this layer should be optional and the user shouldn´t provide it always.

            I find way more hygienic to write this if I want to write a range:

            template <class T>
            struct InputRange {
            bool empty() const;
            T & font() const;
            void popFront();
            };

            Than to write something similar to c_string_iterable, which is an improvement, but still difficult, since you are using a c_range_facade for adaptation. This adaptation should be optional, but ranges still independent from iterators. I don´t know if this is already possible in your implementation, maybe I got it wrong.

            P.S.: You have given way more thought to this problem than me, so don´t kill me when replying 🙂 But the point for me is that a range implementation where we need iterators (old iterators) is going to expose iterators with all its complexities. With an optional adaptation layer, I think it would be a big win in the area of teaching and learning C++, which is another point where the committee makes emphasis.

          • (Meta: this theme’s nested comments really suck. Sorry.)

            I like, for example, the solution that was given with polymorphic memory resources: Now mere humans can use it!

            Don’t be so sure! I was in the room when polymorphic allocators were voted into the library fundamentals TS. There’s a bit of a gotcha. The polymorphic_allocator adaptor you’re referring to holds a raw pointer to a memory_resource. What keeps the pointer from dangling? You do! When I raised an objection, the response was, “People who write allocators are smart enough.” I don’t know whether to laugh or cry.

            Back to your suggestion. Yes, we can let people write D-style input ranges and provide a separate adaptor to turn it into an Iterable or a Range. I personally don’t see the advantage over using range_facade to just build an Iterable or Range directly, without the need for an adaptor. I particularly don’t grok this:

            having to implement iterators in the first place is really difficult

            … when if you look at the implementation of c_range_iterable, you don’t have to implement an iterator — the range facade does it for you. In fact, comparing your InputRange to my c_string_iterable is unfair because c_string_iterable is a Forward iterable, so it’s more powerful. If you renamed dereference to front, done to empty, increment to popFront and (necessary for a Forward D-range) save to equal, you’ll see that these two are nearly identical. I don’t see how forcing people to use a separate adaptor every time they want to call an algorithm is better than typing : range_facade<c_string_iterable> in one place.

          • Addendum: I’ve change the names of the range_facade primitives. Instead of dereference, increment, and decrement (which have a decidedly iterator-ish flavor), they are now called current, next, and prev. Maybe this helps?

          • Thank you for your detailed comment, very interesting!
            I know your quest is very hard since you have to please the committee and come up with a solution that works for every corner case and with all the legacy code. Hope you are successful with the standardization, good luck! 🙂

            My goal is simpler, I just have the feeling it should be possible to come up with some wrapper along the lines of https://gist.github.com/Trass3r/8774345 that allows you to use D-style ranges with the C++11 range-based for and maybe even existing algorithms. Doesn’t matter to me if it is ugly inside or if it doesn’t work for some corner cases, as long as it’s easy to use like just inheriting from another class in this case.

            Now I also wonder if a hybrid solution is possible so find still returns something representing a position, not for iteration, just for constructing ranges.

          • Although, I do agree we should not get rid of iterators(we always need something to represent position), It does make sense to return a range from find rather than an iterator. This is because if find doesn’t find the element it will return a special value(the end iterator). Having these two values together in a range, makes it easy to check if the value is found by checking if the range is empty:

            if (r | find("x") | empty())
            {
            // Do some stuff
            }

            Plus, if you want to retrieve the value or a default, you could have something like this:

            auto x = r | find("x") | front_or(0);

            Futhermore these same constructs can apply to optional as well, since optional can(and should) be adapted to a range. However, find should return a pair of iterators rather than an optional since sometimes you may want the postion in the range(aka iterator) not just the value.

  1. @Trassr3 Your iterator::operator!= is rather fragile as it is not symmetric in its arguments. If a user ever writes for (auto b = rng.begin(), e = rng.end(); e != b; ++b) instead of the usual b != e; then you have a nullptr dereference.

    • Yeah I know it’s just something I quickly hacked together as a proof-of-concept. Feel free to point out more problems that need to be solved 🙂

      • And for a quick hack to get something that works with range-for, it’s fine. But when you change it to fix the bug Rein noticed (by adding conditional checks before calling empty on one or the other iterator) and look at the generated code, you’ll see what I’m talking about: poor code generation. To fix that problem, you’ll probably end up reaching the same conclusion I’ve reached: sentinels should have different types than iterators for optimal code gen. And for a wrapper that works with algorithms, you’ll have to solve the whole bag of issues, along with how to represent position; something that, if it can be done efficiently with D-style ranges, I certainly don’t know how.

  2. Great work! Keep it coming. To me, a proper range concept that plays nice with what we have () seems like one *the most exciting and widely useful things we could get for C++.

    Thanks for the great posts explaining this stuff!

    () *and can model c-style strings without having to invoke strlen() – yay!

  3. Wow, it took me a bit of time (not that much, though) to realize how the iterable was different from range. I was just seeing the mostly the same code in the two versions.

    The code for the operator!= wasn’t visible, then I had to guess/realize (epiphany) by myself that the idea was to realize a different kind of end condition through the static polymorphism.

    Great article, anyway.
    =)

  4. There was one presentation of Andrei Alexandrescu in 2009, “Iterators must go”, and I see (with this range article) every problem go away (or be invalidated by C++11’s lambda features or C++11’s new allocators), but there is still one problem I don’t see solved though:

    Some iteration methods cannot be supported

    What is the general opinion about this one?

      • Sorry, it’s something I picked wrong. Just ignore.

        I thought that Andrei’s proposal was refering to iteration over trees and other things. But now that I looked again, I realized that he was refering to “iterate backwards”, “chain two ranges w/o copy”, “composability”, …

        • Sure. Those are the benefits of range-based interfaces over iterator-based ones. You can have those in C++ today with a range library like Boost.Range or the one I’m writing.

  5. Hello Eric.

    Yes, the name change into prev next and current helps a lot compared to the other naming conventions. Maybe the problem is that one actually. The point is that it is understandable by mere mortals. And if possible simplified, which I saw was achieved actually when I reread.

    Don´t abuse me too much in the comments, maybe I say a couple of stupid things bc you gave more thought to everything. My goal is to open doors for your thinking when I do a comment. If it´s not right, just discard it. 🙂 Sorry for the nested comment. I wiill comment directly on top.

  6. Hi, I was inspired by part one of your range concepts series, and started work on a library to implement algorithms that accept Iterator pairs of separate types. I also added a couple of generic sentinel iterators (such as the sentinel iterator should compare true if a lambda returns true and so on..)
    Its still under development, but here it is: github.com/matthiasvegh/LazyIterator

    In any case, I’m glad that you came to the same conclusion as I did: Sentinel Iterators should have separate types to regular iterators.

  7. Bundling a count with a position comes at a cost for each iterator copy (and iterators are copied often). This is the same kind of hack you are trying to avoid, positions should remain clean. I suspect you will see the same code explosion you are trying to avoid if you package counts this way. I also don’t buy the combinatoric explosion argument – there are 3 basic algorithms for rotate(), not 9, so you will end up funneling down quickly, not fanning out. If you look, many of the existing algorithms already funnel into a counted variant once a trip count has been determined (or do the equivalent inlined). Take lower_bound() for example, it is defined for forward iterators but the first thing it is going to do is determine a length so it can halve it. So you just need to split that out into a lower_bound_n(). All lower_bound() functions will funnel down to that one implementation, and providing it is just a small refactoring [really it should be implemented as partition_point_n] You might consider having the algorithms that determine the trip count actually return it. The prevalence of using the trip count in algorithm implementations speaks to it’s importance. Splitting these out would also allow a client to determine the trip count in advance before calling a sequence of algorithms. I can only think of one place in the standard algorithms where a sentinel (the term Alex uses for your delimiter) is used – it would be worthwhile to surface this.

    I agree with your arguments that InputIterators are a bad hack, and that trying to shoehorn in a delimitated range into an iterator is also a bad hack. Go through the algorithms and work out what is needed for counted and sentinel ranges.

    • Thanks, Sean. I knew things would get interesting once you found this thread. 🙂

      Bundling a count with a position comes at a cost for each iterator copy (and iterators are copied often). This is the same kind of hack you are trying to avoid, positions should remain clean.

      You caught me. I actually felt dirty when I wrote this. I justified it to myself as follows:

      1. To call a count algorithm, you have to pass an iterator and a count one way or another. Bundling the two together doesn’t change the amount of data that gets copied. But …
      2. Passing them separately might have the advantage that the compiler can pass them in registers. But …
      3. I have it on good authority that compilers these days can actually rip a struct up and pass its constituents in registers anyway. (This would be a good thing to check.)
      4. Pre-increment doesn’t copy an iterator, but post-increment does. It’s possible that it++, count++; is more efficient than it_with_count++, but it seems unlikely that a compiler wouldn’t be able to optimize that. (This would be a good thing to check.)
      5. It may be that the problem you describe is real, but that it’s not worth fixing since the wins of unifying the concepts hierarchies makes up for it. As you once said, “Not all problems are worth fixing.”
      6. Assuming the problem turns out to be real and worth fixing, a sufficiently dedicated standard library implementer could give him/herself a way to detect these “counted iterators”, rip them apart, and call a specialized counted algorithm. So this detail doesn’t need to be surfaced in the concepts (although this would admittedly be damning).
      7. Sadly, passing two “counted iterators” to distance (for example) would do more work than is necessary if (a) they are not random access, and (b) the hack in (F) isn’t implemented. But if it is, it can turn an O(N) operation into an O(1) one, which would be nice.

      What you say about rotate is true and interesting. I’ll need to think about that. It doesn’t diminish the other arguments though. There are a great deal of algorithms that would need to be triplicated to handle counted and sentinel ranges. (I avoided the term “sentinel range” since IIRC Alex uses that term specifically for a range that is terminated at a particular value, and I want to expand this notion to include a range that terminates when a predicate evaluates to true. But the naming isn’t important.) I see that ASL has copy, copy_n and copy_sentinel. Where is for_each_n and for_each_sentinel? How hairy a ball is it to handle counted and sentinel ranges with transform (both the single and double sequence versions)?

      And your copy, copy_n, and copy_sentinel algorithms don’t help people who want to stop copying depending on an arbitrary predicate. There’s still no way for users to break out of algorithms early without rolling their own copy_predicate.

      I can go back and take another look, but I strongly suspect I’ll land right where I am — with iterator/sentinel pairs. Looking forward to your response.

  8. I’m not sure how rotate() works without your counted iterator. Here’s a challenge – implement the slide() algorithm from my Seasoning talk.

    I think you are trying to invent a concept instead of discovering one. Start with the algorithms.

    ASL doesn’t include a complete set of algorithms (whatever that would mean) in much that same way that STL largely consists of the algorithms necessary to implement stable_sort(). I’ve only written what I’ve needed. I’m not entirely convinced that we need all algorithms to handle all forms of ranges – find() and copy() are so common and performance critical that you want many variants of those. But to simplify things you can hide much behind a good notion of a range (even if you have 3 or variants to describe ranges).

    I’m not sure that I follow the difficulty in transform():

    template <class I1, class N, class I2, class O, class F>
    pair<I2, O> transform_n(I1 f1, N n, I2 f2, O o, F f);

    If you want a transform that takes two ranges, a bounded version of the call, then besides having a more complicated call you have a complicated return (you need to return 3 iterators), and a different algorithm. [ I’ll point out that I’m fixing a bug in the existing interface, transform only requires an input iterator for the second range, but doesn’t return the final position of that iterator, without that information there is no way to continue. ]

    • I’m not sure how rotate() works without your counted iterator. Here’s a challenge – implement the slide() algorithm from my Seasoning talk.

      I was at that talk. I took your slide algorithm verbatim. It works with counted iterators just fine, since they are iterators, after all. The code is in this gist. When I looked at the optimized assembly of slide for counted iterators vs. non-counted iterators, as you might guess, the counted iterators fared poorly. I won’t defend it; it’s a problem that needs to be addressed.

      Start with the algorithms.

      Always sound advice.

      I’m not entirely convinced that we need all algorithms to handle all forms of ranges […] But to simplify things you can hide much behind a good notion of a range (even if you have 3 or variants to describe ranges).

      I guess I’m not clear on what you’re suggesting. I’m hearing you say that we don’t need counted or sentinel variants of most algorithms. But you’re also saying that it should be possible to build a range from an iterator and a count, or from an iterator and a sentinel. If you pass such a range to an algorithm, it needs to dispatch to something. What is that thing, if not for a counted or sentinel variant of the algorithm? I don’t see how we escape from a 3x blow-up (modulo those algorithms that funnel down to one).

      I think you’re right that some algorithms (not all) need counted variants, and that well-chosen range concepts can hide that complexity from the user by dispatching to the correct implementation. I think it would be a terrible loss if the concepts weren’t unified under the same hierarchy. I have some initial thoughts, but I need to work with the algorithms and look at some assembly.

      • “I guess I’m not clear on what you’re suggesting.”

        Let me give an example, I already mentioned that lower_bound() is effectively implemented on top of a lower_bound_n().

        So if we have a range concept that supports begin(), end(), and size() operations than a range based lower_bound looks like:

        template <typename R, // R denotes a range
        typename T> // T is value_type<R>
        position<R> lower_bound(R& r, const T& x)
        {
        return lower_bound_n(begin(r), size(r), x);
        }

        For a pair of iterators this requires a call to distance(), but so does the current std::lower_bound(). For a delimited range, this is a scan for the delimiter, but I don’t see how you can do better. For a counted range, this is a direct call.

        There are some algorithms where you want to dispatch based on the complexity of size() vs. the complexity of end(), but those are the exception. Note that my concept is not going to be counted vs. not counted, but it is going to hinge on the complexity of size() vs. end(), in this regard, a random access iterator range and a counted range are equivalent . So I would have a forward counted range but not a random access counted range. There is really no need to provide a lower_bound that takes a position and a predicate, all it would do is call distance and lower_bound_n().

        • There are some algorithms where you want to dispatch based on the complexity of size() vs. the complexity of end()

          So, you would loosen the O(1) complexity requirement of end()? Wow. So, to implement a sentinel range you let both size() and end() be O(N). Don’t all algorithm have to traverse the range twice, then? Like a range-based for_each algorithm, to pick a trivial example?

          I agree that a size() range primitive would be a good thing. Being able to know the size of a range in O(1) time would help a lot of algorithms. But letting end() be O(N) seems like it would hurt more than it helps. I was also thinking of adding a SizedIterable concept that adds an O(1) size() primitive, but it would be a refinement of Iterable, rather than a substitute for it.

          I’d still like to know how you plan to avoid a 3x blow-up of the algorithms (again, modulo those that funnel down to one) with your 3 separate range concept hierarchies.

          • Regarding end() and size() – I was using them as terms we know, not implying it was required that all range concepts implement them.

            But conceptually, all ranges do have a size() and end() [ignoring your infinite ranges, and understanding the getting end() or size() might destroy the range]. A delimited range has a constant time predicate which tests the value for an end condition. So write the algorithms to take the predicate.

            For some algorithms you do get three copies (or for if you treat sentinel cases independently – find, find_n, find_until, find_sentinel) but many algorithms don’t have that many useful forms. I pointed out lower_bound really just has lower_bound_n(), all others are written in terms of lower_bound_n(). I don’t have a problem with many forms of find(), copy(), transform(), and for_each() – especially since if you have a range type you really don’t need to care… it just becomes find(r, x).

            What I’d like in a range library is that the following all denote ranges:

            const char* p; // NTBS
            pair<int*, int>; // pair of iterator
            pair<int
            , int>; // iterator and count
            pair<int*, bool (*)(int)>; // iterator and predicate

            I shouldn’t need any kind of adaptors to use those as ranges. The result of std::equal_range() should be a valid range.

            All the containers and arrays should denote ranges (they are not themselves ranges).

  9. I’m not sure I follow your slide() example. I’m not finding any docs on what a range_facade<> is so I’m not clear on what begin() is returning on your range. Your equal() function looks questionable – two ranges are equal if they are the same length? And if the result of slide is a pair of iterators that both contain a position and count, it isn’t clear to me what that range represents.

    • I haven’t written docs yet. range_facade generates an iterator, a sentinel, and begin()/end() members from the minimal interface you see there. The equal() function is correct, I think. You can only compare iterators into the same range. So the two iterators being compared must belong to the same counted range. So comparing counts is equivalent to comparing iterators, and is probably faster. The result of slide() is a pair of iterators. Whether the iterators are counted or not doesn’t change what that means (although it may have performance implications).

        • You can compare the values of the subranges, but you can’t compare iterators from different subranges. The definition of equal could be changed, but I don’t see the problem yet.

  10. The first thought I had after reading the first 2 parts was to represent a range as pair (First, IsLastPredicate), where First is an iterator and IsLastPredicate is a functional object.

    Then (the lambdas are only for brevity),
    for STL range:
    IsLastPredicate = [last] (FirstType it) { return it == last; }
    for delimited range:
    IsLastPredicate = [sentinel] (FirstType it) { return *it == sentinel; }
    for infinite range:
    IsLastPredicate = [] (FirstType it) { return false; }

    But after reading the part 3 I realized that after inlining it is likely the same thing as your variant with First and Last of different types, but less convenient for providing backward compatibility.

    • Given Range defined as (First, IsLastPredicate), then a “universal sentinel” re-enables backwards compatibility of existing algorithms (if you allow End to be a different type):

      class universal_sentinel {
      };

      template <Iterable It>
      bool operator==(It it, universal_sentinel)
      {
      return it.IsLastPredicate();
      }

      ...

      auto some_range = make_pair(first, lastPredicate);
      auto x = std::find(some_range, universal_sentinel, value);

      • You mean like this? 🙂 It’s handy for turning an iterator into an unbounded range.

        You don’t actually want an iterator to have a done() method in the general case. You’d rather define something like an equal() method on the sentinel that takes an iterator. That allows for stateful sentinels. There is a default sentinel that does nothing in it’s equal() than dispatch to a done() member on the iterator, but done() is not part of the requirements ever.

        And of course, done(), and equal() are not actually members of the sentinel or iterator. They’re internal implementation details. The public interface is operator== and operator!=. done() and equal() are generated and used by the range_facade class.

        This interface has evolved over time after implementing many range types. It allows for lots of variability, which is good because different range types have different needs.

  11. // replying to your reply, but not via Reply, as too much cascading gets messy

    You mean like this? 🙂 It’s handy for turning an iterator into an unbounded range.

    I’d say no, not like that, but it depends what you mean by ‘like’ 🙂 They are similar in structure, but not result. Mine turns around and calls rng.done() for you. ie turns it == end syntax into rng.done() syntax.

    You don’t actually want an iterator to have a done() method in the general case.

    I don’t want an Iterator to have a done(), but maybe I want a Range to. More below…

    You’d rather define something like an equal() method on the sentinel that takes an iterator. That allows for stateful sentinels.

    And why are stateful sentinels important? (ie why not stateful ranges with done() functions?) More below…

    And of course, done(), and equal() are not actually members of the sentinel or iterator. They’re internal implementation details. The public interface is operator== and operator!=. done() and equal() are generated and used by the range_facade class.

    This interface has evolved over time after implementing many range types. It allows for lots of variability, which is good because different range types have different needs.

    There are a few questions we have been trying to answer:

    what is a Range (conceptually)
    what is its interface (syntactically)

    I think the first question has an easy answer:
    A Range is something that allows me to
    – iterate over elements
    – stop iterating at the right time

    These are the two properties of the concept. We can break down the second part into different ways of stopping (sentinel, counter, etc), but the general concept is the same.

    Now onto the interface. So far I’d say that you have some good reasons for keeping the “it == end” syntax for stopping. But is this just because it works nice with existing STL? What if you started from scratch? You’ve already shown, via range_facade, that .done() is a good interface for building ranges, why isn’t it a good interface for using ranges?

    More importantly – isn’t .done() the natural interface for the Range concept, if the concept is defined as above?

    If the only reason to choose it == end is for “compatibility” – or even genericity, then my universal_sentinel gives you the same compatibility – same syntax, but calls done() for you. (sentinel_adapter? calls_done_sentinel? some better name?…)

    So I’d like a better reason to not use .done() than just “syntax doesn’t work”, since the syntax can work. (Maybe “don’t want to have to use this sentinel adapter everywhere is a good enough reason…)

    Having said that, I think there may be reasons why it == end is still better – beyond just syntax. ie conceptually. But what are they? (I suspect you have them. Maybe you even stated them or hinted at them in some form but I missed it.)

    (Hint: At the top I said “turns it == end into rng.done()” whereas really it turns “x == end” into “x.done()” – but in one case we think “it” ie iterator/iterable, the other we thing range… conceptually)

    • Mine turns around and calls rng.done() for you. ie turns it == end syntax into rng.done() syntax.

      Oh right. In my code, that’s handled here.

      I don’t want an Iterator to have a done(), but maybe I want a Range to.

      I think you want to separate the range from the thing that iterates over it. After all, the range may contain more information in it than the iterator strictly needs, and you don’t want to copy it all around unnecessarily.

      And why are stateful sentinels important?

      Think of a delimited range consisting of an iterator and a predicate that tells you when you’re done. The predicate could be a large, stateful object. The predicate would go into the sentinel since it doesn’t get copied around as much. (Actually, the sentinel might just contain a pointer back to the range, where the predicate lives.)

      You’ve already shown, via range_facade, that .done() is a good interface for building ranges

      I’ve show that it’s a handy default, no more. .done() is not part of the requirements for any type in my range library.

      So far I’d say that you have some good reasons for keeping the “it == end” syntax for stopping. But is this just because it works nice with existing STL? What if you started from scratch?

      I’d put it like this: Alex Stepanov had good reasons for picking the it == end syntax for iterators. It’s still a win to be able to use raw pointers when calling std algorithms. And considering that it’s a win to separate the range from the thing that traverses it, the logical choice for a range-traversal-thingy is an iterator. So I’m sticking with the it == end syntax.

      • it’s a win to separate the range from the thing that traverses it

        That, to me is the key. (And it is why I don’t like Alexandrescu’s ranges. I don’t like my range shrinking as I iterate over it, for example. I agree that the new value of the incremented iterator, plus the end iterator does make a new range, but it still feels wrong to me. Of course ‘feels wrong’, even if it always gives me the right result in my code, doesn’t make for a good argument. And I appreciate Andrei’s work in seeing how it really turns out.

        If Range was called Sink or Source, I might not feel as bad about it gowing/shrinking as it was iterated (and it being the iterator).)

        I’ve heard a number of times in Range discussions that position (or iterator) is also important, and we shouldn’t lose it as a separate concept. I think that also leans towards “separate the range from the thing that traverses it”.

        I think you arguments for separation are:
        – Alex did it (always a good argument, but much has changed since then, and he wanted to blend in with existing code, not be 100% different)
        – iterator might be smaller than Range

        I think a better argument is just that they are different concepts. (Which I’m sure is also in your argument in a few places. I just want to emphasize it as a fundamental.)

        So it seems a Range is thing that can
        – be iterated over
        – knows when to stop that iteration

        – can easily be broken down into its iterator and more-specific-end-type, for the sake of algorithms.

        But as soon as you break out the iterator, you are back to the risk of using the iterator without the range/end (ie less safe). Back to iterator + end. Is that the cost of efficiency? – they are separated because iterators tend to be cheap and end might be heavier? And they should only be separated very locally (near the base of the algorithm)?

        I think IterationPoint and Range are different concepts, but IterationPoint is still unsafe if it doesn’t contain a reference to the Range/end. IterationPoint, even as a concept is somewhat meaningless without the respective Range. It is like a point on a plane without a plane. Is it a cartesian point or polar? Who knows? It is meaningless.

        At minimum, an Iterator should have a reference back to its range/end. For both safety and conceptually. But that may be too pricey at the lowest level. How do we (syntactically) limit the iterator from being passed around without the range? Just by making a range class that is more convenient?

        Sorry for rambling…

  12. In c++ now 2014, I saw this:

    https://github.com/boostcon/cppnow_presentations_2014

    Value Semantics and Range Algorithms – Composability and Efficiency

    Well, one of the latest slides said something that is really relevant to the design of ranges/iterables: a range is a pair <iterator, bool (iterator)>, namely, the end is a predicate on the iterator. I think this is the best solution I have seen to date. Very easy to understand, way more than a special sentinel iterator type.
    I would like to know about what you think.

  13. Doesn’t work. Any algorithm that needs to decrement the end iterator cannot be implemented if this is how you define a range. Try to implement std::reverse and you’ll see.

  14. The Range concept looks a bit strange to me: It uses the Iterator concept, which, when defined as in C++11[iterator.iterators], does not require EqualityComparable. For a Range as a pair of iterators, it seems to me that being able to iterate from begin to(wards) end is the defining property.

    This is probably one of the reasons for boost’s revised iterator categories; as far as I can tell, the iterator used for a Range must at least be a SinglePassIterator (incrementable and EqualityComparable).

    • In case it wasn’t clear from my post, I’m not suggesting making any changes to the Iterator concept. It will still be EqualityComparable. In addition, for an iterator/sentinel pair, the iterator must be EqualityComparable with the sentinel. I describe the justification and implications of this cross-type EqualityComparable constraint in detail above.

  15. The Iterator concept I know (from C++11[iterator.iterators]) does not require EqualityComparable. Only InputIterator and more refined are EqualityComparable. For example, an OutputIterator is an iterator, but in general cannot be EqualityComparable.

    • The same will be true going forward. There really are no algorithms that have pure output ranges that are delimited. The algorithms that take an output iterator take just one (like std::copy). The output iterator is not compared to anything, so it doesn’t need to be EqualityComparable. I haven’t proposed changing how the algorithms deal with output sequences. So, range-based copy takes an input Iterable and an output iterator.

  16. Hi Eric,

    (sorry if the following has been covered in the discussion I didn’t yet throughly read all of it, or if I’m missing something obvious…)

    After Andrei Alexandrescu did the “Iterators must go” talk, I played with my own toy implementation of ranges and after hitting the problem that for certain use-cases you need something to represent position I thought that it might be solved by defining two concepts:

    A Range (where possible Bidirectional or RandomAccess) with the current, next and done member functions being its interface and a Locator – an equality-comparable type representing constant position in a Range that could be used to access the element it points to (like an Iterator, but without the posibility to change the position, and without the possibility to point past-the-end of the range, which should IMHO greatly simplify its implementation).

    A ForwardRange could than return the Locator for its current element, a BidirectionalRange could return the Locators of its first and last element and a RandomAccess range the locator of any element inside. A Range could then be (at least in some cases) recreated from a pair of Locators.

    I didn’t find the time to incorporate this into the library yet, though and test if it really allows to implement all required algorithms

    I understand the reluctance to drop Iterators completely, legacy code, etc., but ignoring all this for a while, what do you think of the above? Would be the Range/Locator pair of concepts enough to solve the other issues where Iterators/Sentinels currenly seem to be necessary?

    Anyway, thanks for your work, I’m looking forward to see how this pans out

    • You are 100% correct! You should take a look at James Touton’s range library. James calls his idea “Position-Based Ranges”. I describe his approach in my standard proposal here (scroll past the discussion of D’s ranges).

      I think it’s a good design and I say so in the proposal. But it’s not appropriate for the standard library. Having two incompatible abstractions in the standard library for the same thing would cause too much havoc. And based on my experience with the range-v3 library, a new abstraction just isn’t needed.

  17. Oh nice,

    I should have read the whole series and the proposal before commenting, thanks for the links.

    It’s a shame that someone didn’t think about this abstraction 25 years ago, we could have skipped the whole Iterator-gymnastics we have to do now. Range v3 looks very promising though.
    I wish you success with your proposal.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.