Efficient way to remove elements from std vector according to predicate

Question

I'm writing an algorithm which is supposed to remove from a set of points stored inside a vector every element which is inside any of a list of rect that I supply.

I'm using it also as a testing ground for C++11 so, since I'm still getting used to new features, I would like to know if this is an efficient approach or if it has some particular flaw that I'm not getting.

vector<tuple<u16, u16, u16, u16>> limits;

FOR_EACH_AREA_TO_REMOVE
   limits.push_back(make_tuple(
       area->x - VIEWPORT_SIZE_X/2, 
       area->x + VIEWPORT_SIZE_X/2, 
       area->y - VIEWPORT_SIZE_Y/2, 
       area->y + VIEWPORT_SIZE_Y/2));
FOR_EACH_AREA_TO_REMOVE_END

vector<Point2D> points;

remove_copy_if(suitablePoints.begin(), suitablePoints.end(), 
               points.begin(), [&](const Point2D &point) {
  for (auto limit : limits)
    if (point->x > get<0>(limit) && 
        point->x < get<1>(limit) && 
        point->y > get<2>(limit) && 
        point->y < get<3>(limit))
      return true;

  return false;
  }
);

This seems the more trivial solution to the problem, create a vector of bounds that must be excluded from the point set and then iterate over the set point. I wonder if there's a better approach to the problem. I would like to point out that the set of points could be huge, while the set of rects is indeed enough limited.

Answer 1

You could change auto into auto const&, since you do not need to create a copy of each rectangle in limits as you iterate through the collection:

for (auto const& limit : limits)
//        ^^^^^^

This should bring some performance improvement (but as always when performance is concerned, measure it before drawing any conclusions).

Also, unless you need to create a copy of the elements you remove from your vector (the text of the question does not mention this), you could use std::remove_if() instead of std::remove_copy_if().

std::remove_if() works by overwriting removed elements with subsequent ones, and will return the new logical end of the vector without actually resizing the vector itself (which is a desirable behavior if you do not need to do that).

It is therefore up to you whether to do this or not by calling std::vector::erase() after std::remove_if(). This is a very common practice which also has a name.