| Package |
|
| CI/CD |
|
| Meta |
|
Skip list collections with Comparator trait.
Note
Version 1.0.0 is a complete rewrite.
The 1.0.0 release shares no code with the 0.x series. The internal architecture, public API, and crate structure have all changed. If you are upgrading from 0.x, treat this as a new dependency and review the documentation from scratch rather than diffing against the old API.
[dependencies]
skiplist = "1"To use the PartialOrdComparator (for types that implement PartialOrd but not Ord, such as f64), enable the partial-ord feature:
[dependencies]
skiplist = { version = "1", features = ["partial-ord"] }Warning
PartialOrdComparator panics at runtime if a comparison returns None (e.g. when a NaN is inserted or looked up). For floating-point keys, prefer FnComparator with f64::total_cmp, which provides a true total order with no panics.
use skiplist::{SkipList, OrderedSkipList, SkipSet, SkipMap};
// Positional sequence - insertion order is preserved
let mut list: SkipList<i32> = SkipList::new();
list.push_back(10);
list.push_back(20);
list.insert(1, 15); // insert at index 1
assert_eq!(list[1], 15);
// Sorted bag - elements are always kept in order, duplicates allowed
let mut ordered: OrderedSkipList<i32> = OrderedSkipList::new();
ordered.insert(30);
ordered.insert(10);
ordered.insert(10); // duplicate is kept
assert_eq!(ordered.len(), 3);
// Sorted set - like OrderedSkipList but duplicates are rejected
let mut set: SkipSet<i32> = SkipSet::new();
set.insert(3);
set.insert(1);
set.insert(1); // no-op: already present
assert_eq!(set.len(), 2);
// Sorted map - unique keys, sorted by key
let mut map: SkipMap<&str, i32> = SkipMap::new();
map.insert("b", 2);
map.insert("a", 1);
assert_eq!(map.get("a"), Some(&1));Ordered collections accept any comparator via the FnComparator wrapper - no newtype required:
use skiplist::{OrderedSkipList, comparator::FnComparator};
// Sort strings by length, then lexicographically
let cmp = FnComparator(|a: &str, b: &str| {
a.len().cmp(&b.len()).then(a.cmp(b))
});
let mut list = OrderedSkipList::with_comparator(cmp);
list.insert("banana");
list.insert("fig");
list.insert("apple");
// Iteration order: "fig", "apple", "banana"| Collection | Ordering | Duplicates | Docs |
|---|---|---|---|
SkipList |
Insertion order | Yes | docs.rs |
OrderedSkipList |
Sorted by comparator | Yes | docs.rs |
SkipSet |
Sorted by comparator | No | docs.rs |
SkipMap |
Sorted by key comparator | No (unique keys) | docs.rs |
SkipList stores elements in insertion order. It does not require elements to implement Ord. Use it when you need a positional sequence with cheap
OrderedSkipList always keeps elements in sorted order and tolerates duplicates. Unlike BTreeSet, inserting the same value twice places two adjacent entries in the list.
SkipSet wraps OrderedSkipList and enforces uniqueness: inserting a value that already exists is a no-op. It mirrors the BTreeSet API.
SkipMap stores unique key-value pairs sorted by key. Inserting a duplicate key replaces the existing value, identical to BTreeMap semantics.
Full API documentation is on docs.rs.
MIT