012
21.05.2004, 13:37 Uhr
virtual
Sexiest Bit alive
(Operator)
|
ich denke es kommt darauf an, was du eigentlich machen willst:
Du suchst also einen Container, wo jedes Element nur einmal drin vorkommt. Dann wäre ein std::set die natürlichste Lösung. Allerdings hat std::set (und auch std::list) den Nachteil, daß Du da nicht mit dem []- Operator auf die Element zugreifen kannst. Dh wenn Du sehr oft vor der Fragestellung stehst "Wo lautet der Wert vom 4711. Element), dann sind sowohl set als auch list die eher falsche lösung.
Der Einwand, daß das Löschen aus einem std::vector inperformant sei, ist prinzipiell richtig, an dieser Stelle greift er aber nicht. Denn:
| C++: |
std::vector<std::string> data;
... //1 .
std::sort(data.begin(),data.end()); // 2.
std::vector<std::string>::iterator p = std::unique(data.begin(),data.end()); //3.
data.erase(p, data.end()); // 4.
|
Gehen wir mal Schritt für Schritt durch:
1. Im ersten Schritt wird der Container ja aufgebaut. Hier gilt vom Zeitbedarf des Aufbaus vermutlich list <= vector < set; dh set wird hier mit abstand das langsamste sein. Schwieriger wird es allerdings beim Unterschied vector/list: wenn Du ungefähr abschätzen kannst, wie groß der Vector wird, kannst du ein data.reserve machen und damit dürfte die Vectorlösung dann die schnellste sein (weil das umkopieren der Elemente entfällt und der eigentliche Einfügevorgang deutlich einfacher als bei einer List wäre).
2. Das sortieren entfällt bei set, dafür hat man eben im ersten Schritt bezahlen müssen. Hier ist die ungleichung set < vector < list, wobei das Sortieren einer list deutlich langsamer von Statten geht als von einem Vector.
3.Das unique kopiert die elemente um (!Es macht keine Löschoperation!). Hier sind je nach Klasse leichte vorteile für die list denkbar. Enthält der Container simple Objekte, so würde ich mal behaupten, der Zeitunterschied list/Vector wäre marginal.
4. Das entfernen wird beim Vector schneller sein als bei der List: beim vector brauchen nämlich, weil nur am Ende gelöscht wird, lediglich die Destruktoren des zu entfernenden Elemente aufgerufen zu werden, bei einer list muß hingegen auch die Verkettung nachgehalten werden, was je nach implemntierung mehraufwand bedeutet.
Folglich: list würde ich auf keinen fall nehmen, set genau dann, wenn kein Index-Zugriff erforderlich ist und vector, wenn mit Indexzugriff gearbeitet wird.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
Dieser Post wurde am 21.05.2004 um 13:43 Uhr von virtual editiert. |
) für das set...
