Associative array and ranges

[Stanislav Blinov]

On 02/03/2011 08:01 PM, Nrgyzer wrote:
> == Auszug aus Stanislav Blinov (blinov at loniir.ru)'s Artikel
>> 03.02.2011 19:34, Nrgyzer пишет:
>>> == Auszug aus Steven Schveighoffer (schveiguy at yahoo.com)'s Artikel
>>>> This only works if you rarely remove elements (removal in an
>>>> array is an O(n) operation).
>>>> -Steve
>>> I already thought about using an dynamic array like T[] (which
> contains all
>>> elements that should be drawn) and a second like uint[hash_t]
> which contains
>>> the indices in the first array. But it does only shit the problem
> that I can't
>>> remove an index from a dynamic array.
>>>
>>> Thanks for your suggestions.
>>>
>> Why can't you?
>> You can:
>> 1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and
> then
>> reindex all arr[i..$] elements. This is costly, because, as Steven
>> mentioned, such removal is O(n) plus you have to iterate all
> elements
>> with index>= i, and this traversal is O(n) in the worst case.
>> 2) Use unstable removal. Since you store indices separately, you can
>> just swap an element to be removed with last element in the array,
>> shrink array using slicing (arr = arr[0..$-1]) and reindex a single
>> element (the one that was previously last in the array). The
> drawback is
>> that this approach doesn't preserve order of elements in the array.
>
> Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
> there was always an error and I thought, it must be done more simply.

There is no possible simplier way of removing an arbitrary element from 
an array than doing that. Well, maybe there is: if your data is POD you 
could use a memmove with subsequent slice-shrink, but I see we're 
talking about storing references in this case.

> I'm just using a simple, dynamic array and use a for-loop to remove
> them. I don't need remove() often, but I thought there is any way to
> do it in O(1).

Actually, method (2) is O(1) if you discount hash lookup and possible 
postblit (which is absent in case of references). You could even employ 
intrusive indexing (when objects store indices), if that is suitable for 
your application, thus discarding hash table entirely.