I need to write a function which compares every element of an std::vector<std::shared_ptr<Shape >> shapes_
to every other element determine if the shapes overlap, and then remove one of the overlapping shapes if so. Here is what I've got currently:
class Shape {
public:
...
virtual bool overlaps(const std::shared_ptr<Shape>&) const = 0;
...
};
class Square : public Shape { ... } ;
class Circle : public Shape { ... } ;
And utilizing these classes:
std::vector<shared_ptr<Shape>> shapes_;
// ... some code populates the array
for (auto& shape : shapes_) {
// Compare to every other shape
for (unsigned long j = 0; j < shapes_.size(); j++) {
// If they overlap and they aren't the same shape
if (shape->overlaps(shapes_.at(j)) && shape!=shapes_.at(j)) {
shapes_.erase(shapes_.begin() + j);
}
}
}
However I keep running into problems where I'm iterating over a null (removed) element, or beyond the end of the array or something. I keep re configuring it this way or the other but one of these problems keeps popping up.
What would be considered the most sensible, clean way to deal with a problem where you're comparing every element of a vector to every other element, and in the process sometimes deleting some elements?
Additionally, what if I would like to print some information about each overlap that is found, and the shape that is removed?
You can use erase-remove idiom:
auto it = vec.begin();
auto end = vec.end();
while( std::distance( it, end ) > 1 ) {
auto condition = [shape=*it]( const auto &other ) { return shape->overlaps( other ); };
end = std::remove_if( ++it, end, condition );
}
vec.erase( end, vec.end() );
this lambda syntax requires C++14, but it can be easily modified to work with C++11 if necessary (by introducing temp variable shape
before lambda for example, or capturing it
by value not reference).