dynamische Speicherplatzbeschaffung
-
Hallo,
Zum Standard
aus 23.1.1 13The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size().
über op[] habe ich nichts weiter gefunden.
-
Ich kann hierzu jetzt auch nur das sagen was ich aus einem C++ Buch habe (glaube entweder ein Scott Meyer oder ein Herb Sutter Buch, leider weiß ich grad nicht welches).
Danach muß at eine Bereichsprüfung (mit Exception) machen, [] darf eine machen, muss es aber nicht (Compilerspezifisch).
Wie gesagt ist das jetzt nur die Erinnerung an einen Abschnitt aus einem Buch.
cu André
-
Der Zugriff auf ein Array geschiet in konstanter Zeit, richtig? Und die Vorgabe für den Vector lautet (wie richtig gesagt) "kostante Zeit" und "die Elemenete müssen hintereinander im Speicher liegen" (letzteres ist ab C++2009 eine explizite Vorgabe!). Naja, wie sollte man das ganze sonst implementieren? Natürlich ist die Aussage "so schnell wie ein Array" nicht im Standard definiert, aber seien wir ehrlich: wer würde eine Std-Lib benutzen, die einen Vector implementiert, der zwar konstante Zeiten anbietet aber doppelt so langsam als ein Array ist?
Wegen der Exception:
C++0x Working Draft $23.1.1 schrieb:
13 The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size().
Steht aber auch im aktuellen Standard. Und auch im Bjarness Stroustrups Buch. Und kann man auch in jeder C++-Online-Reference nachlesen.
-
Artchi schrieb:
Haben sie Performancetests gemacht? Nein! Haben sie sich den ISO-C++-Standard bzgl. std::vector durchgelesen? Nein! haben sie sich die Implementierung ihrer vector-Implementierung angeschaut? Nein!
Woher weisst Du das?
Oder stellst Du nur so eine Behauptung auf? :p
Artchi schrieb:
Und dann stellen die so eine Behauptung auf?
Einfach nur unprofessionell.
-
tntnet schrieb:
Immer wieder kommt hier die Aussage, std::vector::at würde eine Exception werfen und operator[] nicht. Kann jemand mal die Stelle im Standard nennen, wo das so spezifiziert ist?
Steht in den Sequence-Requirements
23.1.1/13
The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size()
Für den op[] gibt es keine solche Anforderung. Er kann einen Range-Check durchführen, muss dies aber nicht. Das Verhalten bei einem out-of-range-Zugriff wird durch den Standard nicht festgelegt und ist undefiniert.
-
Oha. Hätte wohl mal auf "Aktualisieren" drücken sollen.
-
tntnet schrieb:
...
Auch wird nicht explizit definiert, daß std::vector genauso schnell, wie ein Array sein muß....Aber implizit schon:
* Zugriff std::vector = O(1)
* Zugriff array = O(1)
=> Zugriff std::vector = Zugriff array
Gruß,
Simon2.
P.S.: OK, da IIRC "Zugriff array = O(1)" nicht wirklich vorgegeben ist, könnte theoretisch "Zugriff std::vector < Zugriff array" sein, aber das würde die Verwendung von vector unter Performancegesichtspunkten noch weniger ausschließen.
-
Artchi schrieb:
aber seien wir ehrlich: wer würde eine Std-Lib benutzen, die einen Vector implementiert, der zwar konstante Zeiten anbietet aber doppelt so langsam als ein Array ist?
Wenn es einen Zusatznutzen bringt, dann schon. Und im Falle von Bereichsprüfungen sehe ich schon einen Zusatznutzen. Ich würde es allerdings im release-Build ausschalten, aber vorsichtige Naturen könnten es akzeptieren.
Und Danke auf den Verweis auf den Standard. Das hatte ich gesucht
.Verweise in irgendwelche Bücher und seien sie von Meyers oder Stroustroup helfen übrigens in solchen Fällen nicht weiter. Nur der C++-Standard definiert die Sprache.
-
tntnet schrieb:
Artchi schrieb:
aber seien wir ehrlich: wer würde eine Std-Lib benutzen, die einen Vector implementiert, der zwar konstante Zeiten anbietet aber doppelt so langsam als ein Array ist?
Wenn es einen Zusatznutzen bringt, dann schon.
Das erklärte erste Ziel der C++stdlib ist aber Performance und nicht Sicherheit. Von daher wäre es schon komisch. Ich denke, auch wenn es der Standard nicht explizit vorschreibt, ist durch die Intention des Kommitees sehr wohl gegeben, dass std::vector *kein* Overhead gegenüber einem C-Array haben darf (bzw. sich dieses Overhead auf jeden Fall abstellen lassen muss).
-
tntnet schrieb:
...
Verweise in irgendwelche Bücher und seien sie von Meyers oder Stroustroup helfen übrigens in solchen Fällen nicht weiter. Nur der C++-Standard definiert die Sprache.Stimmt einerseits ... andererseits kennen sich Meyers und Stroustrup im Standard soooo viel besser aus als ich, dass ich auf jeden Fall sehr viel ausdauernder in ihm suche, wenn die Beiden behaupten, es stünde drin.
Gruß,
Simon2.
-
Simon2 schrieb:
tntnet schrieb:
...
Auch wird nicht explizit definiert, daß std::vector genauso schnell, wie ein Array sein muß....Aber implizit schon:
* Zugriff std::vector = O(1)
* Zugriff array = O(1)
=> Zugriff std::vector = Zugriff arrayIch könnte ja jetzt einen Vortrag über Komplexitätsklassen und die genaue Bedeutung der O(...)-Notation bringen, aber das dürfte wohl den Rahmen sprengen
(nur so viel: eine Zugriffszeit von einem Jahr liegt auch noch in O(1), solange sie unabhängig von der aktuellen Größe des Containers ist)
-
Weiß ich - na und ?
Ausgangspunkt waren doch die Komplexitätsklassen:
VerbalKint schrieb:
Ich will keinen Vektor, weil ich dachte, dass bei sehr hohen Datenmengen die Arbeit mit vectoren länger dauert....
VerbalKint schrieb:
... aufgrund des Listenaufbaus die Suche nach bestimmten Daten zu lange dauern würde.
Meine Aussage sollte lediglich sein, dass sie beide in derselben Komplexitätsklasse liegen ...
Wenn ich mal davon ausgehe, dass nicht ein bösartiger STL-Implementierer ein sleep(500000) in vector::operator[]() eingebaut hat, denke ich, kann man (wenn man mit der Komplexitätsklasse von array zufrieden ist) guten Gewissens std::vector verwenden (bzgl. Zugriffsperformance).
Gruß,
Simon2.
-
Simon2 schrieb:
Wenn ich mal davon ausgehe, dass nicht ein bösartiger STL-Implementierer ein sleep(500000) in vector::operator[]() eingebaut hat, denke ich, kann man (wenn man mit der Komplexitätsklasse von array zufrieden ist) guten Gewissens std::vector verwenden (bzgl. Zugriffsperformance).
Yo, sagt auch der Standard:
§23.1.1 schrieb:
vector, list, and deque offer the programmer different complexity trade-offs and should be used accordingly. vector is the type of sequence container that should be used by default. list should....