3. vector-Elemente iterieren und löschen

vector-Elemente iterieren und löschen

  • W

    Hallo,
    ich habe einen std::vector. In einer Schleife möchte ich dabei jedes Element auf etwas überprüfen und je nach Ergebnis dieser Überprüfung löschen.
    Mein Problem ist, dass die Iterator ungültig werden, sobald ein Element gelöscht wird.

    Ein Beispiel dieses Problems wäre:

    #include <stdafx.h>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

bool occurs_multiple_times(int value, const vector<int>& vec)
{
        unsigned int count = 0;
        for (vector<int>::const_iterator iter = vec.begin(); iter != vec.end(); ++iter)
                if (*iter == value)
                        count++;
        return (count > 1);
}

void delete_multiple_numbers(vector<int>& vec)
{
        for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter)
        {
                if (occurs_multiple_times(*iter, vec))
                        vec.erase(iter);
        }
}

int main()
{
        srand(time(0));
        vector<int> vec;
        for (int n = 0; n < 29; ++n)
                vec.push_back(rand() % 50);
        delete_multiple_numbers(vec);
        for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter)
                cout << *iter << ' ';
        return 0;
}

    (http://pastebin.com/v3x2NcPW)

    Ein runtime error tritt auf, da ein ungültiger Iterator dereferenziert wird.
    Wie löst man sowas gut?

    edit 06.11.:
    Ein Beispiel, wie der vector nach dem obrigen Code aussehen soll:
    Vorher {1, 2, 3, 4, 2, 3, 5, 4, 6, 4} -> 2, 3 und 4 tauchen mehrmals auf
    Nacher {1, 5, 6}

    Da der erste Code manchen Usern zu "simpel" war, hier ein zweites Beispiel für das Problem:

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

    delete_intersecting_rects soll alle Rechtecke löschen, die sich mit einem anderen überschneiden. Problem: Das letzte dieser Rechtecke wird nicht mehr gelöscht, da die überschneidenden nicht mehr im vector sind.

    0

  • Schau mal was vector::erase() zurückgibt 😉

    Eine gute Lösung für dein konkretes Problem wär std::sort() gefolgt von std::unique().

    Eine vermutlich noch bessere Lösung für das, was du da zu erreichen versuchst, wär std::random_shuffle.

    0
  • W

    Ah, return values sind ja doch manchmal zu was zu gebrauchen :p
    Danke dafür.

    Dieses Programm habe ich nur geschrieben, um meine Frage zu verdeutlichen. Konkret brauche ich das z.B. für eine Kollisionsabfrage in einem Spiel.

    0
  • W

    Halb 4 Nachts, ich hoffe, man verzeiht mir, dass ich nicht mehr ganz so konzentriert war 🙂

    Das ist nämlich leider doch nicht ganz die Lösung für mein Problem.
    Angenommen ich füttere die Funktion delete_multiple_numbers mit dem Vektor {1, 2, 1, 3}. Das Ergebnis soll dann sein {2, 3}.
    Die erste 1 wird richtig gelöscht, bei der zweiten ist occurs_multiple_times aber false, weshalb diese bestehen bleibt.

    0
  • T

    Wenn es nicht schlimm ist, dass die Sequenz sortiert wird, dann kann man das irgendwie so mit einem set lösen:

    int main()
{
    srand(time(0));
    std::set<int> values;
    std::vector<int> doublettes;
    typedef std::pair<std::set<int>::iterator, bool> insert_result_type;
    for (int n = 0; n < 29; ++n)
    {
        insert_result_type i = values.insert(rand() % 50);
        if(!i.second)
        {
            doublettes.push_back(*i.first);
        }
    }
    for(std::size_t n = 0; n != doublettes.size(); ++n)
    {
        values.erase(doublettes[n]);
    }
    for (std::set<int>::iterator iter = values.begin(); iter != values.end(); ++iter)
    {
        std::cout << *iter << ' ';
    }
    return 0;     
}
    0

  • Naja, dann musst du dir wohl was überlegen 😉

    Wie gesagt, evtl. sort() gefolgt von unique(). Allerdings denk ich, dass die beste Lösung einfach ein random_shuffle wär.

    0
  • 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
Anmelden zum Antworten