C++, Removing an element from a pair, inside a function

I am using C++, I have a vector of paired variables, for which the first element is a vector and the second element is an integer. My problem is that I am trying to remove certain elements from this vector, and can't seem to get it to work!

The code is shown below, and everything is working as I'd expect up to the line:

vec1.erase(i);

as I can cout some other relevant variables from the vector to the screen, and they are c开发者_JAVA百科orrect.

compareVecs is just an element of this class that compares some variables.

void myCode::PairRemoval(vector<myTypeDef> &vec1, const vector<myTypeDef> &vec2, double conditionMax) {
  bool condition=false;
  for (unsigned int i=0; i<vec1.size(); i++){
    for (unsigned int j=0; j<vec2.size(); j++){
      if (vec1[i].first.compareVecs(vec2[j].first) <= conditionMax) {
    condition = true;
       break;
      }
     }  
    if (condition) {
      vec1.erase(i);
      cout<<"removed"<<endl;
    } 
  }
}

I hope to remove the pair from this vector, if the condition is met.

Thanks in advance for any help!

The problem with erase is that it erases the element you're pointing at while also changing the size of the vector. It's massively inefficient as vector requires that each subsequent element be copied down. Hence, if you have 15 elements and erase the first element you've now just copied 14 elements.

You can get around this by using the

for(vector<whatever>::iterator foo = myVector.begin(); foo != myVector.end(); ++foo){
    if( myPredicate( foo ) ){
        foo = myVector.erase(foo);
    }
}

but as I said, it's horribly inefficient. This could take O(N^2) time if every element needs to be erased.

Instead, use the copy and swap technique:

vector<T> myNewVector;
copy_if( myOldVector.begin(), myOldVector.end(), back_inserter(myNewVector), fun_ptr(myPredicate) );
myOldVector.swap(myNewVector);

You shouldn't iterate a vector AND erase elements inside the loop. When you erase elements, the vector size changes and the indexes also change. A recommended way would be to store the elements you have to remove in another structure (like a vector) and then loop to remove them.

void myCode::PairRemoval(vector<myTypeDef> &vec1, const vector<myTypeDef> &vec2, double conditionMax) {
    bool condition=false;
    vector<vector<myTypeDef>::iterator> toRemove;
    for (vector<myTypeDef>::iterator it = vec1.begin(); it != vec1.end(); it++){
        for (unsigned int j=0; j<vec2.size(); j++){
            if ((*it).first.compareVecs(vec2[j].first) <= conditionMax) {
                condition = true;
                break;
            }
        }  
        if (condition) {
            toRemove.push_back(it);
        } 
    }
    for(int i = 0; i < toRemove.size(); i++){
        vec1.erase(toRemove[i]);
    }
}

The standard library already contains a function [template] for removing elements from a sequence based on a custom predicate so it might be clearer to abstract your "condition" into a functor and to use the standard erase/remove idiom.

This sample compiles but I wasn't able to give the functor a meaningful name because I'm not sure what the rationale behind the logic of your condition is.

#include <vector>
#include <algorithm>

struct x { double compareVecs( const x& ) const; };
typedef std::pair<x, int> myTypeDef;

class ErasePredicate
{
public:
    ErasePredicate(const std::vector<myTypeDef>& vec2, double conditionMax)
        : _vec2(&vec2), _conditionMax(conditionMax) {}

    // The valuable condition logic goes here
    bool operator()( const myTypeDef& v ) const // assume this can be const ref
    {
        for (size_t j = 0; j != _vec2->size(); ++j)
        {
            if (v.first.compareVecs((*_vec2)[j].first) <= _conditionMax)
            {
                return true;
            }
        }
        return false;
    }

private:
    // pointer, to get copy-ctor and op= for free
    const std::vector<myTypeDef>* _vec2;
    double _conditionMax;
};

void PairRemoval(std::vector<myTypeDef> &vec1,
                 const std::vector<myTypeDef> &vec2,
                 double conditionMax)
{
    // The mechanics of performing the erase is handled by stdlib functionality
    vec1.erase(std::remove_if(vec1.begin(),
                              vec1.end(),
                              ErasePredicate(vec2, conditionMax)),
               vec1.end());
}

I think your for loop is flawed. Say i is 5 and you remove element 5. i then gets incremented to 6 for the next iteration. But the element that used to be element 6 now is at position 5. This means that your loop won't erase to subsequent elements from the vector.

As a workaround, decrement i after erasing the element from the vector.

by referring to the c++ reference, i think erase should take an iterator as its argument.. maybe your code should be vec1.erase(vec1.begin()+i);

It looks like you want to remove some elements from a container. The C++ Standard Library has an algorithm for just that: std::remove . The only caveat is that it doesn't remove anything from the container :)

If the elements to be removed can be identified with a simple operator==, you can use std::remove. If it's more complicated to identify the elements, you need to use std::remove_if.

Now for the caveat. In the C++ Standard Library, algorithms are decoupled from containers. std::remove takes a couple of iterators, so it can mess with the elements between those iterators, but it doesn't know anything about the container, hence can't change it. The solution is the erase-remove idiom.

auto it = std::remove_if( v.begin(), v.end(), some_predicate_returning_bool());
myOldVector.erase(it, v.end()); // or a lambda^

First, we use remove to shuffle "unremoved" elements towards the beginning of the container. remove returns an iterator which points at the first element we do not want.

std::vector<int> v { 1, 3, 3, 7 };
auto it = std::remove(v.begin(), v.end(), 3);

After this call, v would contain 1, 7, 3, 7 and it points past the fist 7. (1 kept its place and 7 was shuffled behind it). Calling

v.erase(it, v.end());

results in v becoming 1, 7.