#queue #deque

vecdeque-stableix

Deque with stable index values

1 stable release

1.0.0 Sep 7, 2020

#827 in Data structures


Used in 5 crates (via otter)

AGPL-3.0-or-later

18KB
236 lines

deque (double-ended queue) with stable element indices

# use vecdeque_stableix::Deque;
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:

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

Index stabiliy

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 this xxx

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 performs wrapping arithmetic.

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

Dependencies

~140KB