COMS W4995 C++ Deep Dive for C Programmers

Sequence Containers

In the next few chapters, we’ll explore containers and iterators in the C++ Standard Library. These were the two main components of an older C++ library called STL, which stands for Standard Template Library. STL heavily influenced the C++ Standard Library. Many people still refer to the C++ Standard Library as STL. We’ll also use these terms interchangably.

Arrays in C++

Before delving into containers, we’ll start with a primer on C arrays in the context of C++. std::vector has largely replaced the use of C arrays to represent a contiguous sequence of elements, but it’s still important to have a solid handle on C arrays because array types will keep coming up in complex template declarations.

The 10/stl program demonstrates simple usage of a C array:

void print_int(int x)  { cout << x << ' '; }

int main() {
    int a[5] { 100, 101, 102, 103, 104 };
    size_t n = sizeof(a) / sizeof(a[0]);
    for (size_t i = 0; i < n; ++i)  { print_int(a[i]); }

    cout << '\n';
}

Had we written this code in C, we would’ve initialized the array a as follows:

int a[5] = { 100, 101, 102, 103, 104 };

In C++, we can omit the =. This form of initialization is referred to as direct-list-initialization.

Recall that the array name a will decay into a pointer to the first element of the array in most expressions. sizeof(a), giving the total byte size of the entire array, is one of the few exceptions. Thus, sizeof(a) / sizeof(a[0]) gives us the number of elements in the array.

`Array` class template

We now wrap the C array in a class template called Array, defined as follows:

template <typename T, size_t N>
struct Array {

    // typedef T value_type;
    using value_type = T;

    // T(&)[N] is a reference to array of N elements of type T
    using TA = T(&)[N];

    T& operator[](int i) { return a[i]; }
    const T& operator[](int i) const { return a[i]; }

    constexpr int size() const { return N; }
    TA underlying() { return a; }

    T a[N];
};

int main() {

    // int a[5] { 100, 101, 102, 103, 104 };
    // size_t n = sizeof(a) / sizeof(a[0]);
    // for (size_t i = 0; i < n; ++i)  { print_int(a[i]); }

    Array<int,5> v { 100, 101, 102, 103, 104 };
    for (size_t i = 0; i < v.size(); ++i)  { print_int(v[i]); }

    cout << '\n';
}

The class template has a type parameter T and a value parameter N, and holds an array of N elements of type T as the sole member. The main() function now declares an Array<int,5> instead of the C array. We’ve defined operator[]() and size() similarly to how we defined them in the Vec class template from a few chapters ago.

The class definition includes two type aliases. The first one is value_type, which is defined to be the type parameter T. The C++ using syntax is equivalent to the C-style typedef syntax as shown in the comment above. value_type is one of many type aliases that all STL containers define. We’ll revisit this when we discuss iterators shortly.

The second type alias TA is a reference to an array of N elements of type T. The underlying() member function returns this type, demonstrating that it is possible to return a C array by reference in C++. Here’s a quick overview on the relevant syntax for pointers & references to arrays:

int a[5];        // a is an array of 5 ints  
int *p = &a[0];  // p is a pointer to a[0]
int *p = a;      // same as above because a decays into &a[0]

// pa is a pointer to an array of 5 ints and points to the array a
int (*pa)[5] = &a;

// ra is a reference to an array of 5 ints and refers to the array a
int (&ra)[5] = a;

The following code verifies that the underlying() member function returns a reference to the entire array:

constexpr size_t n = sizeof(v.underlying()) /
                     sizeof(decltype(v)::value_type);
static_assert(v.size() == n);

Had v.underlying() decayed into a pointer to the first element, then the assertion would fail.

The constexpr keyword tells the compiler that n can be evaluated at compile time as opposed to run time. Since the size of the array is known at compile time, we also marked the size() member function as constexpr. By the same token, we used static_assert(), which is evaluated at compile time, instead of assert(), which is evaluated at run time.

We also took this opportunity to show how to use the value_type alias to refer to the type of the array element. We used the C++ keyword decltype to refer to the declared type of the variable v.

`std::array` class template

Our Array class template is a simplified version of std::array. The std::array class template is similar to std::vector, but its size is fixed at compile time. We’ve changed the main() function to use std::array as follows:

int main() {
    std::array<int,5> v { 100, 101, 102, 103, 104 };
    for (size_t i = 0; i < v.size(); ++i)  { print_int(v[i]); }

    cout << '\n';
}

std::array and std::vector should replace most uses of C arrays. In fact, C++20 introduced the std::to_array() function template to convert a C array into an std::array:

// Copies each element
template <class T, size_t N>
constexpr std::array<T,N> to_array( T (&a)[N] );

// Moves each element
template <class T, size_t N>
constexpr std::array<T,N> to_array( T (&&a)[N] );

