C++: amortized cost of a growing array
std::vector stores its elements in one contiguous block. When the block is full, push_back allocates a larger block, moves or copies every element into it, and frees the old one. Because capacity grows geometrically, the expensive steps are rare.
C++
#include <cstddef>
#include <iostream>
class IntList {
public:
IntList() = default;
IntList(const IntList&) = delete;
IntList& operator=(const IntList&) = delete;
~IntList() { delete[] data_; }
void add(int value) {
if (size_ == capacity_) {
std::size_t bigger = capacity_ == 0 ? 1 : capacity_ * 2;
int* grown = new int[bigger];
for (std::size_t i = 0; i < size_; ++i) {
grown[i] = data_[i];
++copies_;
}
delete[] data_;
data_ = grown;
capacity_ = bigger;
}
data_[size_++] = value;
}
std::size_t copies() const { return copies_; }
private:
int* data_ = nullptr;
std::size_t size_ = 0;
std::size_t capacity_ = 0;
std::size_t copies_ = 0;
};
int main() {
IntList list;
for (int i = 1; i <= 16; ++i) {
list.add(i);
}
std::cout << "appends=16 copies=" << list.copies() << "\n";
std::cout << "copies per append=" << static_cast<double>(list.copies()) / 16 << "\n";
}