Struct dlv_list::VecList

source · [−]
pub struct VecList<EntryData> { /* private fields */ }
Expand description

A semi-doubly linked list implemented with a vector.

This provides many of the benefits of an actual linked list with a few tradeoffs. First, due to the use of an underlying vector, an individual insert operation may be O(n) due to allocating more space for the vector. However, it is amortized O(1) and it avoids the frequent allocation that traditional linked lists suffer from.

Another tradeoff is that extending a traditional linked list with another list is O(1) but a vector based implementation is O(n). Splicing has a similar disadvantage.

Lastly, the vector based implementation is likely to have better cache locality in general.

Implementations

Returns an immutable reference to the value at the back of the list, if it exists.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.back(), None);

list.push_back(0);
list.push_back(5);
assert_eq!(list.back(), Some(&5));

Returns a mutable reference to the value at the back of the list, if it exists.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.back_mut(), None);

list.push_back(0);
list.push_back(5);

let mut back = list.back_mut().unwrap();
assert_eq!(back, &mut 5);
*back *= 2;

assert_eq!(list.back(), Some(&10));

Returns the capacity of the list.

Examples
use dlv_list::VecList;

let list: VecList<u32> = VecList::new();
assert_eq!(list.capacity(), 0);

let list: VecList<u32> = VecList::with_capacity(10);
assert_eq!(list.capacity(), 10);

Removes all values from the list and invalidates all existing indices.

Complexity: O(n)

Examples
use dlv_list::VecList;

let mut list = VecList::new();

list.push_back(5);
assert!(!list.is_empty());

list.clear();
assert!(list.is_empty());

Returns whether or not the list contains the given value.

Complexity: O(n)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert!(!list.contains(&0));

list.push_back(0);
assert!(list.contains(&0));

Creates a draining iterator that removes all values from the list and yields them in order.

All values are removed even if the iterator is only partially consumed or not consumed at all.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(5);

{
    let mut iter = list.drain();
    assert_eq!(iter.next(), Some(0));
    assert_eq!(iter.next(), Some(5));
    assert_eq!(iter.next(), None);
}

println!("{}", list.len());
assert!(list.is_empty());

Returns an immutable reference to the value at the front of the list, if it exists.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.front(), None);

list.push_front(0);
list.push_front(5);
assert_eq!(list.front(), Some(&5));

Returns a mutable reference to the value at the front of the list, if it exists.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.front_mut(), None);

list.push_front(0);
list.push_front(5);

let mut front = list.front_mut().unwrap();
assert_eq!(front, &mut 5);
*front *= 2;

assert_eq!(list.front(), Some(&10));

Returns an immutable reference to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_front(0);
assert_eq!(list.get(index), Some(&0));

let index = list.push_front(5);
assert_eq!(list.get(index), Some(&5));

Returns a mutable reference to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_front(0);
let value = list.get_mut(index).unwrap();
*value = 100;
assert_eq!(list.get(index), Some(&100));

Returns the index of the value next to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();

let index_1 = list.push_back(0);
assert_eq!(list.get_next_index(index_1), None);

let index_2 = list.push_back(5);
assert_eq!(list.get_next_index(index_1), Some(index_2));

Returns the index of the value previous to the value at the given index.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();

let index_1 = list.push_front(0);
assert_eq!(list.get_previous_index(index_1), None);

let index_2 = list.push_front(5);
assert_eq!(list.get_previous_index(index_1), Some(index_2));

Creates an indices iterator which will yield all indices of the list in order.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_front(0);
list.push_front(5);

let mut indices = list.indices();
let index = indices.next().unwrap();
assert_eq!(list.get(index), Some(&5));

let index = indices.next().unwrap();
assert_eq!(list.get(index), Some(&0));

assert_eq!(indices.next(), None);

Inserts the given value after the value at the given index.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the index refers to an index not in the list anymore or if the index has been invalidated. This is enforced because this function will consume the value to be inserted, and if it cannot be inserted (due to the index not being valid), then it will be lost.

Also panics if the new capacity overflows usize.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_front(0);
let index_1 = list.push_front(5);
list.push_front(10);

let index_2 = list.insert_after(index_1, 1000);
assert_eq!(list.get_next_index(index_1), Some(index_2));

Inserts the given value before the value at the given index.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the index refers to an index not in the list anymore or if the index has been invalidated. This is enforced because this function will consume the value to be inserted, and if it cannot be inserted (due to the index not being valid), then it will be lost.

Also panics if the new capacity overflows usize.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_front(0);
let index_1 = list.push_front(5);
list.push_front(10);

let index_2 = list.insert_before(index_1, 1000);
assert_eq!(list.get_previous_index(index_1), Some(index_2));

Returns whether or not the list is empty.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert!(list.is_empty());

list.push_back(0);
assert!(!list.is_empty());

Creates an iterator that yields immutable references to values in the list in order.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(10);
list.push_back(200);
list.push_back(-10);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&200));
assert_eq!(iter.next(), Some(&-10));
assert_eq!(iter.next(), None);

Creates an iterator that yields mutable references to values in the list in order.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(10);
list.push_back(200);
list.push_back(-10);

let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 0));
assert_eq!(iter.next(), Some(&mut 10));
assert_eq!(iter.next(), Some(&mut 200));
assert_eq!(iter.next(), Some(&mut -10));
assert_eq!(iter.next(), None);

Returns the number of values in the list.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.len(), 0);

