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.