Jules Jacobs' blog About Nov 11, 2014 In the last post I talked about immutable stacks & queues. This post will be on immutable vectors. We want to support 3 operations: public interface Vector { T Lookup ( int i ); Vector Add ( T x ); Vector Set ( int i , T x ); } Lookup finds an element at index i , Add takes a vector of size n , and returns a vector of size n+1 with the additional element added to the end, and Set returns a new vector which has the new value x at index i . I’ve tried many different implementations (check out this ImmutableCollections github repository and check out Sandro Magi’s Sasa repository which contains several other vector implementations by him & me). In the end there were two implementations that were better than the others in my benchmarks. The first implementation is a tree with a fixed branching factor n (cur...