Vector

The default sequence, like ZIO's Chunk. A Vector is a tree of arrays of 32 elements, at most six levels deep.

Access by index, update, adding at either end, take, drop and slice are "effectively O(1)": their cost grows with the depth of the tree, which is never more than six levels.

A Vector built from a primitive array, such as Vector.ofAll(int...) or Vector.range, stores the values unboxed.

When to choose it

Whenever you need a sequence and have no reason to pick another one. Access by index, updates, adding at either end, take, drop, slice and bulk operations are all cheap.

Choose another sequence for a specific need:

• List to take a sequence apart from the front with a switch;
• Queue for first in, first out;
• Stream for a lazy or infinite sequence.

Vector<String> letters = Vector.of("a", "b", "c", "d");
Vector<String> changed = letters.update(1, "B").prepend("z").drop(2);
Tuple2<Vector<String>, Vector<String>> halves = letters.splitAt(2);
// changed is Vector(B, c, d), halves is (Vector(a, b), Vector(c, d))

Vector<Integer> numbers = Vector.range(0, 10);
Vector<Vector<Integer>> windows = numbers.sliding(3, 3);
Tuple2<Vector<Integer>, Vector<String>> parts = numbers.partitionMap(
    n -> n % 2 == 0 ? Either.left(n) : Either.right("odd " + n));
// windows is Vector(Vector(0, 1, 2), Vector(3, 4, 5), Vector(6, 7, 8), Vector(9))

Costs

Operation	Cost	Note
head	effectively O(1)	effectively O(1).
tail	effectively O(1)	effectively O(1) (the path to the first leaf is trimmed).
last	effectively O(1)	effectively O(1).
init	effectively O(1)	effectively O(1) (the path to the last leaf is trimmed).
get	effectively O(1)	effectively O(1) (O(log32 n) trie access).
update	effectively O(1)	effectively O(1) (a path copy; the leaf holding the element is copied).
prepend	effectively O(1)	effectively O(1) (a path copy; the first leaf is copied).
append	effectively O(1)	effectively O(1) (a path copy; the last leaf is copied).
prependAll	O(m)	O(m) for m prepended elements (one leaf copy per 32 elements plus a path copy); O(1) when this Vector is empty and iterable is a Vector, which is returned as is.
appendAll	O(m)	O(m) for m appended elements (one leaf copy per 32 elements plus a path copy); O(1) when this Vector is empty and iterable is a Vector, which is returned as is.
insert	O(min(i, n - i))	O(min(i, n - i)): the shorter side is re-appended or re-prepended element by element.
removeAt	O(min(i, n - i))	O(min(i, n - i)): the shorter side is re-appended or re-prepended element by element.
take	effectively O(1)	effectively O(1) (the path to the new last leaf is trimmed).
drop	effectively O(1)	effectively O(1) (the path to the new first leaf is trimmed).
slice	effectively O(1)	effectively O(1) (the paths to the new first and last leaves are trimmed).
splitAt(Predicate<? super T>)	O(k)	O(k) for k elements before the split, then an effectively O(1) split.
splitAt(int)	effectively O(1)	effectively O(1).
reverse	O(n)	O(n).
sorted	O(n log n)	O(n log n) comparisons; the elements are copied to an array, sorted there and regrouped into leaves.
length	O(1)	O(1); the length is a field of the trie.
contains	O(n)	O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup.
indexOf	O(n)	O(n).
zip	O(min(n, m))	O(min(n, m)) for m elements of that.
sliding(int)	O(n)	O(n) windows, each an effectively O(1) slice sharing this Vector's leaves.
sliding(int, int)	O(n / step)	O(n / step) windows, each an effectively O(1) slice sharing this Vector's leaves.
grouped	O(n / size)	O(n / size) blocks, each an effectively O(1) slice sharing this Vector's leaves.
distinct	O(n)	O(n).

Every method: complexity page.

Sharp edges

• sliding, grouped and crossProduct return a Vector, built at once, not an iterator. Each window shares its elements with the original Vector.
• insert and removeAt in the middle cost O(min(i, n - i)): the shorter side is copied element by element.
• Building element by element is cheapest through Vector.Builder, or Vector.collector() from a java.util.stream.Stream.