Analysis of time and space complexity of C++ STL containers
Characteristics of C++ STL:
- C++ has a low execution time as compared to other programming languages.
- This makes STL in C++ advantageous and powerful.
- The thing that makes STL powerful is that it contains a vast variety of classes that are implementations of popular and standard algorithms and predefined classes with functions that makes them well-optimized while doing competitive programming or problem-solving questions.
Analysis of functions in STL:
- The major thing required while using the STL is the analysis of STL.
- Analysis of the problem can’t be done without knowing the complexity analysis of the STL class used in the problem.
- Implementation and complexity analysis of STL is required to answer the asked interview questions.
Below is the analysis of some STL Containers:
Priority Queue is used in many popular algorithms . Priority Queue is the implementation of Max Heap by default. Priority Queue does even optimize some major operations.
Syntax:
priority_queue<data_type> Q
The Min Heap can also be implemented by using the following syntax.
Syntax:
priority_queue<data_type, vector<data_type>, greater<data_type>> Q
The table containing the time and space complexity with different functions given below:
Function | Time Complexity | Space Complexity |
Q.top() |
O(1) |
O(1) |
Q.push() |
O(log n) |
O(1) |
Q.pop() |
O(log n) |
O(1) |
Q.empty() |
O(1) |
O(1) |
Below is the C++ program illustrating the priority queue:
C++
// C++ program illustrating the // priority queue #include <bits/stdc++.h> using namespace std; // Function illustrating the // priority queue void priorityQueue() { int Array[5] = { 1, 2, 3, 4, 5 }; // Max heap int i; priority_queue< int > Q; for (i = 0; i < 5; i++) { // Pushes array elements to // priority queue and rearranges // to form max heap; Q.push(Array[i]); } // Maximum element in the priority // queue. cout << "The maximum element is " << Q.top() << endl; i = 1; while (Q.empty() != 1) { int peek = Q.top(); cout << "The " << i++ << " th max element is " << peek << endl; // Pops the maximum element // out of priority queue Q.pop(); } cout << " Is priority queue " << "Q empty() ?" << endl << "check -->" << endl; // Checks whether priority // queue is empty if (Q.empty() == 1) cout << "The priority queue" << " is empty" << endl; else cout << "The priority queue" << " is not empty." << endl; } // Driver Code int main() { // Function Call priorityQueue(); return 0; } |
The maximum element is 5 The 1 th max element is 5 The 2 th max element is 4 The 3 th max element is 3 The 4 th max element is 2 The 5 th max element is 1 Is priority queue Q empty() ? check --> The priority queue is empty
Map:
It is the famous class of STL that stores the values in the pattern of key-value pair.
Syntax:
map<data_type, data_type> M
- The map <int, int> M is the implementation of self-balancing Red-Black Trees.
- The unordered_map<int, int> M is the implementation of Hash Table which makes
the complexity of operations like insert, delete and search to Theta(1). - The multimap<int, int> M is the implementation of Red-Black Trees which are self-balancing trees making the cost of operations the same as the map.
- The unordered_multimap<int, int> M is the implemented same as the unordered map is implemented which is the Hash Table.
- The only difference is it keeps track of one more variable which keeps track of the count of occurrences.
- The pairs are inserted into the map using pair<int, int>(x, y) and can be accessed using the map iterator.first and map iterator.second.
- The map by default keeps sorted based on keys and in the case of the unordered map, it can be in any order.
The table containing the time and space complexity with different functions given below(n is the size of the map):
Function | Time Complexity | Space Complexity |
M.find(x) |
O(log n) |
O(1) |
M.insert(pair<int, int> (x, y) |
O(log n) |
O(1) |
M.erase(x) |
O(log n) |
O(1) |
M.empty( ) |
O(1) |
O(1) |
M.clear( ) |
Theta(n) |
O(1) |
M.size( ) |
O(1) |
O(1) |
Below is the C++ program illustrating map:
C++
// C++ program illustrating the map #include <bits/stdc++.h> using namespace std; // Function illustrating the map void Map() { int i; // Declaring maps map< int , int > M; unordered_map< int , int > UM; multimap< int , int > MM; unordered_multimap< int , int > UMM; // Inserting pairs of key // and value for (i = 101; i <= 105; i++) { // Inserted the Key and // value twice M.insert( pair< int , int >(i - 100, i)); UM.insert( pair< int , int >(i - 100, i)); M.insert( pair< int , int >(i - 100, i)); UM.insert( pair< int , int >(i - 100, i)); } for (i = 101; i <= 105; i++) { // Inserted the key and // value twice MM.insert( pair< int , int >(i - 100, i)); UMM.insert( pair< int , int >(i - 100, i)); MM.insert( pair< int , int >(i - 100, i)); UMM.insert( pair< int , int >(i - 100, i)); } // Iterators for accessing map< int , int >::iterator Mitr; unordered_map< int , int >::iterator UMitr; multimap< int , int >::iterator MMitr; unordered_multimap< int , int >::iterator UMMitr; // Output cout << "In map" << endl; cout << "Key" << " " << "Value" << endl; for (Mitr = M.begin(); Mitr != M.end(); Mitr++) { cout << Mitr->first << " " << Mitr->second << endl; } // Unsorted and is unordered output cout << "In unordered_map" << endl; cout << "Key" << " " << "Value" << endl; for (UMitr = UM.begin(); UMitr != UM.end(); UMitr++) { cout << UMitr->first << " " << UMitr->second << endl; } // Sorted output cout << "In multimap" << endl; cout << "Key" << " " << "Value" << endl; for (MMitr = MM.begin(); MMitr != MM.end(); MMitr++) { cout << MMitr->first << " " << MMitr->second << endl; } // Unsorted and is unordered // output cout << "In unordered_multimap" << endl; cout << "Key" << " " << "Value" << endl; for (UMMitr = UMM.begin(); UMMitr != UMM.end(); UMMitr++) { cout << UMMitr->first << " " << UMMitr->second << endl; } cout << "The erase() function" << " erases respective key:" << endl; M.erase(1); cout << "Key" << " " << "Value" << endl; for (Mitr = M.begin(); Mitr != M.end(); Mitr++) { cout << Mitr->first << " " << Mitr->second << endl; } cout << "The find() function" << " finds the respective key:" << endl; if (M.find(1) != M.end()) { cout << "Found!" << endl; } else { cout << "Not Found!" << endl; } cout << "The clear() function " << "clears the map:" << endl; M.clear(); // Returns the size of the map cout << "Now the size is :" << M.size(); } // Driver Code int main() { // Function Call Map(); return 0; } |
In map Key Value 1 101 2 102 3 103 4 104 5 105 In unordered_map Key Value 5 105 4 104 3 103 2 102 1 101 In multimap Key Value 1 101 1 101 2 102 2 102 3 103 3 103 4 104 4 104 5 105 5 105 In unordered_multimap Key Value 5 105 5 105 4 104 4 104 3 103 3 103 2 102 2 102 1 101 1 101 The erase() function erases respective key: Key Value 2 102 3 103 4 104 5 105 The find() function finds the respective key: Not Found! The clear() function clears the map: Now the size is :0
Explanation:
- m.begin(): points the iterator to starting element.
- m.end(): points the iterator to the element after the last which is theoretical.
Set:
- The first useful property of the set is that it contains only distinct elements of course the variation multiset can even contain repeated elements.
- Set contains the distinct elements in an ordered manner whereas unordered set contains distinct elements in an unsorted order and multimaps contain repeated elements.
Syntax:
set<data_type> S
- Set (set<int> s) is the implementation of Binary Search Trees.
- Unordered set (unordered_set<int> S) is the implementation of Hash Table.
- Multiset (multiset<int> S) is implementation of Red-Black trees.
- Unordered_multiset(unordered_multiset<int> S) is implemented the same as the unordered set but uses an extra variable that keeps track of the count.
- The complexity becomes Theta(1) and O(n) when using unordered<set> the ease of access becomes easier due to Hash Table implementation.
The table containing the time and space complexity with different functions given below(n is the size of the set):
Function | Time Complexity | Space Complexity |
s.find( ) |
O(log n) |
O(1) |
s.insert(x) |
O(log n) |
O(1) |
s.erase(x) |
O(log n) |
O(1) |
s.size() |
O(1) |
O(1) |
s.empty( ) |
O(1) |
O(1) |
Below is the C++ program illustrating set:
C++
// C++ program illustrating the set #include <bits/stdc++.h> using namespace std; // Function illustrating the set void Set() { // Set declaration set< int > s; unordered_set< int > us; multiset< int > ms; unordered_multiset< int > ums; int i; for (i = 1; i <= 5; i++) { // Inserting elements s.insert(2 * i + 1); us.insert(2 * i + 1); ms.insert(2 * i + 1); ums.insert(2 * i + 1); s.insert(2 * i + 1); us.insert(2 * i + 1); ms.insert(2 * i + 1); ums.insert(2 * i + 1); } // Iterator to access values // in set set< int >::iterator sitr; unordered_set< int >::iterator uitr; multiset< int >::iterator mitr; unordered_multiset< int >::iterator umitr; cout << "The difference: " << endl; cout << "The output for set " << endl; for (sitr = s.begin(); sitr != s.end(); sitr++) { cout << *sitr << " " ; } cout << endl; cout << "The output for " << "unordered set " << endl; for (uitr = us.begin(); uitr != us.end(); uitr++) { cout << *uitr << " " ; } cout << endl; cout << "The output for " << "multiset " << endl; for (mitr = ms.begin(); mitr != ms.end(); mitr++) { cout << *mitr << " " ; } cout << endl; cout << "The output for " << "unordered multiset " << endl; for (umitr = ums.begin(); umitr != ums.end(); umitr++) { cout << *umitr << " " ; } cout << endl; } // Driver Code int main() { // Function Call Set(); return 0; } |
The difference: The output for set 3 5 7 9 11 The output for unordered set 11 9 7 3 5 The output for multiset 3 3 5 5 7 7 9 9 11 11 The output for unordered multiset 11 11 9 9 3 3 5 5 7 7
It is a data structure that follows the Last In First Out (LIFO) rule, this class of STL is also
used in many algorithms during their implementations.
For e.g, many recursive solutions use a system stack to backtrack the pending calls of recursive functions the same can be implemented using the STL stack iteratively.
Syntax:
stack<data_type> A
- It is implemented using the linked list implementation of a stack.
Function | Time Complexity | Space Complexity |
s.top( ) |
O(1) |
O(1) |
s.pop( ) |
O(1) |
O(1) |
s.empty( ) |
O(1) |
O(1) |
s.push(x ) |
O(1) |
O(1) |
Below is the C++ program illustrating stack:
C++
// C++ program illustrating the stack #include <bits/stdc++.h> using namespace std; // Function illustrating stack void Stack() { stack< int > s; int i; for (i = 0; i <= 5; i++) { cout << "The pushed element" << " is " << i << endl; s.push(i); } // Points to top element of stack cout << "The top element of the" << " stack is: " << s.top() << endl; // Return size of stack cout << "The size of the stack" << " is: " << s.size() << endl; // Pops the elements of the // stack in the LIFO manner // Checks whether the stack // is empty or not while (s.empty() != 1) { cout << "The popped element" << " is " << s.top() << endl; s.pop(); } } // Driver Code int main() { // Function Call Stack(); return 0; } |
The pushed element is 0 The pushed element is 1 The pushed element is 2 The pushed element is 3 The pushed element is 4 The pushed element is 5 The top element of the stack is: 5 The size of the stack is: 6 The popped element is 5 The popped element is 4 The popped element is 3 The popped element is 2 The popped element is 1 The popped element is 0
It is a data structure that follows the First In First Out (FIFO) rule.
Syntax:
queue<data_type> Q
Table containing the time and space complexity with different functions given below:
Function | Time Complexity | Space Complexity |
q.push(x) |
O(1) |
O(1) |
q.pop( ) |
O(1) |
O(1) |
q.front( ) |
O(1) |
O(1) |
q.back( ) |
O(1) |
O(1) |
q.empty( ) |
O(1) |
O(1) |
q.size( ) |
O(1) |
O(1) |
Below is the C++ program illustrating queue:
C++
// C++ program illustrating the queue #include <bits/stdc++.h> using namespace std; // Function illustrating queue void Queue() { queue< int > q; int i; for (i = 101; i <= 105; i++) { // Inserts into the queue // in the FIFO manner q.push(i); cout << "The first and last" << " elements of the queue " << "are " << q.front() << " " << q.back() << endl; } // Check whether the queue is // empty or not while (q.empty() != 1) { // Pops the first element // of the queue cout << "The Element popped" << " following FIFO is " << q.front() << endl; q.pop(); } } // Driver Code int main() { // Function Call Queue(); return 0; } |
The first and last elements of the queue are 101 101 The first and last elements of the queue are 101 102 The first and last elements of the queue are 101 103 The first and last elements of the queue are 101 104 The first and last elements of the queue are 101 105 The Element popped following FIFO is 101 The Element popped following FIFO is 102 The Element popped following FIFO is 103 The Element popped following FIFO is 104 The Element popped following FIFO is 105
Vector:
Vector is the implementation of dynamic arrays and uses new for memory allocation in heap.
Syntax:
vector<int> A
2-dimensional vectors can also be implemented using the below syntax:
Syntax:
vector<vector<int>> A
The table containing the time and space complexity with different functions given below:
Function | Time Complexity | Space Complexity |
sort(v.begin( ), v.end( )) | Theta(nlog(n)) |
Theta(log n) |
reverse(v.begin( ), v.end( )) |
O(n) |
O(1) |
v.push_back(x) |
O(1) |
O(1) |
v.pop_back(x) |
O(1) |
O(1) |
v.size() |
O(1) |
O(1) |
v.clear() |
O(n) |
O(1) |
v.erase() |
O(n) |
O(1) |
Below is the C++ program illustrating vector:
C++
// C++ program illustrating vector #include <bits/stdc++.h> using namespace std; // Function displaying values void display(vector< int > v) { for ( int i = 0; i < v.size(); i++) { cout << v[i] << " " ; } } // Function illustrating vector void Vector() { int i; vector< int > v; for (i = 100; i < 106; i++) { // Inserts an element in vector v.push_back(i); } cout << "The vector after " << "push_back is :" << v.size() << endl; cout << "The vector now is :" ; display(v); cout << endl; // Deletes an element at the back v.pop_back(); cout << "The vector after " << "pop_back is :" << v.size() << endl; cout << "The vector now is :" ; display(v); cout << endl; // Reverses the vector reverse(v.begin(), v.end()); cout << "The vector after " << "reversing is :" << v.size() << endl; cout << "The vector now is :" ; display(v); cout << endl; // Sorts vector using Quick Sort sort(v.begin(), v.end()); cout << "The vector after " << "sorting is :" << v.size() << endl; cout << "The vector now is :" ; display(v); cout << endl; // Erases ith position element v.erase(v.begin() + 2); cout << "The size of vector " << "after erasing at position " "3 is :" << v.size() << endl; cout << "The vector now is :" ; display(v); cout << endl; // Deletes the vector completely v.clear(); cout << "The size of the vector" << " after clearing is :" << v.size() << endl; cout << "The vector now is :" ; display(v); cout << endl; } // Driver Code int main() { // Function Call Vector(); return 0; } |
The vector after push_back is :6 The vector now is :100 101 102 103 104 105 The vector after pop_back is :5 The vector now is :100 101 102 103 104 The vector after reversing is :5 The vector now is :104 103 102 101 100 The vector after sorting is :5 The vector now is :100 101 102 103 104 The size of vector after erasing at position 3 is :4 The vector now is :100 101 103 104 The size of the vector after clearing is :0 The vector now is :