Inability to dup/~ for const arrays of class objects

[Steven Schveighoffer]

On Mon, 03 Jun 2013 20:06:14 -0400, Peter Williams
<pwil3058 at bigpond.net.au> wrote:

> On 04/06/13 00:57, Steven Schveighoffer wrote:
>> On Fri, 31 May 2013 21:04:47 -0400, Peter Williams
>> <pwil3058 at bigpond.net.au> wrote:
>>> I do like the idea that "~=" is generally cheap as it potentially
>>> makes building lists easy (is there any need for the singly linked
>>> list in D?) and I may modify some of my code.  I've been allocating
>>> arrays using "new array[size]" where I know that "size" will be the
>>> max needed but that it may be too much (i.e. throwing away duplicates)
>>> inserting into the array and then adjusting "length" to whatever I
>>> used.  In the case, where it's highly likely that the whole array will
>>> fit in a page I might as well allocate an empty array and use "+=".
>>> NB there's only one copy of the array.
>>
>> You can .reserve the space that you need ahead of time.  Then appending
>> will always deterministically go into the reserved block, and won't
>> reallocate.  This should be relatively quick.  It's not as quick as
>> pre-allocating the entire array and then writing the data directly --
>> you still need calls into the runtime for appending.
>
> That's great news.  When I tried to implement what I described above it  
> didn't go as well as planned (because I'd misunderstood how much gets  
> allocated) and I was thinking that what's needed is a way to tell the  
> compiler how much to allocate at the start.  And now you tell me there  
> is a way.
>
> This is one of the things I like about learning D.  Almost every time I  
> say to myself "I wish there was an easier way to do this" it turns out  
> that there is :-).  Some of them are easier to discover than others,  
> though.

I added the capacity, reserve, and assumeSafeAppend array methods when I  
updated the append code, it's been there for a while now, since the  
beginning of 2010.  It was cited in the article mentioned earlier too.   
You might want to re-read that part (it's near the end).

>> The appending feature of D arrays/slices is intended to be "good enough"
>> for most usages, not horrendously slow, but also not super-optimized for
>> specific purposes.
>>
>> And yes, we still need linked lists, arrays are good for appending, but
>> not inserting :)
>
> I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as I'm  
> willing to pay the cost of allocation for the convenience of array  
> notation.  One advantage is that finding i is O(log(a.length)) instead  
> of O(a.length()).  I also reasoned that the compiler can use memcopy()  
> (or whatever its name is) to do the reallocation and therefore it should  
> be fairly quick.

ugh.  Sorry, the performance miser in me must object :)

There are better ways to do this, using range operations.  I'm pretty sure  
you could do it with std.algorithm.copy.

> I also do a = a[0..i] ~ a[i + 1..$] to remove an item but am starting to  
> suspect this isn't as good an idea as for the insert.  Maybe something  
> like:
>
> auto tmp = a[i + 1..$];
> a.length = i;
> a ~= tmp;
>
> would be more efficient?

No, because that will also reallocate, just like your original.  This one  
is REALLY easy to get right, because it can be done in place (assuming a  
is not const/immutable).

You can even do:

memmove(&a[i], &a[i + 1], a.length - i - 1);
a.length--;

For some reason, D doesn't support overlapping moves, otherwise, this  
would work:

a[i..$-1] = a[i + 1..$];
a.length--;

I think std.algorithm.remove can do the same thing in one line.

-Steve