Previously we've looked at the C++
vector containers and saw why those containers are better than standard C-style arrays. We also learned that containers can take advantage of idioms such as the SBRM design pattern and range-based
Now that we've looked at two containers in depth (as well as the pseudo-container
std::string, I'd like to provide an overview of the remaining C++ containers.
The Standard Containers
The containers library is a collection of templates and algorithms that implement the common data structures that we work with as programmers. A container is an object that stores a collection of elements (i.e. other objects). Each of these containers manages the storage space for their elements and provides access to each element through iterators and/or member functions.
The standard containers implement structures that are commonly used in our programs, such as:
- dynamic arrays
- linked lists
- associative sets
I love the STL containers, as they eliminate an entire set of boilerplate code that I re-implement on every project I work on. The container library also benefits from having a standardized interface for member functions. These standardized interfaces reduce your memory burden and allow containers to be used with STL algorithms.
The C++ container library categorizes containers into four types:
- Sequence containers
- Sequence container adapters
- Associative containers
- Unordered associative containers
Let's dive into each of these categories.
Sequence containers are used for data structures that store objects of the same type in a linear manner.
SequenceContainer types are:
arrayprovides a static contiguous array
vectorprovides a dynamic contiguous array
forward_listprovides a singly-linked list
listprovides a doubly-linked list
dequeprovides a double-ended queue, where elements can be added to the front or back of the queue.
std::string is not included in most container lists, it does in fact meet the requirements of a
Container adapters are a special type of container class. They are not full container classes on their own, but wrappers around other container types (such as a
list). These container adapters encapsulate the underlying container type and limit the user interfaces accordingly.
std::stack is a container that enforces a LIFO-type data structure. Here's the declaration of
template< class T, class Container = std::deque<T> > class stack;
Container defaults to wrapping a
std::deque<T>. You can actually change the type of underlying container to another STL
SequenceContainer or your own custom container. The container you specify has to meet the following requirements:
- The container must satisfy the requirements of a SequenceContainer
- Must provide
The STL containers
std::list all meet these requirements and can be used for underlying storage.
The standard container adapters are:
stackprovides an LIFO data structure
queueprovides a FIFO data structure
priority_queueprovides a priority queue, which allows for constant-time lookup of the largest element (by default)
Associative containers provide sorted data structures that provide a fast lookup (O(log n) time) using keys.
AssociativeContainer types are can be divided in two ways: containers which require unique keys, and those which allow multiple entries using the same key.
- Keys are unique
- Multiple entries for the same key are permitted
map are typically implemented using red-black trees.
Each of the associative containers can specify a comparison function during declaration. Let's take a look at the definition of
template< class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> > class set;
The default comparison function for associative containers is
std::less. This comparison function is used to sort keys. If you prefer a different sorting or allocation scheme, you should override these functions during declaration.
Unordered Associative Containers
Unordered associative containers provide unsorted data structures that can be accessed using a hash. Access times are O(n) in the worst-case, but much faster than linear time for most operations.
For all STL
UnorderedAssociativeContainer types, a hashed key is used to access the data. Similar to the
AssociativeContainer, the standard types are split between those that require unique keys, and those that do not:
- Keys are unique
- Multiple entires for the same key are permitted
Like with the other container types,
UnorderedAssociativeContainer types can have details overridden. Let's look at
template< class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key> > class unordered_set;
You can override the hashing function, the key comparison function, and the allocator. I don't care to improve up on the STL hashing functionality, so I usually leave these details alone. However, if you want to override any of the default functions, you must do it during declaration.
Reasons to Use Standard Containers
Standard containers eliminate much of the boilerplate code that I am required to write when bringing up a new system for a new client. They simplify development and should be utilized instead of custom implementations for four simple reasons:
- STL containers are implemented correctly, and I will not need to spend time debugging the containers
- STL containers are fast, and likely more efficient than anything I'm going to implement on my own
- STL containers share common interfaces, making it quite simple to utilize different containers without looking up member function definitions
- STL containers are well-documented and easily understood by other developers, improving the understandability and maintainability of our projects
By utilizing STL containers, I can become a more productive developer. I'm much more confident in the reliability of my code, and I can trust that other developers will have an easier time maintaining my code in the future.
Standard Container Thread Safety
I want to share with you some relevant points regarding container thread safety, as many embedded systems will likely require sharing objects across threads.
All container functions are safe to be called concurrently on different objects of the same container type.
For operating on objects of the same type, the following guidelines are helpful to keep in mind:
constmember functions can be called concurrently by different threads
- The following member functions are thread-safe:
begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range(), at()
is thread-safe for sequence containers, unordered associative containers, and container adapters.
is NOT thread-safe for associative containers!
- Different elements in the same container can be modified concurrently, except for the elements of
- Iterator operations read from a container, but do not modify it, so they are thread-safe
- Container operations that invalidate iterators are NOT thread-safe, as they modify the container
In general, common-sense concurrency rules apply. If you are modifying the container in multiple threads, you will need to protect that container to prevent concurrent access.
I've aimed to provide a summary of the containers available in C++. In later articles, we will be using these containers to build up our embedded system. I recommend reading the documentation for any containers that immediately interest you.
- cppreference: Containers
- ISO CPP: Container FAQ
- Embedded Artistry Container Articles
- Container Concepts
- Sequence Containers
- Container Adapters
- Associative Containers
- Unordered Associative Containers