Buffer replacement with initial capacity

[Kamirus]

As pointed out in the feedback on the forum there is a missing use case that List is NOT covering from the performance point of view.

List cannot be allocated with an initial capacity like Buffer could. The use case is further described in this comment.

This issue is meant for discussion, tracking the idea and gathering all related info in one place.

---

First, let's mention simpler solutions that are already available and can be used in simpler cases:

• Array can be built directly, e.g. using Array.tabulate<T>(size : Nat, generator : Nat -> T) : [T]
• When the array must be built gradually and the exact size is known: VarArray.repeat(default, size) can be used to initialize the array with a default value, allowing further mutations to build the array.
• In particular, default could be null, which would mean working with ?T values inside the array

---

In most use cases List (which is the mops vector package) performs better than Buffer as it does not need to copy as many elements when resizing. Which results in fewer instructions.
However, Buffer is superior when using the initial capacity to avoid resizing.

Solutions

Ideas from both List and Buffer can be merged to provide both advantages:

type ArrayBuilder<T> = {
  firstElements : [var ?T];
  size : Nat;
  rest : List<T>
}

Usage example by @rvanasa :

import ArrayBuilder "mo:base/ArrayBuilder";

let builder = ArrayBuilder.new<Nat>(5); // returns a class
builder.add(123);

let array = builder.toArray();
assert array == [123];

let varArray = builder.toVarArray();
assert varArray == [var 123]; // pseudocode

Both module and class API could be provided.

• class api for easier use in transient context
• module api for consistency with other modules and persistency

We might consider adding this data structure as a separate mops package.