Ein dynamisches Array wachsen lassen

Ein dynamisches Array wie C++ std::vector speichert seine Elemente in einem einzigen Speicherblock. Wenn der Block voll ist und ein neues Element hinzukommt, allokiert es einen Block doppelt so groß, kopiert die vorhandenen Elemente hinein und gibt den alten frei.

Beginne mit einem leeren Array mit der Kapazität initial_capacity und füge pushes Elemente nacheinander hinzu. Bevor du jedes Element einfügst, gilt: Wenn size == capacity, dann reallokiere: zähle eine Reallokation, addiere die aktuelle size zu den kopierten Elementen und verdopple die capacity.

Implementiere dynamic_array_growth(pushes, initial_capacity).

Eingabe

pushes: Wie viele Elemente eingefügt werden.

initial_capacity: Die Kapazität des leeren Arrays.

Ausgabe

Gib [reallocations, copied_elements, final_capacity] zurück.

Einschränkungen

0 ≤ pushes ≤ 10^7

1 ≤ initial_capacity ≤ 10^6

Beispiele

Eingabe:
pushes = 5
initial_capacity = 1

Erwartete Ausgabe:
expected = [3, 7, 8]

Eingabe:
long long pushes = 5;
long long initial_capacity = 1;

Erwartete Ausgabe:
std::vector<long long> expected = {3, 7, 8};

Eingabe:
long pushes = 5;
long initial_capacity = 1;

Erwartete Ausgabe:
long[] expected = new long[] {3, 7, 8};

Eingabe:
pushes = 4
initial_capacity = 4

Erwartete Ausgabe:
expected = [0, 0, 4]

Eingabe:
long long pushes = 4;
long long initial_capacity = 4;

Erwartete Ausgabe:
std::vector<long long> expected = {0, 0, 4};

Eingabe:
long pushes = 4;
long initial_capacity = 4;

Erwartete Ausgabe:
long[] expected = new long[] {0, 0, 4};

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

• cppreference, std::vector