Crate vecdeque_stableix

Expand description

deque (double-ended queue) with stable element indices

let mut deque = Deque::new();
let pushed_a : i64 = deque.push_back('a');
let pushed_b = deque.push_back('b');
assert_eq!(deque.get(pushed_a), Some(&'a'));
assert_eq!(deque.pop_front(), Some('a'));
assert_eq!(deque[pushed_b], 'b'); // would panic if it had been removed

Index type

You can use a suitable signed integer type, eg. i64, as the element index. It is important that it doesn’t overflow — see below.

You may have to specify the index type explicitly:

let mut deque : Deque<_,i64> = Deque::new();
deque.push_front(42);
assert_eq!(deque.front(), Some(&42));

This Deque is implemented by adding a front counter to std::vec_deque::VecDeque. The abstraction is rather thin. Methods are provided to access the individual parts. If you use them, you may invalidate your existing indices, so that they no longer point to the same elements.

If this happens, your program will still be memory-safe, but it may function incorrectly.

Methods with a risk of panicking are so noted in the documentation.

Panics, and index overflow

This library will panic if the index type overflows. This can occur if you push more than 2^n values through the queue, where n is the size of your integer type.

If you prefer to wrap, reusing element indices rather than panicing, you can impl Offset for a newtype containing an unsigned type, and perform wrapping arithmetic.

It would be possible to provide non-panicing library entrypoints, which return errors instead. Patches for that welcome.