We use certain container types, like maps and dynamic arrays, constantly. Others, like linked lists and queues, more sparingly. Still, they are fundamental structures in virtually every program and the poster children for generic programming. Like C#, the Standard Library in C++ provides a bunch of container types. Today we’ll start going through them, starting with containers for various kinds of arrays!

Table of Contents

Vector

Let’s start with one of the most commonly-used container types: std::vector. This class, found in <vector>, is the equivalent of List in C# as it implements a dynamic array. Here’s a sampling of its API:

#include <vector>
 
void Foo()
{
    // Create an empty vector of int
    std::vector<int> v{};
 
    // Add an element to the end
    v.push_back(123);
 
    // Construct an element in place at the end
    v.emplace_back(456);
 
    // Get size information
    DebugLog(v.empty()); // false
    DebugLog(v.size()); // 2
    DebugLog(v.capacity()); // At least 2
    DebugLog(v.max_size()); // Maybe 4611686018427387903
 
    // Request changes to capacity
    v.reserve(100); // Note: can't shrink
    DebugLog(v.capacity()); // 100
    v.shrink_to_fit();
    DebugLog(v.capacity()); // Maybe 2
 
    // Shrink to just the first element
    v.resize(1);
 
    // Add two defaulted elements to the end
    v.resize(3);
 
    // Access elements with overloaded index operator
    v[2] = 789;
    DebugLog(v[0], v[1], v[2]); // 123, 0, 789
 
    // Access first and last elements
    DebugLog(v.front()); // 123
    v.back() = 1000;
    DebugLog(v[2]); // 1000
 
    // Get a pointer to the first element
    int* p = v.data();
    DebugLog(p[0], p[1], p[2]); // 123, 0, 1000
 
    // Create a vector with four elements
    std::vector<int> v2{ 2, 4, 6, 8 };
 
    // Compare vectors' elements
    DebugLog(v == v2); // false
 
    // Replace the elements of v with the elements of v2
    v = v2;
    DebugLog(v.size()); // 4
    DebugLog(v[0], v[1], v[2], v[3]); // 2, 4, 6, 8
} // Destructors free memory of v and v2

In C++20, the <vector> header also provides a couple of non-member functions to erase elements from a std::vector:

#include <vector>
 
std::vector<int> v1{ 100, 200, 200, 200, 300 };
 
// Erase every element that equals 200
std::vector<int>::size_type numErased = std::erase(v1, 200);
DebugLog(numErased); // 3
DebugLog(v1.size()); // 2
DebugLog(v1[0], v1[1]); // 100, 300
 
std::vector<int> v2{ 1, 2, 3, 4, 5 };
 
// Erase all the even numbers
numErased = std::erase_if(v2, [](int x) { return (x % 2) == 0; });
DebugLog(numErased); // 2
DebugLog(v2.size()); // 3
DebugLog(v2[0], v2[1], v2[2]); // 1, 3, 5

As is the case with std::string, std::vector “owns” the memory that elements are stored in. It allocates the memory when needed by the constructor and functions like push_back. It deallocates the memory when it needs to grow, in functions like shrink_to_fit, and especially in the destructor. Unlike the managed List class in C#, it’s not garbage-collected since C++ has no garbage collector. We can simulate that with the reference-counted std::shared_ptr if needed.

Array

Sometimes we want to use an array but don’t want the overhead of a dynamic array or we want to allocate it on the stack instead of the heap. In C#, we’d use stackalloc or a fixed buffer. If heap allocation was acceptable, we could also use a managed array. In C++, we could use an array but that has some notable downsides. It degrades to a pointer, its size isn’t easily inspected, and it lacks all the convenient member functions that std::vector provides.

To address these issues, the <array> header provides the std::array class template that holds a statically-sized array. While std::vector holds a pointer to the first element of the array, a std::array holds the actual array. It’s the difference between a struct Vector { int* P; }; and struct Array { int E[100]; };. This difference allows std::array to be allocated on the stack. It also requires that the size be specified as a template parameter:

#include <array>
 
// Create an array of 3 int elements
std::array<int, 3> a{ 1, 2, 3 };
 
// Query its size
DebugLog(a.size()); // 3
DebugLog(a.max_size()); // 3
DebugLog(a.empty()); // false
 
// Read and write its elements
DebugLog(a[0], a[1], a[2]); // 1, 2, 3
a[0] = 10;
DebugLog(a.front()); // 10
DebugLog(a.back()); // 3
 
// Get a pointer to the first element
int* p = a.data();
DebugLog(p[0], p[1], p[2]); // 10, 2, 3
 
// Create another array of 3 int elements
std::array<int, 3> a2{ 10, 2, 3 };
 
// Compare elements of arrays
DebugLog(a == a2); // true

