Sagar Medtiya
Sagar Medtiya

Follow

Sagar Medtiya

Follow
🚀C++ Standard Template Library

🚀C++ Standard Template Library

Sagar Medtiya's photo
Sagar Medtiya
·Dec 20, 2022·

13 min read

Play this article

Table of contents

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:

  1. begin() - Returns an iterator pointing to the first element in the vector

  2. end() - Returns an iterator pointing to the theoretical element that follows the last element in the vector.

  3. size() - Returns the number of elements in the vector.

  4. empty() - Returns whether the container is empty.

  5. max_size() – Returns the maximum number of elements that the vector can hold.

  6. front() – Returns a reference to the first element in the vector

  7. back() – Returns a reference to the last element in the vector

  8. push_back() – It pushes the elements into a vector from the back

  9. pop_back() – It is used to pop or remove elements from a vector from the back.

  10. insert() – It inserts new elements before the element at the specified position

  11. erase() – It is used to remove elements from a container from the specified position or range.

  12. 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:

  1. push_front(): Insert an element at the beginning of the list.

  2. push_back(): Insert an element at the end of the list.

  3. pop_front(): Delete the element at the beginning of the list.

  4. pop_back(): Delete the element at the end of the list.

  5. insert(iterator, val): Insert an element at the specified position.

  6. 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:

  1. size(): It returns the number of elements in the container.

  2. at(): It is used to reference the element present at the position given as the parameter to the function.

  3. front(): It is used to refer to the first element.

  4. back(): It is used to refer to the first element.

  5. push_front: It is used to push elements into a deque from the front.

  6. push_back: It is used to push elements into a deque from the back.

  7. pop_front(): It is used to pop elements from the front.

  8. pop_back(): It is used to pop elements from the back.

  9. 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:

  1. push(x): adds the element at the end of the queue.

  2. pop(): deletes the first element of the queue.

  3. front( ): returns a reference to the first element of the queue.

  4. back(): returns a reference to the last element of the queue.

  5. empty(): returns true when the queue is empty.

  6. 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:

  1. empty(): returns true if the queue is empty.

  2. size(): returns the size of the queue.

  3. top(): returns the reference to the topmost element of the queue.

  4. pop(): deletes the first element of the queue.

  5. 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:

  1. empty(): returns whether the stack is empty.

  2. size(): returns the size of the stack.

  3. top(): returns a reference to the topmost element of the stack.

  4. push(x): adds the element 'x' at the top of the stack.

  5. 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:

  1. begin(): returns an iterator to the first element in the set.

  2. end(): returns an iterator to the last element in the set.

  3. size(): returns the number of elements in the set.

  4. empty(): returns whether the set is empty.

  5. insert(x): adds a new element 'x' to the set.

  6. iterator insert(iterator position, x): adds a new element 'x' at the position pointed by the iterator.

  7. erase(x): removes the value 'x' from the set.

  8. 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:

  1. insert(): Insert elements with a particular key in the map container.

  2. erase(): used to erase elements from the container.

  3. find(): returns an iterator to the element with key-value 'x' in the map if found, else returns the iterator to end.

  4. max_size(): returns the maximum number of elements a map container can hold.

  5. size(): returns the number of elements in the map.

  6. empty(): returns whether the map is empty.

  7. 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.

  8. 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:

  1. begin(): returns an iterator to the first element in the set.

  2. end(): returns an iterator that follows the last element in the multiset.

  3. size(): returns the number of elements in the set.

  4. empty(): returns true when the set is empty.

  5. insert(x): Inserts the element x in the multiset.

  6. clear(): removes all the elements from the multiset.

  7. erase(x) – removes all the occurrences of x.

  8. 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:

  1. begin(): returns an iterator to the first element in the multimap.

  2. end(): returns an iterator that follows the last element in the multimap.

  3. size(): returns the number of elements in the map.

  4. empty(): returns whether the map is empty.

  5. pair<int,int> insert(keyvalue,multimapvalue): adds a new element to the multimap.

  6. 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:

  1. insert(): inserts a new {element} in the unordered_set container.

  2. begin(): returns an iterator pointing to the first element in the unordered_set container.

  3. end(): returns an iterator pointing to the past-the-end-element.

  4. count(): counts occurrences of a particular element in an unordered_set container.

  5. find(): search for an element in the container.

  6. clear(): removes all of the elements from an unordered_set and empties it.

  7. erase(): remove either a single element or a range of elements ranging from the start(inclusive) to the end(exclusive).

  8. 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:

  1. at(): it returns the reference to the value with the element as key k.

  2. begin(): returns an iterator pointing to the first element in the container in the unordered_map container.

  3. end(): returns an iterator pointing to the position past the last element in the container in the unordered_map container.

  4. equal_range: return the bounds of a range that includes all the elements in the container with a key that compares equal to k

  5. find(): returns an iterator to the element.

  6. empty()- checks whether the container is empty in the unordered_map container.

  7. 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:

  1. swap(): swaps the contents of one pair object with the contents of another pair object.

  2. 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:

  1. begin(): This function is used to return the beginning position of the container.

  2. end(): This function is used to return the after-end position of the container.

  3. advance(): This function is used to increment the iterator position till the specified number mentioned in its arguments.

  4. next(): This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.

  5. prev(): This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.

🍁References

  1. Geeks For Geeks

  2. Leetcode

Did you find this article valuable?

Support Sagar Medtiya by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this