tcbrindle / flux

A C++20 library for sequence-orientated programming
https://tristanbrindle.com/flux/
Boost Software License 1.0
472 stars 29 forks source link

Remove caching from filter, drop and drop_while #120

Closed tcbrindle closed 1 year ago

tcbrindle commented 1 year ago

This might be a bit controversial...

The filter, drop and drop_while adaptors, when operating on multipass sequences, cache the first cursor: that is, the first call to first() does a (potentially) O(N) pass over the data, but subsequent calls to first()returns the cached cursor. I originally did this for the same reason that Ranges does it: I wanted first() to always be (amortised?) O(1).

As time goes on though, I'm less certain that this was the right choice. We definitely need is_last() to be O(1); I'm very sure we also want last() to be O(1) for bounded sequences. But I'm less convinced about first(). After all, getting the second element with inc() can never be constant-time, so why do we special-case getting the first one?

Various later Flux adaptors don't do caching where the Ranges versions do, and there seems to be little ill effect. Also, the internal iteration implementation of filter has never used the cache, and I don't think anyone has ever noticed.

Getting rid of caching allows const-iteration, which is useful for such fundamental adaptors, and stops people needing to reach for mut_ref. It also makes life easier for the optimiser.

codecov[bot] commented 1 year ago

Codecov Report

Patch coverage: 100.00% and project coverage change: -0.01% :warning:

Comparison is base (16cd229) 97.58% compared to head (5e4c62e) 97.58%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #120 +/- ## ========================================== - Coverage 97.58% 97.58% -0.01% ========================================== Files 66 66 Lines 2280 2278 -2 ========================================== - Hits 2225 2223 -2 Misses 55 55 ``` | [Files Changed](https://app.codecov.io/gh/tcbrindle/flux/pull/120?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tristan+Brindle) | Coverage Δ | | |---|---|---| | [include/flux/op/drop.hpp](https://app.codecov.io/gh/tcbrindle/flux/pull/120?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tristan+Brindle#diff-aW5jbHVkZS9mbHV4L29wL2Ryb3AuaHBw) | `100.00% <100.00%> (ø)` | | | [include/flux/op/drop\_while.hpp](https://app.codecov.io/gh/tcbrindle/flux/pull/120?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tristan+Brindle#diff-aW5jbHVkZS9mbHV4L29wL2Ryb3Bfd2hpbGUuaHBw) | `100.00% <100.00%> (ø)` | | | [include/flux/op/filter.hpp](https://app.codecov.io/gh/tcbrindle/flux/pull/120?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tristan+Brindle#diff-aW5jbHVkZS9mbHV4L29wL2ZpbHRlci5ocHA=) | `100.00% <100.00%> (ø)` | | ... and [2 files with indirect coverage changes](https://app.codecov.io/gh/tcbrindle/flux/pull/120/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tristan+Brindle)

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.