CODEWITHSUNDEEP
c++vector
shn
shn

Reputation: 5266

removing some elements from a vector by position

what is the fastest way to remove a set of non-contiguous elements (which I have their positions) from a vector ? Or getting a new vector without these elements.

For example I have vector v1 = <5, 9, 6, 7, 12, 0, 3>. And I have a vector of positions that I want to eliminate vector rem = <0, 3, 4, 6> or a vector containing true/false depending on whether or not the element should be eliminated or not vector rem = . Then the new vector would be vector v2 = <9, 6, 0>.

Upvotes: 0

Views: 289

Answers (3)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

If order of the elements in the original vector does not matter I would suggest you iterate over the indices you want to remove in increasing order(that is important) and for each element to swap it with the last element in the vector and than call pop_back.

You will also have to perform checks to see if the last element of the vector is to be removed before performing the swap. While the index of the last element is also among the ones to be removed pop_back and then do the swap and pop_back.

EDIT: just to clarify - as you have the indices of the elements to be removed already sorted, you may check if the last element is to be removed by simply checking the last value you have not yet removed in the array of indices. Use an helper integer index to keep track of which that index is, initialize it to the size of the array of indices to remove minus one and decrement it by one each time the last element is to be removed.

Upvotes: 2

Rob I
Rob I

Reputation: 5737

I would iterate through the vectors together, kind of like a merge algorithm. Something like this:

int index1=0, index2=0;

while (index1 < v1.size()) {
    if ( index2 < rem.size() && index1 == rem[index2] ) {
        index2++; // skip this one
    }
    else {
        v2.push_back(v1[index1]); // keep this one
    }

    index1++;
}

Using iterators would be cleaner, and note that the rem vector must be sorted.

Edit: corrected by using a 3rd variable name for the indices vector.

Upvotes: 0

EddieBytes
EddieBytes

Reputation: 1343

By fastest I'm assuming with the shortest amount of code and also a bit of optimization:

size_t i = 0;
size_t end = v1.size();
vector<int> vresult;

vresult.reserve(v1.size() - rem.size()); // avoid reallocations

size_t remIt = 0;
for ( ; i != end; ++i )
{
  if ( i != rem[remIt] )
    vresult.push_back(v1[i]); // push our element into the new vector
  else
    remIt++;
}

Might not compile, code above is written purely for its algorithm.

Upvotes: 0

Related Questions