Dynamic Arrays: Geometric Growth Factors (2× vs 1.5×) & Memory Reuse

Contiguous Representation and Geometric Growth

At the machine level, a dynamic array (such as C++ std::vector<T>, Rust Vec<T>, or Java ArrayList<E>) is a 24-byte header struct stored on the stack or inline within an object: a base pointer T* data, a current element count size_t size, and an allocated slot count size_t capacity. Whenever size < capacity, appending an element writes directly to data[size++] in a single store instruction with zero allocator interaction.

When size == capacity, the container must allocate a new contiguous region of capacity $\lceil k \cdot C \rceil$, move or copy the existing $C$ elements into the new region, destroy the old elements (if non-trivially destructible), and free the old block. If the array grew arithmetically by a constant $c$ (e.g., adding 100 slots each time), appending $N$ elements would copy $c + 2c + 3c + \dots + N = \Theta(N^2)$ elements, yielding $\Theta(N)$ amortized cost per append. Geometric growth by $k > 1$ ensures that reallocation distances grow exponentially, bounding total copies to a geometric series:

$$\sum_{i=0}^{\lfloor \log_k N \rfloor} k^i = \frac{k^{\lfloor \log_k N \rfloor + 1} - 1}{k - 1} \le \frac{k N - 1}{k - 1} = \Theta(N)$$

Dividing by $N$ insertions yields $1 + \frac{k}{k - 1} = O(1)$ amortized work per append. Notice the trade-off embedded in $\frac{k}{k - 1}$: as $k$ decreases toward $1$, wasted slack memory $(k - 1)N$ shrinks, but the copy multiplier $\frac{1}{k - 1}$ explodes (for $k = 2$, at most $2N$ copies occur; for $k = 1.5$, at most $3N$ copies occur; for $k = 1.1$, $11N$ copies occur).

Comparative Growth Strategies Across Runtimes

Visualizing $k=2.0$ Heap Crawl vs. $k=1.5$ Coalesced Reuse

Reallocation Lifecycle & Exception Safety

Production Implementation: Aligned 1.5× Vector with Strong Exception Guarantee

#include <cstdlib>
#include <cstring>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

template <typename T>
class FbStyleVector {
  T* data_ = nullptr;
  std::size_t size_ = 0;
  std::size_t cap_ = 0;

  static std::size_t next_capacity(std::size_t current) noexcept {
    if (current == 0) return 4;
    if (current < 64) return current * 2;
    // 1.5x growth (k = 1.5 < phi) enables coalesced heap reuse
    return current + (current >> 1);
  }

  void grow() {
    const std::size_t new_cap = next_capacity(cap_);
    T* new_data = static_cast<T*>(::operator new(new_cap * sizeof(T), std::align_val_t{alignof(T)}));

    if constexpr (std::is_trivially_copyable_v<T>) {
      if (size_ > 0) {
        std::memcpy(new_data, data_, size_ * sizeof(T));
      }
    } else if constexpr (std::is_nothrow_move_constructible_v<T>) {
      std::uninitialized_move_n(data_, size_, new_data);
      std::destroy_n(data_, size_);
    } else {
      // Strong exception guarantee: copy first; if an exception is thrown,
      // destroy already-copied elements in new_data and leave data_ intact.
      std::size_t constructed = 0;
      try {
        for (; constructed < size_; ++constructed) {
          std::construct_at(new_data + constructed, data_[constructed]);
        }
      } catch (...) {
        std::destroy_n(new_data, constructed);
        ::operator delete(new_data, std::align_val_t{alignof(T)});
        throw;
      }
      std::destroy_n(data_, size_);
    }

    if (data_) {
      ::operator delete(data_, std::align_val_t{alignof(T)});
    }
    data_ = new_data;
    cap_ = new_cap;
  }

public:
  void push_back(const T& value) {
    if (size_ == cap_) grow();
    std::construct_at(data_ + size_, value);
    ++size_;
  }

  std::size_t size() const noexcept { return size_; }
  std::size_t capacity() const noexcept { return cap_; }
};