Struct sortedvec::SortedVec

pub struct SortedVec<T, F> { /* fields omitted */ }

A Vec wrapper type for orderable elements, providing log(N) lookups.

SortedVec is a Vec whose elements are sorted with respect some comperator function. This provides some behaviour in between regular vectors and hashmaps, namely:

• a compact memory representation
• fast iteration
• semi-fast lookups: O(log(N)), compared to a hashmap's O(1) and a vector's O(n)
• slow insertions and deletions: O(n)

Its main use case is for small lookup tables where inserts and deletions are infrequent.

Example

use sortedvec::SortedVec;
 
struct A {
    val: f64,
    key: u32,
}
 
let mut sv = SortedVec::new(|a: &A| a.key);
sv.insert(A { val: 3.14, key: 0 });
sv.insert(A { val: 0.00, key: 10 });
sv.insert(A { val: 5.00, key: 4 });
 
assert_eq!(3, sv.len());
assert!(sv.find(&5).is_none());
 
let search_result = sv.find(&4).unwrap();
assert_eq!(5.00, search_result.val);

Methods

impl<T, F, K> SortedVec<T, F> where     F: Fn(&T) -> K,     K: Ord + Eq,

pub fn new(comp: F) -> Self

Creates a new, empty SortedVec. Does not allocate until elements are inserted.

pub fn from_vec(vec: Vec<T>, comp: F) -> Self

Creates a sorted vector from an existing vector, which does not need to be sorted beforehand, and a comparison function.

pub fn insert(&mut self, val: T)

Inserts a new value into the vector, maintaining the internal order invariant. Note that this is an O(n) operation.

pub fn comperator(&self) -> &F

Provides access to the internal comperator function.

pub fn find(&self, key: &K) -> Option<&T>

Tries to find an element in the vector with the given 'key'. It has logarithmic worst case time complexity. The elements' keys are computed using the internal comperator function, which is exposed through the SortedVec::comperator method.

pub fn contains(&self, key: &K) -> bool

Checks whether there is a value with that key in the vector. This is done in O(log(n)) time.

pub fn into_inner(self) -> Vec<T>

Destructs the SortedVec to its inner Vec, which is guaranteed to be sorted with respect to the comperator function.

Methods from Deref<Target = Vec<T>>

pub fn capacity(&self) -> usize

Returns the number of elements the vector can hold without reallocating.

Examples

let vec: Vec<i32> = Vec::with_capacity(10);
assert_eq!(vec.capacity(), 10);

pub fn as_slice(&self) -> &[T]

Extracts a slice containing the entire vector.

Equivalent to &s[..].

Examples

use std::io::{self, Write};
let buffer = vec![1, 2, 3, 5, 8];
io::sink().write(buffer.as_slice()).unwrap();

pub fn len(&self) -> usize

Returns the number of elements in the vector, also referred to as its 'length'.

Examples

let a = vec![1, 2, 3];
assert_eq!(a.len(), 3);

pub fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

Examples

let mut v = Vec::new();
assert!(v.is_empty());

v.push(1);
assert!(!v.is_empty());

Trait Implementations

impl<T, F> AsRef<[T]> for SortedVec<T, F>

fn as_ref(&self) -> &[T]

Performs the conversion.

impl<T, F> AsRef<Vec<T>> for SortedVec<T, F>

fn as_ref(&self) -> &Vec<T>

Performs the conversion.

impl<T, F, K> Extend<T> for SortedVec<T, F> where     F: Fn(&T) -> K,     K: Ord + Eq,

fn extend<I>(&mut self, iter: I) where     I: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

impl<T, F> IntoIterator for SortedVec<T, F>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

Important traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> type Item = T;

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.

impl<T, F> Hash for SortedVec<T, F> where     T: Hash,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where     H: Hasher,

Feeds a slice of this type into the given [Hasher].

impl<T, F> Deref for SortedVec<T, F>

type Target = Vec<T>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T, F> Borrow<[T]> for SortedVec<T, F>

fn borrow(&self) -> &[T]

Immutably borrows from an owned value.