Note that std::array doesn’t require that it’s allocated on the stack. We can easily allocate one on the heap like any other class:

#include <array>
 
std::array<int, 3>* a = new std::array<int, 3>{ 1, 2, 3 };
DebugLog((*a)[0], (*a)[1], (*a)[2]); // 1, 2, 3
delete a;

C++20 adds the non-member std::to_array function to copy an array into a std::array:

#include <array>
 
// Plain array
int a[3] = { 1, 2 };
 
// Copy the plain array into a std::array
std::array<int, 3> c{ std::to_array(a) };
 
// Changing one doesn't change the other
a[0] = 10;
c[1] = 20;
DebugLog(a[0], a[1]); // 10, 2
DebugLog(c[0], c[1]); // 1, 20
Valarray

The <valarray> header is part of the numbers library but also a container. The same can be said for std::basic_string. Like std::vector, both are backed by arrays. The major difference is the set of member functions which operate on those arrays. As std::basic_string has functions for finding sub-strings, std::valarray is geared toward operations on every element of a std::valarray object or on pairs of elements in two std::valarray objects:

#include <valarray>
 
void Foo()
{
    // Create an array of two ints
    std::valarray<int> va1{ 10, 20 };
 
    // Create another array of two ints
    std::valarray<int> va2{ 10, 30 };
 
    // Compare element 0 in each, element 1 in each, and so on
    // Return a valarray of comparison results
    std::valarray<bool> eq{ va1 == va2 };
    DebugLog(eq[0], eq[1]); // true, false
 
    // Add elements
    std::valarray<int> sums{ va1 + va2 };
    DebugLog(sums[0], sums[1]); // 20, 50
 
    // Access elements
    DebugLog(va1[0]); // 10
    va1[1] = 200;
    DebugLog(va1[0], va1[1]); // 10, 200
 
    // Shift elements 1 toward the front, filling in with zeroes
    std::valarray<int> shifted{ va1.shift(1) };
    DebugLog(shifted[0], shifted[1]); // 200, 0
 
    // Shift elements 1 toward the front, rotating around to the back
    std::valarray<int> cshifted{ va1.cshift(1) };
    DebugLog(cshifted[0], cshifted[1]); // 200, 10
 
    // Copy all elements to another valarray
    va1 = va2;
    DebugLog(va1[0], va1[1]); // 10, 30
 
    // Call a function with each element and assign the return value to it
    std::valarray<int> plusOne{ va1.apply([](int x) { return x + 1; }) };
    DebugLog(plusOne[0], plusOne[1]); // 11, 33
 
    // Take 2^4 and 3^2
    std::valarray<float> bases{ 2, 3 };
    std::valarray<float> powers{ 4, 2 };
    std::valarray<float> squares{ std::pow(bases, powers) };
    DebugLog(squares[0], squares[1]); // 16, 9
} // Destructors free memory of all valarrays

Like std::vector, std::valarray “owns” the memory that stores its elements. C# doesn’t have an equivalent of this class template.

Some helper classes exist to “slice” more than one element out of a std::valarray by passing instances of the class to the overloaded [] operator:

#include <valarray>
 
std::valarray<int> va1{ 10, 20, 30, 40, 50, 60, 70 };
 
// A slice that starts at index 1 plus 2 elements with 0 stride
std::slice s{ 1, 2, 0 };
 
// Slice the valarray to get a slice_array that refers to the slice
std::slice_array<int> sa{ va1[s] };
 
// Copy the slice into a new valarray
std::valarray<int> sliced{ sa };
DebugLog(sliced.size()); // 2
DebugLog(sliced[0], sliced[1]); // 20, 30
 
// Slice that starts at index 1 with sizes 2 and 3 and strides 1 and 2
std::gslice g{ 1, {2, 3}, {1, 2} };
 
// Slice the valarray to get a gslice_array that refers to the slice
std::gslice_array ga{ va1[g] };
 
// Copy the slice into a new valarray
std::valarray<int> gsliced{ ga };
DebugLog(gsliced.size()); // 6
DebugLog(gsliced[0], gsliced[1], gsliced[2]); // 20, 40, 60
DebugLog(gsliced[3], gsliced[4], gsliced[5]); // 30, 50, 70
Deque

std::deque, pronounced like “deck” and located in <deque>, is a doubly-ended queue that owns its elements. Internally, it holds a list of arrays but this is hidden by its API which gives the appearance that it’s one contiguous array similar to a std::vector. This means element access involves a second indirection, but it’s fast to add and remove elements from the beginning and end of a std::deque. C# has no equivalent to this container type. Here’s how to use it:

#include <deque>
 