`std::vector` class template

Let’s now change our main() function to use std::vector:

int main() {
    std::vector<int> v { 100, 101, 102, 103, 104 };
    v.push_back(105);
    for (size_t i = 0; i < v.size(); ++i)  { print_int(v[i]); }

    cout << '\n';
}

As before, we initialize v using direct-list-initialization. The presence of the initializer enables the compiler to deduce the type parameter for std::vector. As such, we could’ve omitted int as follows:

std::vector v { 100, 101, 102, 103, 104 };

When we previously implemented our Vec class template, we discussed how it stores its elements contiguously in an underlying array that gets reallocated whenever it exceeds its capacity. std::vector works the same way, and therefore has the following characteristics:

Elements are guaranteed to be laid out contiguously in memory
std::vector::push_back() has amortized O(1) run time
Due to possible reallocation of the underlying array, push_back() may invalidate existing pointers and references to any elements

`std::deque` class template

STL provides another sequential container called deque, which stands for double-ended queue. We’ve swapped out the std::vector for a std::deque in the main() function:

int main() {
    deque<int> v { 100, 101, 102, 103, 104 };
    v.push_front(99);
    v.push_back(105);
    for (size_t i = 0; i < v.size(); ++i)  { print_int(v[i]); }

    cout << '\n';
}

Unlike vector, deque provides a push_front() member function. Both push_front() and push_back() are amortized O(1) operations. Even better, neither push_front() nor push_back() will invalidate any pointers or references. All of this comes at the cost of deque no longer guaranteeing that its elements are contiguously laid out in memory. We sketch the memory layout of a typical deque implementation in the diagram below:

10-deque

As we can see, push_front() and push_back() are amortized O(1) operations since they simply prepend and append to the chunks at the front and the back, respectively. If a chunk fills up, a new chunk gets allocated and a pointer to it is added to the chunk pointer array. If the chunk pointer array fills up, it’ll have to be reallocated and copied over. The deque elements are never relocated by push_front() and push_back(), thereby never invalidating any existing pointers or references.

Note that pointers or references are invalidated by insert() and erase() at some arbitrary position in the middle of the deque. The same goes for vector.

Just because std::deque provides amortized O(1) run time for both push_front() and push_back(), it doesn’t necessarily make it a better choice than std::vector. When accessing elements through operator[](), deque has two levels of indirection whereas vector only has one. Furthermore, vector enjoys better cache performance because of its contiguous layout. At the end of the day, the only way to determine the relative performance in any particular application is to make actual measurements.

`std::list` class template

STL provides a doubly linked list implementation called std::list. We’ve changed the main() function to use it:

int main() {
    list<int> v { 100, 101, 102, 103, 104 };
    v.push_front(99);
    v.push_back(105);
    while (!v.empty())  {
        print_int(v.front());
        v.pop_front();
    }

    cout << '\n';
}

std::list does not implement operator[]() because element access takes O(N) time for a linked list. std::vector and std::deque do implemnent operator[]() because they can offer random access in constant time. Generally speaking, given the choice between providing an inefficient version of an API function and omitting the function altogether, STL prefers the latter. Another example of this is std::vector not implementing push_front().

We’ll cover how to use iterators to traverse a linked list shortly. In the meantime, we print out the front element and then discard it in a loop until the list is empty.

As one would expect from a doubly linked list implementation, push_front() and push_back() run in O(1) time. Insertions & deletions anywhere in the list are also O(1), provided you have a pointer to the position. None of these operations invalidate any existing pointers or references.

As was the case with std::deque, the aforementioned O(1) run times of std::list operations do not make it the best container. In fact, std::vector will outperform std::list in many situations because of its contiguous memory layout. Again, the only way to know for sure is to perform measurements.

`std::forward_list` class template

std::forward_list is a minimal singly linked list implementation. In the main() function shown below, we swapped std::list for std::forward_list, removed the call to push_back() because std::forward_list doesn’t implement it, and verifies that the byte size of the forward_list<int> class is 8 bytes.

int main() {
    forward_list<int> v { 100, 101, 102, 103, 104 };
    v.push_front(99);
    while (!v.empty())  {
        print_int(v.front());
        v.pop_front();
    }
    static_assert(sizeof(forward_list<int>) == 8);

    cout << '\n';
}

std::forward_list doesn’t implement push_back() because it would be an O(N) operation, given that it’s a singly linked list. The byte size of the class is just 8 bytes, which suggests that the class only holds a pointer to the first node of the linked list.

Last updated: 2025-10-14

COMS W4995 C++ Deep Dive for C Programmers

Sequence Containers

Arrays in C++

Array class template

std::array class template

std::vector class template

std::deque class template

std::list class template