Why C++ ranges “transform -> filter” calls transform twice for values that match the filter’s predicate?

by

why can’t filter just pass the value to whoever is after it in the pipeline as soon as it finds a match?

Because in the iterator model, positioning and accessing are distinct operations. You position an iterator with ++; you access an iterator with *. These are two distinct expressions, which are evaluated at two distinct times, resulting in two distinct function calls that yield two distinct values (++ yields an iterator, * yields a reference).

A filtering iterator, in order to perform its iteration operation, must access the values of its underlying iterator. But that access cannot be communicated to the caller of ++ because that caller only asked to position the iterator, not to get its value. The result of positioning an iterator is a new iterator value, not the value stored in that iterated position.

So there’s nobody to return it to.

You can’t really delay positioning until after accessing because a user might reposition the iterator multiple times. I mean, you could implement it that way in theory by storing the number of such increments/decrements. But this increases the complexity of the iterator’s implementation. Especially since resolving such delayed positioning can happen through something as simple as testing against another iterator or sentinel, which is supposed to be an O(1) operation.

This is simply a limitation of the model of iterators as having both position and value. The iterator model was designed as an abstraction of pointers, where iteration and access are distinct operations, so it inherited this mechanism. Alternative models exist where iteration and access are bundled together, but they’re not how standard library iteration works.

More Related Contents:

  1. Can I take the address of a function defined in standard library?
  2. What exactly are C++ modules?
  3. Will specialization of function templates in std for program-defined types no longer be allowed in C++20?
  4. Can class template constructors have a redundant template parameter list in c++20
  5. Class type non-type template parameter initialization does not compile
  6. non-defaulted operator doesn’t generate == and != in C++20
  7. Why do we require requires requires?
  8. How to use c++20 modules with CMake?
  9. Why does aggregate initialization not work anymore since C++20 if a constructor is explicitly defaulted or deleted?
  10. Which headers in the C++ standard library are guaranteed to include another header?
  11. What is `constinit` in C++20?
  12. Will consteval functions allow template parameters dependent on function arguments?
  13. Does constraint subsumption only apply to concepts?
  14. C++20 constexpr vector and string not working
  15. C++ Concept that requires a member function with an OutputIterator as parameter
  16. How to use std::views::transform on a vector?
  17. Ramifications of C++20 requiring two’s complement
  18. Why is volatile deprecated in C++20?
  19. Comparing 3 modern c++ ways to convert integral values to strings
  20. Why default three-way operator (spaceship ) generates equality operator (==) and user define three-way operator not?
  21. Is C++20 ‘char8_t’ the same as our old ‘char’?
  22. Range TS idioms and the mysterious auto &&
  23. asio How to change the executor inside an awaitable?
  24. Why does Clang 12 refuse to initialize aggregates in the C++20 way?
  25. Is lambdification of a concept an improvement or bad practice?
  26. Why must a std::ranges::filter_view object be non-const for querying its elements?
  27. How to use C++20’s likely/unlikely attribute in if-else statement
  28. Will consteval allow using static_assert on function arguments?
  29. if constexpr – why is discarded statement fully checked?
  30. if constexpr – why is discarded statement fully checked?

Leave a Comment