fixed-vec-deque

A double-ended queue implemented with a fixed ring buffer.

This queue has O(1) amortized inserts and removals from both ends of the container. It also has O(1) indexing like a vector. The contained elements are not required to be copyable, and the queue will be sendable if the contained type is sendable.

The size of the FixedVecDeque must be completely specified at construction time, like this:

use fixed_vec_deque::FixedVecDeque;

let _ = FixedVecDeque::<[Foo; 4]>::new();

#[derive(Default)]
struct Foo;

Modifications can only happen in-place, this means that items stored in the queue must always implement Default.

push_back and push_front don't take an argument, instead they return a mutable reference so that the newly inserted element is mutated in-place:

use fixed_vec_deque::FixedVecDeque;

let mut buf = FixedVecDeque::<[Foo; 4]>::new();
buf.push_back().data = 42;

#[derive(Default)]
struct Foo {
    data: u32,
}

On a similar note, pop_front and pop_back returns references instead of moving the elements.

A consequence of this is that this structure never modifies the data it contains, even if it has been popped.

Missing APIs

Some APIs are missing. If you want to help out, leave a comment in the issue!

When should I use FixedVecDeque?

Generally when the following holds:

• You have a maximum number of elements that you need to store for a short period of time.
• You only need to modify part of the element from the default when pushed.

A conventional collection require you to write a "complete" element every time it is added to it. With FixedVecDeque we can instead modify the existing elements in place, and keep track of how many such logical "additions" we have done. For example:

use fixed_vec_deque::FixedVecDeque;
use std::collections::VecDeque;

pub struct BigStruct {
    fields: [u64; 100],
}

impl Default for BigStruct {
    fn default() -> Self {
        BigStruct {
            fields: [0u64; 100],
        }
    }
}

let mut deq = FixedVecDeque::<[BigStruct; 0x10]>::new();

for i in 0..100 {
    deq.push_back().fields[i] = i as u64;

    let mut count = 0;

    for big in &deq {
        count += 1;
        assert_eq!(big.fields[i], i as u64);
    }

    assert_eq!(count, 1);
    deq.clear();
}

deq.clear();

// Note: modifications are still stored in the ring buffer and will be visible the next time we
// push to it unless we cleared it.
for i in 0..100 {
    assert_eq!(deq.push_back().fields[i], i as u64);
    deq.clear();
}