#double-ended #deque #slice #contiguous #contiguous-memory #queue #linear

linear-deque

A double-ended queue that can be sliced at any time without preparation

3 releases

0.1.2 Jun 29, 2023
0.1.1 May 26, 2023
0.1.0 May 26, 2023

#1665 in Algorithms

MIT license

80KB
1.5K SLoC

A double-ended queue that can be sliced at any time without preparation.

LinearDeque vs VecDeque

The standard VecDeque uses a ring buffer. It requires that the make_contiguous method is called to ensure that the deque content can all be referenced in a single slice. make_contiguous is only callable on a mutable instance of the deque.

The LinearDeque provided by this lib uses a linear buffer, keeping all its content contiguous and allowing to have a slice with all the content at any time, even when the deque is not mutable.


lib.rs:

A double-ended queue that can be sliced at any time without preparation.

LinearDeque vs VecDeque

Slicing

The standard VecDeque uses a ring buffer. It requires that the make_contiguous method is called to ensure that the deque content can all be referenced in a single slice. make_contiguous is only callable on a mutable instance of the deque.

The LinearDeque provided by this lib uses a linear buffer, keeping all its content contiguous and allowing to have a slice with all the content at any time, even when the deque is not mutable.

Memory Usage

By using a ring buffer, all spare memory allocated by the standard VecDeque can be used for elements added at both the front and the back ends.

Using a linear buffer, each end of the LinearDeque have its own reserved memory, so it tends to use more memory than VecDeque.

No runtime deps