C++: amortized cost of a growing array

Before you start

C++ classes, new[] and delete[].

Count the copies made by a doubling array to see why push_back is amortized constant time.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

This hand-written array doubles its capacity and counts element copies. Over 16 appends, the growth steps copy 1 + 2 + 4 + 8 = 15 elements, less than one copy per append on average. Doubling is not the only choice, as implementations use other growth factors, but any constant factor greater than 1 gives amortized O(1).

Code example

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";
}

Output

appends=16 copies=15
copies per append=0.9375

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <cstddef>

2#include <iostream>

4class IntList {

5 public:

6 IntList() = default;

7 IntList(const IntList&) = delete;

8 IntList& operator=(const IntList&) = delete;

9 ~IntList() { delete[] data_; }

11 void add(int value) {

12 if (size_ == capacity_) {

13 std::size_t bigger = capacity_ == 0 ? 1 : capacity_ * 2;

14 int* grown = new int[bigger];

15 for (std::size_t i = 0; i < size_; ++i) {

16 grown[i] = data_[i];

17 ++copies_;

18 }

19 delete[] data_;

20 data_ = grown;

21 capacity_ = bigger;

22 }

23 data_[size_++] = value;

24 }

26 std::size_t copies() const { return copies_; }

28 private:

29 int* data_ = nullptr;

30 std::size_t size_ = 0;

31 std::size_t capacity_ = 0;

32 std::size_t copies_ = 0;

33};

35int main() {

36 IntList list;

37 for (int i = 1; i <= 16; ++i) {

38 list.add(i);

39 }

40 std::cout << "appends=16 copies=" << list.copies() << "\n";

41 std::cout << "copies per append=" << static_cast<double>(list.copies()) / 16 << "\n";

42}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
When full, the new capacity is double the old one: 1, 2, 4, 8, 16.	`capacity doubles`	—
Each existing element is copied once per growth step.	`copies = 1 + 2 + 4 + 8 = 15`	—
The old block is freed after the copy. The destructor frees the final block.	`copies = 1 + 2 + 4 + 8 = 15`	—
Fifteen copies over sixteen appends.	`copies = 1 + 2 + 4 + 8 = 15`	appends=16 copies=15 copies per append=0.9375

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

Cost and common mistakes

Each add is amortized O(1); n adds cost O(n) time in total and O(n) space.

Copying is deleted in this class on purpose. A default copy would duplicate the raw pointer and cause a double delete.
Real code should use std::vector, which also handles exceptions and moves instead of copies where possible.

Try it yourself

How many copies after 64 appends?

Reveal answer and reasoning

63 copies (1 + 2 + 4 + 8 + 16 + 32).