1 unstable release
0.1.0 | Sep 9, 2024 |
---|
#543 in Algorithms
146 downloads per month
76KB
1K
SLoC
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) |