Build the idea behind vector yourself: an array that makes room as it fills.
What to build
A DynArray class that stores numbers in a heap array and doubles it when it is full.
Requirements
- Start with room for 1 number.
- When a new number does not fit, double the capacity and print
grow to C. - Release the old block with
delete[]after copying, and the last block in the destructor. - At the end, print the size and capacity, then the numbers.
Input
The first line has n. The second line has the n numbers.
Output
One grow to C line for each time the array grows, then size S capacity C, then the numbers separated by spaces.
Constraints
1 ≤ n ≤ 1000.
Example
Input:
5
1 2 3 4 5
Output:
grow to 2
grow to 4
grow to 8
size 5 capacity 8
1 2 3 4 5
Why it works
Doubling means the array grows only about log₂ n times, so the total copying stays proportional to n. Freeing each old block straight after copying means nothing is leaked.
Examples
5 1 2 3 4 5
grow to 2 grow to 4 grow to 8 size 5 capacity 8 1 2 3 4 5
1 7
size 1 capacity 1 7
Hints
Hint 1
Keep three members: a pointer to the items, the size and the capacity. Start with capacity 1.
Hint 2
When the array is full, make a block twice as big with `new`, copy the items, `delete[]` the old block and point at the new one.
Hint 3
Free the block in the destructor.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
using namespace std;
class DynArray {
int* items;
int size;
int capacity;
public:
DynArray() : items(new int[1]), size(0), capacity(1) {}
DynArray(const DynArray&) = delete;
DynArray& operator=(const DynArray&) = delete;
~DynArray() {
delete[] items;
}
void push(int x) {
if (size == capacity) {
int* bigger = new int[capacity * 2];
for (int i = 0; i < size; i++) bigger[i] = items[i];
delete[] items;
items = bigger;
capacity *= 2;
cout << "grow to " << capacity << endl;
}
items[size++] = x;
}
void print() const {
cout << "size " << size << " capacity " << capacity << endl;
for (int i = 0; i < size; i++) cout << items[i] << " ";
cout << endl;
}
};
int main() {
int n, x;
cin >> n;
DynArray a;
for (int i = 0; i < n; i++) {
cin >> x;
a.push(x);
}
a.print();
return 0;
}