How can I eliminate an element in a vector if a condition is met

I have a vector of Rect: vector<Rect> myRecVec;

I would like to remove the ones which are overlapping in the vector:

开发者_如何学编程

So I have 2 nested loop like this:

vector<Rect>::iterator iter1 = myRecVec.begin();
vector<Rect>::iterator iter2 = myRecVec.begin();

while( iter1 != myRecVec.end() ) {
    Rectangle r1 = *iter1;

    while( iter2 != myRecVec.end() ) {
        Rectangle r2 = *iter1;

        if (r1 != r2) { 
             if (r1.intersects(r2)) {
                 // remove r2 from myRectVec
             }
        }
    }
}

My question is how can I remove r2 from the myRectVect without screwing up both my iterators? Since I am iterating a vector and modifying the vector at the same time? I have thought about putting r2 in a temp rectVect and then remove them from the rectVect later (after the iteration). But how can I skip the ones in this temp rectVect during iteration?

---

1. You need to increment iter1 and iter2.
2. erase returns an iterator to the next element. When you delete, use this instead of incrementing the iterator.

Like so:

while( iter1 != myRecVec.end() ) {
    Rectangle r1 = *iter1;

    iter2 = iter1 + 1;

    while( iter2 != myRecVec.end() ) {
        Rectangle r2 = *iter2;

        if( r1.intersects(r2) ) {
            iter2 = myRectVec.erase(iter2);
        }
        else {
            ++iter2;
        }
    ++iter1;
}

---

First of all, you probably only want to run iter2 from iter1 to end, since r1.intersects(r2) iff r2.intersects(r1). Once you make this adjustment, all you will have to do is not increment r2 in the same cycle you erase it. You can do this, because erasing an element guaranteed does not cause std::vector to reallocate memory.

---

Another technique is to start at the end and iterate to the front, then the current iterator is alwasy valid and the the begin() of course never changes.
It's also more efficient since you move fewer elements.

If you are removing a lot of items, it may be faster (and easier) to copy those that are NOT eliminated to a new vector and then replace the original.

Finally if the elements can be sorted you can use set_intersects to find the intersecting vector ranges.

---

Use vector::erase which returns an interator to the element after the erased element. You can use this iterator to keep looping, (after checking it against .end()) . Don't use any other iterators since it may have been invalidated.

---

1. Using erase is probably a bad idea because it causes all of the rectangles appearing after the erasure point to be copied one entry down. Although you are spending O(n^2) time anyway just on the comparisons, the added copying might amount to significant overhead. I would strongly suggest copying the recatngles you want to keep into an output vector instead. (If you want the operation to affect the input vector, start by cloning it and clearing it, and then filter the clone and copy the surviving rectangles back to the original vector.

2. Did you consider the fact that in general there are many ways to remove rectangles such that the remaining ones do not overlap? Do you have any preference?

3. Assuming the answer to 2 is that any maximal subset will do (maximal subset = a subset X such that each rectangle not in X intersects at least one that is in X), if you first sort the rectangles by, say, their bottom left x coordinate (and then possibly secondarily by the y coordinate) you stand a good chance of reducing the total number of comaprisons, although the worst case remains O(n^2).

---

Does the order of elements in the vector matter? If not, swap the item you want to delete with myRecVec.back() (may no-op but that's ok) and then do a pop_back. This shouldn't invalidate iterators and will probably perform better than shifting the elements forward on each erase.

If order does matter you can use reverse iteration instead of forward iteration (you would save an iterator of the item to erase and then increment the reverse iterator).