03.02.2011 19:34, Nrgyzer пишет:
== Auszug aus Steven Schveighoffer (schvei...@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.
