#insert #array #dynamic #vec #delete #rotated #access

rotated-vec

A dynamic array mostly compatible with std::vec::Vec, supporting O(√n) inserts and deletes

2 releases

0.1.1 Jan 9, 2020
0.1.0 Jan 9, 2020

#43 in #insert

Apache-2.0

50KB
783 lines

rotated-vec

A dynamic array with O(1) access and O(√n) inserts and deletes

This is roughly a drop-in replacement for Vec, except that there is no deref to a slice, so underlying slice methods are unavailable. Many of the most useful slice methods have been ported.

Complete documentation is available at https://docs.rs/rotated-vec/.

This implementation is written in Rust. Property-based tests are implemented using the proptest library.

If you have Rust installed, you can run property-based tests from the repository root directory by typing cargo test.


lib.rs:

A dynamic array based on a 2-level rotated array.

See the rotated-array-set README for a detailed discussion of the performance benefits and drawbacks of an equivalent data structure.

Dependencies

~460KB