Expanding dynamic size array by using std::vector

#include <algorithm>            // std::sort
#include <iostream>
#include <vector>               // std::vector
using namespace std;

int main()
{
    vector<int> a{3, 8, 1, 5, -8, 33, 4};
    sort( a.begin(), a.end() );
    int const n = a.size();
    for( int i = 0; i < n; ++i ) { cout << a[i] << ' '; }
    cout << '\n';
}

-8 1 3 4 5 8 33 

std::vector is a standard library class template that provides the notion of a variable size array. It takes care of all the memory management, and the buffer is contiguous so a pointer to the buffer (e.g. &v[0] or v.data()) can be passed to API functions requiring a raw array. A vector can even be expanded at run time, via e.g. the push_back member function that appends an item.

The complexity of the sequence of n push_back operations, including the copying or moving involved in the vector expansions, is amortized O(n). “Amortized”: on average.

Internally this is usually achieved by the vector doubling its buffer size, its capacity, when a larger buffer is needed. E.g. for a buffer starting out as size 1, and being repeatedly doubled as needed for n=17 push_back calls, this involves 1 + 2 + 4 + 8 + 16 = 31 copy operations, which is less than 2×n = 34. And more generally the sum of this sequence can’t exceed 2×n.

Compared to the dynamic size raw array example, this vector-based code does not require the user to supply (and know) the number of items up front. Instead the vector is just expanded as necessary, for each new item value specified by the user.