5 releases (2 stable)

1.1.0 Feb 6, 2021
1.0.0 Jan 21, 2021
0.3.0 Jan 17, 2021
0.2.0 Jan 10, 2021
0.1.0 Dec 28, 2020

#2168 in Data structures

MIT license

93KB
1.5K SLoC

TsilCev

Rust LICENSE Crates Documentation

LinkedList on Vec. Add and remove O(1) amortized. It has a similar interface to LinkedList and similar to Vec.

Example

use tsil_cev::TsilCev;

let mut tc = TsilCev::from(vec![5, 6, 7, 8, 9, 10]);
tc.push_front(4);

let mut cursor = tc.cursor_front_mut();
assert_eq!(cursor.current(), Some(&4));

cursor.move_next();
assert_eq!(cursor.current(), Some(&5));

cursor.remove();
assert_eq!(cursor.current(), Some(&6));

cursor.remove().remove().move_next_length(2);
assert_eq!(cursor.current(), Some(&10));

cursor.move_prev();
assert_eq!(cursor.current(), Some(&9));

tc.drain_filter_tsil(|x| *x % 2 == 0);
assert_eq!(tc.to_vec(), &[9]);

Comparison with LinkedList and VecDeque (thank Criterion)

VecDeque use swap_remove_back

Current Implementation

The allocator for the elements is Vec and each element has two indexes (next and previous element). When delete an item, it moves to the end, and something like pop is called. The time of addition and removal is amortized to O(1).

Optional features

serde

When this optional dependency is enabled, TsilCev implements the serde::Serialize and serde::Deserialize traits.

Dependencies

~180KB