C++ vektor

Fuchs aus dem Wald

Hey Leute,
ich werde auf meiner arbeit immer wieder dadrauf hingewiesen doch bloß kein std und schon gar nicht std::vektor zu benutzen. Vektor wäre ja so unglaublich viel langsamer und es gäbe ja die viel bessere Methode der "Vorwärstdeklaration".
Ein Beispiel:

Ich hab ein Programm was, wenn es durchgelaufen ist in einem Array Teildaten hat. So die könnte man ja nun ganz einfach in einem Vektor speichern und dann erneut durchlaufen, das Array wird dann überschrieben aber man hätte es ja nun im Vektor ... Darf ich ja nun aber nicht also lieber so ein scheiß hier:

if(!first){
    first = new COLOR;
    curr = first;
  }else{
    curr->next = new COLOR;
    curr = curr->next;
  }
  curr->next=NULL;

COLOR ist ein struct

struct COLOR{
  char col[256];
  COLOR* next;
};

COLOR* curr;
COLOR* first;

Konstruktor(){ curr = NULL; first = NULL}

Ich brauch Argumente dagegen ich hab da keine lust drauf! Helft mir!!!

P.S.:
Wenn es doch in den C++ bereich soll bitte verschieben. Dachte mir nur das es eher kein Problem ist sondern von mir einfach mal gesagt werden wollte.

knivil

Das Problem kenne ich. Dir werden keine Argumente helfen, da jene beratungsresitent sind. Wenn Performance ein Thema ist, kannst du nach Performance-Requirements fragen oder aktuellen Performanceproblemen. 'So schnell wie moeglich' ist kein ordentliches Requirement. Wenn dir das alles zu sehr auf den Keks geht, dann schaue dich nach einer anderen Stelle um.

So die könnte man ja nun ganz einfach in einem Vektor speichern

Nun, es gibt viele Moeglichkeiten. Ob std::vector angebracht ist, haengt von vielen Faktoren ab. Ob globale Variablen wie im Beispiel angebracht sind, weiss ich auch nicht.

Fuchs aus dem Wald

Ja es nervt schon, weil ich angst habe ich "verpasse" was. Also ich gewöhn mir ja dadurch so ein kram an. Ich mein wenn man plötzlich ALLES nur noch so löst? ... :S

C++ Forumbot

Dieser Thread wurde von Moderator/in Marc++us aus dem Forum Neuigkeiten aus der realen Welt in das Forum C++ (auch C++0x und C++11) verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

ScottZhang

Miss doch einfach die Performance mal, und die wirst die ganz schnell davon überzeugen das std::vector sau schnell ist.

Es besteht effektiv kein Unterschied zu

struct COLOR2{
  unsigned char col[256];
};
std::forward_list<COLOR2> colors;

(nur, dass forward_list schneller ist, weil es besser gecoded ist und diese if-Abfrage nicht hat).

Wenn die Messung richtig gefaked ist, ist

std::vector<COLOR> colors;

langsamer, dann nimm

std::deque<COLOR2> colors;

Das ist garantiert schneller.

Was du nicht machen darfst, ist das col-Array durch einen Vektor ersetzen.

Youka

Die Leistung der STL hängt nicht wenig von der Implementation ab, so ist sie in älteren Compiler-Bibliotheken in vielen Fällen schlechter als in neueren.
Desweiteren sind STL-Klassen oftmals überladen, was in C++11 durch schlankere Alternativen verbessert wurde.
Ein neuerer Compiler und der Nutzen von std::array wäre eine Überlegung wert.

Zu beachten sei auch das Speichermodell eines STL Vektors und deiner Vorwärts-Liste:
Ein Vektor ist ein Wrapper um ein dynamisches Array. Mit neuen Elementen findet auch eine Reallokierung statt, dies macht das Erweitern von Vektoren teuer, das Löschen kann ungenutzen Speicher zur Folge haben. Jedoch ist der Zugriff wegen des aneinander liegenden Speichers schnell.
Deine Liste ist ein durch Zeiger zusammengehaltenes Speicherkonstrukt. Hinzufügen oder entfernen von Elementen ist günstig, jedoch der Zugriff auf ein bestimmtes Element teuer, weil erst durch die Liste durchgegangen werden muss.

Zusammenfassend ließe sich sagen, dass Vektoren gut sind, wenn es um schnellen Zugriff auf ein bereits fertiges Datenkonstrukt geht, wohingegen Listen empfehlenswerter für das Gegenteil sind, also noch einiges an Daten hinzugefügt oder entfernt werden muss.

