[−][src]Crate tsil_cev
Implementation of the linked list on Vec
. Has an
O(1)
amortized insertion and removal time due to
linear placement in memory. It is added in the
same way as in Vec
, but at deletion the element
moves to the end and something like pop is called,
and if the length equals capacity / 4
then the Vec
is reallocated and the capacity == 2 * length
invariant is always executed.
tsil
and cev
TsilCev
has 2 types of iterators Tsil
and Cev
.
Tsil
- iterating as in LinkedList
. Cev
- iterating
as in Vec
(a bit faster because memory access is sequential).
Examples
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)); let _ = tc.drain_filter_tsil(|x| *x % 2 == 0).collect::<Vec<_>>(); assert_eq!(tc.into_vec(), &[9]);
Current Implementation
The allocator for the elements is Vec
and each
element has two indexes (next and previous element).
Also if the number of elements is less than capacity / 4
then it is reallocated to size capacity / 2
. 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.
Structs
CevIter | |
CevIterMut | |
Cursor | |
CursorMut | |
DrainFilterCev | |
DrainFilterTsil | |
TsilCev | |
TsilIntoIter | |
TsilIter | |
TsilIterMut |