dynamische Speicherplatzbeschaffung
-
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....