const-ness of view operations

[CaseyCarter]

Containers

Containers in C++ may have both const and non-const overloads of begin. They differ only in their return types: non-const begin returns a mutable iterator, and const begin a constant iterator. Neither overload changes the bits of the container representation or modifies the semantic value of the container object. Two overloads exist so that it is necessary to establish a non-const access path to the container object in order to obtain a mutable iterator. end is the same. size is always const because it provides no way to modify the container's content.

Views

Views in range-v3 may have both const and non-const overloads of begin/end/size (herein termed "operations"). Views have pointer semantics - a view is essentially a pointer to a sequence of elements - so mutability of the elements viewed is orthogonal to mutability of the view object itself. The const distinction here has no relation to that of containers. Non-const operations do not modify the semantic objects being viewed, nor do they "swing the pointer" so that the same view designates different semantic objects. Non-const operations mutate internal state that does not contribute to the semantic value of the view; the const-ness here is purely bitwise.

The const-ness model used by views makes view composition painful. You can always provide the non-const overloads, but const overloads are preferred when achievable. So a composer, e.g.:

template<typename View>
class wrap_view : view_facade<wrap_view<View>>
{
    View base_;
public:
    wrap_view() = default;
    wrap_view(View v)
    : base_(std::move(v))
    {}
    // ...
};

ends up providing two definitions of each operation: one const that's constrained to require const operations over the underlying view(s):

    // We need the dependent type V so that range_iterator_t<V const> doesn't hard
    // error when View has no const begin operation (or: use C++14 deduced return type).
    template <typename V = View, CONCEPT_REQUIRES_(Range<View const>())>
    range_iterator_t<V const> begin() const
    { return ranges::begin(base_); }

and one mutable that's constrained to only be available when the const version isn't:

    CONCEPT_REQUIRES(!Range<View const>())
    range_iterator_t<View> begin()
    { return ranges::begin(base_); }

Ranges

I'm concerned that the differing const distinctions for containers and views don't mesh well into a consistent notion of what const means for operations on general ranges. I see a potential for latent bugs where a programmer accustomed to the fact that calling begin/end on mutable containers is threadsafe calls begin/end on mutable ranges without realizing there are sharp corners here.

The only mutating operation on pointers is assignment. If views are supposed to be range-pointers, perhaps assignment should be the only mutating operation? We (I) need to investigate an alternative model where view operations are always const and perform internal synchronization if needed.

[gnzlbg]

I see a potential for latent bugs where a programmer accustomed to the fact that calling begin/end on mutable containers is threadsafe calls begin/end on mutable ranges without realizing there are sharp corners here.

I agree with the tone of this RFC, these are real issues.

We (I) need to investigate an alternative model where view operations are always const and perform internal synchronization if needed.

I think that views are already expensive, and that the serial case is an important one, so my feelings are currently against a model that requires internal synchronization to implement a conforming view. Still, this hasn't been investigated yet and maybe (hopefully?) isn't as bad as I expect it to be.

There is another issue. While views are not thread-safe in general, they are (or should be) cheap to copy, so the thread-safety issues that might arise are from users inadvertently sharing views between threads instead of copying them (which is what users should be doing) [*] . This is another point in which views differ from containers (which are expensive to copy and might be worth sharing). Views should almost never be worth sharing and by making them thread-safe we might be encouraging the wrong usage patterns.

Sometimes one might really want to share a view, but in those cases one wants to perform sharing explicitly as opposed to by mistake, so I think thread-safe versions of some of the views (something that you are not proposing) could be really useful even though having the world split might impact re-usability (e.g. can't reuse view::a | view::b | view::c because view::b is/isn't thread-safe).

Is there a list somewhere of which views are not thread safe? (e.g. probably all the SinglePass views but maybe others as well).

[*] Maybe the cppguidelines could in the future improve the safety issues by allowing marking some views as not-thread safe in the spirit of rust Send<T> and Sync<T> traits but that's a long shot.

[ilyapopov]

I quickly searched the code and I discovered that box.hpp and stride.hpp already use atomics for some synchronization. I find that surprising. Could anyone comment what is rationale behind that? Is not we paying for what we don't normally use?

PS seems like this is for some mutable members which, where the user would assume thread-safety because of const interface.

[ericniebler]

I'm concerned that the differing const distinctions for containers and views don't mesh well into a consistent notion of what const means for operations on general ranges. I see a potential for latent bugs where a programmer accustomed to the fact that calling begin/end on mutable containers is threadsafe calls begin/end on mutable ranges without realizing there are sharp corners here.

