#deque #double-ended #pinned #queue #element #constant-time #boost

pinned-deque

A fine-tuned double-ended queue, inspired by BOOST deque. Every element in this deque are pinned until their popping and dropping

1 unstable release

0.1.0 Sep 9, 2024

#543 in Algorithms

Download history 104/week @ 2024-09-07 30/week @ 2024-09-14 12/week @ 2024-09-21

146 downloads per month

Custom license

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)

No runtime deps