[PATCH] libstdc++: Memoize {drop,drop_while,filter,reverse}_view::begin

[Jonathan Wakely]

On 27/02/20 14:26 -0500, Patrick Palka wrote:
>On Wed, 26 Feb 2020, Patrick Palka wrote:
>
>> On Tue, 11 Feb 2020, Patrick Palka wrote:
>>
>> > This patch adds memoization for these four views so that their begin() has the
>> > required constant time amortized complexity.
>> >
>> > In the general case we use std::optional to cache the result.  When the
>> > underlying range is a random_access_range then we store the cache as an offset
>> > from the beginning of the range, which should be more compact.  And when the
>> > underlying iterator is not copyable, then we completely disable the cache.
>> >
>> > Using std::optional in the cache is not ideal though because it means that the
>> > cache can't be utilized during constexpr evaluation.  If instead of
>> > std::optional we store a separate flag to denote an empty cache then we'll be
>> > able to use the cache during constexpr evaluation at the cost of a extra byte or
>> > so.  I am not sure which design to settle on.
>>
>> Here's v2 of this patch which uses the new helper
>> __detail::__maybe_empty_t and provides a more descriptive commit
>> message.  It also refines the constraints on the partial specializations
>> of _CachedPosition.
>>
>> -- >8 --
>>
>
>Here's v3 of this patch which takes advantage of the fact that
>value-initialized forward iterators can be compared to.  This means we
>can cache the bare iterator instead of having to use std::optional or
>needing an external flag denoting the empty state of the cache, which is
>both optimal space-wise and constexpr safe!

Nice. OK for master, thanks.