Forward List and List of Unordered Maps in C++ with Examples
Forward List
Forward list in STL implements singly linked list. Introduced from C++11, forward lists are more useful than other containers in insertion, removal, and moving operations (like sort) and allow time constant insertion and removal of elements. It differs from the list by the fact that the forward list keeps track of the location of only the next element while the list keeps track of both the next and previous elements, thus increasing the storage space required to store each element. The drawback of a forward list is that it cannot be iterated backward and its individual elements cannot be accessed directly. Forward List is preferred over the list when only forward traversal is required (same as singly linked list is preferred over doubly linked list) as we can save space. Some example cases are, chaining in hashing, adjacency list representation of the graph, etc.
Functions used with forward list:
- push_front(x): Adds a new element ‘x’ at the beginning of the forward list.
- pop_front(): This function is used to delete the first element of the forward list.
List
Lists are sequence containers that allow non-contiguous memory allocation. As compared to vector, the list has slow traversal, but once a position has been found, insertion and deletion are quick. Normally, when we say a List, we talk about a doubly linked list. For implementing a singly linked list, we use a forward list.
Functions used with the list:
- front(): Returns the value of the first element in the list.
- back(): Returns the value of the last element in the list.
- push_front(x): Adds a new element ‘x’ at the beginning of the list.
- push_back(x): Adds a new element ‘x’ at the end of the list.
Unordered_Map
An Unordered map is an associated container that stores elements formed by the combination of 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. Internally, an unordered map is implemented using Hash Table.
Functions used with unordered map:
- at(): This function in C++ unordered_map 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
- size(): Returns the number of elements present inside the unordered map.
This article focuses on how we can use a forward list and a list of unordered maps in C++. vector of lists and forward lists can be quite useful while designing complex data structures.
Forward List of Unordered Maps
Below is the implementation using a forward list of unordered maps:
Example 1:
C++
// C++ program to implement // the above concept #include <bits/stdc++.h> using namespace std; // Function to print forward // list elements void print(forward_list<unordered_map< int , int > >& forwardList1) { cout << "Forward List : \n" ; for ( auto currentUnorderedMap : forwardList1) { // Each element of the forward_list // is a unordered map cout << "Unordered Map : " ; cout << "[ " ; // Print unordered map elements for ( auto it = currentUnorderedMap.begin(); it != currentUnorderedMap.end(); it++) { cout << "First : " << it->first << " , " << "Second : " << it->second << " " ; } cout << "]\n" ; } } // Driver code int main() { // Declaring a forward list of // unordered maps forward_list<unordered_map< int , int > > forwardList1; // Declaring a unordered map unordered_map< int , int > unorderedMap1; // Hashing values unorderedMap1[2] = 4; unorderedMap1[4] = 3; unorderedMap1[6] = 9; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap1); // Declaring another unordered map unordered_map< int , int > unorderedMap2; // Hashing values unorderedMap2[31] = 8; unorderedMap2[11] = 3; unorderedMap2[23] = 7; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap2); // Declaring another unordered map unordered_map< int , int > unorderedMap3; // Hashing values unorderedMap3[7] = 3; unorderedMap3[18] = 1; unorderedMap3[9] = 6; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap3); // Declaring another unordered map unordered_map< int , int > unorderedMap4; // Hashing values unorderedMap4[32] = 9; unorderedMap4[15] = 3; unorderedMap4[97] = 5; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap4); print(forwardList1); return 0; } |
Output:
Forward List :
Unordered Map : [ First : 97 , Second : 5 First : 32 , Second : 9 First : 15 , Second : 3 ]
Unordered Map : [ First : 9 , Second : 6 First : 7 , Second : 3 First : 18 , Second : 1 ]
Unordered Map : [ First : 23 , Second : 7 First : 31 , Second : 8 First : 11 , Second : 3 ]
Unordered Map : [ First : 6 , Second : 9 First : 2 , Second : 4 First : 4 , Second : 3 ]
Example 2:
C++
// C++ program to implement // the above concept #include <bits/stdc++.h> using namespace std; // Function to print forward // list elements void print(forward_list<unordered_map< int , string> >& forwardList1) { cout << "Forward List : \n" ; for ( auto currentUnorderedMap : forwardList1) { // Each element of the forward list is // a unordered map cout << "Unordered Map : " ; cout << "[ " ; // Print unordered map elements for ( auto it = currentUnorderedMap.begin(); it != currentUnorderedMap.end(); it++) { cout << "First : " << it->first << " , " << "Second : " << it->second << " " ; } cout << "]\n" ; } } // Driver code int main() { // Declaring a forward_list of // unordered maps forward_list<unordered_map< int , string> > forwardList1; // Declaring a unordered map unordered_map< int , string> unorderedMap1; // Hashing values unorderedMap1[2] = "Beginner" ; unorderedMap1[4] = "for" ; unorderedMap1[6] = "Beginner" ; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap1); // Declaring another unordered map unordered_map< int , string> unorderedMap2; // Hashing values unorderedMap2[3] = "Python" ; unorderedMap2[11] = "Java" ; unorderedMap2[23] = "C++" ; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap2); // Declaring another unordered map unordered_map< int , string> unorderedMap3; // Hashing values unorderedMap3[7] = "C" ; unorderedMap3[18] = "PHP" ; unorderedMap3[9] = "Swift" ; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap3); // Declaring another unordered map unordered_map< int , string> unorderedMap4; // Hashing values unorderedMap4[121] = "Hello" ; unorderedMap4[97] = "Coding" ; unorderedMap4[197] = "World" ; // Push back the unordered map in // the forward list forwardList1.push_front(unorderedMap4); print(forwardList1); return 0; } |
Output:
Forward List :
Unordered Map : [ First : 197 , Second : World First : 121 , Second : Hello First : 97 , Second : Coding ]
Unordered Map : [ First : 9 , Second : Swift First : 7 , Second : C First : 18 , Second : PHP ]
Unordered Map : [ First : 23 , Second : C++ First : 3 , Second : Python First : 11 , Second : Java ]
Unordered Map : [ First : 6 , Second : Beginner First : 2 , Second : Beginner First : 4 , Second : for ]
List of Unordered Maps
Below is the implementation using a list of unordered maps:
Example 1:
C++
// C++ program to implement // the above concept #include <bits/stdc++.h> using namespace std; // Function to print list elements void print(list<unordered_map< int , int > >& List) { cout << "List : \n" ; for ( auto currentUnorderedMap : List) { // Each element of the list is // a unordered map cout << "Unordered Map : " ; cout << "[ " ; // Print unordered map elements for ( auto it = currentUnorderedMap.begin(); it != currentUnorderedMap.end(); it++) { cout << "First : " << it->first << " , " << "Second : " << it->second << " " ; } cout << "]\n" ; } } // Driver code int main() { // Declaring a list of unordered maps list<unordered_map< int , int > > List; // Declaring a unordered map unordered_map< int , int > unorderedMap1; // Hashing values unorderedMap1[2] = 4; unorderedMap1[4] = 3; unorderedMap1[6] = 9; // Push back the unordered map // in the list List.push_front(unorderedMap1); // Declaring another unordered map unordered_map< int , int > unorderedMap2; // Hashing values unorderedMap2[31] = 8; unorderedMap2[11] = 3; unorderedMap2[23] = 7; // Push back the unordered map // in the list List.push_front(unorderedMap2); // Declaring another unordered map unordered_map< int , int > unorderedMap3; // Hashing values unorderedMap3[7] = 3; unorderedMap3[18] = 1; unorderedMap3[9] = 6; // Push back the unordered map // in the list List.push_front(unorderedMap3); // Declaring another unordered map unordered_map< int , int > unorderedMap4; // Hashing values unorderedMap4[32] = 9; unorderedMap4[15] = 3; unorderedMap4[97] = 5; // Push back the unordered map // in the list List.push_front(unorderedMap4); print(List); return 0; } |
Output:
List :
Unordered Map : [ First : 97 , Second : 5 First : 32 , Second : 9 First : 15 , Second : 3 ]
Unordered Map : [ First : 9 , Second : 6 First : 7 , Second : 3 First : 18 , Second : 1 ]
Unordered Map : [ First : 23 , Second : 7 First : 31 , Second : 8 First : 11 , Second : 3 ]
Unordered Map : [ First : 6 , Second : 9 First : 2 , Second : 4 First : 4 , Second : 3 ]
Example 2:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to print list elements void print(list<unordered_map< int , string> >& List) { cout << "List : \n" ; for ( auto currentUnorderedMap : List) { // Each element of the list is // a unordered map cout << "Unordered Map : " ; cout << "[ " ; // Print unordered map elements for ( auto it = currentUnorderedMap.begin(); it != currentUnorderedMap.end(); it++) { cout << "First : " << it->first << " , " << "Second : " << it->second << " " ; } cout << "]\n" ; } } // Driver code int main() { // Declaring a list of unordered maps list<unordered_map< int , string> > List; // Declaring a unordered map unordered_map< int , string> unorderedMap1; // Hashing values unorderedMap1[2] = "Beginner" ; unorderedMap1[4] = "for" ; unorderedMap1[6] = "Beginner" ; // Push back the unordered map in // the forward list List.push_front(unorderedMap1); // Declaring another unordered map unordered_map< int , string> unorderedMap2; // Hashing values unorderedMap2[3] = "Python" ; unorderedMap2[11] = "Java" ; unorderedMap2[23] = "C++" ; // Push back the unordered map in // the forward list List.push_front(unorderedMap2); // Declaring another unordered map unordered_map< int , string> unorderedMap3; // Hashing values unorderedMap3[7] = "C" ; unorderedMap3[18] = "PHP" ; unorderedMap3[9] = "Swift" ; // Push back the unordered map in // the forward list List.push_front(unorderedMap3); // Declaring another unordered map unordered_map< int , string> unorderedMap4; // Hashing values unorderedMap4[121] = "Hello" ; unorderedMap4[97] = "Coding" ; unorderedMap4[197] = "World" ; // Push back the unordered map in // the forward list List.push_front(unorderedMap4); print(List); return 0; } |
Output:
List :
Unordered Map : [ First : 197 , Second : World First : 121 , Second : Hello First : 97 , Second : Coding ]
Unordered Map : [ First : 9 , Second : Swift First : 7 , Second : C First : 18 , Second : PHP ]
Unordered Map : [ First : 23 , Second : C++ First : 3 , Second : Python First : 11 , Second : Java ]
Unordered Map : [ First : 6 , Second : Beginner First : 2 , Second : Beginner First : 4 , Second : for ]
Contact Us