STL: Set (Menge) soll nicht intern sortieren...

Hallo!

Weiß jemand von euch, ob man eine Menge (set) dazu bringen kann, nicht zu sortieren?
Im Konstruktoraufruf läßt sich ein Ordnungskriterium angeben - default ist da less<T> angegeben. Will im Prinzip Zahlen in eine Set einfügen und zwar am Ende (eine push_back-Methode gibt es ja nicht). Jetzt fragt sich vielleicht einer von euch, warum ich überhaupt eine Menge statt z.B. einer list verwende: Ich wollte auf einfache Weise verhindern, dass doppelte Elemente auftreten...tja...
Gibt es eine unsortierte set? Ich kann ja nur insert zum Einfügen verwenden

Danke schonmal

Gruß,
[NeoSpee]

Shade Of Mine

ein set muss _immer_ sortiert sein, sonst kann es ja nicht klappen

doppelte elemente kannst du zB mit unique aus algorithm raus suchen, oder direkt vor dem einfügen testen (zB wrapper um list schreiben).

Nein, set's sind per Default sortiert, du könntest dir nur eine eigene Vergleichsfunktion schreiben, die nicht anhand des Zahlenwertes vergleicht (dürfte allerdings problematisch werden, da diese auch für vorhanden-Tests genutzt wird) oder eine eigene unsortierte Menge auf list-Basis schreiben:

template<typename T> class USet
{
public:
  ...
  bool insert(const T& val)
  {
    if(find(data.begin(),data.end(),val)==data.end()) return false;
    data.push_back(val);
    return true;
  }
  ...
private:
  list<T> data;
};

Danke!

Habe jetzt wieder eine Liste verwendet, und beim Einfügen auf doppelte Elemente geprüft. Funktioniert auch wunderbar...wenn ich damals nicht so faul gewesen wäre (wollte mir durch die Menge das Suchen nach doppelten Elementen ersparen), hätte ich jetzt auch dieses Problem nicht gehabt

Na ja, wieder was dazu gelernt

Gruß! und nochmals Danke!

Mathias

So wie du es anwenden möchtest müsstest du im Schnitt immer halb soviele Objektvergleiche durchführen wie es Elemente in deinem Container gibt um zu wissen ob du das Objekt einfügen kannst oder nicht.
Durch die Sortierung reduziert sich dies auf (wenn ich mich ganz nicht irre) log (Anzahl der Elemente). Also ein kleines bißchen schneller.

Die Definition einer Menge erlaubt deren Sortierung. Wenn du einen Container benötigst, bei dem die Position der Elemente fest sein soll musst du auf eine andere Container-Art zurückgreifen.

volkard

wenn du ne set nimmst, haste die einfügereihenfolge verloren.
wenn du ne list (oder besser queue) nimmst, kannste nur mit O(n) doppel verhindern.

die lösung: nimm beides.
beim einfügen schauste erst in die set, ob da schon sowas ist und nur wenn da nix ist, fügste in set und queue ein. beim löschen (löschen am anfang nehme ich an) brauchste nix weiter zu beachten, kannst ja nur sachen löschen, die drin sein.