EDITOR’S PICK

C++ STL UNDER THE HOOD

Not knowing what you are using can be dangerous!

Internal Implementation of C++ STL — Standard Template Library.

Who can be a better best friend in competitive programming than STL? me?

But Priyansh… Why do all this?

— Well, This can come in handy during interviews, (or, good to know what you are using at least).

Couldn’t find a more direct and complete list over the internet so made one myself.

So let's jump right in!

[STL] | [INTERNAL IMPLEMENTATION DATA STRUCTURE]

meaning —
for e.g — Set STL, which we use blindly everywhere, has its internal implementation(what it’s coded with) using a Red-Black Tree.

1. stack — Array, List, Deque.
2. vector — Dynamic Array
3. list — Dynamic Array and Doubly Linked List
4. pair — defined in <utility> header file
5. queue — Array, List
6. deque(double-ended-queue) — Dynamic Array
7. priority_queue — Heap

more…

1. set — Red Black Tree
2. multiset — Binary Search Tree
3. unordered set — Hash Table

and more…

1. map — Red Black Tree (Self-Balancing BST)
2. multimap — Red Black Tree
3. unordered map(4x faster than the map) — Hash Table

sort() — uses IntroSort(a hybrid of Quicksort, Heapsort, and Insertion Sort), Faster than qsort().

I’d love to hear your thoughts about this, so feel free to reach out to me on LinkedIn or Twitter or respond in the comments below, that’d be great.

— If this article helped you in any way, consider sharing it with 2 friends you care about.

Till then stay alive.

references —

leetcode.com