Struct dlv_list::VecList[−][src]

pub struct VecList<EntryData> { /* fields omitted */ }
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);

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

Performs the conversion.

Performs the conversion.

The resulting type after obtaining ownership.

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

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

recently added

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.