remove a set of values in an array given a set of indexes

knivil

cooky451 schrieb:

Guys.. he doesn't have values, he already has the index of the elements.

Maybe you can use unused bits in your "number".

cooky451

..what?

eg. bit 31 is never set because the input range (of array) is limited. So you can loop through Index_to_remove, set bit 31 for every index in array, then loop through array and remove the values with bit 31 set...

cooky451

Geri1 still didn't write if the order is actually important or not, I think it's kinda senseless to continue without that information.

Do you have to keep the order?

yes i want to keep the order!

but would also be interested in the approach without keeping the order...

Michael E.

Geri1 schrieb:

Do you have to keep the order?

yes i want to keep the order!

Then for few elements to remove I can't think of a better way than sorting the index array and moving pointers through the arrays like:

index_to_remove.sort!
i = 0, j = 0, k = 0
while i != array.size
  if k != index_to_remove.size && i == index_to_remove[k]
    k += 1
  else
    array[j] = array[i]
    j += 1
  end
  i += 1
end
truncate array to the correct size

Edit: Oh, of course you can do this in linear time, e.g. with a boolean array which marks for every entry in array if it has to be deleted. This is exactly Tim's method but in the general case, i.e. you can't store additional chunks of information in the array, it requires lineare space. Depending on the size of index_to_remove, my algorithm can be faster in practise than this linear approach.

camper

to summarize:
The trick to make the remove-Operation linear is to transform it into something like remove_if. Better than linear complexity isn't possible for this, unless the array supports removal of elements in less than linear time or if the order of elements isn't required to be stable.
in order to achieve this, several options exist:
- sort the set of indexes to be removed (O(N*log(N) in general)
- create an array of bool for all values (linear + requires extra memory)
- use special values instead of bool if such exist (linear, may be expensive if T is expensive to copy - though in that case the remove operation itself will be expensive too).

Other options may exist if the underlying data structure isn't an array.

krümelkacker

you don't need to explicitly create this boolean array since it can be generated on-the-fly when needed from the sorted indices.

Michael E.

krümelkacker schrieb:

you don't need to explicitly create this boolean array since it can be generated on-the-fly when needed from the sorted indices.

(Highlighting by me.) The indices are not sorted. Are you confused by camper's enumeration? The items are options, not a workflow.

also so?

// remove a set of values in an array given a set of indexes
void remove_values_given_index() {
	int arr[] = {1, -5, 3, 2, -1, 6, 7, 1, -4, 3, 2, 6, -1, -5, 4};
	vector<int> array_(arr, arr+15);
	int index[] = {0, 3, 5, 9, 2};
	vector<int> index_to_remove(index, index+5);

	std::sort(index_to_remove.begin(), index_to_remove.end());

	int o = 0; 
	int k = 0;
	int j = 0;

	while(k != array_.size()) {
		// index not available
		if(j < index_to_remove.size() && k == index_to_remove[j]) {
			j += 1;
		}
		else {
			array_[o] = array_[k]; 
			o += 1;
		}
		k += 1;
	}

	array_.resize(index_to_remove.size());
}