STL, or Standard Template Library, is a powerful library in C++ that helps with working on data structures. It comes with a collection of pre-made tools like algorithms, containers, and iterators that can be easily used in your programs.
The main goal of STL is to provide a flexible and efficient way to handle data structures and algorithms. It does this by giving you ready-made tools with clear rules and templates for implementing them. This means you can use these tools with different types of data without worrying about performance issues.
STL is divided into four main parts: algorithms, containers, functions and iterators. Algorithms are functions that perform common tasks like sorting, searching, and manipulating collections of items. Containers are data structures like vectors, lists, sets, maps, and queues that can hold and manage elements efficiently. Iterators act as helpers that let you go through the elements in a container and modify them.
In simpler terms, STL is a useful library in C++ that provides tools for working with data structures. It helps you save time and write efficient code by giving you pre-made functions and data structures that you can use in your programs.
A header file that contains all standard functions, alogrithms and containers is :
#include <bits/stdc++.h>
Part 1: Containers.
STL containers
STL containers are pre-defined data structures in C++ that offer efficient ways to store and manage elements. Examples include vectors, lists, sets, maps, and queues. They provide ready-to-use implementations for common operations and can be easily integrated into your programs for effective data management.
Popular STL containers:
Pair: The pair STL is a powerful tool in C++ that allows you to combine two values of different types into a single entity. It is commonly used when you need to associate two related pieces of information.
#include<iostream> #include<utility> using namespace std; int main() { pair<string, int> person; person.first = "John"; person.second = 25; cout << "Name: " << person.first << endl; cout << "Age: " << person.second << endl; return 0; }Vectors: The vector STL is a versatile and dynamic data structure in C++ that provides a resizable array-like container. It allows you to store and manipulate a collection of elements in a sequential manner.
Please check out my blog about vectors in C++ by clicking here.
There are various ways to declare a vector. they include:
v(5, 100): This syntax creates a vector named v with an initial size of 5 elements, where each element is initialized to the value 100. In other words, it creates a vector containing five elements, all set to the value of 100.
v(5): This syntax creates a vector named v with an initial size of 5 elements, but without specifying any specific initial values. The elements are default-initialized according to their type. For example, if the vector is of type int, the elements will be initialized to 0.
v(): This syntax creates an empty vector named v with no initial elements. It is essentially a vector declaration without specifying any initial size or values. This can be useful when you plan to dynamically add elements to the vector later based on your program's requirements.
The values stored in the vector can be accessed in 2 ways
accessing value directly:
#include <iostream> #include <vector> using namespace std; int main() { vector<int> numbers = {1, 2, 3, 4, 5}; for (auto it : numbers) cout << it << " "; return 0; }accessing via iterator:
#include <iostream> #include <vector> using namespace std; int main() { vector<int> numbers = {1, 2, 3, 4, 5}; for (auto it = numbers.begin(); it != numbers.end(); ++it) cout << *it << " "; return 0; }
Lists: A list is a doubly-linked list data structure in C++. It is a container that allows efficient insertion and removal of elements at both ends and in the middle of the list. Each element in the list is stored along with pointers to the previous and next elements.
Technically, a list is implemented as a sequence of nodes, where each node contains the element value and two pointers: one pointing to the previous node and another pointing to the next node. This linked structure enables efficient insertion and deletion operations compared to other container types.
The list STL provides a range of operations to manipulate the elements in the list. You can easily add elements at the beginning or end of the list, insert elements at any position, remove elements, and traverse the list using iterators.
To use the list STL, you need to include the <list> header.
#include <iostream> #include <list> using namespace std; int main() { list<int> numbers; numbers.push_back(10); numbers.push_front(5); list<int>::iterator it = numbers.begin(); ++it; numbers.insert(it, 7); numbers.pop_back(); for (auto it = numbers.begin(); it != numbers.end(); ++it) cout << *it << " "; cout << endl; return 0; }push_back() function is used to add an element to the end of the list, push_front() to add an element to the beginning,
insert() to insert an element at a specific position.
The pop_back() function removes the last element from the list.
Lists offer a better time complexity over vectors when it comes to manipulating data from between.
Stack: Kindly visit my blog post about stack data structure by clicking here.
Queue: A queue is a First-In-First-Out (FIFO) data structure in C++. It is a container that allows elements to be inserted at one end and removed from the other end. The element that is inserted first will be the first one to be removed.
Technically, a queue is implemented as a container adapter, which means it uses an underlying container (such as a deque or a list) to store the elements. The queue provides operations like enqueue (to insert elements) and dequeue (to remove elements) with specific rules that maintain the FIFO order.
The queue STL provides a range of operations to manipulate the elements in the queue. You can easily add elements to the back of the queue, remove elements from the front, and access the front and back elements.
To use the queue STL, you need to include the <queue> header.
#include <iostream> #include <queue> using namespace std; int main() { queue<int> numbers; numbers.push(10); numbers.push(20); numbers.push(30); cout << "Front of the queue: " << numbers.front() << endl; cout << "Back of the queue: " << numbers.back() << endl; numbers.pop(); cout << "Front of the queue after pop: " << numbers.front() << endl; return 0; }A Priority queue(std::priority_queue<int> numbers) is a container that stores elements based on their priority. Elements with higher priority are placed at the front and have precedence over elements with lower priority. It uses a binary heap as its underlying data structure to efficiently retrieve the highest priority element. Priority queues are commonly used in situations where elements need to be processed in a specific order, such as task scheduling or event handling. By default, the priority queue orders elements in descending order(max heap), but the order can be customized using comparison functions or operator overloading.
Ascending order can also be achieved by the following syntax:
priority_queue<int, vector<int>, greater<int>> numbers;This order is also referred to as "min heap". Since this works on the principle of binary heap, the push/pop functions have a time complexity of O(log n) as compared to a normal queue, for which the push/pop functions have a time complexity of O(1).
Sets: A set is a container from the Standard Template Library that stores unique elements in a specific order. It is implemented using a balanced binary search tree, which allows for efficient insertion, deletion, and search operations.
Sets maintain a sorted order of elements, which means that elements are automatically arranged in ascending order. The uniqueness property ensures that each element appears only once in the set.
Basically, the main thing to remember about sets is that they store data in a sorted order and all elements are unique.
A multiset is a container that allows duplicate elements and maintains them in sorted order. Insertion, deletion, and search operations have a time complexity of O(log n) since they involve traversing the binary search tree.
An unordered set is a container that stores unique elements in no particular order. It is implemented using a hash table, which offers constant-time insertion, deletion, and search operations on average. The elements in an unordered set are not sorted but are unique. The lower_bound() and upper_bound() functions don't work with an unordered set.
#include <iostream> #include <set> #include <unordered_set> using namespace std; int main() { // Set set<int> mySet; mySet.insert(30); mySet.insert(10); mySet.insert(20); mySet.insert(10); // Duplicates are ignored for (auto it : mySet) cout << it << " "; cout << endl; // Multiset multiset<int> myMultiset; myMultiset.insert(30); myMultiset.insert(10); myMultiset.insert(20); myMultiset.insert(10); // Duplicates are allowed for (auto it : myMultiset) cout << it << " "; cout << endl; // Unordered Set unordered_set<int> myUnorderedSet; myUnorderedSet.insert(30); myUnorderedSet.insert(10); myUnorderedSet.insert(20); myUnorderedSet.insert(10); // Duplicates are ignored for (auto it : myUnorderedSet) cout << it << " "; cout << endl; return 0; }Output:
10 20 30 10 10 20 30 20 10 30
Maps: Maps is an associative container that stores elements in key-value pairs. It allows efficient lookup, insertion, and deletion of elements based on their keys. Each key in a map is unique, and the elements are automatically sorted by their keys in ascending order.
map<int,int> mpp;
First int will be key while the second int will be value. the keys are unique and are stored in a sorted order(ascending order by default). Every value gets associated with a unique key. The time complexity of maps is O(log n).
The multimap container is an associative container that allows multiple elements with the same key. It is similar to the map container but differs in that it permits duplicate keys. Each element in a multimap consists of a key-value pair, where the keys are used for ordering the elements, and the values are associated with those keys.
the unordered_map container in C++ provides a hash-based implementation for storing key-value pairs. It offers fast lookup, insertion, and deletion operations with an average constant time complexity. Unlike multimap, unordered_map does not order elements based on keys but instead relies on a hash function to map keys to unique indices. This makes it suitable for scenarios where the order of elements is not important, but fast access to values is desired.
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
int main() {
// Map
map<int, string> myMap;
myMap[1] = "Alice";
myMap[2] = "Bob";
myMap[3] = "Charlie";
for (auto it : myMap)
cout << it.first << ": " << it.second << endl;
// Multimap
multimap<int, string> myMultimap;
myMultimap.insert({1, "Alice"});
myMultimap.insert({2, "Bob"});
myMultimap.insert({3, "Charlie"});
myMultimap.insert({3, "David"});
for (auto it : myMultimap)
cout << it.first << ": " << it.second << endl;
// Unordered Map
unordered_map<int, string> myUnorderedMap;
myUnorderedMap[1] = "Alice";
myUnorderedMap[2] = "Bob";
myUnorderedMap[3] = "Charlie";
for (auto it : myUnorderedMap)
cout << it.first << ": " << it.second << endl;
return 0;
}
Output:
1: Alice
2: Bob
3: Charlie
1: Alice
2: Bob
3: Charlie
3: David
3: Charlie
2: Bob
1: Alice
Thank you :)