Crate extended_collections

extended-collections-rs

extended-collections contains various implementations of collections that are not found in the standard library.

Usage

Add this to your Cargo.toml:

[dependencies]
extended-collections = "*"

and this to your crate root:

extern crate extended_collections;

References

• Fast set operations using treaps

Blelloch, Guy E., and Margaret Reid-Miller. 1998. “Fast Set Operations Using Treaps.” In Proceedings of the Tenth Annual Acm Symposium on Parallel Algorithms and Architectures, 16–26. SPAA ’98. New York, NY, USA: ACM. doi:10.1145/277651.277660.

• A Skip List Cookbook.

Pugh, William. 1990a. “A Skip List Cookbook.” College Park, MD, USA: University of Maryland at College Park.

• Skip Lists: A Probabilistic Alternative to Balanced Trees

Pugh, William. 1990b. “Skip Lists: A Probabilistic Alternative to Balanced Trees.” Commun. ACM 33 (6). New York, NY, USA: ACM: 668–76. doi:10.1145/78973.78977.

Modules

arena

Fast, but limited allocator.

avl_tree

Self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.

bp_tree

Disk-resident N-ary tree.

lsm_tree

Hybrid tree comprised of disk-resident sorted runs of data and memory-resident tree.

radix

Space-optimized trie.

red_black_tree

Self-balancing binary search tree that uses a color bit to ensure that the tree remains approximately balanced during insertions and deletions.

skiplist

Probabilistic linked hierarchy of subsequences.

splay_tree

Self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.

sync

Lock-free data structures.

treap

Probabilistic binary search tree where each node also maintains the heap invariant.