Pinned Deque
This is a double-ended queue, inspired by BOOST deque in the C++ world. Once an element is pushed into this queue, it will never move until it is popped. Like the BOOST counterpart, this deque also takes constant-time in indexing.
Performance
NOTICE: It is important to run benchmarks in your environement, especially under your allocator.
push_back & push_front
- For small datasets, this deque is almost as fast as Vec and VecDeque.
- For large datasets, this deque intends to be faster. This is because it is hard for allocators to find large, consecutive memory regions. And this deque never requests such allocations.
- As conclusions, this deque is more predictable than Vec and VecDeque.
iteration
- Iterations over this deque is almost as fast as those over Vec and VecDeque.
indexing
- Although indexing on this deque (
get/get_mut) takes constant time, it is not as fast as Vec and VecDeque. It is almost 10x slower.
Complexity
| Operation | Complexity |
|---|---|
| push_back | O(1) |
| push_front | O(1) |
| pop_back | O(1) |
| pop_front | O(1) |
| front/front_mut | O(1) |
| back/back_mut | O(1) |
| get/get_mut | O(1) |
| iter/iter_mut | amortized O(1) |