The current model is: either the range has visible mutable state and does not have const begin()/end(), or else it guards any internal mutation so as to be thread-safe. I agree it's not ideal, but I haven't come up with anything better.

I quickly searched the code and I discovered that box.hpp and stride.hpp already use atomics for some synchronization.

It's so that view::stride can have an amortized O(1) begin()/end() by caching some data rather than recomputing it every time. The cache variables are guarded by atomics. The alternative would be to make begin()/end() non-const. I considered the atomic to be the lesser evil, but I am open to other views (har har).

The only mutating operation on pointers is assignment. If views are supposed to be range-pointers, perhaps assignment should be the only mutating operation? We (I) need to investigate an alternative model where view operations are always const and perform internal synchronization if needed.

Ack. Baby, meet bathwater. Some views simply cannot be const, logical or physical; an istream view, for instance. Unless you want to disallow such a view (I don't), it seems to me that the problem must be addressed.

[ericniebler]

One simplification is that no views have const begin()/end() members. That way nobody has to think about it. Seems like a fool's consistency to me, though.

[CaseyCarter]

This implementation of istream_range:

template<typename Val>
struct istream_range
  : view_facade<istream_range<Val>, unknown>
{
private:
    friend range_access;
    std::istream *sin_;
    mutable semiregular_t<Val> obj_;
    struct cursor
    {
    private:
        istream_range const *rng_;
    public:
        cursor() = default;
        explicit cursor(istream_range const &rng)
          : rng_(&rng)
        {}
        void next()
        {
            rng_->next();
        }
        Val &get() const noexcept
        {
            return rng_->cached();
        }
        bool done() const
        {
            return !*rng_->sin_;
        }
        Val && move() const noexcept
        {
            return detail::move(rng_->cached());
        }
    };
    void next() const
    {
        *sin_ >> cached();
    }
    cursor begin_cursor() const
    {
        return cursor{*this};
    }
    Val & cached() const noexcept
    {
        return obj_;
    }
    istream_range(std::istream &sin, Val *)
      : sin_(&sin), obj_{}
    {}
    istream_range(std::istream &sin, semiregular<Val> *)
      : sin_(&sin), obj_{in_place}
    {}
public:
    istream_range() = default;
    istream_range(std::istream &sin)
      : istream_range(sin, _nullptr_v<semiregular_t<Val>>())
    {
        next(); // prime the pump
    }
};

has const begin & end, and meets the thread-safety requirements of [res.on.data.races]. Note that cursor::next cannot race with get/done/move: input iterators are not required to be dereferenceable after increment, so a program in which two threads simultaneously increment and dereference input iterators with the same value has undefined behavior.

[ericniebler]

That's interesting, but it feels a bit dirty. I don't like const members that mutate the object in a visible way, especially if it's unsynchronized. I'm not particularly swayed by the argument that we've defined things such as to permit it.

[CaseyCarter]

I disagree with the claim that there are "
const members that mutate the object in a visible way." No such mutations are observable in a program with defined behavior. If that guarantee is strong enough for the C++ memory model, surely it suffices for istream_range.

Do you disagree with the semantics we've defined for views and input iterators that make this implementation valid, or do you disagree with the results this implementation produces for programs with undefined behavior?

[ericniebler]

Do you disagree with the semantics we've defined for views and input iterators that make this implementation valid, or do you disagree with the results this implementation produces for programs with undefined behavior?

Neither. I'm expressing my distaste for using up all the wiggle room we've given ourselves wrt input ranges. I don't think I disagree that this is allowed. And it probably should be. But man does it feel wrong.

EDIT: I think it feels wrong because not everybody will be cognizant of the fact that input iterators are not required to be dereferenceable after increment, and the type system is giving them no help. A good interface makes it easy to write correct code and hard to write incorrect code. This is not that.

[ericniebler]

For the record, this issue interests me greatly. The interaction of the type system with views is very important to get right. I would love to hear a better suggestion, but so far I favor the current design as warty and surprising as it can be. Perhaps we look for a library solution that guides people away from the warts and toward doing the right thing, like providing the const-correct begin/end overloads for them, depending on whether their range has to cache mutable state. ??? I'm spitballing here. Open to other suggestions.

EDIT: One of the reasons view_adaptor exists, as crummy as it is, is because it makes it easier to get this const business right.

[gnzlbg]

I think it feels wrong because not everybody will be cognizant of the fact that input iterators are not required to be dereferenceable after increment, and the type system is giving them no help. A good interface makes it easy to write correct code and hard to write incorrect code.

What exactly do you mean here? Iterators are only dereferenceable after increment if it < end() right? So all iterators kind of have this problem. Maybe that if I have two copies of InputIterators and increment one the other is invalidated?.

[gnzlbg]

If that is the case the problem is IMO that dereferencing doesn't mean the same thing for InputIterator than for other iterators, and it looks to me that we got ourselves into this hole by calling it the same thing. A solution could then be to call it something else .get() and for example return an optional.

This is far from perfect, breaks the iterator hierarchy, and optional is not free, but it could make things safe by forcing the users to check if they got a value from an InputIterator or not.

EDIT: going this far is IMO not worth the trouble, and making InputIterators return a range is too weird.

[ericniebler]

Maybe that if I have two copies of InputIterators and increment one the other is invalidated?).

