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));

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 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.

Changelog

1.1.1

  • Update the README from the crate-level docs.

1.1.0

  • Provide IterMut (from iter_mut).
  • Provide draining IntoIter (via impl IntoIterator).
  • Implement Eq and PartialEq for Deque.
  • Implement FromIterator and Extend for Deque.

1.0.0

  • Initial public release.

Structs

Double-ended queue with stable indices
Owning iterator over the elements of a Deque
Iterator over elements of a Deque
Iterator over elements of a Deque, that returns mutable references

Traits

Types that can be used as an index for a Deque.