Inability to dup/~ for const arrays of class objects

[Peter Williams]

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.

>
> 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.

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?

Peter