skiplist

Package
CI/CD
Meta

Skip list collections with $O(\log n)$ average-case performance for access, insertion, and removal. Four variants cover the common use cases: positional sequences, sorted bags, sorted sets, and sorted maps, all with pluggable ordering via a 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.

Adding to your project

[dependencies]
skiplist = "2"

To use the PartialOrdComparator (for types that implement PartialOrd but not Ord, such as f64), enable the partial-ord feature:

[dependencies]
skiplist = { version = "2", 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.

Cursor API (unstable)

The cursor feature adds lower_bound / upper_bound factory methods to OrderedSkipList, SkipSet, and SkipMap. A cursor points at a gap between two adjacent elements and supports O(1) peeking in both directions, O(log n) insertion and removal, and efficient range traversal:

[dependencies]
skiplist = { version = "2", features = ["cursor"] }

use skiplist::SkipSet;
use core::ops::Bound;

let set: SkipSet<i32> = (1..=10).collect();

// Find the neighbours of 5 without a full search.
let cur = set.lower_bound(Bound::Included(&5));
assert_eq!(cur.peek_prev(), Some(&4)); // largest element < 5
assert_eq!(cur.peek_next(), Some(&5)); // smallest element >= 5

Note

The cursor API is modelled on the BTreeMap cursor design tracked in rust-lang/rust#107540, which has not yet been stabilised in the standard library. This implementation is likewise unstable: the API may change in a future minor release. See the cursor documentation on docs.rs for the full guide.

no_std

The crate is no_std and needs alloc. Disable the default features to drop std, and optionally enable getrandom to seed from the operating system:

[dependencies]
skiplist = { version = "2", default-features = false, features = ["getrandom"] }

Without std or getrandom there is no entropy source, so pass a seed yourself:

use skiplist::{SkipList, level_generator::geometric::Geometric};

let generator = Geometric::new_with_seed(16, 0.5, 42).unwrap();
let mut list: SkipList<i32> = SkipList::with_level_generator(generator);

See the no_std documentation on docs.rs for the constructor availability table and the reasons there is no fallback seed.

Basic usage

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));

Custom ordering

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"

Collections

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 $O(\log n)$ insertion and removal anywhere in the list, not just at the ends.

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.

License

MIT