1

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?

transiti0nary
  • 493
  • 6
  • 25

1 Answers1

2

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).

Slava
  • 43,454
  • 1
  • 47
  • 90
  • One problem: it would remove all elements, because it tries to check overlap with itself as first loop iteration. You want pre-increment here. – Revolver_Ocelot Dec 07 '17 at 18:24
  • Thanks I will look into this, I will eventually need to print some information about each overlap (which two shapes overlapped), and which shape was removed. Would I put this inside the lambda body? – transiti0nary Dec 07 '17 at 18:28
  • @transiti0nary yes of course you can put it in lambda, or you can iterate over `end, vec.end()` range before erase. – Slava Dec 07 '17 at 18:30
  • Thanks, think it's working as intended now! Lambdas are still a bit of a mystery to me so I'd never have thought of this – transiti0nary Dec 07 '17 at 19:21
  • @transiti0nary it does not have to be a lambda, you can use a functor or any function (with std::bind if signature does not match). Using lambda is just simpler. – Slava Dec 07 '17 at 19:58