`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.

[ericniebler]

No compiler will tell you that you are using invalidated input iterators:

std::istream_iterator<int> i1{std::cin};
auto i2 = i1;
++i1; // i2 made invalid here
int x = *i2; // use of invalid iterator here

This is the nature of input iterators, and has been since C++98. Is it easy to misuse them? You betcha.

[gnzlbg]

Are you really considering this or is it more like a fun excercise?

I mean, when a user passes a view by const&, what are the chances that "the user intends to degrade the view category to input so that the const view can be iterated" taking into account our experience about how error prone input ranges already are?

I would assume close to none. Iff somebody really needs this, they can implement their own view::input range adaptor that degrades any view to an InputView so that they can happily shoot themselves in the foot.

Maybe I am missing the context but if the only case where this matters is when ensuring thread-safety, I'd rather provide a view::synchronized range-adaptor that locks range accesses with a mutex while preserving the range interface.

[ericniebler]

Are you really considering this or is it more like a fun excercise?

Ha! OK, you make a good point. I think you talked me out of it.

Iff somebody really needs this, they can implement their own view::input range adaptor that degrades any view to an InputView so that they can happily shoot themselves in the foot.

I kinda like this idea.

[pfultz2]

I've been kicking around an idea where views with mutable state are const-iterable but their category degrades to Input.

That seems backwards. If the views are just caching a value, I don't see the problem with the const version always recomputing it. In most cases, this would be faster than dealing with atomic synchronization.

[gnzlbg]

@pfultz2 IIUC the problem with recomputing it is that then the complexity of some "fundamental" operations (begin, end, size, ...) changes from amortized O(1) to O(N).

[h-2]

One could make all the views in the regular namespace never be const-iterable at all, but then also provide an extra namespace (view::const:: or const_view:: ?) whose view implementations are guaranteed to be const-iterable in standard STL manner (thread-safe) – either because they are anyway, or because locking / atomic operations are used. In line with container behaviour one could also make these views always have reference types that resolve to const & or copy so that the underlying data is never modified.

It does mean more implementation work, but it would provide a solution for the many STL users expecting container-like behaviour without encumbering the original versions of the the views. It would also be very easy to document this and much easier to provide diagnostic to the user when a regular view is mis-used.

It has the drawback that people might more often use the const-version when they should actually just use && in their interface instead of const &, but at least there would be some possibility to use this in const contexts and maybe even constexpr.

[schoedl]

I am not opposed to begin()/end() being non-const in general. It is certainly better than locking. But any non-const-iteratable view loses thread safety. I would not give this away lightly, in particular for frequent use cases.

Use cases in our fairly generic (as in: not special) codebase are dominated by transform, filter and slice, often stacked on top of each other. reverse happens, but much rarer. I can get hard numbers.

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

I see reverse as the most frequent one. reverse needs to check for begin() to know if on increment to assign the second iterator stored inside the reverse iterator, because if you are incrementing into reverse::end(), this would otherwise access begin()-1.

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.

In contrast to filter, transform and slice, which are pretty natural to implement, reverse is an ugly duckling anyhow because of its iterator having to store two iterators internally, so I have little qualms making it uglier still, as opposed to making filter uglier.

Reverse being so strange is actually rooted in the fact that iterators describe both boundaries and elements. It could be remedied by making these two concepts distinct, see my talk [https://www.think-cell.com/en/career/talks/], first thing on the page. This won't happen overnight, but since this is in my eyes the right, principled way out for implementing a clean reverse adaptor, we should not break filter's thread safety for the benefit of the weird reverse we have now.

[tonyelewis]

Tagging connection to #254.

[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.