iter::Flatten, FlatMap should return more precise size_hint and be TrustedLen when item type is an array

[adrian17]

If I understand correctly, presence of TrustedLen trait allows .collect::<Vec<_>>() to avoid reallocations, right?

In that case, given the following:

    #[derive(Clone, Copy)]
    pub struct Pixel(u8, u8, u8, u8);

    let pixels: Vec<Pixel> = vec![Pixel(1, 2, 3, 4); 10];
    let iter = pixels
        .iter()
        .flat_map(|p| [p.0, p.1, p.2, p.3]); // or: .map(|p| [p.0, p.1, p.2, p.3]).flatten();
    println!("{:?}", iter.size_hint());

    let v: Vec<u8> = iter.collect();

Since the type I map to has known const size ([u8; 4]), size_hint should be able to precisely return (40, Some(40)), and the iterator specialization should implement TrustedLen.
Currently, it returns (0, None). This means that to implement this function efficiently, I'd need to manually do Vec::with_capacity(pixels.len() * 4).

[the8472]

Currently, it returns (0, None).

It does a bit better than that. Collecting into a Vec first takes an element and only then queries the size_hint, which allows Flatten to give a better result than you get from its initial state.

rust/library/alloc/src/vec/mod.rs

Lines 2550 to 2562 in b5a2cce

	while let Some(element) = iterator.next() {
	let len = self.len();
	if len == self.capacity() {
	let (lower, _) = iterator.size_hint();
	self.reserve(lower.saturating_add(1));
	}
	unsafe {
	ptr::write(self.as_mut_ptr().add(len), element);
	// Since next() executes user code which can panic we have to bump the length
	// after each step.
	// NB can't overflow since we would have had to alloc the address space
	self.set_len(len + 1);
	}

But yes, we should be able to do better for array::IntoIter.

[adrian17]

It does a bit better than that. Collecting into a Vec first takes an element and only then queries the size_hint, which allows Flatten to give a better result than you get from its initial state.

Only a bit better:

    let _ = iter.next();
    println!("{:?}", iter.size_hint());

results in (3, None). It knows that the first flattened array has 4 elements, but not about further ones.

[SkiFire13]

But yes, we should be able to do better for array::IntoIter.

I don't think you can that much better for array::IntoIter. The problem is that the closure passed to flat_map could advance the array::IntoIter before returning it, so you can statically know only the upper limit, not the lower one.

However this doesn't apply when you directly return an array because they can't be advanced, so the adapter can know the exact number of elements they have.

[the8472]

Yeah, sorry, that's what I meant.