3. Doppelte Elemente aus einem unsortierten Container entfernen

Doppelte Elemente aus einem unsortierten Container entfernen

  • R

    Hi

    Ich möchte aus einem STL-Container alle doppelten Elemente entfernen, leider kann ich auf dem Datentyp, der in dem Container enthalten ist, keine Ordnung definieren, weshalb ein sortieren, und damit std::unique usw. entfällt.

    Um dieses Problem zu lösen habe ich mir folgendes ausgedacht:

    #include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

class Point { // Für Punkte kann man keine Ordnung definieren, oder?
public:
 Point(int _x, int _y) : x(_x), y(_y) 
 {
 }
 int x, y;
};

ostream& operator<<(ostream& o, const Point& p) {
  o << "(" << p.x << "," << p.y << ")";
  return o;
}

bool operator==(const Point& a, const Point& b) {
  return a.x == b.x && a.y == b.y;
}

int main(void) {

  vector<Point> v;

  v.push_back(Point(1,1));
  v.push_back(Point(3,1));
  v.push_back(Point(2,1));
  v.push_back(Point(5,4));
  v.push_back(Point(3,1));
  v.push_back(Point(1,6));
  v.push_back(Point(7,1));
  v.push_back(Point(1,8));
  v.push_back(Point(7,1));
  v.push_back(Point(2,1));
  v.push_back(Point(4,1));
  v.push_back(Point(1,1));

  copy(v.begin(), v.end(), ostream_iterator<Point>(cout, " "));
  cout << endl;
  for( int i = 0; i < v.size(); ++i ) {

    v.erase(remove(v.begin() + i + 1, v.end(), v[i]), v.end());
  }  

  copy(v.begin(), v.end(), ostream_iterator<Point>(cout, " "));
  cin.get();
  return 0;
}

    Aber jetzt meine Fragen.

    Ist das überhaupt gültiger C++ Code? Ich habe mal gelesen dass man einen Container nicht verändern darf wenn man durch seine Elemente iteriert. Ich weiß sicher dass man das bei Iteratoren nicht darf, weil der Zähliterator ungültig werden kann, aber galt das auch für einen Zugriff über einen Index?

    Gibt es noch eine bessere Möglichkeit, ohne über einen Index auf die Elemente zuzugreifen, damit ich z.B. auch std::list verwenden kann?

    Danke, Stefan

    0
  • ?

    Klar kannst du für Punkte ne Ordnung definieren. In diesem Fall wär das einfachste wohl

    bool operator<(Point const &p, Point const &q) {
  return p.x < q.x || (p.x == q.x && p.y < q.y);
}

    ...also ne einfache lexikographische Ordnung.

    0
  • R

    Stimmt! Wieso bin ich nicht auf sowas einfaches gekommen 😕

    Wahrscheinlich weil man bei den komplexen Zahlen keine Ordnung hat, oder Irre ich schon wieder? Warum nimmt man für diese Zahlen nicht diese Ordnung?

    Aber das ursprüngliche Problem interessiert mich immernoch wie man vorgehen würde wenn man für einen Datentyp keine Ordungsrelation hätte, also unabhängig davon dass ich mich bei Punkten geirrt habe, wie würde man die Elemente aus einem unsortierten Container entfernen und ist meine Lösung gültiger C++ Code?

    0
  • ?

    Du kannst jede Menge ordnen, und das meistens auf mehrere Weisen. Für die komplexen Zahlen gibt es, wenn ich mich recht entsinne, überüberabzählbar viele Ordnungsrelationen - und die lexikographische ist für Probleme mit komplexen Zahlen eher selten brauchbar.

    0
  • J

    Das Problem bei Ordnungen auf mathematischen Objekten wie C(komplexe Zahlen) ist, daß man hier meist noch ein paar Zusatzeigenschaften haben möchte:

    Zum Beispiel wäre es nett, wenn für c>0

    a*b > a*c <=> b > c

    und da liegt auch schon das Problem: nehmen wir mal i.
    Ist i > 0, dann können wir jede Ungleichung einfach mit i multiplizieren. Und danach nochmal... das ist aber eine Multiplikation mit -1... also hätten wir eigentlich das Zeichen umdrehen müssen. Wählen wir i < 0, so besteht das gleiche Problem. zweimal rumdrehen ist genauso wie garnicht rumdrehen. Wenn wir also eine Ordnung haben wollen, die je zwei Werte vergleichbar macht, so bleibt uns nur noch der Ausweg i=0 und das stimmt wie wir wissen auch nicht.

    MfG Jester

    0
  • R

    Okay, Danke! Bleiben aber immernoch die anderen Fragen ungeklärt ...

    0
  • B

    Gibt es noch eine bessere Möglichkeit, ohne über einen Index auf die Elemente zuzugreifen, damit ich z.B. auch std::list verwenden kann?

    Hängt vom Iterator Type ab. Bei std::list wird nur der Iterator der auf das gelöschte Element zeigt ungültig. Bei std::vector alle.

    0
  • R

    Sicher? Also ich meine steht das auch so im C++ Standard?

    Soviel ich weiß ist bei std::list der Iterator vom Type BidirectionalIterator, und bei std::vector hat man einen RandomAccessIterator. Nun kann doch, denke ich, ein
    RandomAccessIterator alles was ein BidirectionalIterator auch kann.

    Gibt es eine Methode die für alle Iteratoren/Container funktioniert? Also das ich mir eine Templatefunktion für alle Container schreiben kann? Die meisten Container haben ja mindestens bidirektionale Iteratoren.

    0
  • B

    Sicher? Also ich meine steht das auch so im C++ Standard?

    Sicher, dass Referenzen auf Elemente einer verketteten List gültig bleiben ist ja eins der Hauptvorteile gegenüber eines Arrays. Der Standard ist nicht so dumm das nicht zu garantiren.

    Gibt es eine Methode die für alle Iteratoren/Container funktioniert? Also das ich mir eine Templatefunktion für alle Container schreiben kann? Die meisten Container haben ja mindestens bidirektionale Iteratoren.

    Nein gibt es nicht. Da hättest du eigentlich auch selber drauf kommen können, da nicht alle Container löschen von Elementen erlauben (Array). Oder wieso glaubst du, dass std::unique nichts löscht sondern nur herumschieb und das neue Ende des Container zurückgibt? Mit nur Iteratoren kommst du hier nicht weiter.

    0
  • R

    Okay, Danke für die Antworten!

    0
Anmelden zum Antworten