Iterators and Ranges: Comparing C++ to D to Rust

[Petar]

On Monday, 14 June 2021 at 12:33:37 UTC, IGotD- wrote:
> On Monday, 14 June 2021 at 01:48:18 UTC, Friendly Neighborhood 
> Weirdo wrote:
>> This is a talk from the 2021 c++now conference: 
>> https://www.youtube.com/watch?v=d3qY4dZ2r4w
>
> Interesting video. There is something that I'm kind of confused 
> about. The narrator in the video claims that in D popFront 
> doesn't consume the element. Is this true? When I do a 
> popFront, doesn't it consume the first element in an array for 
> example. Can someone clarify this?

In D, `.popFront()` advances the range to the next element, just 
like `++it` advances a C++ iterator. I think the presenter makes 
a point that D's `popFront` doesn't consume, because in C++'s STL 
the convention is to have `pop_{front,back}` as names of 
container member functions that indeed "consume" (remove, erase) 
the first/last element, i.e. the destructor of that element will 
be called.

So it's not an insight w.r.t D's design, but rather a 
clarification for the C++ audience which presumably expects 
`popFront` to be method on a container and not a range (view) of 
the container.

That said, the whether `poprFront` "consumes" is dependent on 
type of range. Most Phobos algorithms like 
[`map`](https://dlang.org/phobos/std_algorithm_iteration#map) and 
[`filter`](https://dlang.org/phobos/std_algorithm_iteration#filter) are range adaptors which won't change the structure of the container they're iterating (e.g. if the underlying range is a linked list, they can't really unlink elements from it).
However, some range types are actually "containers" themselves, 
and calling `popFront` on them would indeed consume their current 
element. For example:
* [`iota`](https://dlang.org/phobos/std_range#iota)
* [`generate`](https://dlang.org/phobos/std_range#generate)
* [`only`](https://dlang.org/phobos/std_range#only)
* [`recurrence`](https://dlang.org/phobos/std_range#.Recurrence)
* [`sequence`](https://dlang.org/phobos/std_range#.Sequence)
* RNG engines in 
[`std.random`](https://dlang.org/phobos/std_random)

> Also in Rust, next does consume the element. However, in Rust 
> you can iterate over references (which also automatically 
> borrows). So iterating over borrowed references does not 
> consume the underlying data structure.

I don't have much Rust experience, but my understanding is that 
Rust's `std::iter::Iterator.next(&mut self) -> 
Option<Self::Item>` design leans into its move-by-default, single 
mutable reference nature. I don't know if D's range design would 
be ergonomic or even admissible in a purely non-`unsafe` library 
in Rust. Seems like Rust's advantage is that is solves the 
iterator invalidation problem at the cost of more limited 
algorithmic expressiveness and generic power. Perhaps their 
"efficient, yet safe at all costs" design guideline basically 
paints them into a corner by essentially dictating this design. 
(I'm just speculating, I'm interested to to hear from people more 
experienced with Rust!)