# How to construct a new empty Vec<Vec<T>> with specified capacities

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 = 20;
vec = 1;

// Getting some output to see how it works.
println!("Vector size = {}", vec.len());
println!("Vector at [0, 0] = {}", vec);
println!("Vector at [0, 1] = {}", vec);
println!("Vector at [1, 0] = {}", vec);
println!("Vector at [1, 1] = {}", vec);
println!("Vector at [1, 2] = {}", vec);
``````
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.

``````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