Rust - Flattening nested vectors: Vec> into Vec

In the Rust programming language, a common occurrence when handling complex data structures is dealing with nested vectors, specifically a Vec<Vec<T>>. This structure represents a vector of vectors, allowing for the representation of complex multi-dimensional data. However, working with such nested structures can be cumbersome, and there are many situations where you might prefer a single, flattened vector, Vec<T>. In this article, we'll explore how to efficiently flatten these nested vectors in Rust.

Understanding Nested Vectors

Nested vectors are essentially vectors that contain other vectors as their elements. For example, Vec<Vec<T>> can model a matrix or a grid. Here’s a simple representation:

let nested_vec: Vec<Vec<i32>> = vec![
    vec![1, 2, 3],
    vec![4, 5, 6],
    vec![7, 8, 9],
];

This creates a 3x3 matrix, but if you want all elements within a single flat Vec<i32>, you'll need to flatten it.

Using Iterators

The most idiomatic way to flatten a vector in Rust is by using iterators. The flat_map() function is particularly useful for this purpose. Here's how you can flatten the matrix above:

let flattened: Vec<i32> = nested_vec.iter()
    .flat_map(|inner_vec| inner_vec.iter())
    .cloned()
    .collect();

Here's a breakdown of what happens:

• iter(): Returns an iterator over the nested vector.
• flat_map(): Applies a closure that maps each inner vector and flattens the result into a single iterator.
• cloned(): Clones each element so that it can be collected into a new Vec.
• collect(): Collects the iterator into a Vec<i32>.

Using Extend

Another approach involves using the extend() method, which extends a vector by appending elements from an iterator or another vector:

let mut result: Vec<i32> = Vec::new();
for inner_vec in &nested_vec {
    result.extend(inner_vec);
}

In this example, we create a mutable result vector and extend it with the contents of each inner_vec.

Comparison and Performance Considerations

Performance-wise, using iterators is often preferred due to its succinctness and flexibility. However, using extend() and a loop might be slightly more performant if you have tight loops where reducing allocation is crucial. Let's compare the two methods:

use std::time::Instant;
let start = Instant::now();
// Method using iterators
let _: Vec<i32> = nested_vec.iter()
    .flat_map(|x| x.iter())
    .cloned()
    .collect();
println!("Iterators took: {} ms", start.elapsed().as_millis());

let start = Instant::now();
// Method using extend
let mut result = Vec::new();
for inner in &nested_vec {
    result.extend(inner);
}
println!("Extend took: {} ms", start.elapsed().as_millis());

Note: When benchmarking in Rust, ensure to use complex data with more iterations for impactful results.

Conclusion

Flattening a Vec<Vec<T>> into a Vec<T> in Rust can be efficiently achieved using iterators with flat_map() or by using the extend() method within a loop. Both techniques have their own scenarios where they can be optimal. Overall, Rust's powerful iterator and collection APIs make these tasks concise and performant.