This.

If that is the case the problem is IMO that dereferencing doesn't mean the same thing for InputIterator than for other iterators, and it looks to me that we got ourselves into this hole by calling it the same thing.

If by "we" you mean the original designers of the STL then I agree. It's too late to change it now. The question is, what hand can we make of the cards we've been dealt? Casey thinks he can pull an inside straight (stretching the metaphor), I think we should settle for a std pair.

[CaseyCarter]

Dereference is fine, really, it's increment that causes the insanity. Increment has spooky action-at-a-distance in that it renders copies invalid. Such action-at-a-distance is anathema to our ability to reason locally about program behavior.

EDIT: I think it feels wrong because not everybody will be cognizant of the fact that input iterators are not required to be dereferenceable after increment, and the type system is giving them no help. A good interface makes it easy to write correct code and hard to write incorrect code. This is not that.

Yes, and that ship got on the bus and left the train station long ago. We can't bolt safety onto single-pass iterators now. What we can do is suggest implementation techniques that exploit the undefined behavior to provide at least some error detection. An input range that detects repeated calls to begin, or late calls to size, or use of invalid iterators adds more realistic safety than an input range that has mutable size or begin.

And yes, I admit I'm doing a lot more complaining about problems in this thread than discussing solutions. My goal was not to belittle the current use of const/mutable for views, so much as to point out some things I think need improvement and see of others agree.

[mgaunard]

I don't think const should affect the behaviour of views. If you want to cache state, using mutable is fine.

This issue took me unexpectedly and made me lose a lot of time. Had I known this beforehand, I might have stuck with boost range v2 instead.

[ericniebler]

If you want to cache state, using mutable is fine.

Possibly for Input ranges, but how could it be fine to mutate a const object that is possibly being read concurrently from different parts of your program? Guarding against that kinds of misuse is exactly what const is for.

Had I known this beforehand, I might have stuck with boost range v2 instead.

Seriously? Be my guest.

[mgaunard]

Boost.Iterator/Boost.Range are fairly simple both in concept and implementation, are well documented, well understood, mature, and I happen to have a lot of experience with it. I chose to use Range v3 for a toy project since it was a chance to evaluate it, but given the minimal documentation, the amount of complexity I ran into, and the open major design issues like this one, it might appear that it's not quite ready.
Now that is but an opinion, but it's based on somewhat unquestionable facts, so I don't think being so dismissive was justly deserved.

Anyway, I'm not quite used to the view/cursor dichotomy as opposed to the range/iterator one yet, but couldn't all state go into the iterator rather than the view, removing all needs for synchronization?

[gnzlbg]

I think maybe the library needs a FAQ because @mgaunard questions are fair for new users to have, and come up very often. New users seem to have two issues with the library:

• they don't know that views are stateful algorithms by design and that it doesn't make sense to try to make them const (in general).
• they don't know that views have amortized O(1) begin/end.

So because they don't know this, and some of them come with a Boost.Range v2 background, they first try to make everything const, and "clash" against the library. Then they ask themselves why can't I make a view const? It has no state! And because they don't know the second point, they end up very confused.

@mgaunard

views are stateful algorithms by definition

This is how range-v3 is designed. While some views don't store state, most do. Don't make them const. This might be hard if you are used to "make everything const", but ask yourself, does this stateful algorithm really need to be const here?

In range-v3, begin / end are amortized O(1)

That is, if you do:

auto v = range | view::remove_if(pred);
for (auto&& i : v) { ... }  // begin/end are amortized O(1) here
for (auto&& i : v) { ... }  // begin/end are amortized O(1) here as well

