Rust中Vec的插入复杂度及头部插入大向量的效率问题

Let's tackle your questions one by one—these are great points to clarify for anyone working with Rust's most common collection!

1. Time Complexity of Vec::insert() #

The time complexity of Vec::insert(index, element) is O(n) in the worst case, where n is the number of elements in the Vec. Here's the breakdown:

• Inserting at the end of the Vec is amortized O(1)—we just add the element to the unused capacity, no element movement needed.
• For any position before the end (including the head), we have to shift every element from index to the end one position to the right. That's n - index elements to move, which scales linearly with the total number of elements.

2. How Vec::insert() Works Under the Hood #

Based on the Rust standard library's implementation, here's the core flow of the method:

• Ensure capacity: First, the method calls reserve(1) to guarantee space for the new element. If the Vec is already at maximum capacity, this triggers a reallocation: a new, larger memory chunk is allocated (growth strategy: double the capacity until the Vec has 1024 elements, then grow by ~50% afterward), all existing elements are copied/moved to the new buffer, and the old memory is deallocated.
• Shift elements: Using safe pointer operations (like ptr::copy, which handles overlapping memory correctly), the method shifts all elements starting at index one position to the right. This is done from the end of the Vec backwards to avoid overwriting elements that haven't been moved yet.
• Insert the new element: Once the space at index is cleared, the new element is written to that position, and the Vec's length counter is incremented by 1.

3. Efficiency of Inserting at the Head of a Billion-Element Vec #

Put plainly: it's going to be painfully slow. Inserting at the head requires shifting every single one of those billions of elements one position to the right. This isn't just a CPU-intensive task—moving that much data will completely bypass your CPU cache (a billion-element Vec is way too large to fit in cache), leading to slow memory-bound operations. Depending on your hardware, this could take seconds or even minutes to finish, and if there's no spare capacity, it'll also trigger a full reallocation, making the process even slower.

If you need to perform frequent head insertions, swap to VecDeque instead. It's purpose-built for efficient push/pop operations at both ends (amortized O(1) time for both head and tail actions) and avoids the massive element shifts that make Vec so inefficient for this use case.

内容的提问来源于stack exchange，提问作者Allen Lee