Time and space complexity of STL containers

Stack

Stacks are containers that operate on a LIFO (Last In First Out) basis, where a new element is added at one end (top). An element is deleted from that end.

Operations of stack and their time and space complexities are:

Queue

Queues are container that operate on a FIFO (First In First Out) basis, where a new element is added at one back (end) of the queue and an element is deleted from the front.

Operations of queue and their time and space complexities are:

Vector

Vectors are similar to dynamic arrays in that they may resize themselves dynamically when an element is added or removed, and their storage is handled automatically by the container. Vector items are stored in contiguous storage so that iterators may access and traverse them.

Operations of queue and their time and space complexities are:

Here N is the number of elements inserted in the vector.

List

Lists are sequence containers that enable for the allocation of non-contiguous memory. List traversal is slower than vector traversal, but if a point is discovered, insertion and deletion are rapid.

Operations of lists and their time and space complexities are:

Here N is the number of elements inserted in the list.

Read More - Time Complexity of Sorting Algorithms

Priority Queue

Priority queue is an abstract data type for holding a collection of prioritized elements that allows for the insertion and deletion of components based on their priorities; for example, the element with the highest priority can be deleted at any moment. We can implement both max heap-based priority queue and min heap-based priority queue.

Operations of Priority Queue and their time and space complexities are:

Here N is the number of elements inserted in the priority queue.

Map

Maps are associative containers for storing items in a mapped manner. Each element has a mapped value and a key value. The key values of the two mapped values cannot be the same.

In C++ Stl, maps are of two types based on their implementation

Map

It is implemented using binary search trees ( Typically Red-Black Trees ). It keeps elements in sorted order.

Time and space complexity of its operations are:

Here N is the number of elements inserted in the map.

Unordered Map

It is implemented using hashing.It is formed by combination of  Key-value pair and hashed/mapped value.

Time and space complexity of its operations are:

Here N is the number of elements inserted in the unordered map.

You can practice by yourself with the help of Online C++ Compiler for better understanding.

Set

The C++ STL includes sets. Sets are containers that hold distinct components in a predefined sequence.

Set

It is implemented using binary search tress ( Typically Red Black Trees ). It keeps elements in sorted order.

Time and space complexity of its operations are:

Here N is the number of elements inserted in the set.

Unordered Set

It is implimented using hashing.It is formed by combination of  Key-value pair and hashed/mapped value.

Time and space complexity of its operations are:

Here N is the number of elements inserted in the unordered set.

Check out this problem - Queue Implementation

Frequently Asked Questions

How is stack implemented in STL C++?

Stack is built in C++ STL utilizing deque and hides much of its functionality to give a simpler interface for the stack's LIFO structure.

How is queue implemented in STL C++?

The queue is built in C++ STL utilizing deque and hides much of its functionality to give a simpler interface for the stack's FIFO structure.

What is Heap?

A Heap is a tree-based data structure in which the tree is an entire binary tree. Heaps are classified into two types:
Max-Heap: In a Max-Heap, the key at the parent node must be greater than the keys at all of its descendants.
Min-Heap: In a Min-Heap, the key at the parent node must be the smallest of all the keys at all of its descendants.

Conclusion

In this article, we have extensively discussed the Time and space complexity of STL containers.

We hope that this blog has helped you enhance your knowledge regarding the Time and space complexity of STL containers and if you want to practice top problems, visit our practice platform Code360. You can learn about Priority Queue using C++ and Difference between Queue and Deque in C++.

Do upvote our blog to help other ninjas grow. Happy Coding!