#set #sorting #element #duplicates #sorted-vec

sorted-vec

Create and maintain sorted vectors and vector-backed sets

21 releases

0.8.6 Jan 25, 2025
0.8.5 Oct 24, 2024
0.8.3 Sep 28, 2023
0.8.2 Jan 4, 2023
0.3.1 Mar 19, 2019

#120 in Data structures

Download history 31234/week @ 2025-01-30 35527/week @ 2025-02-06 25895/week @ 2025-02-13 31290/week @ 2025-02-20 23820/week @ 2025-02-27 23252/week @ 2025-03-06 29013/week @ 2025-03-13 29194/week @ 2025-03-20 28180/week @ 2025-03-27 24954/week @ 2025-04-03 30118/week @ 2025-04-10 32759/week @ 2025-04-17 32178/week @ 2025-04-24 31121/week @ 2025-05-01 26801/week @ 2025-05-08 26750/week @ 2025-05-15

122,009 downloads per month
Used in 90 crates (20 directly)

Apache-2.0

50KB
1K SLoC

Sorted vectors.

Repository

  • SortedVec -- sorted from least to greatest, may contain duplicates
  • SortedSet -- sorted from least to greatest, unique elements
  • ReverseSortedVec -- sorted from greatest to least, may contain duplicates
  • ReverseSortedSet -- sorted from greatest to least, unique elements

The partial module provides sorted vectors of types that only implement PartialOrd where comparison of incomparable elements results in runtime panic.


sorted_vec

Create and maintain collections of sorted elements.

Documentation

let mut v = SortedVec::new();
assert_eq!(v.insert (5), 0);
assert_eq!(v.insert (3), 0);
assert_eq!(v.insert (4), 1);
assert_eq!(v.insert (4), 1);
assert_eq!(v.len(), 4);
v.dedup();
assert_eq!(v.len(), 3);
assert_eq!(v.binary_search (&3), Ok (0));
assert_eq!(*SortedVec::from_unsorted (
  vec![5, -10, 99, -11, 2, 17, 10]),
  vec![-11, -10, 2, 5, 10, 17, 99]);

Also provides sorted set containers only containing unique elements.

serde support

serde de/serialization is an optional feature.

By default, deserializing an unsorted container is an error.

To sort on deserialization, tag the field with #[serde(deserialize_with = "SortedVec::deserialize_unsorted")]:

#[derive(Debug, Eq, Ord, PartialEq, PartialOrd, Deserialize, Serialize)]
pub struct Foo {
  #[serde(deserialize_with = "SortedVec::deserialize_unsorted")]
  pub v : SortedVec <u64>
}

Dependencies

~150KB