Some Performance Considerations
Learn about performance considerations when working with containers.
Performance considerations
We have now covered the three major container categories:
Sequence containers
Associative containers
Container adaptors
This lesson will provide us with some general performance advice to consider when working with containers.
Balancing between complexity guarantees and overhead
Knowing the time and memory complexity of data structures is important when choosing between containers. But it's equally important to remember that each container is afflicted with an overhead cost, which has a bigger impact on the performance of smaller datasets. The complexity guarantees only become interesting for sufficiently large datasets. It's up to us, though, to decide what sufficiently large means in our use cases. Here, again, we need to measure our program while executing it to gain insights.
In addition, the fact that computers are equipped with memory caches makes the use of data structures that are friendly to the cache more likely to perform better. This usually speaks in favor of the std::vector
, which has a low memory overhead and stores its elements contiguously in memory, making access and traversal faster.
The following diagram shows the actual running time of two algorithms. One runs in linear time,
Get hands-on with 1200+ tech skills courses.