CODEWITHSUNDEEP
rust
Allen Lee
Allen Lee

Reputation: 471

What's the complexity of inserting to a vector in Rust?

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

Upvotes: 2

Views: 5807

Answers (2)

kaiser
kaiser

Reputation: 1009

Found this question and need to add a thing.

It all depends on your usage. If you're inserting once, it's maybe worth to accept that O(n). If you then do millions of get requests with O(1).

Other datatypes maybe have better insertion time but have O(log(n)) or even O(N) for getting items.

Next thing is iteration where cache friendlyness comes into play for such large arrays, where Vector is perfect.

May advice: if you're inserting once and then do lot of requests, stay with Vec. If inserting and removing is your main task, like a queue, go for something else.

I often found myself in some situation where I need sorted arrays and then go for something like Btreemap, or BTreeSet. I removed them completely and used a Vec now, where after adding all values, I do a sort and a dedup.

Upvotes: 0

Shepmaster
Shepmaster

Reputation: 431619

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)

The documentation for Vec::insert explains details, emphasis mine:

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?

A VERY bad idea, as everything needs to be moved. Perhaps a VecDeque would be better (or finding a different algorithm).

Upvotes: 8

Related Questions