was ist schneller (vector, map, usw.)???

Hallo zusammen,

ich lese in Speicher (Structur) ca. 10.000 Datensätze die Structur seht so aus:

typedef struct
{
CString spalte1;
CString index1;
int index2;
double index3;
} tS;

Die spalten index1-3 sind eindeutig, jetzt muss ich auf Grund von den drei spalten in der Structur suchen und die Structur um die spalte1 ergänzen.
Es gibt ca. 400.000 Suchvorgänge bzw. Zugriffe über Index.

Meine Frage: wie sollte ich vorgehen damit ich es so performant wie möglich programmier:
(vector, map, usw.)???

CStoll

Also auf jeden Fall benötigst du einen Vergleichsoperator ("kleiner als") für deine Klasse, sonst bleibt dir nichts anderes übrig als vector.

Danach kommt es wohl darauf an, wie deine Daten reinkommen. Wenn du einmal alles einliest und dann nur noch suchst, könnte der Vector sogar schneller sein^*, wenn du ständig neue Werte einliest, ersetzt und ändern willst, ist eine map günstiger (dabei mußt du allerdings deine struct in zwei Teile zerlegen - map-Schlüssel dürfen nicht verändert werden).

^* das gilt allerdings nur, wenn du Sortierung nutzt:

vector<tS> data;
copy(istream_iterator<tS>(fin),istream_iterator<tS>(),data);
sort(data.begin(),data.end();

...
tS searchval;
vector<tS>::iterator p=lower_bound(data.begin(),data.end(),searchval);
searchval->spalte1=...;

Ich lese erstmal alles auf einmal ein, und dann möchte ich suchen.
Also vector ist für mich besser, ok ich brauche aber trotzdem den Vergleichsoperator oder wie geht es denn beim vector?????

CStoll

Brauchen tust du ihn nicht unbedingt, aber er ist von Vorteil (suchen auf einer unsortierten Folge benötigt O(n), suchen auf einer sortierten Folge schaffst du in O(log n) - allerdings brauchst du ein Ordnungskriterium, um suchen zu können).

Und wie du mit dem Vektor umgehst, habe ich doch sogar mit Code unterlegt: Am Anfang alle Werte einlesen und anschließend sortieren (sort()), danach kannst du per lower_bound() das "richtige" Element suchen und bearbeiten.