Ein Array von Paaren oder zwei Arrays - Was ist sinnvoller?

Ich verwende ints aus dem Bereich [0..max_n] als Schlüssel um auf ein Paar von Daten zuzugreifen. Ich sehe zwei (sinnvolle) Möglichkeiten dies konkret zu realisieren.

Variante 1:

struct { int a, b; } m[max_n+1];
//...
m[n].a = 1;
m[n].b = 2;

Variante 2:

int m_a[max_n+1],  m_b[max_n+1];
//...
m_a[n] = 1;
m_b[n] = 2;

Ist eines von beiden generell sinnvoller als das andere? Der erzeugte Code wird verschieden sein.

SeppJ

Variante a).
Stilargumente: Bessere Objektorientierung, besser veränderbar, besser wartbar, besser zu verstehen.
Technisches Argument: Dürfte bessere Lokalität des Codes erzeugen

würde sagen das hängt auch ein bischen von deiner Anwendung ab. Also wenn du die Paare immer gemeinsam braucht ist a) vermutlich besser. wenn du aber normalerweise nur von allen paaren a oder von allen b brauchst dürfte b) besser sein (besser = geschwindigkeit hier)
Denn bei b) werden die Arrays hintereinander gelegt, sodass du um von a1 nach b1 zu kommen weit im speicher springen musst, von a1 nach a2 aber nicht. Bei a) ist es genau umgekehrt.

Wobei ich SeppJ zustimmen muss. Vom Aussehen/Programmierstil ist a) wirklich besser.

könnt ihr mal etwas "c-plus-plus"-iger sein? (wir sind hier in einem c++ Forum )

#include<map>

typedef struct { int a, b; } s;

std::map<unsigned,s> m;

[quote="!rr!rr_."]könnt ihr mal etwas "c-plus-plus"-iger sein? (wir sind hier in einem c++ Forum )
[/qoute]

Was hat dann das typedef in deinem Code verloren?

!rr!rr_. schrieb:

typedef struct { int a, b; } s;

Bashar

!rr!rr_. schrieb:

std::map<unsigned,s> m;

O(1) Zugriff durch O(log n) ersetzt.

SideWinder

Bashar schrieb:

!rr!rr_. schrieb:
std::map<unsigned,s> m;
O(1) Zugriff durch O(log n) ersetzt.

Kommt darauf an, oder? Wenn ich nach dem Wert mit a=4 suche habe ich O(n) durch O(log n) ersetzt. Falls die Paare nicht immer sequentiell durchgegangen werden würde ich persönlich zu einer hashmap tendieren.

MfG SideWinder

SideWinder schrieb:

Kommt darauf an, oder? Wenn ich nach dem Wert mit a=4 suche habe ich O(n) durch O(log n) ersetzt.

a) Stimmt nicht, da die Werte nicht nach a sortiert sind, sondern nach dem Schlüssel. Es bleibt O(n) außer du suchst nach dem Schlüssel.
b) Stand in der Aufgabenstellung, dass man Schlüssel hat und a und b sucht und nicht anders rum.

es ist halt methodisch unschön (wenn auch effizient), ein ganzes Array für alle möglichen Schlüssel zu reservieren, wenn man nur ein paar Daten speichern will. Sowas ist konzeptionell eher eine partielle Abbildung (-> map)

hustbaer

!rr!rr_. schrieb:

es ist halt methodisch unschön (wenn auch effizient), ein ganzes Array für alle möglichen Schlüssel zu reservieren, wenn man nur ein paar Daten speichern will.

Er will ein Paar (=std::pair) Daten zu jeweils einem Key speichern, nicht Daten zu ein paar (=wenigen) Keys.
Deine Annahme dass nur wenige Keys verwendet werden ist daher einigermassen unbegründet.

Samyboy

Hallo,

Ich denke Methode a ist besser wartbar und verständlicher.

Gruss,

samyboy