Fuchs aus dem Wald

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß. Nur das ich halt bestimmt 15 Zeilen mehr habe.

Die nehmen im Ernst eine verkettete Liste, weil std::vector langsam ist? Sag denen mal, dass dynamische Speicheranforderung pro Element viel teurer als pro Array ist, und dass man die Daten cache-unfreundlich im RAM verteilt hat.

Youka: vector ist fast immer schneller als list. Und was meinst du mit "STL-Klassen sind oftmals überladen"? Die Anzahl der Funktionen hat keinen Einfluss auf die Performance... Und besonders viele Datenmember gibts üblicherweise auch nicht.

<>

Fuchs aus dem Wald schrieb:

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß.

Niemals ist std::vector gleich schnell wie die verkettete Liste. Du misst bestimmt falsch.

<>

Youka schrieb:

Desweiteren sind STL-Klassen oftmals überladen, was in C++11 durch schlankere Alternativen verbessert wurde.
Ein neuerer Compiler und der Nutzen von std::array wäre eine Überlegung wert.

Die einzige überladene STL-Klasse ist std::array. Es gibt wirklich keinen Grund, das zu benutzen.

@Fuchs aus dem Wald: Wenn nicht mal eine Messung diese Leute vom Gegenteil überzeugt (lass auch ruhig mal die messen), kommst du mit rationalen Begründungen auch nicht weit.

Fuchs aus dem Wald

ScottZhang schrieb:

Miss doch einfach die Performance mal, und die wirst die ganz schnell davon überzeugen das std::vector sau schnell ist.

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß. Nur das ich halt bestimmt 15 Zeilen mehr habe.

formanz schrieb:

Was du nicht machen darfst, ist das col-Array durch einen Vektor ersetzen.

Nein leider darf ich das nicht ...

Youka schrieb:

Die Leistung der STL hängt nicht wenig von der Implementation ab, so ist sie in älteren Compiler-Bibliotheken in vielen Fällen schlechter als in neueren.
Desweiteren sind STL-Klassen oftmals überladen, was in C++11 durch schlankere Alternativen verbessert wurde.
Ein neuerer Compiler und der Nutzen von std::array wäre eine Überlegung wert.

Zu beachten sei auch das Speichermodell eines STL Vektors und deiner Vorwärts-Liste:
Ein Vektor ist ein Wrapper um ein dynamisches Array. Mit neuen Elementen findet auch eine Reallokierung statt, dies macht das Erweitern von Vektoren teuer, das Löschen kann ungenutzen Speicher zur Folge haben. Jedoch ist der Zugriff wegen des aneinander liegenden Speichers schnell.
Deine Liste ist ein durch Zeiger zusammengehaltenes Speicherkonstrukt. Hinzufügen oder entfernen von Elementen ist günstig, jedoch der Zugriff auf ein bestimmtes Element teuer, weil erst durch die Liste durchgegangen werden muss.

Zusammenfassend ließe sich sagen, dass Vektoren gut sind, wenn es um schnellen Zugriff auf ein bereits fertiges Datenkonstrukt geht, wohingegen Listen empfehlenswerter für das Gegenteil sind, also noch einiges an Daten hinzugefügt oder entfernt werden muss.

Danke so sehe ich das auch. Und da bei mir nichts mehr im nachhinein hin zu kommt oder entfernt werden muss ...

glühbirne schrieb:

Fuchs aus dem Wald schrieb:

Hab ich schon ... es ist einfach genau so schnell wie der andere scheiß.

Niemals ist std::vector gleich schnell wie die verkettete Liste. Du misst bestimmt falsch.

<>

Ich konnte nicht feststellen das mein Programm dadurch langsamer wird(Vektor) aber auch nicht schneller ...

Fuchs aus dem Wald schrieb:

formanz schrieb:

Was du nicht machen darfst, ist das col-Array durch einen Vektor ersetzen.

Nein leider darf ich das nicht ...

Ich meinte: Aus Performanz-Gründen darfst du auf keinen Fall das col-Array durch einen Vektor ersetzen. Wenn das Array eine fixe Länge (<1Mrd) hat, ist ein statisches Array IMMER* besser als std::vector.

Btw: Wie misst du? Mit der Stoppuhr in der Hand neben dem Computer?

