Some Performance Considerations

Performance considerations

We have now covered the three major container categories:

1. Sequence containers

2. Associative containers

3. 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, $O(n)$, and the other runs in logarithmic time, $O(log\ n)$, but with a larger overhead. The logarithmic algorithm is slower than the linear time algorithm when the input size is below the marked threshold: