3. vector-Elemente iterieren und löschen

vector-Elemente iterieren und löschen

  • T

    dot schrieb:

    [...]Allerdings denk ich, dass die beste Lösung einfach ein random_shuffle wär.

    +1 btw.

    0
  • W

    @ Tachyon: Es geht mir darum, dass es mit einem vector möglich ist.

    @ dot: Wie gesagt, der oben von mir gepostete Code ist nur ein vereinfachtes Beispiel und hat außer dem Prinzip nichts mit den praktischen Anwendungsfällen zu tun.

    0

  • Dann verrat uns vielleicht mal die praktischen Anwendungsfälle, sodass wir eine passende Lösung vorschlagen können...

    0
  • W

    Wozu brauchst du denn noch anderen Code?
    Ich habe meine Frage doch geschildert und der Code oben zeigt genau ein solches Problem.

    Wenn du es komplexer haben willst, denk dir für das int einfach irgendeine Klasse und in Zeile 13 irgendwelche Funktionsaufrufe.

    0

  • Was ich damit sagen wollte: Wenn du wirkliche Hilfe willst, dann erklär uns, was du eigentlich genau erreichen willst anstatt dich auf den einen Lösungsweg, den du gerade verfolgst zu verbeißen. Wenn du nur deinen Lösungsweg fixen willst, dann steht die Antwort ja schon in meinem ersten Post. Der Punkt ist aber, dass dieser eine Lösungsweg vermutlich fernab eines guten Lösungsweges liegt...

    0

  • Wie wär´s dann mit remove_if / erase ?

    0
  • W

    @ dot:

    // CLASS RECTANGLE
class Rectangle
{
public:
	Rectangle() : x(0), y(0), width(0), height(0) {}
	Rectangle(int x_, int y_, int w, int h) : x(x_), y(y_), width(w), height(h) {}
	bool intersects(const Rectangle& other);
	bool includes_point(int px, int py);
private:
	int x;
	int y;
	int width;
	int height;
};

bool Rectangle::intersects(const Rectangle& other)
{
	if (includes_point(other.x, other.y)) return true;
	if (includes_point(other.x + other.width, other.y)) return true;
	if (includes_point(other.x, other.y + other.height)) return true;
	if (includes_point(other.x + other.width, other.y + other.height)) return true;
	if ((x < other.x) && (x+width > other.x+other.width) && (y > other.y) && (y+height < other.y+other.height)) return true;
	if ((x > other.x) && (x+width < other.x+other.width) && (y < other.y) && (y+height > other.y+other.height)) return true;
	if ((x < other.x) && (x+width > other.x+other.width) && (y < other.y) && (y+height > other.y+other.height)) return true;
	return false;
}

bool Rectangle::includes_point(int px, int py)
{
	return (px > x) && (px < x+width) && (py > y) && (py < y+height);
}
// END CLASS

// Lösche jedes Rechteck, dass sich mit einem anderen überschneidet
void delete_intersecting_rects(vector<Rectangle>& vec)
{
	for (vector<Rectangle>::iterator iter1 = vec.begin(); iter1 != vec.end(); ++iter1)
	{
		for (vector<Rectangle>::iterator iter2 = vec.begin(); iter2 != vec.end(); ++iter2)
		{
			if (iter1 == iter2)
				continue;
			if (iter1->intersects(*iter2))
			{
				iter1 = vec.erase(iter1);
				break;
			}
		}
	}
}

    @ DocShoe: remove_if braucht aber eine Funktion, die genau ein Element als Parameter hat. Meine braucht aber ein Element und den Vektor.

    0

  • Ok, da stellt sich nun natürlich die Frage mit wievielen Rechtecken du es da zu tun hast und ob es Performancemäßig ein Problem gibt.

    Der Bug in dem Code ist übrigens: Im Fall von einem erase() darfst du iter1 natürlich nicht inkrementieren...

    0
  • W

    Ok, da stellt sich nun natürlich die Frage mit wievielen Rechtecken du es da zu tun hast und ob es Performancemäßig ein Problem gibt.

    Weiß nicht, vielleicht 50. Wäre aber auch nicht uninteressiert an einer performanten Lösung für ganz viele Rechtecke 🙂

    0

  • Naja, die beste Lösung wär, von vornherein keine sich überlappenden Rechtecke zu erzeugen.

    Abgesehen davon: Eine effiziente Lösung für sehr viele Dreiecke würde sich irgendeine Beschleunigungsstruktur zu Nutze machen. Man könnte z.B. alle Rechtecke in ein Grid einsortiert halten, um dann beim Testen nicht immer alle anderen Rechtecke überprüfen zu müssen, sondern nur die, die das aktuelle Rechteck auch wirklich potentiell schneiden.
    Statt vector::erase() wäre es vermutlich effizienter std::remove_if() zu verwenden, denn bei einem erase() muss immer alles was hinter dem gelöschten Element liegt nach vorne kopiert werden.

    Aber wenn du nur so 50 Rechtecke hast, dann wird die Performance sowieso eher kein Problem sein 😉

    0
  • W

    Die Sache mit dem Grid verstehe ich nicht.

    Ob ich nun erase oder remove_if verwende ist ja egal, denn funktionieren tut es trotzdem nicht.

    0

  • Wurstinator schrieb:

    @ DocShoe: remove_if braucht aber eine Funktion, die genau ein Element als Parameter hat. Meine braucht aber ein Element und den Vektor.

    Nö. remove_if kann auch mit Funktoren arbeiten, die einen internen Status besitzen (und damit z.B. deinen Vektor):

    struct MyPredicate : std::unary_function<Rectangle,bool>
{
   std::vector<Rectangle>& Data_;

