3 unstable releases

✓ Uses Rust 2018 edition

new 0.1.1 Apr 15, 2019
0.0.2 Apr 15, 2019
0.0.1 Apr 15, 2019

#159 in Algorithms

5 downloads per month

CC0 license

285 lines


Split Vecs in O(1) time.

Build Status Coverage Status License: CC0-1.0

You can split a Vec into two using Vec::split_off, but since most allocators can't just go and split up an allocation, this needs to allocate space for a second Vec and, even worse, copy the relevant elements over, which takes O(n) time. You could also split it into slices using Vec::split_at or Vec::split_at_mut, but this will not give you owned data you can move around or move out of at will.

This crate provides a way to split a Vec into two owned VecShards that behave similar to Vecs that takes constant time. The catch is that the VecShards use reference counting to determine when the last of them is dropped. Only then is the memory from the original Vec deallocated. The individual items in the shards, however, are dropped as soon as the shard is dropped.

This functionality is provided through an extension trait for Vec, ShardExt.

Basic Example

use vecshard::ShardExt;

let animals = vec!["penguin", "owl", "toucan", "turtle", "spider", "mosquitto"];

// split the vec into 2 shards
let (cool_animals, uncool_animals) = animals.split_inplace_at(4);

// shards can be indexed as usual
assert_eq!(cool_animals[3], "turtle");
assert_eq!(uncool_animals[0], "spider");

// ..including with a range as index
assert_eq!(cool_animals[1..3], ["owl", "toucan"]);

// they deref into slices, so you can use them as such:
assert_eq!(cool_animals.len(), 4);

// shards can also be split up again:
let (cool_birds, cool_reptiles) = cool_animals.split_inplace_at(3);
assert_eq!(*cool_birds, ["penguin", "owl", "toucan"]);
assert_eq!(*cool_reptiles, ["turtle"]);


Shards can be freely converted both From and Into Vecs. Note that the latter may need to allocate if there are other shards also using the shards allocation.

let vec = vec![1, 2, 3];
let shard = VecShard::from(vec);
let vec2 : Vec<_> = shard.into();


To iterate over a VecShard, you have several choices. VecShard<T> itself is a draining Iterator and returns owned T instances, removing them from its own storage. If you only need &T or &mut T, you can deref it to a slice and iterate over that. Finally, if you need an owning Iterator but do not want to drain the shard, you can clone the shard and iterate over that.

let mut shard = VecShard::from(vec!['y', 'e', 'e', 't']);

assert_eq!(Some('y'), shard.next());
assert_eq!(Some('e'), shard.next());

assert_eq!(*shard, ['e', 't']);

License: CC0-1.0

No runtime deps