/vecset-rs

A Vec-based binary-searching ordered map and set implementation for rust

Primary LanguageRustApache License 2.0Apache-2.0

vecset

Build Status crates.io docs.rs License: Apache 2.0 License: MIT

A vector-based sorted map and set implementation with zero dependencies and support for #![no_std].

The crate provides VecMap, VecSet and KeyedVecSet which are basically a map interface wrapper of sorted vectors. For all types, searching is O(n) using Vec::binary_search.

VecMap<K, V> is a map interface for a sorted vector Vec<(K, V)>. It is a wrapper of KeyedVecSet specialization KeyedVecSet<K, (K, V)>.

VecSet<T> is a set interface for a sorted vector Vec<T>. It is a wrapper of KeyedVecSet specialization KeyedVecSet<T, T>. This is also same as sorting-guaranteed Vec<T>.

KeyedVecSet<K, V> is a generalized interface of a sorted vector Vec<V> where V: Keyed<K>. It means V provides a key value using the key accessor <V as Keyed<K>>::key() -> &K. This is useful when value contains its own key. Accessing mutable reference of KeyedVecSet elements is unsafe because editing the key value may corrupt sorting of the container. The same functions will be safe for VecMap by hiding the key part from mutable reference.

Map keys are required to form a total order.

Cargo features

The following features are available:

  • serde: Provides Serialize and Deserialize implementations for VecMap and VecSet. This feature is disabled by default. Enabling it will pull in serde as a dependency.

License

The source code of vecset is licensed under either of Apache License, Version 2.0 or MIT license at your option.

Thanks to vecmap-rs, the first version of this project based on.