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)": they read or copy a few small arrays whatever the size, because the tree is never more than six levels deep. A result shares every other element with the original.

The first and the last leaves are kept apart from the rest of the tree. So head and last read one array, and prepend and append usually copy one leaf of at most 32 elements.

Concatenating two vectors reuses the arrays of the longer one: only the shorter one is copied.

Elements are always stored as objects: Vector.ofAll(int...) and Vector.range box every value.

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 pattern matching;
• Queue for first in, first out;
• LazyList for a lazy or infinite sequence.

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

var numbers = Vector.range(0, 10);    // Vector<Integer>
var windows = numbers.sliding(3, 3);  // Vector<Vector<Integer>>
var parts = numbers.partitionMap( // Tuple2<Vector<Integer>, Vector<String>>
    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	O(1)	O(1): the first elements are kept apart, in their own array.
tail	effectively O(1)	effectively O(1): the first array, at most 32 elements, is copied without its first element; the few arrays above it change only when it held one element.
last	O(1)	O(1): the last elements are kept apart, in their own array.
init	effectively O(1)	effectively O(1): the last array, at most 32 elements, is copied without its last element; the few arrays above it change only when it held one element.
get	effectively O(1)	effectively O(1): at most six array reads, whatever the size; one for the first and the last 32 elements.
update	effectively O(1)	effectively O(1): the array of 32 elements that holds it is copied, with at most five arrays above it; the rest is shared.
prepend	effectively O(1)	effectively O(1): the first array, at most 32 elements, is copied; once every 32 prepends, a few arrays above it are copied too.
append	effectively O(1)	effectively O(1): the last array, at most 32 elements, is copied; once every 32 appends, a few arrays above it are copied too.
prependAll	O(m)	O(m) for m prepended elements; O(min(n, m)) when iterable is a Vector: the longer side is shared and only the shorter one is copied. 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; O(min(n, m)) when iterable is a Vector: the longer side is shared and only the shorter one is copied. 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 elements on the shorter side of i are copied, those on the longer side are shared.
removeAt	O(min(i, n - i))	O(min(i, n - i)): the elements on the shorter side of i are copied, those on the longer side are shared.
take	effectively O(1)	effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied.
drop	effectively O(1)	effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied.
slice	effectively O(1)	effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied.
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): one take and one drop; both parts share their elements with this Vector.
reverse	O(n)	O(n).
sorted	O(n log n)	O(n log n) comparisons; the elements are copied to an array and sorted there.
size	O(1)	O(1): the size is stored.
sizeCompare(Iterable<?>)	O(min(n, m))	O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return.
sizeCompare(int)	O(1)	O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1.
contains	O(n)	O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a 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): one effectively O(1) slice per window; each window shares its elements with this Vector, so no element is copied.
sliding(int, int)	O(n / step)	O(n / step): one effectively O(1) slice per window; each window shares its elements with this Vector, so no element is copied.
grouped	O(n / size)	O(n / size): one effectively O(1) slice per block; each block shares its elements with this Vector.
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 elements on the shorter side are copied.
• Building element by element is cheapest through Vector.Builder, or Vector.collector() from a java.util.stream.Stream.