Containers

This page goes over the various type of containers that are available in C++. These containers cover the many different way in which you might wish to store data.

The following containers are sorted alphabetically.

arrays

Header	#include <deque>
Full Path	std::array
Time Complexity	Random Access: $\mathcal{O}(1)$ Insertion At Start Or End: n/a Insertion In Middle: n/a

Of course, we will always be able to use C-style arrays in C++, which are normally just used and passed around as a pointer to the element type. However, some issues with standard C-style arrays include; no built-in memory management, no bounds checking, and no information about the size of the array is carried with it (so you usually have to indicate the size by passing in another variable to functions).

C++11 provides us with a std container which encapsulates a fixed-size array.

std::array<int, 3> myArray = { 1, 2, 3};

A std::array is more restrictive than a C-style array in that the size must be provided at compile time. e.g.:

int size = 4;
int cArray[x];                  // This WILL compile
std::array<int, size> cppArray; // This WON'T compile

If you want a runtime resizable array-like container, reach for a std::vector instead.

Before C++11 introduced std::array, you could use the Boost equivalent. Boost provides a templated class to create fixed-size arrays of a particular type. To create a fixed array that stored 6 doubles, you would use:

boost::array<double, 6> myArray;

Note that boost::array provides exactly the same syntax as std::array for initialization. The first template parameter is the type you wish the array to store, and the second parameter is the number of elements in the array.

deque

Header	#include <deque>
Full Path	std::deque
Time Complexity	Random Access: $\mathcal{O}(1)$ Insertion At Start Or End: $\mathcal{O}(1)$ Insertion In Middle: $\mathcal{O}(n)$

std::deque stands for double-ended queue (usually pronounced similar to “deck”). It is an indexed sequence container used for storing data in C++. It is dynamically sized, and can be quickly expanded/contracted both at the front and back.

A deque is not guaranteed to store all of it’s data in a continuous memory sequence. Thus it’s data cannot be accessed via pointer addition (unlike a vector).

Example

// Create a new queue initialised with 4 integers
std::deque<int> myDeque = {5, 6, 7, 8};
myDeque.push_front(4);
myDeque.push_back(9);

// queue now equals 4, 5, 6, 7, 8, 9

map/multimap

Header	#include <map>
Full Path	std::map , std::multimap
Time Complexity	Random Access: $\mathcal{O}(1)$ Insertion At Start Or End: $\mathcal{O}(1)$ Insertion In Middle: $\mathcal{O}(n)$

std::map is an associative C++ container. Is is similar to a dictionary in Python. While an array or vector only allows you to store and retrieve data using an integer, a map allows you to store and retrieve data via any other object.

For example, we could store peoples data based on their first name:

std::map <string, int> peoplesAges;

We could now store a value into the map:

peoplesAges["John"] = 32;

Notice how we can use a string to index into the map, rather than an integer!

We can retrieve values from a map by using the find() method.

auto it = peoplesAges.find("John");
if(it != peoplesAges.end()
    std::cout << "Found John's age of " << *it << std::endl;

Different Ways Of Adding An Element To A Map

emplace() was added to std::map in C++11. It allows you to pass in the arguments used to create a new element in the map separately. emplace() then forwards these arguments onto the element’s constructor.

set/multiset

A set is an associative, ordered container in where the value of the element also serves as a key (as opposed to a map, where the key is different from the value). Another interesting property of sets is that the elements are const, that is, you cannot modify them directly. However, you can add and remove elements.

std::set<std::string> mySet;

mySet.insert("Hello, ");
mySet.insert("world!");

for(it = mySet.begin(); it != mySet.end(); it++){
    std::cout << *it << std::endl;
}

The C++ standard does not specify how the library must implement a std::set. However, std::set is normally implemented behind-the-scenes as binary search trees.

Each element in a set must be unique. If you want to store multiple elements of the same value, use a multiset instead.

vector

A std::vector is your bread-and-butter array type in C++. It supports the insertion and removal of elements and dynamic resizing at run-time.

std::vector<int> myVector;
myVector.push_back(1);
myVector.push_back(2);
myVector.push_back(3);

std::cout << myVector[1] << std::endl; // "2", no bounds checking
std::cout << myVector.at(1) << std::endl; // "2", with bounds checking!

myVector[<element index>] provides the standard, no bounds checking way of getting and setting elements within the vector. However, if you want bounds checking, you can use .at() instead.

Since C++11, you can get a C-style pointer to the array using the data() method:

std::vector<int> myVector = { 1, 2, 3 };
int * ptrToArray = myVector.data();

The C++ standard guarantees that the data will be stored in a contiguous memory space, and accessible like a C-style array.

std::span

std::span is a container introduced in C++20 that provides a view into a contiguous sequence of objects. It is a lightweight, non-owning view of a contiguous sequence of objects, such as an array or a vector.¹ It does not perform any memory allocation as part of it’s construction, nor does it keep smart pointers alive (it is a reference type).

Tip

std::span was formerly known as an array_view and even earlier as array_ref.²

There are two types of std::span:¹

1. Static extent: The number of elements in the sequence is known at compile time and is encoded in the type.
2. Dynamic extent: The number of elements in the sequence is not known at compile time.

You can think of a std::span being a struct { T * ptr; std::size_t size; } with a bunch of convenience methods added like iterator support.²

Here is a basic example showing how you can pass a std::span to a function instead of a raw pointer and size:

#include <cstdint>
#include <cstdio>
#include <span>

void worseWay(uint8_t* data, size_t size) {
    for (size_t i = 0; i < size; i++) {
        std::printf("%d ", data[i]);
    }
    std::printf("\n");
}

void betterWay(std::span<uint8_t> data) {
    for (auto& byte : data) {
        std::printf("%d ", byte);
    }
    std::printf("\n");
}

int main() {
    std::array<uint8_t, 5> data = {1, 2, 3, 4, 5};
    worseWay(data.data(), data.size());
    betterWay(data);
    return 0;
}

worseWay() is the traditional way of doing it. Note that the caller has to explicitly pass in the size, and there are more ways for things to go wrong. betterWay() is the “better” way of doing it using a std::span. No explicit size is needed (the compiler automatically captures that for you).

The ISO C++ core guidelines recommend the use of std::span instead of passing in raw pointers and sizes to functions which need to operate on an array.³

Footnotes

1. cppreference.com. C++ > Containers library > std::span [documentation]. Retrieved 2025-05-06, from https://en.cppreference.com/w/cpp/container/span. ↩ ↩²

2. Stack Overflow. What is a “span” and when should I use one? [forum post]. Retrieved 2025-05-06, https://stackoverflow.com/questions/45723819/what-is-a-span-and-when-should-i-use-one. ↩ ↩²

3. Bjarne Stroustrup, Herb Sutter. C++ Core Guidelines. Retrieved 2025-05-06, from https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines. ↩