Vectors vs Arrays: Internal Implementation and Optimization Insights

Books explain that when you use a vector, it internally relies on a flat array, meaning the memory is allocated contiguously. When you compile with optimization flags like -O3, the compiler can optimize the code in such a way that iterators may effectively be eliminated, and operations are performed directly using internal pointers.

Therefore, using a vector is perfectly fine, especially if you can set its size initially. Preallocating the size helps avoid repeated reallocations and memory copying that happen during dynamic resizing.

Similarly, there is another data structure to analyze: the array.

In the case of arrays as well, the internal implementation is based on contiguous memory allocation. The advantage of this approach is that it is cache-friendly and provides constant time O(1) access to elements.