There's more...

The vector should always be your go-to collection. Internally, it is implemented as a continuous chunk of memory stored on the heap:

The important keyword here is continuous, which means that the memory is very cache-friendly. In other words, the vector is pretty fast! The vector even allocates a bit of extra memory in case you want to extend it. Be careful, though, when inserting a lot of data at the beginning of the vector: the entire stack will have to be moved.

At the end, you can see a bit of extra capacity. This is because Vec and many other collections preallocate a bit of extra memory each time you have to move the block, because it has grown too large. This is done in order to prevent as many reallocations as possible. You can check the exact amount of total space of a vector by calling capacity[140] on it. You can influence the preallocation by initializing your vector with with_capacity[137]. Use it when you have a rough idea about how many elements you plan on storing. This can be a big difference in capacity when working with big amounts of data.

The extra capacity doesn't go away when shortening the vector. If you had a vector with a length of 10,000 and a capacity of 100,000 and called clear on it, you would still have a capacity of 100,000 preallocated. When working on systems with memory limitations, like microcontrollers, this can become a problem. The solution is calling shrink_to_fit periodically on such vectors [143]. This will bring the capacity as close as possible to the length, but it is allowed to still leave a little bit of preallocated space ready.

Another way to optimize really big vectors is to call swap_remove [150]. Normally, when removing an element from a vector, all elements after it will be shifted to the left in order to preserve continuous memory. This is a lot of work when removing the first element in a big vector. If you don't care about the exact order of your vector, you can call swap_remove instead of remove. It works by swapping the element that is to be removed with the last element, and adjusting the length. This is great, because you don't create a hole that needs to be filled by shifting, and because swapping memory is a really fast operation in today's processors.