2 unstable releases
| 0.2.0 | Oct 19, 2024 |
|---|---|
| 0.1.0 | Sep 9, 2024 |
#677 in Algorithms
90KB
1.5K
SLoC
Pinned Deque
This is a high-performance double-ended queue, inspired by BOOST deque. Once an element is pushed into this queue, it will never move until it is popped. So, pointers to elements in this queue will never be invalidated when other elements are pushed or popped.
Complexity
| Operation | Complexity |
|---|---|
| push_front/push_back | O(1) |
| pop_front/pop_back | O(1) |
| front/front_mut | O(1) |
| back/back_mut | O(1) |
| get/get_mut | O(1) |
| iter/iter_mut | O(1) |
| next in Iter/IterMut | O(1) |
| next_back in Iter/IterMut | O(1) |
Benchmarks
NOTICE: It is important to run benchmarks in your environement, especially under your allocator. Our results are collected under jemalloc.
- In most cases, this deque is among the best choices.
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 about 10x slower.
Dependencies
~220KB