vecdeque-stableix

Crates.iovecdeque-stableix
lib.rsvecdeque-stableix
version1.1.1
sourcesrc
created_at2020-09-07 20:21:21.522402
updated_at2022-11-06 22:43:07.452747
descriptionDeque with stable index values
homepage
repositoryhttps://salsa.debian.org/iwj/rust-vecdeque-stableix
max_upload_size
id285905
size58,047
Tony Finch (fanf2)

documentation

README

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 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.
Commit count: 0

cargo fmt