Komplexität von vector::resize?

Ich wundere mich gerade, ob bei einem vector push_back(T()) die gleichen Laufzeitgarantien macht wie resize(size()+1) , also ob beides in amortisiert konstanter Zeit abläuft. Verschiedene Referenzen behaupten entweder O(new_size - old_size) oder O(new_size).

Also welche Laufzeitkomplexität hat vector::resize()?

SeppJ

resize mit einer erhöhten Größe macht ein insert(end, new_size - size, T()). Die Komplexität von insert(position, n, x) ist O(n + end - position), hier also O(n). Und n ist hier 1. Also O(1), konstant.
Im Standard werden insert und push_back bezüglich der Komplexität auch im gleichen Absatz genannt, die Angabe ist daher für beide gleich, bloß dass bei push_back eben automatisch schon n = 1 und position = end ist. Kurz: Ja, insert von einem Element am Ende ist das gleiche wie push_back.

SeppJ schrieb:

resize mit einer erhöhten Größe macht ein insert(end, new_size - size, T()).

Wo hast du das gefunden? Das würde nicht funktionieren, wenn T move-only ist.

SeppJ

resiz0r schrieb:

SeppJ schrieb:

resize mit einer erhöhten Größe macht ein insert(end, new_size - size, T()).

Wo hast du das gefunden? Das würde nicht funktionieren, wenn T move-only ist.

Im C++98-Standard . Wenn ich sage, dass (new_size -size) value-initialisierte Elemente am Ende eingefügt werden, ist es dann aktuell genug?

krümelkacker

resiz0r schrieb:

Also welche Laufzeitkomplexität hat vector::resize()?

Gute Frage. Die stellte ich mir auch schon. Und was für eine Garantie macht reserve ?

Der Standard sagt bei resize (mit einem Parameter) nur, dass falls size()<parameter entsprechend viele neue Elemente "value-initialized" werden. Als Bedingung steht dann noch ein "Requires: T shall be CopyInsertable" into *this.

resize mit zwei Parametern sagt, dass der Effekt äquivalent zu

insert(end(),parameter1-size(),parameter2);

ist, falls size()<parameter1 . Und bei dem entsprechenden insert steht dann unter "Complexity", dass der Aufwand linear in der Anzahl der Elemente sei plus die Entfernung des Iterators zum Ende, die hier in diesem Fall aber 0 ist. Wahrscheinlich muss man sich das Wort "amortisiert" noch dazu denken.

Daraus schließe ich, dass x.resize(x.size()+1) auch nur amortisiert konstante Zeit kostet.

Hätte ich das früher mal nachgeguckt, hätte ich mir in einer Situation etwas Komplizierteres mit von Hand geschriebener Verdoppelung der Kapazität per reserve sparen können. Hoffen wir mal, dass sich die Implementierungen dran halten.