Oct 20, 2018
2 min read
“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
- 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, …
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
