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: ?Sized> SortedVec<T, F> where     F: Clone + for<'t> Fn(&'t T) -> &'t K,     K: Ord + Eq,

pub fn split_off(&mut self, at: usize) -> Self

Splits the collection into two at the given index.

Returns a newly allocated Self. self contains elements [0, at), and the returned Self contains elements [at, len).

Note that the capacity of self does not change.

Panics

Panics if at > len.

impl<T, F, K: ?Sized> SortedVec<T, F> where     F: for<'t> Fn(&'t T) -> &'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.

Example

use sortedvec::*;

let v = vec!["hello".to_string(), "world".to_string()];
let sv = SortedVec::from_vec(v, |x| &x[1..]);

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.

#Example

use sortedvec::*;

let sv = sortedvec![1, 5, 3, 10];
let res = sv.find(&5).unwrap();
assert_eq!(&5, res);

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.

pub fn remove(&mut self, index: usize) -> T

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

Panics

Panics if index is out of bounds. #[unstable(reason = "indices are opaque for this data structure")]

pub fn truncate(&mut self, len: usize)

Shortens the vector, keeping the first len elements and dropping the rest.

If len is greater than the vector's current length, this has no effect.

Note that this method has no effect on the allocated capacity of the vector.

pub fn dedup_by_key(&mut self)

Removes all elements but one that resolve to the same key generated by the internal key function.

pub fn pop(&mut self) -> Option<T>

Removes the last element from a vector and returns it, or None if it is empty.

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> 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, K: ?Sized> Extend<T> for SortedVec<T, F> where     F: for<'t> Fn(&'t T) -> &'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> 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> 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> Borrow<[T]> for SortedVec<T, F>

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

Immutably borrows from an owned value.