== 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. 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).
