I know how to construct a new empty Vec<T> with specified capacity, using the with_capacity method:
let mut vec = Vec::with_capacity(10);
I have a 2D array data. How can I do the same with a nested vector?
The outer can't be empty, it should contain the empty vectors.
Otherwise you could define your own 2D matrix with few methods. Or use one from crates.
4 Likes
If rows have the same width, consider:
let vec = Vec::with_capacity(width * height);
vec[x + y * width]
(That's not a 2D vector type, but that's a way to represent 2D data as one contiguous block. It avoids a level of indirection and likely improves cache locality, so depending on the nature of the problem it may be faster)
6 Likes
Your answer comes up with an assumption that the provided capacity is used to calculate a simple size on the heap and nothing else happens. I've checked it out and you are right 
EDIT: I thought that we are talking about Vector of Vectors where you can access the items like this: vec[x][y], but you are just simulating fix width and various hight 2-dimensional Vector by using 1-dimensional Vector.
I looked at how the
Vec::with_capacity(capacity: usize) -> Vec<T>
operates to see that internally it uses
RawVec::allocate_in(cap: usize, zeroed: bool, mut a: A) -> Self
and inside of it the following is used to calculate capacity
let alloc_size = cap.checked_mul(elem_size).unwrap_or_else(|| capacity_overflow());
on the line 94, so it is a simple multiplication of cap (capacity provided to Vec::with_capacity) and elem_size (size of the Vec element calculated as mem::size_of::<T>();)
And finally the RawVec as a buffer of Vec is constructed and it doesn't seems to me that it would do anything more structural about the capacity then just allocating the space:
RawVec {
ptr: ptr.into(),
cap,
a,
}
But the manipulation with the 2-dimensional vector can not work as you've stated, I've tested it to be sure.
The following example works for me just fine:
let width = 8;
let height = 8;
let mut vec: Vec<Vec<i32>> = Vec::with_capacity(width * height);
// Filling the vector.
vec.push(vec!(2, 4));
vec.push(vec!(3, 5, 7));
// Modifying some positions.
vec[0][0] = 20;
vec[1][0] = 1;
// Getting some output to see how it works.
println!("Vector size = {}", vec.len());
println!("Vector at [0, 0] = {}", vec[0][0]);
println!("Vector at [0, 1] = {}", vec[0][1]);
println!("Vector at [1, 0] = {}", vec[1][0]);
println!("Vector at [1, 1] = {}", vec[1][1]);
println!("Vector at [1, 2] = {}", vec[1][2]);
1 Like
This doesn't allocate space for a 2D vector, it only allocates space for the top level vector. The inner vectors don't get space allocated for them, in fact they don't even exist.
In @kornel's example, the type of vec is Vec<_>, we don't know anything about what is stored in the Vec<_>. He is allocated space for the Vec and then treating it as if it was a 2D array.
If you don't care about if the Vec<_> is empty too much, you could use vec![vec![0; width]; height] or vec![vec![0; height]; width]. This will allocate exactly as much space as needed to store all of the items.
1 Like
Yes, you are right 
I focused on the method Vec::with_capacity(capacity: usize) -> Vec<T> and then jumped to quick conclusions with my example, but obviously every new vector allocation (like the vec![...]) creates a new vector with its own space on heap.
It is probably a good idea to look for some crate for n-dimensional vectors to inspect how they are dealing with the problem if they even allow initial allocation with capacity. They migh quite likely not use standard vectors internally, but rather optimised solution for n-dimensional usecases.
If you know for sure how big the array is, you can use statically sized arrays instead of vectors for it.
If you want to use standard vectors to have the dynamic nature of it present, probably something like the following code could be of help:
let width = 8;
let height = 8;
let mut vec: Vec<Vec<i32>> = Vec::with_capacity(height);
for _ in 0..height {
vec.push(Vec::with_capacity(width));
}
println!("Vector size = {}", vec.len());
println!("Vector size = {:?}", vec);
EDIT: from 0..width to 0..height
should be 0..height not 0..width in for loop, but yes. Popular n-dimensional vector crates may use quite a bit of unsafe in the name of performance, the most popular ones are nalgebra and ndarray.
https://crates.io/crates/nalgebra
https://crates.io/crates/ndarray
How about this:
let mut vec: Vec<Vec<i32>> = std::iter::repeat(Vec::with_capacity(width)).take(height).collect();
2 Likes
That clones an empty Vec, giving a Vec with capacity 0, so doesn't do what was requested: Rust Playground
1 Like
...am I the only one who thinks there should be a way to pre-allocate an empty nested vector?
Do the same thing using repeat_with instead of repeat.
Honest opinion? Yes. If you're worried about performance of allocations, you shouldn't be using a nested vector.
There are exceptions to this rule, but for those, repeat_with should be enough.
3 Likes
Please let me know what I should use, without using an external crate, thanks.
If you're that worried about performance, I doubt there is much you can do without an external library or handrolling a wrapper around a flat Vec<T>. Feel free to try anyways and benchmark it, but I suspect the difference will be peanuts.
I have opted to handroll small types like this for private use in a number of projects; any given project usually only needs a very small subset of the API that such a type is capable of providing.
If you must use Vec<Vec<_>>, the preferred method is to use collect to produce each inner vector, rather than pushing elements to them. If done on Iterators of known size (i.e. you don't use e.g. filter or flat_map), the resulting vectors will be preallocated to the right size on creation. Barring that, you can use repeat_with.
1 Like