Ansonsten würde ich isoliert von der Anwendung an einem Minimalbeispiel zeigen, dass std::vector schneller ist. Bei einem kleinen übersichtlichen Programm mit Vector vs. Intrusive-List können die sich auch schlecht rausreden.

*gut, gibt exotische Ausnahmen wie move-Operationen.

Fuchs aus dem Wald

Also ob ich hier per Hand messe ...

timeval start, end;///debugg
  gettimeofday(&start, 0);
  /*
   * code
   */
  gettimeofday(&end, 0);///debugg
  std::cout << start.tv_sec << ':' << start.tv_usec << std::endl;///debugg
  std::cout << end.tv_sec << ':' << end.tv_usec << std::endl;///debugg

jokurt schrieb:

Die einzige überladene STL-Klasse ist std::array. Es gibt wirklich keinen Grund, das zu benutzen.

Genau andersherum: Mit std::array gibt es keinen Grund mehr, C-Arrays zu nutzen. Man hat nur fehlende Sicherheit und Wertsemantik.

Fuchs: Mach ein minimales Programm mit dem Benchmark und poste die Ergebnisse. Ich bezweifle nach wie vor, dass beides gleich schnell ist.

<>

glühbirne schrieb:

fehlende Sicherheit

Sicherheit hat man nur im Debug-Build. Und da können auch Array-Zugriffe überprüft werden, sonst hat man die falschen Tools.

glühbirne schrieb:

Wertsemantik.

Praktisch immer ein Fehler. Arrays zu kopieren sollte man vermeiden oder zumindest syntaktisch kenntzeichnen. C-Arrays unterstützen einen dabei.

.begin(), .end(), .size() sollte man sowieso durch std::begin, std::end, ::size ersetzen, C-Arrays unterstützen einen dabei.

C-Arrays können auch automatisch ihre Größe herausfinden, bei std::array besteht immer die Gefahr, sich um eins verzählt zu haben.

<>

camper

Bei einem 256-Byte großen Element dürfte die Containerwahl relativ unbedeutend für die Performance sein (bei einfachen iterativen Algorithmen). Der Vorteil von vector in Bezug auf bessere Cachlokalität ist dann einfach kaum noch gegeben, und der Speicheroverhead von Node-basierten Containern ist auch unbedeutend.

Fuchs aus dem Wald

glühbirne schrieb:

Fuchs: Mach ein minimales Programm mit dem Benchmark und poste die Ergebnisse. Ich bezweifle nach wie vor, dass beides gleich schnell ist.

<>

Liste:
START: 1370425812:811620
ENDE: 1370425812:811626
hier sind es 6 Mikrosekunden
Vektor:
START: 1370426056:420174
ENDE: 1370426056:420196
Hier sind es 22 Mikrosekunden

Ok es ist mit dem Vektor wirklich langsamer. Ich hatte das auf dem gesamten Durchlauf getestet jetzt nur auf den einzel Part. Und dann auch nur grob gerechnet.

camper

formanz schrieb:

glühbirne schrieb:

Wertsemantik.

Praktisch immer ein Fehler. Arrays zu kopieren sollte man vermeiden oder zumindest syntaktisch kenntzeichnen. C-Arrays unterstützen einen dabei.

Warum?

formanz schrieb:

C-Arrays können auch automatisch ihre Größe herausfinden, bei std::array besteht immer die Gefahr, sich um eins verzählt zu haben.

Nicht relevant in diesem Thread, schließlich geht es hier nicht um automatische oder statische Arrays, die ihre Größe aus einem Initialisierer ermitteln können.

@Fuchs:

formanz schrieb:

Wenn die Messung richtig gefaked ist, ist
std::vector<COLOR> colors;
langsamer, dann nimm
std::deque<COLOR> colors;
Das ist garantiert schneller.

Beachte, dass du auch auf die Member zugreifst.

camper schrieb:

formanz schrieb:

glühbirne schrieb:

Wertsemantik.

Praktisch immer ein Fehler. Arrays zu kopieren sollte man vermeiden oder zumindest syntaktisch kenntzeichnen. C-Arrays unterstützen einen dabei.

Warum?

Wertsemantik ist hauptsächlich sinnvoll als Member und da ist die Wertsemantik gegeben.

Nicht relevant in diesem Thread:
Rückgabewert -> Referenz auf Parameter (falls man Pech bei RVO hat)
Parameter -> const-Referenz oder Iteratoren