Vergleichen Sie jedes Element in einem Vektor mit jedem anderen Element, während Sie einige Elemente löschen?

Question

Ich muss eine Funktion schreiben, die jedes Element eines std::vector<std::shared_ptr<Shape >> shapes_ mit jedem anderen Element vergleicht, um zu bestimmen, ob sich die Formen überlappen, und dann eine der überlappenden Formen zu entfernen, falls dies der Fall ist. Hier ist, was ich zur Zeit habe:

class Shape { 
    public: 
    ... 
     virtual bool overlaps(const std::shared_ptr<Shape>&) const = 0; 
    ... 
}; 

class Square : public Shape { ... } ; 
class Circle : public Shape { ... } ; 

Und die Verwendung dieser Klassen:

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); 
     } 
    } 
} 

Jedoch habe ich am Laufen halten Probleme, wo ich über einen null (entfernt) Element bin iterieren, oder über die Ende des Arrays oder etwas. Ich konfiguriere es immer wieder so oder so, aber eines dieser Probleme taucht immer wieder auf.

Was wäre der vernünftigste und sauberste Weg, um mit einem Problem umzugehen, bei dem jedes Element eines Vektors mit jedem anderen Element verglichen wird und dabei manchmal einige Elemente gelöscht werden?

Zusätzlich, was, wenn ich einige Informationen über jede Überschneidung, die gefunden wird, und die Form, die entfernt wird, drucken möchte?

Answer 1

kann erase-remove Idiom verwenden:

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()); 

Diese Lambda-Syntax erfordert C++ 14, aber es kann leicht mit C++ 11, falls erforderlich (durch die Einführung von Variable TEMP shape vor lambda arbeitet modifiziert werden, um Beispiel oder Erfassung it von Wert nicht Referenz).