On 02/03/2011 08:01 PM, Nrgyzer wrote:
== Auszug aus Stanislav Blinov (bli...@loniir.ru)'s Artikel
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.
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.
