altdeque

An Alernative Deque implemention written in Rust.

AltDeque is an alternative to the standard library's VecDeque. It exposes mostly the same methods and has the performance characteristics. But instead of using a ring buffer to achieve efficient insertion on both ends, it uses two stacks. One stack to push and pop elements for each end of the deuque. If pop is called on one end but it's stack is empty, then all elements from the other stack are removed, reversed and put into it. This operation takes O(n) time (where n is the length of the deque) but after it n elements can be popped in constant time resulting in an amortized runtime of O(1) for popping.

For more efficient memory usage both stacks are located at the ends of one allocated buffer:

        growth ->               <- growth
+- back stack --+               +- front stack -+
|               |               |               |
v               v               v               v
+---+---+---+---+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 |   |   |   |   | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+---+---+
                  |               |
            head -+               +- tail

This stack based approach has some advantages over a ringbuffer:

• no need for masks or modular arithmetic to access elements
• no need for a power of 2 capacity
• no need to always leave one element empty

But it also has a few disadvantges:

• accessing elemnts needs an additional branch to check in which stack they are
• popping elements is only amortized constant time, a single pop-call will take linear time if the coresponding stack is empty
• popping elements alternating from both sides is very inefficient as all elements need to be moved from one side to the other every time the side is changed

In my simple tests AltDeque and VecDeque are about equally fast for a simply push_back and pop_front workload.

Some of the code and a lot of the docs and examples are taken from the code in the rust repository, so credits to it's contributors.