Reversing an array

help
1

Hmmm..

      #[test]
      fn invert_array(){

        let m1: [i32; 5] = [1,2,3,4,5];
        let m2 : [i32; 5] = m1.iter().rev().collect();

        assert_eq!([5,4,3,2,1], m2);

      }

This looks good to me at first sight, I wonder why it doesn't compile?

value of type [i32; 5] cannot be built from std::iter::Iterator<Item=&i32>

I tried using a Vec, but with the same results. Thanks in advance!

2

You have an iterator of references &i32, but you need an iterator of values i32 to build the array, and you have to build a Vec because the compiler doesn't know how many elements the iterator will produce. There's two ways to do that:

#[test]
fn invert_array_copy() {
    let m1: [i32; 5] = [1, 2, 3, 4, 5];
    let m2: Vec<i32> = m1.iter().copied().rev().collect();

    assert_eq!(vec![5, 4, 3, 2, 1], m2);
}

#[test]
fn invert_array_move() {
    let m1: Vec<i32> = vec![1, 2, 3, 4, 5];
    let m2: Vec<i32> = m1.into_iter().rev().collect();

    assert_eq!(vec![5, 4, 3, 2, 1], m2);
}

(Playground)

2 Likes
3

Another option:

let m1: [i32; 5] = [1, 2, 3, 4, 5];
let mut m2 = m1;
m2.reverse();
10 Likes
4

Also, as to why you can't construct a [i32; 5] from the iterator, even though the iterator yields from a [i32; 5], doing that would require const generics so as to propagate that type information.

5

the compiler doesn't know how many elements the iterator will produce

Oh, I see, gotcha. Thanks!

6

This is one of the few places where const-generics looks like it could help, but it can't. Even with const-generics you could exhaust an iterator beforehand, so it may produce fewer than the required number of elements.

7

Hypothetically, could we not have a const equivalent to ExactSizeIterator?

2 Likes
8

While that would be lovely, @RustyYato is correct, how would the const equivalent work if I tried to do this:

trait ConstIterator<const Size: usize> {
   ///...
}
let x = [0, 1, 2, 3];
let mut y = x.iter();
y.next();
let z: [&i32; 4]  = y.collect::<_>();

The tracking of calls to next could not change the type of the iterator, since the const Size is part of the type. Additionally, the compiler probably couldn't solve whether or not the iterator will be called prior to collecting.

2 Likes
9

Technically, this can be solved with abstraction based on another trait.

pub trait ConstIterator: IntoIterator {
    const SIZE: usize;

    fn collect<T>(self) -> T
        where T: FromConstIterator<Size=Self::Size>;
    fn map...
}

It's not an iterator directly but IntoIterator so can be converted into Iterator with dynamic length. But I think this kind of solutions are not explored well so we should experiment on crates.io first when we have const generics.

3 Likes
10

I think that meanwhile one can just implement fallible version of FromIterator and collect into arrays with it:

use std::mem::MaybeUninit;
use std::mem::drop;

trait FallibleFromIterator: Sized {
    type Item;
    fn fallible_from_iter<I>(iter: I) -> Option<Self>
        where I: IntoIterator<Item=Self::Item>;
}

const SIZE: usize = 5;

impl<T> FallibleFromIterator for [T; SIZE] {
    type Item = T;

    fn fallible_from_iter<I>(iter: I) -> Option<Self>
        where I: IntoIterator<Item=Self::Item>
    {
        let mut ret = MaybeUninit::<[T; SIZE]>::uninit();
        let mut init_count = 0;
        let mut ret_ptr = ret.as_mut_ptr().cast::<T>();
        for item in iter.into_iter() {
            unsafe { ret_ptr.write(item) };
            ret_ptr = unsafe { ret_ptr.add(1) };
            init_count += 1;
            if init_count == SIZE {
                break;
            }
        }
        let init_count = init_count;
        if init_count < SIZE {
            for _ in 0..init_count {
                drop(unsafe { ret_ptr.read() });
                ret_ptr = unsafe { ret_ptr.sub(1) };
            }
            None
        } else {
            Some(unsafe { ret.assume_init() })
        }
    }
}

trait FallibleCollectExtension {
    type Item;

    fn collect_fallible<A>(self) -> Option<A>
        where A: FallibleFromIterator<Item=Self::Item>;
}

impl<T, I> FallibleCollectExtension for I
    where I: Iterator<Item=T>
{
    type Item = T;

    fn collect_fallible<A>(self) -> Option<A>
        where A: FallibleFromIterator<Item=Self::Item>
    {
        A::fallible_from_iter(self)
    }
}

fn main() {
    let m1: [i32; 5] = [1, 2, 3, 4, 5];
    let m2: [i32; 5] = m1.iter().copied().rev().collect_fallible().unwrap();
    eprintln!("{:?}", m2);
    let mut iter = m1.iter().copied().rev();
    iter.next();
    let m3: Option<[i32; 5]> = iter.collect_fallible();
    eprintln!("{:?}", m3);
}

Without constant generics you will have to implement FallibleFromIterator for each array size you care about though. And you still have to do something with the fact that there is no IntoIterator implementation on arrays (which is why I had copied() in the example), only on references, so you only get &T or &mut T out of them and not T.

11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.