void Foo()
{
    // Create a deque of three floats
    std::deque<float> d{ 10, 20, 30 };
 
    // Query its size
    DebugLog(d.size()); // 3
    DebugLog(d.max_size()); // Maybe 4611686018427387903
    DebugLog(d.empty()); // false
 
    // Access its elements
    DebugLog(d.front()); // 10
    d[1] = 200;
    DebugLog(d[1]); // 200
    DebugLog(d.back()); // 30
 
    // Add to and remove from the beginning and the front
    d.push_front(5);
    d.push_back(35);
    DebugLog(d[0], d[1], d[2], d[3], d[4]); // 5, 10, 200, 30, 35
    d.pop_front();
    d.pop_back();
    DebugLog(d[0], d[1], d[2]); // 10, 200, 30
 
    // Remove all but the first two elements
    d.resize(2);
    DebugLog(d.size()); // 2
    DebugLog(d[0], d[1]); // 10, 200
 
    // Compare elements of two deques
    std::deque<float> d2{ 10, 200 };
    DebugLog(d == d2); // true
 
    // Remove all of a particular element value
    std::deque<float>::size_type numErased = std::erase(d, 10);
    DebugLog(numErased); // 1
    DebugLog(d[0]); // 200
 
    // Remove all elements that a function returns true for
    numErased = std::erase_if(d2, [](float x) { return x < 100; });
    DebugLog(numErased); // 1
    DebugLog(d2[0]); // 200
}  // Destructors free memory of all deques
Queue

Unlike std::deque, the std::queue class template in <queue> is an adapter to provide a queue API to another collection. The default container type is std::deque, but other containers with back, front, push_back, and push_front member functions may be used. The std::queue contains this collection type and provides member functions that are implemented by calls to the contained collection.

#include <queue>
#include <deque>
 
void Foo()
{
    // Explicitly use std::deque<int> to hold elements of a std::queue of int
    std::queue<int, std::deque<int>> qd{};
 
    // Use the default collection type, which is std::deque
    // It's initially empty
    std::queue<int> q{};
 
    // Add elements to the back
    q.push(10);
    q.push(20);
    q.emplace(30); // In-place construction
 
    // Query the size
    DebugLog(q.size()); // 3
    DebugLog(q.empty()); // false
 
    // Access only the first and last elements
    DebugLog(q.front()); // 10
    DebugLog(q.back()); // 30
 
    // Remove elements from the front
    q.pop();
    DebugLog(q.size()); // 2
    DebugLog(q.front()); // 20
 
    // Copy elements to another queue
    std::queue<int> q2{};
    q2 = q;
    DebugLog(q2.size()); // 2
    DebugLog(q2.front()); // 20
    DebugLog(q2.back()); // 30
} // Destructors free memory of all queues

C# has an equivalent Queue class. Unlike std::queue, it’s not an adapter for another collection type. Instead, it implements a particular collection internally.

Stack

The other adapter type, similar to std::queue, is std::stack in the <stack> header. It also defaults to std::deque as its collection type. Since stacks only operate on the back, more types of collections can be used. All they need to have are back, push_back, and pop_back member functions:

#include <stack>
#include <vector>
 
void Foo()
{
    // Make a stack backed by a std::vector
    std::stack<int, std::vector<int>> sv{};
 
    // Make a stack backed by the default std::deque
    std::stack<int> s{};
 
    // Add elements to the back
    s.push(10);
    s.push(20);
    s.emplace(30); // In-place construction
 
    // Query the size
    DebugLog(s.size()); // 3
    DebugLog(s.empty()); // false
 
    // Access only the last element
    DebugLog(s.top()); // 30
 
    // Remove elements from the back
    s.pop();
    DebugLog(s.size()); // 2
    DebugLog(s.top()); // 20
 
    // Copy elements to another stack
    std::stack<int> s2{};
    s2 = s;
    DebugLog(s2.size()); // 2
    DebugLog(s2.top()); // 20
} // Destructors free memory of all stacks

Also like Queue, C# has a std::stack equivalent in Stack. It also is not an adapter, but a uniquely-implemented container type.

Conclusion

Arrays are so ubiquitous that the C++ Standard Library provides several container types to wrap and access them. vector, array, and valarray join basic_string in holding elements in a contiguous block of memory. The vector type provides resizing, array provides stack allocation and low overhead, and valarray provides element-wise access and advanced slicing. C#’s has a close equivalent to vector in List, but stackalloc only supporting unmanaged types limits it quite a lot compared to array and there’s simply no analog to valarray.

The deque type is suprisingly useful when we need to cheaply add to and remove from the front of an array. While not completely contiguous in memory, it is still mostly contiguous and may represent an acceptable tradeoff given that insertion and removal operations at the front of the collection are now in O(1) instead of O(N). C# lacks this collection type.

Finally, there are queue and stack as adapter types for any collection providing the necessary member functions. The C# Queue and Stack classes instead mandate particular collection implementations.

Next up we’ll explore some of the non-array collection types. Stay tuned!