Confusions about designing APIs of Vec and others


#1

Vec's (so as String's) remove and swap_remove return an element, and will panic when index is out of bound; while VecDeque's (remove, swap_remove_back, swap_remove_front) return an Option.
Another observation is that when it comes to reference based removing remove_item, Vec indeed returns Option. This is consistent with other removals like in HashMap etc.
So can we say Vec's position based removal merely results from certain performance considerations?

Side question: is there an efficient data structure for pure FIFO queue operation (rather than VecDeque)? This crate is inefficient since dequeue is O(n).


#2

I almost always tend to go with a ring buffer whenever I need fast FIFO operation. The fixed-size variant is trivial to implement if your standard library doesn’t have it (as is the case in too many programming languages), and with a bit of extra thought there are ways to grow one as well.

EDIT: The rust stdlib docs says that VecDeque is actually implemented that way, unlike C++'s deque which is more complicated in an attempt to avoid invalidating pointers. So you should consider using that even though you don’t need the double-ended part. That feature basically falls out for free from the ring buffer design and comes with no extra overhead if you don’t use it.


#3

OK, I think presently I should just use VecDeque (my current issue is that I need a relatively long FIFO queue that involves many enqueue/dequeue operations…).


#4

https://github.com/rust-lang/rust/pull/20061#issuecomment-68485599. There are comments in that issue where the Vec case is discussed.

It’s not about performance but chosen semantics by the API author. It’s interesting that VecDeque decided to go with the Option API for indexed operations.