A quick C++ standard container overview

published at 15.10.2026 22:58 by Jens Weller
Save to Instapaper Pocket

Part four in the new C++ content series, visiting the heap. Meeting C++ 2026 is only 6 weeks away!

The last entry looked at heap allocations, but one important part about heap allocations was missing: hidden allocations. Often you don't allocate directly, but a used class does. The C++ containers and string classes are the perfect example of this. Allocations for containers in the standard are done via allocators, which usually means heap allocations. These can be categorized as node based, chunk based and continuous memory containers.

Node based containers allocate their data as nodes in memory, which has a certain overhead for this node structure. For (forward_)list this means a linked list of an internal node type holding pointers to the next and previous nodes + the memory of the data entry. For a map/set (and the multi versions) the internal nodes form a (red-black) tree instead of a list. An unordered_map/set usually consists of an array of buckets for the hashes and linked list for the entries of a bucket.

The performance of these node based containers is acceptable for many use cases. Still, its not an optimal design for a world where performance and cache efficiency matter. For performance centric use cases better alternatives usually exist already, you can find them on codeberg/github/gitlab or in frameworks like abseil/boost/Dlib/folly/POCO/Qt and others.

An upside of the node based implementations is, that this gives stronger guarantees for iterators and references to elements stored in these. An iterator to a list or map will stay valid when a new element is added or a different element is removed. An overview on all containers is given on the container overview page on cppreference.

Vector is the container that allocates all its data into one large array of continuous heap memory, while deque does so in chunks/memory blocks, which makes memory access in a deque a bit slower, as it takes one step to access the correct chunk, and another to arrive at the correct element. An advantage of deque is (or was) that it does not reallocate all of its memory when its grows and needs to allocate. A single larger chunk will do. An implementation detail of deque is that its move constructor is not noexcept. And types like vector fall back to copy instead of moving when this is the case. With move semantics the growth of vector has become a lot cheaper, while access to an element is faster and by design more efficient then in deque. This and the cache friendly memory storage has made vector the default container of choice.

There is one exception to this, the infamous vector. When vector was added to the standard, it was very early in C++ history. So it was decided that vector would be different, as here was a great opportunity to optimize for space! Instead of wasting a byte for storing a bool in an array, one would simply store each entry as a single bit. For this vector had to be specialized, so that the index operator[] would translate the index to the correct bit. All for saving a few bytes. This then brings disadvantages when trying to tread a vector like any other vector in generic code. It does not behave like a C array, the iterator is a proxy iterator and other differences. When one needs a vector that isn’t specialized, a deque can be an alternative. One other good idea I’ve seen is to use an enum with the underlying type of bool. Others have used vector or vector to store boolean states. There is also std::bitset, which offers storage for a fixed size of bits. So its more like std::array then std::vector.

Which brings up a general problem of the older standard containers: they are kinda locked in how they are. Some things could be improved, but backward compatibility is very important to the standard and ABI stability is also important for its implementations independent of the standard. Remember std::mutex under MSVC? So unfortunately vector will likely stay what it is, as surely some folks depend on its current implementation.

With C++26 comes the new container using chunk based memory: std::hive, which provides stable memory addresses and allocates internally similar to deque in memory blocks. But it will not shrink when an element is being removed, the memory block is then added to an internal free list for reuse. Hive also offers move constructors and assignment operator that are noexcept, if the value type permits this.

A group of containers is implemented through the adapter design pattern, where the used container is part of the templated interface as a default type. This is deque for stack and queue, and vector for priority_queue. C++26 brings flat_map and flat_set and their multi versions to the standard, these are implemented as adapters, with defaulting to vector.

With std::array there exists a thin wrapper around a C array with a container interface, and C++26 brings inplace_vector, a vector like type which stores allocations on an internal, fixed array it operates on. Both std::array and std::inplace_vectors are of great use when you need to store result sets of compile time calculations. Both types are essentially arrays residing on the stack.

Have you ever wondered about the actual usage of all these containers?

This is from the Meeting C++ community survey. The bars are alphabetically ordered and from left to right: array, deque, forward_list, list, map, multimap, multiset, priority_queue, set, stack, span, queue, unordered_map, unordered_multimap, unordered_multiset, unordered_set and vector.

The 5 most popular containers are vector, array, map, unordered_map and set.

Did you notice span? I did include it into the survey question back then, as I was curious about its usage. Also I’d rather have folks ask why its included, then why its not there. I’ll add C++26 additions to the containers one day when its available and actually in use by folks.

Introduced with C++20, span is not a container, it is a view into a continuous array of type T and the size you give it. With mdspan C++23 added a multidimensional version of span into the standard, which also operates on continuous memory of a supplied type T. Both types work very well with std::array or std::vector. A view in C++ is always a good hint that the type is not owning the memory its pointing to. One exception to this is owning_view in std::ranges which owns the range it views and is move only, similar to unique_ptr<T[]>. An interesting trivia of owning_view is that its derived from view_interface, one of the few times CRTP is getting used in the standard. Ranges has many more views like subrange, filter_view, take_(while_)view, drop_(while_)view and others. One of the big differences is that these views operate on ranges, not necessarily on continuous memory.

The first view that was introduced to C++ was std::string_view with C++17. It represents the interface of a const string, which has some overlap with span. But string_view does not support some of the functionality that span has like first/last or subspan. Both serve the same use case, to have a non-owning type that represents a range of continuous memory, which is light weight in its memory usage. Both types are 16 bytes, the size of a pointers for begin and a size_t for its size. All views are not observers, there is no “reset”/set to nullptr mechanism watching if the viewed memory range is being freed.

From its design std::string_view is a drop in replacement of const std::string&, this also helps when one needs to replace a string_view with a string. As string_view depends on that the life time of its viewed range exceeds its own life time, only converting to std::string will extend the life time if needed. For function arguments you should opt for taking string_views by value, as then this variable can be placed in a register. A reference prevents this.

Join the Meeting C++ patreon community!
This and other posts on Meeting C++ are enabled by my supporters on patreon!