Associative array and ranges

Stanislav Blinov blinov at loniir.ru
Thu Feb 3 08:44:45 PST 2011


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.


More information about the Digitalmars-d-learn mailing list