Removing multiple elements from array

[H. S. Teoh]

On Fri, Dec 20, 2013 at 07:13:59PM -0800, H. S. Teoh wrote:
> On Fri, Dec 20, 2013 at 07:01:17PM -0800, Ali Çehreli wrote:
> > On 12/20/2013 06:17 PM, aldanor wrote:
> > >On Saturday, 21 December 2013 at 01:42:04 UTC, Ali Çehreli wrote:
> > >
> > >>That's probably a bug, right? The indexes would probably become off as
> > >>the array gets shorter.
> > >
> > >Note the .reverse there?
> > 
> > Yes, I missed that part. :)
> > 
> > >Which makes sure indices don't get off. Still,
> > >that's probably an inefficient way of doing this...
> > 
> > Yeah, every removal would move the right-hand elements one position
> > to the left. But you would be removing only M times (the number of
> > indexes). So the complexity is I think O(M logM) + O(NM) for sorting
> > the indexing plus removing M elements by shifting at the order of N
> > elements.
> > 
> > The range solution that I've come up with is I think O(M log M) +
> > O(M) + O(N), for sorting the indexes, removing the duplicates with
> > uniq and iterating the elements. Since O(M log M) dominates O(M), it
> > should be O(M log M) + O(N).
> [...]
> 
> If you know the which elements you're going to remove, you can remove
> them all at once in O(N) time:
> 
> 	int[] arr = [ ... ];
> 	for (i=0, j=0; i < arr.length; i++)
> 	{
> 		if (deleteThisElement(arr[i]))
> 			continue;
> 		if (j < i)
> 			arr[j] = arr[i];
> 		j++;
> 	}
> 	arr.length = j;

There's also a Phobos solution: the above code is equivalent to:

	import std.algorithm : remove;
 	int[] arr = [ ... ];
	arr = arr.remove!deleteThisElement();


> Of course, if you know which *indices* you're going to remove, then
> you can do even better (by starting your loop at the first index to be
> deleted).
[...]

Unfortunately, while std.algorithm.remove does provide a way to do this
if the number of indices to remove are known beforehand, it doesn't seem
to be able to remove a dynamic list of indices. Probably an enhancement
request should be filed:

	http://d.puremagic.com/issues

If the number of indices to remove are fixed, though, you can do this:

	import std.algorithm : remove;
 	int[] arr = [ ... ];
	int i1, i2, i3;  // indices to remove
	arr = arr.remove(i1, i2, i3);


T

-- 
It's bad luck to be superstitious. -- YHL