The standard template library(STL) provides common data structures and functions such as lists, stacks, queues, vectors, maps, etc.
STL has four components:
Algorithms
Containers
Functions
Iterators
In this blog, we will only discuss containers and Iterators.
Containers stores data and objects. Containers are further classified into four categories
Sequence Containers
Container Adaptors
Associative Containers
Unordered Associative Containers
🍁Sequence Containers
Sequence containers implement data structures that can be accessed sequentially.
Vector
List
Deque
🍀Vector
Vectors are dynamic arrays with the ability to resize themselves automatically when the element is inserted or deleted, with their storage being handled automatically by the container. Vectors elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes the array may need to be extended. Removing the last element takes only constant time because no resizing happens.
Time Complexity: O(1) for push and pop operation.
Syntax: vector<data_type> var_name
Functions:
begin() - Returns an iterator pointing to the first element in the vector
end() - Returns an iterator pointing to the theoretical element that follows the last element in the vector.
size() - Returns the number of elements in the vector.
empty() - Returns whether the container is empty.
max_size() – Returns the maximum number of elements that the vector can hold.
front() – Returns a reference to the first element in the vector
back() – Returns a reference to the last element in the vector
push_back() – It pushes the elements into a vector from the back
pop_back() – It is used to pop or remove elements from a vector from the back.
insert() – It inserts new elements before the element at the specified position
erase() – It is used to remove elements from a container from the specified position or range.
swap() – It is used to swap the contents of one vector with another vector of the same type. Sizes may differ.
🍀List
Lists are sequence containers that allow non-contiguous memory allocation. As compared to the vector, the list has slow traversal, but once a position has been found, insertion and deletion are quick. when we say a list, Normally, we talk about the doubly linked list. For implementing a singly linked list, we use a forward list.
Time Complexity: O(1) for push and pop operation.
Syntax: list<data_type> var_name
Functions:
push_front(): Insert an element at the beginning of the list.
push_back(): Insert an element at the end of the list.
pop_front(): Delete the element at the beginning of the list.
pop_back(): Delete the element at the end of the list.
insert(iterator, val): Insert an element at the specified position.
erase(iterator): Delete an element from a specified position.
🍀Deque
Double-ended queues are sequence containers with the feature of expansion and contraction on both ends. They are similar to vectors but are more efficient in the case of insertion and deletion of elements. Unlike vectors, contiguous storage allocation may not be guaranteed.
Double Ended Queues are an implementation of the data structure double-ended queue. A queue data structure allows insertion only at the end and deletion from the front. This is like a queue in real life, wherein people are removed from the front and added at the back. Double-ended queues are a special case of queues where insertion and deletion operations are possible at both ends.
Time Complexity: O(1 ) - Accessing the elements
O(N) - Insertion or removal of elements
O(1) - Insertion or removal of elements at the start or end
Syntax: deque<data_type> var_name
Functions:
size(): It returns the number of elements in the container.
at(): It is used to reference the element present at the position given as the parameter to the function.
front(): It is used to refer to the first element.
back(): It is used to refer to the first element.
push_front: It is used to push elements into a deque from the front.
push_back: It is used to push elements into a deque from the back.
pop_front(): It is used to pop elements from the front.
pop_back(): It is used to pop elements from the back.
insert(): inserts an element and returns an iterator that points to the first of the new element.
🍁Container Adaptors
It provides a different interface for the sequential container.
Queue
Priority Queue
Stack
🍀Queue
The queue is a type of container adaptor that operates in a First In First Out(FIFO) type of arrangement. Elements are inserted at the back(end) and deleted from the front. Queues use an encapsulated object deque and list as an underlying container, providing a specific set of member functions to access its element. It is implemented using a linked list.
Time Complexity: O(1) for all the operations.
Syntax: queue<data_type> var_name
Functions:
push(x): adds the element at the end of the queue.
pop(): deletes the first element of the queue.
front( ): returns a reference to the first element of the queue.
back(): returns a reference to the last element of the queue.
empty(): returns true when the queue is empty.
size(): returns the size of the queue.
🍀Priority Queue
Priority queues are a type of container adapter, specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue and elements are in non-increasing order (hence we can see that each element of the queue has a priority{fixed order}). However in C++ STL, by default, the top element is always the greatest element. We can also change it to the smallest element at the top. Priority queues are built on the top of the max heap and use an array or vector as an internal structure.
Time Complexity: O(log n) - push and pop operation
O(1) - top and empty check operation
Syntax: priority_queue<data_type> var_name
Functions:
empty(): returns true if the queue is empty.
size(): returns the size of the queue.
top(): returns the reference to the topmost element of the queue.
pop(): deletes the first element of the queue.
push(): adds the element at the end of the queue.
🍀Stack
stacks are a type of container adaptor with a Last-In-First-Out(LIFO) type of work, where a new element is added at one end(top) and an element is removed from the end only. Stack uses an encapsulated object of either vector or deque or list as its underlying container, providing a specific set of member functions to access its element.
Syntax: stack<data_type> var_name
Time Complexity: O(1) for all the operations.
Functions:
empty(): returns whether the stack is empty.
size(): returns the size of the stack.
top(): returns a reference to the topmost element of the stack.
push(x): adds the element 'x' at the top of the stack.
pop(): deletes the topmost element of the stack.
🍁Associative Containers
It implements a sorted data structure that can be easily searched.
🍀Set
Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. The values are stored in a specific sorted order i.e either ascending or descending.
Syntax: set<data_type> var_name
Note: set<data_type, greater<data_type>> var_name; is used for storing values in a set in descending order.
Time Complexity: O(log N) for insertion and deletion of the element.
Functions:
begin(): returns an iterator to the first element in the set.
end(): returns an iterator to the last element in the set.
size(): returns the number of elements in the set.
empty(): returns whether the set is empty.
insert(x): adds a new element 'x' to the set.
iterator insert(iterator position, x): adds a new element 'x' at the position pointed by the iterator.
erase(x): removes the value 'x' from the set.
erase(iterator_position): removes the element at the position pointed by the iterator.
🍀Map
Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values.
Syntax: map<data_type1, data_type2> var_name
Time Complexity: O(log N) for insertion and deletion.
Functions:
insert(): Insert elements with a particular key in the map container.
erase(): used to erase elements from the container.
find(): returns an iterator to the element with key-value 'x' in the map if found, else returns the iterator to end.
max_size(): returns the maximum number of elements a map container can hold.
size(): returns the number of elements in the map.
empty(): returns whether the map is empty.
begin() and end(): begin() returns an iterator to the first element in the map. end() returns an iterator to the theoretical element that follows the last element in the map.
at() and swap(): at() is used to return the reference to the element associated with the key k. swap() is used to exchange the contents of two maps but the maps must be of the same type although sizes may differ.
🍀Multiset
Multisets are a type of associative container similar to the set, with the exception that multiple elements can have the same values.
Syntax: multiset<data_type1, data_type2> var_name
Time Complexity: O(1): for begin(), end(), size() and empty() method.
O(log N): for insert() and erase() method.
O(N): for clear() method.
Functions:
begin(): returns an iterator to the first element in the set.
end(): returns an iterator that follows the last element in the multiset.
size(): returns the number of elements in the set.
empty(): returns true when the set is empty.
insert(x): Inserts the element x in the multiset.
clear(): removes all the elements from the multiset.
erase(x) – removes all the occurrences of x.
iterator insert (iterator position, const x): adds a new element ‘x’ at the position pointed by the iterator.
🍀Multimap
Multimap is similar to a map with the addition that multiple elements can have the same keys. Also, it is NOT required that the key value and mapped value pair have to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always. These properties of multimap make it very much useful in competitive programming.
Syntax: multimap<data_type1, data_type2> var_name
Time Complexity: same as a multiset.
Functions:
begin(): returns an iterator to the first element in the multimap.
end(): returns an iterator that follows the last element in the multimap.
size(): returns the number of elements in the map.
empty(): returns whether the map is empty.
pair<int,int> insert(keyvalue,multimapvalue): adds a new element to the multimap.
erase(): removes the key value from the map.
🍁Unordered Associative Containers:
It implement unordered data structures that can be quickly searched.
🍀Unordered Set
An unordered_set is implemented using a hash table where keys are hashed into indices of a hash table so that the insertion is always randomized. All operations on the unordered_set take constant time O(1) on average which can go up to linear time O(n) in the worst case which depends on the internally used hash function, but practically they perform very well and generally provide a constant time lookup operation.
The unordered_set can contain a key of any type- predefined or user-defined data structure but when we define the keys of the type user define the type, we need to specify our comparison function according to which keys will be compared.
Sets vs Unordered Sets
Set is an ordered sequence of unique keys whereas unordered_set is a set in which a key can be stored in any order, so unordered. Set is implemented as a balanced tree structure which is why it is possible to maintain order between the elements (by specific tree traversal). The time complexity of set operations is O(log n) while for unordered_set, it is O(1).
Syntax: unordered_set <data_type> var_name
Functions:
insert(): inserts a new {element} in the unordered_set container.
begin(): returns an iterator pointing to the first element in the unordered_set container.
end(): returns an iterator pointing to the past-the-end-element.
count(): counts occurrences of a particular element in an unordered_set container.
find(): search for an element in the container.
clear(): removes all of the elements from an unordered_set and empties it.
erase(): remove either a single element or a range of elements ranging from the start(inclusive) to the end(exclusive).
size(): returns the number of elements in the unordered_set container.
🍀Unordered Map
unordered_map is an associated container that stores elements formed by the combination of a key value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined. In simple terms, an unordered_map is like a data structure of dictionary type that stores elements in itself. It contains successive pairs(key, value), which allows fast retrieval of an individual element based on its unique key.
Internally unordered_map is implemented using Hash Table, the key provided to map is hashed into indices of a hash table which is why the performance of data structure depends on the hash function a lot but on average, the cost of search, insert, and delete from the hash table is O(1).
Syntax: unordered_map<data_type1, data_type2> var_name
Functions:
at(): it returns the reference to the value with the element as key k.
begin(): returns an iterator pointing to the first element in the container in the unordered_map container.
end(): returns an iterator pointing to the position past the last element in the container in the unordered_map container.
equal_range: return the bounds of a range that includes all the elements in the container with a key that compares equal to k
find(): returns an iterator to the element.
empty()- checks whether the container is empty in the unordered_map container.
erase(): elements in the container in the unordered_map container
🍁Pair
Pair is used to combine two values that may be of different data types. Pair provides a way to store two heterogeneous objects as a single unit. It is basically used if we want to store tuples. The pair container is a simple container defined in <utility> header consisting of two data elements or objects.
The first element is referenced as 'first' and the element as ' second' and the order is fixed.
Pair can be assigned, copied, and compared. The array of objects allocated in a map or hash_map is of type 'pair; by default in which all the 'first' elements are unique keys associated with the 'second' value objects.
To access the elements, we use a variable name followed by the keyboard first or
Syntax: pair (data_type1, data_type2) Pair_name (value1, value2)
Different ways to initialize pair:
pair g1; //default
pair g2(1, 'a'); //initialized, different data type
pair g3(1, 10); //initialized, same data type
pair g4(g3); //copy of g3
Another way to initialize a pair is by using the make_pair() function.
g2 = make_pair(1, 'a');
Functions:
swap(): swaps the contents of one pair object with the contents of another pair object.
make_pair(): It allows the creation of a value pair without writing the types explicitly.
🍁Iterators
Iterators are used to point at the memory addresses of STL containers. They are primarily used in sequences of numbers, characters etc. They reduce the complexity and execution time of the program.
Functions:
begin(): This function is used to return the beginning position of the container.
end(): This function is used to return the after-end position of the container.
advance(): This function is used to increment the iterator position till the specified number mentioned in its arguments.
next(): This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.
prev(): This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.