Объединение вектора векторов строк

Question

Я пытаюсь написать функцию, которая получает вектор векторов строк и возвращает все векторы, объединенные вместе, т. Е. Возвращает вектор строк.

Лучшее, что я мог сделать до сих пор было следующее:

fn concat_vecs(vecs: Vec<Vec<String>>) -> Vec<String> { 
    let vals : Vec<&String> = vecs.iter().flat_map(|x| x.into_iter()).collect(); 
    vals.into_iter().map(|v: &String| v.to_owned()).collect() 
} 

Однако, я не доволен этим результатом, потому что кажется, я должен быть в состоянии получить Vec<String> от первого collect вызова, но почему-то я не могу понять, как это сделать.

Мне еще больше интересно выяснить, Почему точно возвращается тип collect is Vec<&String>. Я попытался вывести это из документации API и исходного кода, но, несмотря на все мои усилия, я даже не мог понять подписи функций.

Итак, позвольте мне попытаться проследить типы каждого выражения:

- vecs.iter(): Iter<T=Vec<String>, Item=Vec<String>> 
- vecs.iter().flat_map(): FlatMap<I=Iter<Vec<String>>, U=???, F=FnMut(Vec<String>) -> U, Item=U> 
- vecs.iter().flat_map().collect(): (B=??? : FromIterator<U>) 
- vals was declared as Vec<&String>, therefore 
     vals == vecs.iter().flat_map().collect(): (B=Vec<&String> : FromIterator<U>). Therefore U=&String. 

Я предполагаю, что выше, что тип inferencer способен понять, что U=&String на основе типа vals. Но если я дам Выражение явных типов в коде, это компилируется без ошибок:

fn concat_vecs(vecs: Vec<Vec<String>>) -> Vec<String> { 
    let a: Iter<Vec<String>> = vecs.iter(); 
    let b: FlatMap<Iter<Vec<String>>, Iter<String>, _> = a.flat_map(|x| x.into_iter()); 
    let c = b.collect(); 
    print_type_of(&c); 
    let vals : Vec<&String> = c; 
    vals.into_iter().map(|v: &String| v.to_owned()).collect() 
} 

Очевидно, что U=Iter<String> ... Пожалуйста, помогите мне прояснить этот беспорядок.

EDIT: благодаря bluss' намек, я был в состоянии достичь одного collect следующим образом:

fn concat_vecs(vecs: Vec<Vec<String>>) -> Vec<String> { 
    vecs.into_iter().flat_map(|x| x.into_iter()).collect() 
} 

Я понимаю, что с помощью into_iter я передать право собственности vecs на IntoIter и далее вниз по вызову цепь, которая позволяет мне избежать копирования данных внутри лямбда-звонка, и поэтому - магически - система типа дает мне Vec<String>, где раньше всегда давали мне Vec<&String>. Хотя, конечно, очень здорово видеть, как концепция высокого уровня отражается в работе библиотеки, я бы хотел, чтобы я знал, как это достигается.

EDIT 2: После трудоемкого процесса догадок, глядя на API Docs и используя this method расшифровать типы, я их полностью аннотированный (без учета времени жизни):

fn concat_vecs(vecs: Vec<Vec<String>>) -> Vec<String> { 
    let a: Iter<Vec<String>> = vecs.iter(); 
    let f : &Fn(&Vec<String>) -> Iter<String> = &|x: &Vec<String>| x.into_iter(); 
    let b: FlatMap<Iter<Vec<String>>, Iter<String>, &Fn(&Vec<String>) -> Iter<String>> = a.flat_map(f); 
    let vals : Vec<&String> = b.collect(); 
    vals.into_iter().map(|v: &String| v.to_owned()).collect() 
} 

Answer 1

Я думаю, about: почему вы используете iter() на внешнем vec, но in_iter() на внутренних vecs? Использование into_iter() действительно имеет решающее значение, поэтому нам не нужно копировать сначала внутренние векторы, а затем строки внутри, мы просто получаем право собственности на них.

Мы можем написать это точно так же, как суммирование: объединить векторы два на два. Поскольку мы всегда повторно используем содержимое & содержимого одного и того же вектора накопления, эта операция представляет собой линейное время.

Чтобы свести к минимуму время, затрачиваемое на увеличение и перераспределение вектора, вычислите необходимое пространство впереди.

fn concat_vecs(vecs: Vec<Vec<String>>) -> Vec<String> { 
    let size = vecs.iter().fold(0, |a, b| a + b.len()); 
    vecs.into_iter().fold(Vec::with_capacity(size), |mut acc, v| { 
     acc.extend(v); acc 
    }) 
} 

Если вы хотите клонировать все содержимое, уже есть способ для этого, и вы бы просто использовать vecs.concat() /* -> Vec<String> */

---

Подход с .flat_map прекрасно, но если вы не» t хотите снова клонировать строки, вы должны использовать .into_iter() на всех уровнях: (x - Vec<String>).

vecs.into_iter().flat_map(|x| x.into_iter()).collect()

Если вместо этого вы хотите клонировать каждую строку, которую вы можете использовать это: (Измененная .into_iter() к .iter() так x здесь является &Vec<String> и оба метода фактически приводят то же самое!)

vecs.iter().flat_map(|x| x.iter().map(Clone::clone)).collect()