“Choosing Wisely !!! ” — C++ Containers and Big-Oh complexity

Why we have different data structures in programming languages? Is there a real impact in terms of time and resources consumption? Yes, there is. I will use C++ programming language as reference.

Types of containers supported by STL

Container Presents in C++

• std::unordered_map and std::unordered_set are implemented using hash functions
• std::map are implemented using Red-Black-Tree

Containers and Complexity

The next tables resumes the Bih-Oh consumption for each container, thinking when we are insert a new element, access an elements, erase in front or in middle, find, …

C++ STL Containers Complexity

Table from: “ STL Container Performance ”

When to use? What is the best container for each scenario?

We have to take in consideration some points:

• Order is important ?
• Can be duplicates keys ?
• Insert in middle, front, back ?

The follow flowchart cam be used as azimuth when we have to choose the wright container for write propose

Flowchart based on: “ In which scenario do I use a particular STL container ?”

Rules of Thumb

• use sequential containers to access elements by positions and associative when access by key
• use vector as default sequential containers
• if the size is immutable choose std::array
• use std::list for remove and add elements at middle o sequence
• use std::unordered_map or std::unordered_set unless order matters and use std::map or std::set
• associative containers have logarithmic access time

Also read

Know your algorithm’s complexity

Containers and Iterators ( C++ GitHub repository Notes )

Choosing the Right Container: Sequential Containers