2 个版本
使用旧 Rust 2015
| 0.1.1 | 2016 年 7 月 7 日 |
|---|---|
| 0.1.0 | 2016 年 7 月 7 日 |
4 在 #node-index
200KB
4K SLoC
Rust 稳定跳表
跳表提供了一种以 log(i) 时间复杂度访问、插入和删除第 i 个位置的元素的方法。
这里定义了三种集合
- 跳表 这类似于其他任何双向链表。
- 有序跳表 确保元素始终排序。仍然允许访问给定索引处的节点。
- 跳表映射 键是有序的映射。
文档 在此。
该项目是从 https://github.com/JP-Ellis/rust-skiplist 分支出来的，并修改以使用自己的 Bound 版本，使其 range 方法可与其他稳定 Rust 一起使用。
lib.rs:
跳表是一种以平均 O(log(n)) 时间复杂度高效访问、插入和删除元素的方法。
概念上，跳表类似于以下结构
<head> ----------> [2] --------------------------------------------------> [9] ---------->
<head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
<head> ----------> [2] ----------> [4] ------------------> [7] ----------> [9] --> [10] ->
<head> --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] --> [7] --> [8] --> [9] --> [10] ->
其中每个节点 [x] 都有指向列表中更下方的节点的引用，使得算法能够有效地跳过。
有序跳表有一个相关的排序函数，该函数 必须 表现良好。具体来说，给定某些排序函数 f(a, b)，它必须满足以下属性
- 定义良好：
f(a, b)应始终返回相同的值 - 反对称：如果
f(a, b) == 大于当且仅当f(b, a) == 小于并且f(a, b) == 等于等于 f(b, a)。 - 通过传递性：如果
f(a, b) == 大于并且f(b, c) == 大于，那么f(a, c) == 大于。
不满足这些属性可能导致最坏的情况是出现意外的行为，甚至可能导致段错误、空指针解引用或其他不良行为。
依赖关系
~320–540KB