A vector is basically a tree (trie) with 32 branches at each level. If you have a Vector, say, 3000 elements, and you want, for example, to index the element 2045, which is converted to 100000010101 in binary format, it will decompose it into 5-bit blocks to use as indexes in the tree: 10 (i.e. e. 2) in the first branch, then 00000 (i.e. 0) in the next, and finally 10101 (i.e. 21) in the terminal branches, and then there the data.
Given this structure, it's easy to see how to structure common things: you can use any subtrees that don't change. Therefore, if you create a new vector with another element 2045, you need to change not all 3000 elements, but recreate "only" three 32-size arrays: terminal one is replaced with a copy with its updated element 21; then its parent should be replaced with a copy with this new child at index 0; then its parent should be replaced with the correct subtree in index 2.
Now this provides quite a bit of structural separation if you have a lot more than 32 elements in your vector, but this is still pretty big overhead. Because of this, adding to the end of the vector is done in a special way, so you just add to the existing array. Old Vectors still point to this array, but they think the end was earlier (and this part hasn't changed), so it works fine.
There is a more complex, but similar scheme, allowing the addition along the front of the vector in a similar way (basically, leaving space in front and tracking where to indicate through indexes and offsets in addition to the indexing scheme).
The trick, as implemented, does not work to allow alternating additions both front and back, however, so you will effectively rebuild the trees with each addition. It is possible to create a version with even better structure separation, but access will probably be slightly slower.
Rex kerr
source share