The way this is implemented is that some views cache the begin/end on construction, so that all the calls to begin/end from that point on are O(1). This requires state, so vies that do this cannot be const (@ericniebler: I don't find this in the design paper, have you written about this somewhere besides in the issues? I guess this also would belong to a FAQ).

@mgaunard This is just a guarantee that range-v3 views offer you. If you don't need this/want this, range-v3 offers you the tools to build your own view::remove_if_mgaunard that does not cache any internal state, that offers O(N) begin and end, and can be made const.

But think about it thrice before going down that route. What do you win? The ability to make a view const? For what? Is that worth it? What do you loose? (O(1) begin/end)

[ericniebler]

From @CaseyCarter in #428 :

remove_if caches the value of the first "non-removed" iterator in the range so as to amortize the cost of multiple calls to begin since begin is supposed to be O(1). This is odd given that next and prev are not O(1) and more likely to be called frequently and repeatedly

The difference between begin and next is that begin is assumed to O(1) is so many places. Consider this code from reverse_view's next member:

if(0 != ranges::advance(it, -1, ranges::begin(rng_->mutable_base())))
    it = rng_->get_end_(BoundedRange<Rng>());

If begin is O(M), then next becomes O(M). That's bad.

For ranges like filter_view, next is permitted to be O(M) so long as traversing the entire range is O(N). next is more expensive, but it must be called fewer times to traverse the entire range.

begin and end get called frequently in the implementation of next and prev of many other range adaptors. The alternative is to have the adaptor's iterators cache the underlying range's begin and end iterator. That makes iterators fat -- a problem that compounds as adaptor chains grow -- and spreads the cost out as begin and end get recomputed over and over.

The design compromise that is currently implemented makes begin/end always amortized O(1) so it is safe to be called from a loop where it is used in expressions that test for begin- or end-of-range. The win is that iterators stay small and the beginning and end of the range, if it is computed, gets computed only once, and that result can be reused over and over. The downside, as you've noticed, is that ranges become stateful.

I'm sure you can find examples in the other views where next and prev get called in loops in a way that make the algorithms O(N*M). Caching all the positions returned by next and prev is obviously unfeasible. I made begin and end different (a) because they so frequently appear in end-of-range checking expressions, and (b) there are only two such positions, so caching them is feasible.

So, here are the alternatives I see:

1. Status quo: Ranges may lack const begin/end members and are permitted to cache data from begin/end without synchronization overhead.
2. Any cached state must be computed on construction/assignment. View move/copy/assign becomes O(N).
3. Caching from begin/end in non-Input ranges is verboten. Ranges like filter_view can either satisfy Forward or have O(1) begin/end members, but not both. Caching Input ranges have const begin/end members, increasing the likelihood they will be used unsafely.
4. Ranges that want to be Forward, cache state from begin/end, and have const begin/end must guard the mutation with synchronization.
5. All views and cursors must be implemented with the assumption that begin/end are O(N). Cursors that compare an iterator with the beginning or end of a range must store those positions internally. Iterator bloat becomes a problem that compounds as adaptor chains grow.

Any other options I missed?

<spitballing> I can imagine a separate range adaptor that caches the underlying range's begin/end on construction. With C++17's guarantees about copy elision, we can investigate the possibility of using this either internally or letting users use it directly. That requires that let filter_view have O(N) begin. That doesn't give our users much guidance to know when such a caching adaptor would be needed.

[pfultz2]

The difference between begin and next is that begin is assumed to O(1) is so many places. Consider this code from reverse_view's next member:

Why wouldn't you just do --it? In the deference oprerator, it would require one iteration back but that seems better than all that branching.

[ericniebler]

(Drifting off-topic):

Why wouldn't you just do --it? In the deference oprerator, it would require one iteration back but that seems better than all that branching.

This implementation of reverse_view avoids LWG#198.

[mgaunard]

Was this design aspect (constness drops range status of certain views) discussed in WG21 yet?

[ericniebler]

constness drops range status of certain view

With the current design, const does not effect the strength of the concept that a range satisfies. So no, it has not been discussed in WG21.

[ericniebler]

So, here are the alternatives I see:
[...]
Any other options I missed?

@CaseyCarter Thoughts? I'm going to start work on Range TS2 "Views Edition" soon/eventually, and as of right now, I haven't heard a better alternative than the current design. I can play with improved designs for range_adaptor that do more of this work for the user, but the fundamental model would be unchanged.

[gnzlbg]

I ran into this when trying to improve a bit the views part of the range-v3 documentation. Describing them as "lazy range combinators" doesn't give users enough information to avoid common questions and mistakes, so I was trying to come up with a slightly longer description that explains the semantics a bit more and covers some pitfalls.

Needless to say, I gave up since the best I could come up with was this:

Views are:

• range algorithms: from some input (which might be a range), they produce a range of values,
• composable: views producing and accepting ranges can be chained to construct more complex algorithms,
• lazy: the sequence of values produced by a view is computed on demand as the view is iterated over, every time the view is iterated over
  • views present the trade-off "compute every time, no extra memory", while the opposite tradeoff, "compute once, store in memory" is provided by actions. Both views and actions can be composed.
• non-owning: in general, views do not own their input, which makes them "cheap" to copy,
  • cheap means that the complexity of copying a view is independent of the number of elements in the range taken/produced by the view
  • some views do own their input when this condition can be satisfied to make them more convenient to use (e.g. view::single(value) owns by default a copy of value which can be avoided by using view::single(ref(value))),
• stateful: views often store some state that might be mutated during iteration,
  • that is, making a view const might prevent iteration,
  • all views provide O(1) amortized begin and end. Some views must pre-compute begin and end on construction to provide this guarantee. To benefit from amortized O(1) begin and end, prefer storing these views and keeping them around instead of constructing them anew over and over.
  • However! Iterating more than once over a SinglePass view is undefined behavior. Use the !SinglePass<range> concept to constrain algorithms that iterate more than once over a range.
• thread-safe: in the standard library sense, that is, const operations are thread safe:
  • However! often views do not have const iteration methods. One can:
    • (if possible) use view::const to ensure that the input of the range algorithm is not mutated and copy the view between threads,
    • use external synchronization (e.g. std::mutex) to share a mutable view between threads.

Given the current situation, maybe it is possible to implement a "view::synchronized" that either uses view::const (when that is sufficient), or protects the mutable state with a std::mutex to provide thread-safe const methods to whatever view it is composed with. That, or something like that, would make teaching the thread-safety part of the view story a bit easier (want to share a view between threads? Just use | view::synchronized).

It would also improve teachability if we had a more solid story for the undefined behavior behind SinglePass ranges (e.g. by requiring a run-time diagnostic in case one is iterated multiple times). I've run into them a couple of times and they were always painful to debug.

[ericniebler]

But any non-const-iteratable view loses thread safety.

This is a fallacy. It is exactly as thread-safe as any other component in the standard library.

So reverse could cache begin() of the underlying range. I would do it on construction to make begin() const and thus reverse adaptor thread-safe. Copying ranges is rare in our codebase because the code is usually oblivious if it is dealing with a view or a container.

The problems with calculating begin/end of the underlying range on view construction are discussed above. What are you contributing to the discussion that is new? That in your use case view copy doesn't happen very often? Should we conclude from this that for all use cases it's OK for copy (and move and construct) to be O(N) instead of O(1) just so that users can iterate over a const filtered, reversed view? That doesn't seem like the right tradeoff.

And what to do about the other views that need to maintain mutable internal state, like view::join, which is important to make ranges monadic?

Reverse being so strange is actually rooted in the fact that iterators describe both boundaries and elements.

That is not my understanding. Iterators always refer to boundaries between elements. std::find, for instance, returns the position between the found element and the element that precedes it (if any). A clear example of this is regex_search. For a sequence of N elements, there are N+1 valid positions at which a match might be found. The pattern ^ can find a match immediately before the first element, and the pattern $ can match immediately after the last element. std::find is a degenerate case of regex_search where the pattern is a 1-element sequence consisting of the element to be found. It matches immediately before the first occurrence of that element in the target sequence. (Because std::find can never find a match after the last element, it returns that position to mean "not found". That is a convenient convention, but it's not general. regex_search, for instance, must return a bool for found/not found.)

The same is true of pointers to objects in memory. Despite the fact that objects take up a range of bytes in memory, the singular address of that object is the point at which the object starts. That is the boundary between memory that is not part of the object and memory that is.

Iterators (and pointers) combine access and traversal. By convention, dereferencing the pointer (or iterator) yields the value of the first element of that range. In different algorithms, the "access" mode of the iterator has greater prominence than the "traversal" mode. This can give the impression that the iterator denotes the element as opposed to the boundary immediately before the element. (The language of the standard doesn't help here.) For most cases, the difference is immaterial and we've skated by this long with muddled language and muddled thinking.

see my talk [https://www.think-cell.com/en/career/talks/]

I've looked at the slides. As I discuss above, I disagree with your premise. There is no confusion or inconsistency that I can see about what an iterator denotes, so there is no reason to conclude that iterators are a broken abstraction that needs to be abandoned.

When you create a reverse view of a sequence, the begin iterator denotes the end (the boundary immediately following the last element):

| 1 | 2 | 3 | 4 |
                ^

Dereferencing that iterator yields the element before that boundary, which, when taken together with the way increment is defined, is consistent with the convention that dereference yields the value of the first element of the range. So what should .base() return? It's a very interesting question because it reveals a lot about the nature of iterators. You might think, ".base() removes the reverse-ness, so it should return an iterator that points to the same element (4) as before. Therefore, base() should return current_ - 1.". But that's clearly wrong. The end of the reverse view is the begin of the underlying range, and you can't decrement the begin.

Instead, if we see the reverse view's end iterator as denoting a boundary, then it is natural for base() to return an iterator that refers to the same boundary, only the boundary's meaning has flipped: previously it denoted the boundary before the first element, and now -- after reverse-ness has been stripped -- it is the boundary after the last element. It is, however, the same boundary.

I don't think this nature of iterators is one that is widely appreciated, but I have found it leads to some confusion. I should probably write a blog post.

[schoedl]

But any non-const-iteratable view loses thread safety.

This is a fallacy. It is exactly as thread-safe as any other component in the standard library.

If you pass your filter range to two threads and they both call begin(), you have a race, or not? You think it is more important that begin()/end() is O(1) than filter being thread-safe. If you want that for your filter, that’s fine with me. But my trade-off, thread-safety over O(1) begin(), is a trade-off that is also reasonable to make. Anyone implementing such a filter should be able to use it with the rest of the standard library, rather than being non-conformant because it is not a View. And yes, this would require the library to document which adaptors (such as your reverse) have an operator++() with the same complexity as begin() of the underlying range, so people like me are warned.

[schoedl]

And regarding reverse, I think we agree that this is the canonical form of a reverse iterator loop:

auto const itBegin=begin();
for(auto it=end();it!=itBegin;){
  —it;
  ... *it ...
}

When inlining the current reverse adaptor, we get something like:

auto const itBegin=begin();
it1=end()
if(it1!=itBegin) it2=prev(it1);
while(it1!=itBegin){
  ... *it2 ...
  it1=it2;
  if(it2!=itBegin) —it2;
}

So reverse is not a zero-cost abstraction. Why? What are we missing?

We have the wrong abstraction. If we write the loop abstractly as:

auto border=begin();
auto const borderEnd=end();
while(border!=borderEnd){
  auto elem=border.elem_after();
  ... *elem ...
  border=elem.border_after();
}

reverse can be implemented as

end(){return base.begin();}
begin(){return base.end();}
border::elem_after(){return prev(m_it);}
elem::border_after(){return m_it;}

with no extra ifs, no two iterators and no access to base::begin() while iterating.

With iterators defined as they are today, the element after a border is a no-op, the element before a border requires an iterator decrement. But in a reverse adaptor, the element after a border requires a base iterator decrement, the element before a border is a noop. The reverse adaptor is a victim of the lack of symmetry in the definition of iterators.

[ericniebler]

If you pass your filter range to two threads and they both call begin(), you have a race, or not?

"If you pass [any standard library component] to two threads and they both [call non-const methods on it without external synchronization], you have a race, or not?" Yes, absolutely. Nothing about views differs in any way to anything else in the standard library.

So reverse is not a zero-cost abstraction.

Correct. Accessing every element of a range using reverse_iterator does twice as many iterator decrements.

Why? What are we missing?

We're not missing anything. It not the point of the iterator abstraction -- or any abstraction for that matter -- to provide exactly zero overhead for all use cases. Stepanov was well aware of this when he designed the STL. A good example is the iterators of std::deque. Segmented iterators and hierarchical algorithms would remove the overhead of the STL iterator model for segmented data structures, but they were not adopted. Why? Because it complicates the abstraction for too little benefit.

The reverse adaptor is a victim of the lack of symmetry in the definition of iterators.

The lack of symmetry is in the mathematical notion of a half-open range, not in iterators. I'll grant that the convention that the dereference operation, in returning the value of the element following the denoted boundary, is not symmetric, but that property comes from pointers. Your beef is with Dennis Ritchie, not Stepanov, and it's not something we can change by choosing a different iterator abstraction.

It is valid for you to say that reverse is not optimally efficient. It's valid for you to say that reverse is sufficiently important for your use case that you are abandoning the iterator abstraction. It is not valid for you to conclude that the iterator abstraction is inconsistent in what it denotes (it isn't) or that the abstraction is broken and should be abandoned because it doesn't provide exactly zero overhead for all possible use cases.

[schoedl]

I think we understand each other‘s arguments.

To be more constructive, can‘t we have two begin() functions, one being guaranteed O(1) and the other one not? This way, adaptors which query begin() while iterating could use the O(1) one, while others who merely get begin() once use the regular begin(). I would suggest begin() and an added tag, like begin(fast_t), allowing different const on either one.

This way, there would be compile time safety regarding the performance guarantees of adaptors. Ranges V3 can provide the fast version for all adaptors, but others like me making a different trade-off do not have to. This would not add undue complexity. Novice users could probably go for a long time without knowing the fast_t tag, and begin() implementations which are trivially O(1) have fast_t as default parameter.

And adaptors like join only need begin() for decrement, so join on a base with slow begin() would compile just fine for forward traversal.

[gnzlbg]

@schoedl

If you pass your filter range to two threads and they both call begin(), you have a race, or not?

While @ericniebler answered to this above I have to dig a bit deeper here:

What do you mean by pass? Do you mean storing the view on thread A, and passing references to the view to threads B and C so that they can concurrently mutate it? If so, none of what's being proposed here would be enough because we would need to store every pointer and every counter in all the adaptors behind atomics (or rwlocks/mutexes) for this to work, and this is a price that everybody would need to pay. The alternative being pursued here is that those who want to do this should just put the view behind a synchronization primitive.

If what you meant instead was about passing copies of the view to thread B and C, then that just works. Views are cheap to copy. You can create the view in thread A, call begin once, and just copy the view to threads B and C. Or what am I missing?

---

So what are the use cases where iteration would become quadratic with begin() or end() being linear?

It doesn't really matter. What matters is what's the complexity of begin and end. Is it linear? quadratic? Dependent on the range / view ?

For me at least the largest advantages of worst-case amortized O(1) are:

• easy to reason about: adding a new view adaptor to a pipeline does not make the complexity of begin/end blow up
• easy to teach: don't need to check the complexity of begin/end for each adaptor and keep that in mind

When you ask "Can't we have two begin functions" with subtly different call syntaxes (const vs non-const overloads) but widely different complexity guarantees (amortized O(1) vs O(N)), I'd hope that this change would be motivated in the context of how does that change affect reasoning about ranges as a whole.

This change destroys the two advantages mentioned above. What does the change buy us that make that worth it?

---

@ericniebler I found it very enlightening to think of reversing the range [a, b) as just (b, a] where the begin iterator points to [a in the first range but to (b in the reversed range. Thanks, you should definitely write a blog post.

[schoedl]

What do you mean by pass? Do you mean storing the view on thread A, and passing references to the view to threads B and C so that they can concurrently mutate it?

Just concurrently iterate, no mutation. You could make a copy, but then you may have to hold the functor by reference if it has non-trivial size, and your code needs to reason about whether to make a copy or not. I also have filtering containers in my library, a container aggregated into a lazy filter. They are very practical (try returning a lazily transformed vector from a function), but expensive to copy.

When you ask "Can't we have two begin functions" with subtly different call syntax but widely different complexity guarantees, you need to motivate that in the context of how does that change affect reasoning about ranges as a whole. Is that worth sacrificing being able to reason about range adaptor pipelines and teachability ?

We have differences either way, the world isn't as uniform as we want it to be. I find subtle race conditions occuring with some adaptors harder to teach or reason about than performance differences.

I do not want to impose this view on everyone, I just want to have the option to have that view within the specifications of the standard library. If you want to make all your adaptors O(1) begin and non-thread-safe, be my guest. But I favor thread safety over O(1) begin, based on the experience with our library.

[gnzlbg]

Are all the range adaptors in your library thread safe? If so, how do you implement view::generate ?

[schoedl]

No, they are not. And even if they would be, this is not a requirement I want to impose on everyone and everything. In particular, imposing a requirement such as O(1) begin()/end() or thread safety so early in the process while people are still learning how to use and also how to implement ranges is premature. Even with the C++20 standard finalized, users still won't be able to judge if we made the right choices because there are no adaptors in C++20 for them to try out. Let's put out a RangesWithAdaptors TS first, so we get multiple implementations and users taking ranges seriously and starting to use them first before cementing the fundamentals.

[gnzlbg]

I am confused.

I thought that you were arguing that by making begin/end amortized O(1), and thus non-const, we were sacrificing thread safety, which for you was important.

But now you are saying that thread-safety is not it. So what problems do you see in amortized O(1) non-const begin/end ? Or did I just completely misunderstood this and we all agreed that there weren't any? (I haven't had my coffee yet).

[schoedl]

I do not want to impose any blanket constraints on implementations at this point. For many ranges, such as slice, begin() is trivially O(1) and likewise, for many ranges, thread safety is trivial to achieve. But there are cases where there is a trade-off, such as for filter, which happens to be one of the most frequently used adaptors, so any decision there is important. I want to allow implementations to make this trade-off either way, to cater to certain use cases and allow building of experience.

[schoedl]

Just to add some data, here are the counts of various adaptors in our codebase:

tc::transform 1011
tc::filter 309
tc::reverse 60
tc::concat (join of variadic list of ranges) 85
tc::flatten (join of range of ranges) 47

[schoedl]

Looking through Ranges TS, where is the View concept used? Where does the implementation of the library as it is proposed depend on it?

[ericniebler]

Nowhere in the Ranges TS directly, but it is used in proposals that build on the TS, like P0789, "Range Adaptors and Utilities".

[schoedl]

I think there is a possiblity for filter with O(1) const begin() and O(1) copy by using index instead of iterator as the abstraction and doing the caching in the filter view ctor (but not again in the copy ctor). index'es are like iterators, but any operation gets supplied the index and its range. Iterators can easily be built on top by aggregating an index and a pointer to the range, so compatibility is no problem. Typically, the index of an adaptor is the index of the container (which for legacy containers is simply an iterator) at the very bottom of the adaptor stack, or a std::variant storing one of them in case of concat and index plus one of them for join. So as long as the container is not copied, view indices are trivially stable against copy and move, and copying/moving a filter view can simply copy the begin() cache. I will try an implementation in our codebase.

[gnzlbg]

@schoedl How would this index approach work for an InputRange/View, like view::generate(...) | view::filter(...)?

[schoedl]

Does filter need to cache begin() for input ranges? You cannot iterate twice anyway...

[gnzlbg]

Does filter need to cache begin() for input ranges?

Good question.

You cannot iterate twice anyway...

You can still take multiple begins to the same range. This code produces the output below today:

#include <iostream>
#include <range/v3/all.hpp>
auto perms() {
    return ranges::view::generate([x = 0]() mutable -> int{
        std::cout << "Calling generate: x = " << x << '\n';
        return x++;
    });
}
int main(int /*argc*/, char ** /*argv*/) {
    auto ps = perms();
    auto ps_f = ps | ranges::view::filter([](auto&& v) { return v % 2 != 0; }) | ranges::view::take(3);
    std::cout << "before begin\n";
    auto b = ranges::begin(ps_f);  // maybe cached? advances the range
    std::cout << "before end\n";
    auto e = ranges::end(ps_f);  // end not cached: not BidirectionalRange
    std::cout << "deref: " << *b << std::endl;
    // take another begin - don't know if this re-uses the cached value or 
    // or not (the first element in the range satisfies the filter so...): 
    std::cout << "begin deref: " << *ranges::begin(ps_f) << std::endl;
    std::cout << "loop\n";
    while (b != e) {
        std::cout << "x = " << *b << '\n';
        ++b;
    }
}

Prints:

Calling generate: x = 0
before begin
Calling generate: x = 1
before end
deref: 1
begin deref: 1
loop
x = 1
Calling generate: x = 2
Calling generate: x = 3
x = 3
Calling generate: x = 4
Calling generate: x = 5
x = 5
Calling generate: x = 6
Calling generate: x = 7

[ericniebler]

You can still take multiple begins to the same range.

begin is not required to be equality preserving for non-Forward ranges. You can't depend on it returning the same position every time you call it.

[ericniebler]

I think there is a possiblity for filter with O(1) const begin() and O(1) copy by using index instead of iterator as the abstraction and doing the caching in the filter view ctor (but not again in the copy ctor). index'es are like iterators, but any operation gets supplied the index and its range. Iterators can easily be built on top by aggregating an index and a pointer to the range, so compatibility is no problem.

I argued against position-based (or index-based) ranges in 2014 here:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html#position-based-ranges

This is rather late in the game to suggest a different set of basis operations, and it has never been clear to me that the benefits of such a design outweigh the costs. In particular, you need a different set of APIs to access a begin/end index (begin_pos/end_pos in James Touton's library), and iterators would no longer fit in registers.

[schoedl]

My original motivation for positions was to make adaptor stack iterators smaller. With purely iterators, iterator size grows linearly with stack height. With positions as implementational helper, iterator size is typically 2 words, independent of stack height. Any container can keep its (1-word) iterator, which will moonlight as position if someone (typically an adaptor) really wants one.

[ericniebler]

I think with the standardization of views, we can finally put this old issue to rest. Thanks all.

[tonyelewis]

Then let the GitHub record of this issue and of #254 stand as a permanent memento of those heady days in late-2015 / early-2016 when we were youthful and idealistic; when we exuberantly frolicked through the design-space of ranges; when we waved our views in the air like we just didn't care.

Thanks all.