> Never worked in Rust though so wondered if the iterator api had some weird optional notion of size that could be utilised throughout the chain.

Fwiw, this does exist: [Iterator::size_hint] (https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...)

It seems `map` should have less restrictive semantics (specifically ordering) than `for`, does that allow more optimization? I don't know much about Rust internals.

Reading the godbolt it looks like for the push loop llvm is unable to remove the `grow_one` capacity check after every push. Becaue of this the Vec could possibly reallocate after every push meaning it can't auto vectorize.

It's a little bit surprising to me that LLVM can't eliminate the grow_one check. It looks like there's a test ensure it's not needed in the easier case of vec.push(vec.pop()) [0]. With the iterator the optimization is handled in the standard library using specialization and TrustedLen[1].

[0]: https://github.com/rust-lang/rust/blob/master/tests/codegen/...

[1]: https://github.com/rust-lang/rust/blob/d4025ee454169fbd22f57...

Yep that can be used for pre allocating the Vec like in the `with_capacity` example

That's not accurate, it can be used while consuming an Iterator and, depending on the implementation, be used to guide the consumer during runtime. The stdlib likely is not doing this but the API very much allows advanced behavior. We, e. G., used this for some part of a query engine in a course in uni to guide algorithm choice for operators.

> The stdlib likely is not doing this

Um, yes it is, extensively?

SpecFromIterNested is a specialization trait for alloc::vec::Vec's FromIterator which handles both the TrustedLen and ordinary Iterator scenarios

For an ordinary Iterator, it calls next() once to check this Iterator isn't done, if it's done, we can just give back a Vec::new() since that's exactly what was needed. Otherwise, it then consults the hint's low estimate, and it pre-allocates enough capacity on that basis, unless it's lower than Vec's own guess of the minimum worthwhile initial capacity.

For Iterators which impl TrustedLen (ie promise they know exactly how many items they yield) it instead checks the upper end of the hint, to see if it's None, if it is the iterator knows it's too big to store in memory, we should panic. Otherwise though we can Vec::with_capacity

    let v: Vec<_> = (0..23456).collect();

... will just give you a Vec with the 23456 values from zero to 23455 inclusive, it won't waste time growing that Vec because it knows from the outset that there are going to be exactly 23456 items in the Vec.

> Um, yes it is, extensively?

Sorry, that was a mistake on my part. I did not see it explicitly in any of the code. Thank you for pointing out in detail where the stdlib uses this.

Interesting! Thanks.

If I recall correctly, there was actually some unstable specialisation in the std library that allowed reusing the backing storage if you do an `into_iter()` and then a `collect()`.