array idioms

spir denis.spir at gmail.com
Fri Feb 25 14:48:19 PST 2011


On 02/25/2011 09:09 PM, Jonathan M Davis wrote:
> On Friday, February 25, 2011 11:30:28 spir wrote:
>> Hello,
>>
>> What's the idiomatic way to:
>>
>> * delete an element in an associative array
>
> If you have the key, then just use remove. The online documentation for
> asseciative array discusses it. e.g.
>
> b.remove("hello");
>
> If you're looking to remove by value, however, you're going to have to figure out
> what its key is. And if you want to remove _all_ elements with the same value,
> then you're going to need to find _all_ of their keys. The best way to do that
> would probably just be to use a foreach loop:
>
> foreach(k, v; aa)
> {
>      if(v == value)
>          aa.remove(k);
> }
>
> I'm not sure if there are any problems with removing from an associative array
> while iterating over it though. I wouldn't think so, but I don't know so. Worst
> case though, you save the list of keys to remove and then remove them all once
> you have them all.
>
>> * delete an element in a dyn array
>
> I don't think that there is one right now. There should probably be a function
> in std.array which does what remove in std.container would do, but I don't
> believe that there's a function for it right now. So, the simplest way at the
> moment (albeit not the most efficient) would probably do to something like
>
> auto found = findSplit(arr, value);
> auto newArr = array(chain(found[0], found[2]));
>
> The efficient way to do it, however, would involve shifting all of the elements in
> the array, which is more complicated and not the kind of code that you really
> want to be rewriting every time that you need to remove an element. But you _do_
> need to remember that removing an arbitrary element from an array is _not_
> cheap, because even in the most efficient case, that means moving a potentially
> large number of elements in the array - unlike a linked list where removal is
> cheap.
>
> Of course, popFront and popBack would be the best way to remove from the ends of
> an array, and _that_ is efficient.
>
>> * insert an element in a dyn array
>
> Same as remove. There's no function for doing it at the moment. The best way at
> present would probably be to just concatenate the slices.
>
> auto newArr = arr[0 .. i] ~ [value] ~ [i .. $];
>
> But again, that's not particularly efficient. What you'd really want to do would
> be increase the size of the array by one, shift all of the elements after the
> insertion point over by one, and then set the element at the insertion point to
> the value that you're inserting. And of course, if appending to the array, ~=
> would be the best way to do it.
>
> And again, inserting into arrays is _not_ efficient regardless, so if you're doing
> that sort of thing a lot, you probably should be using a different type of
> container.

Thank you very much Jonathan. That's what I was afraid of (and why I asked): 
there is no builtin func for those operations because they cannot by simple & 
cheap. The issue, imo, by deletion or insertion (except at end) is we cannot 
even use something like memcopy because the source & target mem areas overlap 
(indeed). D also refuses idioms like (to delete 1 elem):
	a[i..$-1]=a[i+1..$];
for the same reason.

Shifting elems by hand from insertion/deletion point is indeed not cheap, but 
avoids copying *all* (remaining) elements as is done by concat. I think there 
should be one builtin array-elem-shift functions that does that (also because 
it's easy to have wrong, since one must proceed backwards on insertion). The 
obvious process of the function (indicated by its name), and the fact that it 
is not called insert/delete, would clearly tell I guess that this is not cheap; 
while still providing the functionality.
What do you all think?

So, well, I'll just concatenate in the meantime.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com



More information about the Digitalmars-d-learn mailing list