Array Appenders

[Denis Koroskin]

On Tue, 07 Apr 2009 07:08:22 +0400, dsimcha <dsimcha at yahoo.com> wrote:

> Ever since D emerged from the primordial soup back in the Paleozoic Era,
> there's been discussion around here about array appending and the  
> need/want
> for a capacity field.  To solve this problem, Andrei's pre-release Phobos
> includes an array appender struct (see
> http://www.erdani.dreamhosters.com/d/web/phobos/std_array.html).  While  
> this
> gets the job done, IMHO it feels kind of hackish and undermining of  
> builtin
> arrays, especially now that D supports alias this.
>
> When alias this came out (yes, this was just last week but it feels like
> forever ago with the pace of evolution lately), I started playing around  
> with
> the idea that an ArrayAppender!(T) should consist of an extremely thin  
> wrapper
> around a T[].  It should implicitly convert to T[] and be usable exactly  
> like
> a T[], except that it should have a capacity field and its ~= operator  
> should
> be overridden to use the capacity field for fast appends.  IMHO this is  
> a much
> more elegant solution than having an ArrayAppender that is a completely
> different animal than builtin arrays and doesn't allow access to the  
> builtin
> array's operators without an explicit conversion.
>
> Right now, my prototype of the implicitly-converting ArrayAppender  
> doesn't
> work well due to bugs 2777, 2778, and 2781, but if there's sufficient
> interest, I'd be willing to release the prototype anyhow for comment  
> after
> it's cleaned up a little.  What do others think?  Should arrays w/  
> capacity
> fields blend in with and implicitly convert to builtin arrays, or should  
> there
> be a high wall distinguishing the two?

Well, actually I think that having an Appender object is an overkill. I never use, although I wrote a few implementations. Instead, I found the following method to be extemely handy, very fast and cover all my cases:

void append(T)(T[] array, ref size_t index, T value)
{
    assert(array.length >= index);
    if (array.length == index) {
        array.length = array.length * 2;
    }
	
    array[index++] = value;
}

It fits very well with the following D pattern: whenever you want to avoid allocation, you provide an external buffer to write. Buffer may be too small to store the result, in which case it grows using heap.

Here is an example:

// converts an array from one type to another
template toArray(Dst)
{
    Dst[] toArray(Src)(Src[] items, Dst[] buffer = null) {
        size_t index = 0;
        foreach (i; items) {
            buffer.append(index, to!(Dst)(i));
        }
	
        return buffer[0..index];
    }
}

string[] s = ["123", "345", "567"];
int[] i = toArray!(int)(s); // no buffer provided

int[3] tmp;
int[] ii = toArray!(int)(s, tmp[]); // same but with a buffer

(Not tested)