Previously we’ve looked at the C++ array
and 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 for
loops.
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.
Table of Contents:
- The Standard Containers
- Reasons to Use Standard Containers
- Standard Container Thread Safety
- Further Reading
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
- queues
- stacks
- linked lists
- trees
- 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
Sequence containers are used for data structures that store objects of the same type in a linear manner.
The STL SequenceContainer
types are:
array
represents a static contiguous arrayvector
represents a dynamic contiguous arrayforward_list
represents a singly-linked listlist
represents a doubly-linked listdeque
represents a double-ended queue, where elements can be added to the front or back of the queue.
While std::string
is not included in most container lists, it does in fact meet the requirements of a SequenceContainer
.
Container Adapters
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 vector
, deque
, or list
). These container adapters encapsulate the underlying container type and limit the user interfaces accordingly.
Let’s consider std::stack
. std::stack
is a container that enforces a LIFO-type data structure. Here’s the declaration of std::stack
:
template<
class T,
class Container = std::deque<T>
> class stack;
Notice that 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
back()
,push_back()
, andpop_back()
interfaces
The STL containers std::vector
, std::deque
, and std::list
all meet these requirements and can be used for underlying storage.
The standard container adapters are:
stack
provides an LIFO data structurequeue
provides a FIFO data structurepriority_queue
provides a priority queue, which allows for constant-time lookup of the largest element (by default)
Associative Containers
Associative containers provide sorted data structures that provide a fast lookup (O(log n) time) using keys.
The STL 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
set
is a collection of unique keys, sorted by keysmap
is a collection of key-value pairs, sorted by keysset
andmap
are typically implemented using red-black trees
- Multiple entries for the same key are permitted
Each of the associative containers can specify a comparison function during declaration. Let’s take a look at the definition of std::set
:
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
unordered set
is a collection of keys, hashed by keysunordered_map
is a collection of key-value pairs, hashed by keys
- Multiple entires for the same key are permitted
unordered_multiset
is a collection of keys, hashed by keysunordered_multimap
is a collection of key-value pairs, hashed by keys
Like with the other container types, UnorderedAssociativeContainer
types can have details overridden. Let’s look at std::unordered_set
:
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. The following general thread-safety rules apply:
- All container functions are safe to be called concurrently on different objects of the same container type (i.e. it is safe to use two different
std::vector
instances on two different threads - All
const
member functions can be called concurrently by different threads - Containers can be safely read from multiple threads if no thread is making asynchronous writes
- Different elements in the same container can be modified concurrently, except for the elements of
std::vector<bool>
. - If an object is written to by one thread and read by other threads, the object must be protected
- In general, 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
The most important detail to keep in mind: if you are modifying the container in multiple threads, you will need to protect that container to prevent concurrent access. For more information using containers in a thread-safe way, see Implementing a Thread-Safe Queue using Condition Variable
Also, Boost provides a selection of lock-free container alternatives which you can consider for multi-threaded use cases.
Further Reading
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
- Microsoft: Thread Safety in the C++ Standard Library
- Implementing a Thread-Safe Queue using Condition Variables
- Embedded Artistry Container Articles
- <a href=”https://embeddedartistry.com/blog/2017/6/28/an-introduction-to-stdarray “>Introduction to
std::array
- Introduction to
std::vector
- Ditch Those Built-in Arrays for C++ Containers
- Range-based
for
Loops - Take Advantage of RAII/SBRM
std::string
vs C-string
- <a href=”https://embeddedartistry.com/blog/2017/6/28/an-introduction-to-stdarray “>Introduction to
- Container Concepts
- Sequence Containers
- Container Adapters
- Associative Containers
- Unordered Associative Containers
Major Revisions
- 20181026:
- Updated notes on thread-safety for unordered associative containers. Operator
[]
andat()
are not thread safe due to the possibility for re-indexing to invalidate all iterators.
- Updated notes on thread-safety for unordered associative containers. Operator
- 20181105:
- Further improved notes on thread-safety of containers
- Updated cppreference links: “concept” URLs were updated to “named_req”
Using C++ Without the Heap
Want to use C++, but worried about how much it relies on dynamic memory allocations? Our course provides a hands-on approach for learning a diverse set of patterns, tools, and techniques for writing C++ code that never uses the heap.
Learn More on the Course Page
Would you please comment on whether "operator []" on an unordered associative container is thread-safe (may be executed concurrently) with other container operations?
Your list indicates:
Operator [] is thread-safe for sequence containers, unordered associative containers, and container adapters.
and
Container operations that invalidate iterators are NOT thread-safe, as they modify the container
but this reference:
https://en.cppreference.com/w/cpp/container/unordered_map/operator_at
says that:
If an insertion occurs and results in a rehashing of the container, all iterators are invalidated.
That is, operator [] on std::unordered_map may invalidate iterators, and thus would seem not to be thread safe.
Hi Bill,
You are correct in your assessment, and as such the possibility of rehashing would make unordered_map not thread safe.
Whether that is a practical concern or not I can’t say – perhaps for specific use cases with known maximum sizes this would be "safe" to use. I cannot advise it in general though if there is a rehashing possibility.
Thanks for pointing this out, I will get this article updated.
Hello Guys
thanks this was useful for me, i had so many problems with STLs
I think c++ is the best
Regarding thread safety, container adapters are NOT thread safe in STL. This statement is misleading "The following member functions are thread-safe: begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range()"
Please refer to this famous thread https://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html
Thanks for the feedback Nachiket. I’ve clarified the section; let me know what you think.
My original logic for calling those functions out is that they do not modify the container and thus are in fact generally safe to use from multiple threads. The exception is that they are not safe against data races. As such, I agree with you calling it misleading.
Thanks for the update. Your blog is very useful reference and informative.
In my application PerfectTIN, I use map<int,foo> as if it were vector (i.e. the keys are contiguous integers; the reason is that three foo types point to each other, and the pointers would be invalidated when the vectors are moved when resized). I found it necessary to lock the elements (I used spatial contiguity to use many fewer locks than the possibly millions of elements in the container) and additionally define a readers-writer lock (shared mutex) for the map itself. Inserting or deleting an element in the map counts as writing to it; accessing any element (including writing to it) and counting the elements count as reading from it. Something similar should apply to other container classes.
“map is a collection of key-value pairs, sorted by keys”
Was this supposed to say UNIQUE key-value pairs? This definition is identical to the one for multimap just below it.
Hi Jeremy,
Indeed. I note that the line you quote is a sub-bullet of the “keys are unique” list item :).
Adding a single integer vector of 1 element blew up my code size by ~100kB. Using the latest major version of the ARM gnu toolchain. On an embedded device with limited flash, this would preclude the use of STL containers. Would you agree?
Toolchain:
https://launchpad.net/gcc-arm-embedded/+announcement/15345
I’m surprised about the 100kB increase, but that might also be because it pulls in a lot of functionality that is otherwise excluded (e.g, Malloc). We have successfully used the STL in embedded systems without this problem, but we used a custom libc in that situation.
For embedded projects, we typically recommend the Embedded Template Library, which provides static memory equivalents for the STL containers (and many other useful features).