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