CODEWITHSUNDEEP
rustdeque
ethicnology
ethicnology

Reputation: 606

How to correctly use VecDeque with capacity?

I'm trying to understand how VecDeque with capacity works in Rust:

From the following snippet i expect that if the VecDeque is full and I'm still push_back an element it will pop_front another element before, but it doesn't, can you help me to understand with_capacity usage ?

use std::collections::VecDeque;
fn main() {
    let mut a = VecDeque::with_capacity(2);
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    eprintln!("{:?}", a); //return [1, 2, 3] but i expect: [2, 3]
}

Playground link

Upvotes: 0

Views: 1408

Answers (2)

mxp-xc
mxp-xc

Reputation: 504

I am not familiar with English, so I express my meaning through translation tools. It may not be completely accurate

First of all, we need to know the principle that VecDeque(or Vec) can be added dynamically.

When you create it, it will apply for part of the space to store data. Suppose we apply for 7, let mut v = VecDeque::<u8>::with_capacity(7), It will apply for a space that can meet 7 u8 data. we just created it and didn't store data, so its capacity is 7, but the len is 0, Because we only create the v and do not push to add the number. When we add data, it will be directly added to the space we apply for, When we add more than its capacity

for _ in 0..7 {
    v.push_back(1)
}
println!("{}", v.capacity()); // v.len() == 7
v.push_back(2);  // This addition will exceed the requested capacity

In the last v.push_back(2) will exceed capacity. because the underlying capacity is not enough, it needs to re apply for a larger space and copy the original data to the newly applied area. As for how much the re application is the implementation of the internal algorithm, for example, you can apply for 2 * capacity + 1, After v.push_back(2); is executed, its capacity is 15 and len is 8

When and why use with_capacity

From the above, we can see that when we add, the capacity will be expanded when it exceeds the cap. This operation is relatively expensive.

If we can know the maximum length of VecDeque in advance and apply for the length as the capacity between us, then the capacity expansion operation will not occur in subsequent additions

As can be seen from the above, it will not produce the results you expect

Upvotes: 2

Daniel A. White
Daniel A. White

Reputation: 190986

with_capacity means the initial size of the underlying memory buffer, but not the size of the collection, nor is it maintained if more items are added.

on the Vec documentation an important sentence is included but is missing on VecDeque:

The vector will be able to hold exactly capacity elements without reallocating. If capacity is 0, the vector will not allocate.

Upvotes: 7

Related Questions