   MyPredicate( std::vector<Rectangle>& v ) : Data_( v )
   {
   }

   bool operator()( const Rectangle& r ) const
   {
      // auf Überschneidung testen
   }
};

    Das Dumme ist nur, dass du für das aktuelle Rechteck dessen Position im Vektor nicht mehr kennst, d.h. du müsstest erst die Position feststellen und dann mit den nachfolgenden Rechtecken auf Überschneidung testen.

    0
  • T

    Wieso fügst Du überlappende Rechtecke überhaupt in den Vektor ein, wenn Du sie nicht drin haben willst? Du kannst doch vor ein Einfügen z.B. mit find_if prüfen, ob das einzufügende Rechteck mit anderen überlappt, und es dann gar nciht erst einfügen.

    0
  • W

    @ DocShoe: Okay, das wusste ich nicht. Trotzdem entfernt remove_if nur das erste überlappende Rechteck (oder die ersten, wenn sich mehrere an einer Stelle überlappen) und nicht das letzte.

    @ Tachyon: Vielleicht brauche ich vorher alle Rechtecke und später nur noch die, die sich nicht überlappen. Vielleicht verändern sie sich, nachdem sie eingefügt wurden.

    0
  • W

    push

    0
  • K

    Vielleicht solltest Du ein neues Thema aufmachen, dessen Titel auch etwas mit Deinem aktuellen Problem zu tun hat. Wenn ich mir nämlich hier Deinen ersten Beitrag durchlese, schreit das ganz einfach nach einer Antwort a la "Benutze erase-remove_if". Ich habe zumindest keine Lust, zu suchen, wo Deine aktuelle Frage steht und worum es eigentlich geht...

    0
  • W

    Der Titel passt und das Problem ist das selbe wie am Anfang.

    Da die Frage scheinbar nicht ganz klar war, habe ich den Startpost jetzt noch etwas erweitert.

    0
  • ?

    Is das ne blöde Idee?

    void delete_intersecting_rects(vector<Rectangle>& vec)
{
    vector<bool> intersects;
    bool intersectTmp;
    for (vector<Rectangle>::iterator iter1 = vec.begin(); iter1 != vec.end(); ++iter1)
    {
        intersectTmp = false;
        for (vector<Rectangle>::iterator iter2 = vec.begin(); iter2 != vec.end(); ++iter2)
        {
            if(iter1==iter2) {
                continue;
            }
            if (iter1->intersects(*iter2))
            {
                intersectTmp = true;
                break;
            }
        }
        intersects.push_back(intersectTmp);
    }
    int position = intersects.size() -1 ;
    for(vector<bool>::reverse_iterator ri = intersects.rbegin(); ri != intersects.end(); ++ri, --position)
    { //von hinten löschen, damit vorne die positionierung nicht verkackt weil der rest nachrutscht
        if(*ri)
        {
            vec.erase(vec.begin()+position);
        }
    }
}

    Bin grad a bißerl müde und unkonzentriert, also verzeih falls ich da grad nen fundamentalen fehler mache, aber so sollts zumindest gehen. Die Prüfung am Anfang kann man noch optimieren, weil man jedes paar doppelt prüft - aber zufaul drüber gedanken zu machen.

    0
  • W

    Hm, ich hatte die Idee, einen vector<size_type> zu erstellen, mit dem die Indexe der zu löschenden Elemente gespeichert werden. Deine vector<bool>-Idee gefällt mir besser, aber ich find es trotzdem nicht so toll, wenn man einen neuen vector dafür erstellen muss.
    Vielleicht kennt ja jemand eine noch bessere Lösung 🙂

    0
Anmelden zum Antworten