Code Yarns ‍👨‍💻
Tech BlogPersonal Blog

Vector growth factor in languages

📅 2019-Mar-06 ⬩ ✍️ Ashwin Nanjappa ⬩ 📚 Archive

Growth factor is the factor by which the new size of a C++ STL vector is computed when we need to insert beyond its current capacity. There are dynamic arrays similar to the STL vector in other languages. It is quite interesting to see what factors were chosen in those implementations.

int newCapacity = oldCapacity + (oldCapacity >> 1);
size_t newmaxsize = reqmaxsize >= a->maxsize * 2
    ? (reqmaxsize < 4 ? 4 : reqmaxsize)
    : a->maxsize * 2;
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;