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