list.push_back(0);
list.push_back(1);
list.push_back(2);
assert_eq!(list.len(), 3);

Creates a new list with no initial capacity.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_back(0);
assert_eq!(list.get(index), Some(&0));

Reorganizes the existing values to ensure maximum cache locality and shrinks the list such that the capacity is exactly [minimum_capacity].

This function can be used to actually increase the capacity of the list.

Complexity: O(n)

Panics

Panics if the given minimum capacity is less than the current length of the list.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index_1 = list.push_back(5);
let index_2 = list.push_back(10);
let index_3 = list.push_front(100);
list.remove(index_1);

assert!(list.capacity() >= 3);

let mut map = list.pack_to(list.len() + 5);
assert_eq!(list.capacity(), 7);
assert_eq!(map.len(), 2);

let index_2 = map.remove(&index_2).unwrap();
let index_3 = map.remove(&index_3).unwrap();

assert_eq!(list.get(index_2), Some(&10));
assert_eq!(list.get(index_3), Some(&100));

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&100));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), None);

Reorganizes the existing values to ensure maximum cache locality and shrinks the list such that no additional capacity exists.

This is equivalent to calling VecList::pack_to with the current length.

Complexity: O(n)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index_1 = list.push_back(5);
let index_2 = list.push_back(10);
let index_3 = list.push_front(100);
list.remove(index_1);

assert!(list.capacity() >= 3);

let mut map = list.pack_to_fit();
assert_eq!(list.capacity(), 2);
assert_eq!(map.len(), 2);

let index_2 = map.remove(&index_2).unwrap();
let index_3 = map.remove(&index_3).unwrap();

assert_eq!(list.get(index_2), Some(&10));
assert_eq!(list.get(index_3), Some(&100));

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&100));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), None);

Removes and returns the value at the back of the list, if it exists.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.pop_back(), None);

list.push_back(0);
list.push_back(1);
list.push_back(2);
assert_eq!(list.len(), 3);

assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.len(), 2);

Removes and returns the value at the front of the list, if it exists.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
assert_eq!(list.pop_front(), None);

list.push_front(0);
list.push_front(1);
list.push_front(2);
assert_eq!(list.len(), 3);

assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.len(), 2);

Inserts the given value to the back of the list.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the new capacity overflows usize.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_back(0);
assert_eq!(list.get(index), Some(&0));

Inserts the given value to the front of the list.

The index of the newly inserted value will be returned.

Complexity: amortized O(1)

Panics

Panics if the new capacity overflows usize.

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_front(0);
assert_eq!(list.get(index), Some(&0));

Removes and returns the value at the given index, if it exists.

If the index refers to an index not in the list anymore or if the index has been invalidated, then None will be returned and the list will be unaffected.

Complexity: O(1)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
let index = list.push_back(0);
assert_eq!(list.remove(index), Some(0));
assert_eq!(list.remove(index), None);

Removes the value at the given index.

This function is highly unsafe in the sense that it will break logical invariants for this type, but it does not expose any undefined behavior. Any further use of this type after calling this function is highly likely to cause a panic (but no memory unsafety). It should only be used when both of the following conditions apply:

  1. You only want to remove values from the list; no iteration, insertion or retrieval is to be done afterwards. This is the only removal function that can be used after at least one invocation of it (i.e., do not use VecList::remove, it will probably panic).
  2. For some reason, you require the ability to parallelize independent removals from the list without locking. This is the primary reason this function is unsafe, as it does not try to maintain logical invariants since that would require accessing shared memory.
Panics

Panics if there is no value at the given index or if the generation does not match.

Reserves capacity for the given expected size increase.

The collection may reserve more space to avoid frequent reallocations. After calling this function, capacity will be greater than or equal to self.len() + additional_capacity. Does nothing if the current capacity is already sufficient.

Panics

Panics if the new capacity overflows usize.

Examples
use dlv_list::VecList;

let mut list: VecList<u32> = VecList::new();
assert_eq!(list.capacity(), 0);

list.reserve(10);
assert!(list.capacity() >= 10);

Removes all elements from the list not satisfying the given predicate.

Complexity: O(n)

Examples
use dlv_list::VecList;

let mut list = VecList::new();
list.push_back(0);
list.push_back(-1);
list.push_back(1);
list.push_back(-2);
list.retain(|&mut value| value >= 0);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), None);

Creates a new list with the given capacity.

Examples
use dlv_list::VecList;

let mut list: VecList<u32> = VecList::new();
assert_eq!(list.capacity(), 0);

let mut list: VecList<u32> = VecList::with_capacity(10);
assert_eq!(list.capacity(), 10);

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Returns the “default value” for a type. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Creates a value from an iterator. Read more

Feeds this value into the given Hasher. Read more

Feeds a slice of this type into the given Hasher. Read more

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

Performs the mutable indexing (container[index]) operation. Read more

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Creates an iterator from a value. Read more

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Creates an iterator from a value. Read more

Which kind of iterator are we turning this into?

The type of the elements being iterated over.

Creates an iterator from a value. Read more

This method returns an Ordering between self and other. Read more

Compares and returns the maximum of two values. Read more

Compares and returns the minimum of two values. Read more

Restrict a value to a certain interval. Read more

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method returns an ordering between self and other values if one exists. Read more

This method tests less than (for self and other) and is used by the < operator. Read more

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more

This method tests greater than (for self and other) and is used by the > operator. Read more

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.