[LLVMdev] [cfe-dev] C++11 reverse iterators (was C++11 is here)

[Francisco Jerez]

Chandler Carruth <chandlerc at google.com> writes:

> I suspect that at a certain point (soon) those of us who feel strongly
> about this should sit down if possible and hash this out either over lunch,
> beers, or a whiteboard. =D
>
> On Tue, Mar 4, 2014 at 9:26 PM, Duncan P. N. Exon Smith <
> dexonsmith at apple.com> wrote:
>
>> I agree.  Algorithms should be verbs.
>>
>> However, I disagree that range adaptors are algorithms.
>>
>> “reverse” sounds like an algorithm.  Consider, from the STL:
>>
>>     template <class Iterator> void reverse(Iterator F, Iterator L);
>>
>> I’d expect a range version of the algorithm to look like this:
>>
>>     template <class Range> void reverse(Range &R) {
>>       reverse(std::begin(R), std::end(R));
>>     }
>>
>> On the other hand, “reversed” sounds like an accessor, and I’d expect it
>> to look something like this:
>>
>
> I understand the point you're trying to make here, and how you would
> implement it, however I'm not persuaded this is the right design.
>
> First, while an in-place approach to the interface of range algorithms is
> one possibility, it has a fatal flaw: it is not composable. I want to be
> able to write something equivalent to "x = reverse(sort(slice(std::move(x),
> 1, 10)))" because this allows us to factor apart the different aspects of
> using ranges. It addresses the "<foo>_if" composition problem, the
> "<foo>_n" composition problem, etc. The solution requires us to bring value
> semantics to algorithms, what I think would be the best result of ranges in
> C++.
>

I strongly agree with this point of view. [Don't take my opinion too
seriously though, I'm merely a (very interested) external observer]

Being able to compose adaptors is a strong plus, as it solves the
problem of needing different variants of each algorithm with different
combinations of "_n", "_if", "_if_not", "_backward", etc. without
needing to split an expression that logically belongs together and
declare temporary containers that you only intend to use as "glue"
between different algorithms, whose type and size could be deduced by
the library itself if adaptors with value semantics were used as you
suggest.

> Second, I really don't want two different patterns, because I find it very
> hard to tell what is an algorithm and what isn't. Maybe "sliced" clearly
> isn't an algorithm, and "sort" clearly is, but "reversed" starts to blur
> the line. What about rotate? I have heard many argue that filter should be
> an accessor. If sort is an algorithm, than surely partition is. But
> partition is just the same as filter! I think it is all simpler if these
> all follow the same fundamental pattern.
>

I completely agree that we'd be better off with just one pattern.  I
think that the "adaptor" pattern (as it is implemented by boost::range,
i.e. as an expression template with range-like semantics that transforms
a given source range) is the way to go in most cases, because it
alleviates the overhead of temporary object allocation, and it's a neat
way to decouple the definition of an adaptor from the container type you
ultimately intend to assign its contents to.  E.g. it's more concise and
more efficient to do something like:

| std::deque<float> result = map(minus<float>(), xs, reverse(ys));

and have things directly calculated into the deque (if that's what you
want to assign the result to) than to pick a preferred container type as
the return type for every algorithm and copy things unnecessarily when
doing composition.

Quite often you can replace the use of a mutating algorithm with the use
of an adaptor followed by an assignment.  Even some traditionally
mutating algorithms like sort() can be implemented reasonably as
adaptors without much loss of efficiency by leveraging C++11's move
semantics.

> Third, this is *exactly* what I mean that we don't yet know what ranges
> look like in C++. Whatever we end up with, I think we should be prepared to
> change it based on experience and based on the discussions that go on in
> the committee. My hope is that we can try out some of these approaches and,
> if they work, also contribute to that discussion.

There's quite a bit of prior art, starting with boost::range.  In Mesa's
Clover project (which was written in C++11 from the start) we use a
utility library [1] that was greatly influenced by boost::range, but it
attempts to make more extensive use of some C++11 features.  Among other
things, it takes into account the rvalue-ness of its arguments properly
to allow code like:

| auto result = map(f, automatically_allocated_container_or_nested_adaptor(...));
| //...
| for (auto x : result) // Crash, because the nested range went out of
|                       // scope and it's been destroyed already.
|    //...

by moving range arguments which are passed as rvalue references into an
internal copy inside the adaptor object.

It also provides variadic variants of some algorithms, e.g. there's a
variadic map() that takes an n-argument functor along with n different
range arguments which are iterated in parallel (which mostly solves the
parallel iteration problem discussed earlier in this thread in a
convenient way), a variadic zip() that combines n ranges as a range of
n-tuples, variadic all_of(), any_of(), etc.

I admit that in some respects it's very sketchy compared to
boost::range, but it would be easy to relicense it under the LLVM
license if someone finds it useful as starting point.

[1] http://cgit.freedesktop.org/mesa/mesa/tree/src/gallium/state_trackers/clover/util

> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 229 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140305/1698a27e/attachment.sig>