rust - 在 Rust 中插入向量的复杂性是什么？

Question

如何insert在 Rust Vec 中工作？在具有数十亿个元素的非常大向量的开头插入一个元素的效率如何？

Answer 1

The documentation lists the complexities for all the standard collections and operations :

Throughout the documentation, we will follow a few conventions. For all operations, the collection's size is denoted by n. If another collection is involved in the operation, it contains m elements. Operations which have an amortized cost are suffixed with a *. Operations with an expected cost are suffixed with a ~.

      get(i)  insert(i)   remove(i)   append  split_off(i)
Vec   O(1)    O(n-i)*     O(n-i)      O(m)*   O(n-i)

Vec::insert 的文档解释细节，强调我的:

Inserts an element at position index within the vector, shifting all elements after it to the right.

How efficient is it to insert an element at the start of a VERY large vector which has billions of elements?

一个非常糟糕的主意，因为所有东西都需要移动。也许是 VecDeque会更好(或找到不同的算法)。