#### varray

This library provides an implementation of **var**iable sized **arrays**, which

are also called resizable arrays, dynamic arrays or even "vectors" in C++ and

"ArrayList" in Java. Just like an array, accessing any element by its index is

constant time, but one can also efficiently insert and delete at any location

(with the array resizing automatically to meet the need).

Following the above paper, the family of tiered vectors yields a nice

compromise between random access and resizing:

| Module Circular | `get`

, `set`

| `{push,pop}_{back,front}`

| `insert_at`

, `pop_at`

| Memory overhead |

|-------------------------------|-------------:|:-------------------------:|:----------------------------------:|:-----------------------:|

| Circular | O(1) | O(1) amortized | O(N) | O(N) |

| Root(Circular) | O(1) | O(1) amortized | O(√N) | O(√N) |

| Root^{k-1}(Circular) | O(k) | O(k) amortized | O(k^{2} × ^{k}√N) | O(N^{k-1 / k}) |

In other words, each instantiation of the `Root`

functor leads to slower random

access into the array, but it also makes insertion and deletion faster!

You can expect the following constant factors on random access:

| | Array | Circular | Root | Root^{2} | Root^{3} | Root^{4} | Root^{5} |

|----:|------:|---------:|-----:|-----------------:|-----------------:|-----------------:|-----------------:|

| get | 1x | 3x | 8x | 17x | 27x | 31x | 33x |

| set | 1x | 2x | 4x | 8x | 12x | 14x | 15x |

The memory usage is competitive:

`push_front`

,`push_back`

and their respective`pop`

, are*amortized*

constant time, since they frequently need to allocate small chunks of

O(^{k}√N) up to O(k^{k}√N) memory as the varray grows or

shrinks.The growth strategy is incremental: the worst case slowdown following a

resize is also O(k^{k}√N) which is unobtrusive for k>1. There is no

"stop the world while every elements is moved to a larger array".The amount of memory used for bookkeeping and allocated in anticipation of a

growth is pretty tight. In particular for k=2, the O(√N) memory overhead is

optimal if random access and`push_back`

are to be O(1).

If you only care about fast random access and resizing at the right end with`{push,pop}_back`

, then the pre-existing libraries provide smaller constant

factors : (in alphabetical order) BatDynArray from Batteries, CCVector from

Containers, RES as a standalone library or even vector as a single module.

sha256=69a22c87d9eb4cd27ddd74b24d9fd6fe4e3ec28781012f6eb99203a9fb78e167

sha512=c5c2292a1eff693d8f10a7b398b1924b17ab3d7b84788f94e689460106df5f41f7bba3e0e30b51f9faaba88db7b502448f4850c344a4765bfd2e37da7fe7f460