Containers in C++ STL

This article is just continuation of previous article C++ STL , Here you learn about Containers in C++ STL.

Container Adapter

It provide a different interface for sequential containers.

Queue : Queues are a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front.

// CPP code to illustrate  
// Queue in Standard Template Library (STL) 
#include <iostream> 
#include <queue> 
  
using namespace std; 
  
void showq(queue <int> gq) 
{ 
    queue <int> g = gq; 
    while (!g.empty()) 
    { 
        cout << '\t' << g.front(); 
        g.pop(); 
    } 
    cout << '\n'; 
} 
  
int main() 
{ 
    queue <int> gquiz; 
    gquiz.push(10); 
    gquiz.push(20); 
    gquiz.push(30); 
  
    cout << "The queue gquiz is : "; 
    showq(gquiz); 
  
    cout << "\ngquiz.size() : " << gquiz.size(); 
    cout << "\ngquiz.front() : " << gquiz.front(); 
    cout << "\ngquiz.back() : " << gquiz.back(); 
  
    cout << "\ngquiz.pop() : "; 
    gquiz.pop(); 
    showq(gquiz); 
  
    return 0; 
}

Output :

The queue gquiz is :     10    20    30

gquiz.size() : 3
gquiz.front() : 10
gquiz.back() : 30
gquiz.pop() :  20    30     

Priority Queue : Priority queues are a type of container adapters, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are in non decreasing order(hence we can see that each element of the queue has a priority{fixed order}).

#include <iostream> 
#include <queue> 
  
using namespace std; 
  
void showpq(priority_queue <int> gq) 
{ 
    priority_queue <int> g = gq; 
    while (!g.empty()) 
    { 
        cout << '\t' << g.top(); 
        g.pop(); 
    } 
    cout << '\n'; 
} 
  
int main () 
{ 
    priority_queue <int> gquiz; 
    gquiz.push(10); 
    gquiz.push(30); 
    gquiz.push(20); 
    gquiz.push(5); 
    gquiz.push(1); 
  
    cout << "The priority queue gquiz is : "; 
    showpq(gquiz); 
  
    cout << "\ngquiz.size() : " << gquiz.size(); 
    cout << "\ngquiz.top() : " << gquiz.top(); 
  
  
    cout << "\ngquiz.pop() : "; 
    gquiz.pop(); 
    showpq(gquiz); 
  
    return 0; 
} 

Output :

The priority queue gquiz is :     30    20    10    5    1

gquiz.size() : 5
gquiz.top() : 30
gquiz.pop() :     20    10    5    1

Stack : Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is added at one end and (top) an element is removed from that end only.

// CPP program to demonstrate working of STL stack 
#include <iostream> 
#include <stack> 
using namespace std; 
  
void showstack(stack <int> s) 
{ 
    while (!s.empty()) 
    { 
        cout << '\t' << s.top(); 
        s.pop(); 
    } 
    cout << '\n'; 
} 
  
int main () 
{ 
    stack <int> s; 
    s.push(10); 
    s.push(30); 
    s.push(20); 
    s.push(5); 
    s.push(1); 
  
    cout << "The stack is : "; 
    showstack(s); 
  
    cout << "\ns.size() : " << s.size(); 
    cout << "\ns.top() : " << s.top(); 
  
  
    cout << "\ns.pop() : "; 
    s.pop(); 
    showstack(s); 
  
    return 0; 
} 

Output :

The stack is :     1    5    20    30    10

s.size() : 5
s.top() : 1
s.pop() : 5    20    30    10 

Associative Container

It implement sorted data structures that can be quickly searched (O(log n) complexity).

Set : Sets are a type of associative containers in which each element has to be unique, because the value of the element identifies it.
The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element.

#include <iostream> 
#include <set> 
#include <iterator> 
  
using namespace std; 
  
int main() 
{ 
    // empty set container 
    set <int, greater <int> > gquiz1;         
  
    // insert elements in random order 
    gquiz1.insert(40); 
    gquiz1.insert(30); 
    gquiz1.insert(60); 
    gquiz1.insert(20); 
    gquiz1.insert(50); 
    gquiz1.insert(50); // only one 50 will be added to the set 
    gquiz1.insert(10); 
  
    // printing set gquiz1 
    set <int, greater <int> > :: iterator itr; 
    cout << "\nThe set gquiz1 is : "; 
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) 
    { 
        cout << '\t' << *itr; 
    } 
    cout << endl; 
  
    // assigning the elements from gquiz1 to gquiz2 
    set <int> gquiz2(gquiz1.begin(), gquiz1.end()); 
  
    // print all elements of the set gquiz2 
    cout << "\nThe set gquiz2 after assign from gquiz1 is : "; 
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) 
    { 
        cout << '\t' << *itr; 
    } 
    cout << endl; 
  
    // remove all elements up to 30 in gquiz2 
    cout << "\ngquiz2 after removal of elements less than 30 : "; 
    gquiz2.erase(gquiz2.begin(), gquiz2.find(30)); 
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) 
    { 
        cout << '\t' << *itr; 
    } 
  
    // remove element with value 50 in gquiz2 
    int num; 
    num = gquiz2.erase (50); 
    cout << "\ngquiz2.erase(50) : "; 
    cout << num << " removed \t" ; 
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) 
    { 
        cout << '\t' << *itr; 
    } 
  
    cout << endl; 
  
    //lower bound and upper bound for set gquiz1 
    cout << "gquiz1.lower_bound(40) : "
         << *gquiz1.lower_bound(40) << endl; 
    cout << "gquiz1.upper_bound(40) : "
         << *gquiz1.upper_bound(40) << endl; 
  
    //lower bound and upper bound for set gquiz2 
    cout << "gquiz2.lower_bound(40) : "
         << *gquiz2.lower_bound(40) << endl; 
    cout << "gquiz2.upper_bound(40) : "
         << *gquiz2.upper_bound(40) << endl; 
  
    return 0; 
  
} 

Output :

The set gquiz1 is :      60    50    40    30    20    10

The set gquiz2 after assign from gquiz1 is : 10      20    30    40    50    60

gquiz2 after removal of elements less than 30 : 30    40    50    60
gquiz2.erase(50) : 1 removed     30    40    60
gquiz1.lower_bound(40) : 40
gquiz1.upper_bound(40) : 30
gquiz2.lower_bound(40) : 40
gquiz2.upper_bound(40) : 60

Maps : 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 same key values.

#include <iostream> 
#include <iterator> 
#include <map> 
  
using namespace std; 
  
int main() 
{ 
  
    // empty map container 
    map<int, int> gquiz1; 
  
    // insert elements in random order 
    gquiz1.insert(pair<int, int>(1, 40)); 
    gquiz1.insert(pair<int, int>(2, 30)); 
    gquiz1.insert(pair<int, int>(3, 60)); 
    gquiz1.insert(pair<int, int>(4, 20)); 
    gquiz1.insert(pair<int, int>(5, 50)); 
    gquiz1.insert(pair<int, int>(6, 50)); 
    gquiz1.insert(pair<int, int>(7, 10)); 
  
    // printing map gquiz1 
    map<int, int>::iterator itr; 
    cout << "\nThe map gquiz1 is : \n"; 
    cout << "\tKEY\tELEMENT\n"; 
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) { 
        cout << '\t' << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
    cout << endl; 
  
    // assigning the elements from gquiz1 to gquiz2 
    map<int, int> gquiz2(gquiz1.begin(), gquiz1.end()); 
  
    // print all elements of the map gquiz2 
    cout << "\nThe map gquiz2 after"
         << " assign from gquiz1 is : \n"; 
    cout << "\tKEY\tELEMENT\n"; 
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
        cout << '\t' << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
    cout << endl; 
  
    // remove all elements up to 
    // element with key=3 in gquiz2 
    cout << "\ngquiz2 after removal of"
            " elements less than key=3 : \n"; 
    cout << "\tKEY\tELEMENT\n"; 
    gquiz2.erase(gquiz2.begin(), gquiz2.find(3)); 
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
        cout << '\t' << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
  
    // remove all elements with key = 4 
    int num; 
    num = gquiz2.erase(4); 
    cout << "\ngquiz2.erase(4) : "; 
    cout << num << " removed \n"; 
    cout << "\tKEY\tELEMENT\n"; 
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
        cout << '\t' << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
  
    cout << endl; 
  
    // lower bound and upper bound for map gquiz1 key = 5 
    cout << "gquiz1.lower_bound(5) : "
         << "\tKEY = "; 
    cout << gquiz1.lower_bound(5)->first << '\t'; 
    cout << "\tELEMENT = "
         << gquiz1.lower_bound(5)->second << endl; 
    cout << "gquiz1.upper_bound(5) : "
         << "\tKEY = "; 
    cout << gquiz1.upper_bound(5)->first << '\t'; 
    cout << "\tELEMENT = "
         << gquiz1.upper_bound(5)->second << endl; 
  
    return 0; 
} 

Output:

The map gquiz1 is : 
	KEY	ELEMENT
	1	40
	2	30
	3	60
	4	20
	5	50
	6	50
	7	10

The map gquiz2 after assign from gquiz1 is : 
	KEY	ELEMENT
	1	40
	2	30
	3	60
	4	20
	5	50
	6	50
	7	10


gquiz2 after removal of elements less than key=3 : 
	KEY	ELEMENT
	3	60
	4	20
	5	50
	6	50
	7	10

gquiz2.erase(4) : 1 removed 
	KEY	ELEMENT
	3	60
	5	50
	6	50
	7	10

gquiz1.lower_bound(5) : 	KEY = 5		ELEMENT = 50
gquiz1.upper_bound(5) : 	KEY = 6		ELEMENT = 50

Unordered Associative Containers

It implement unordered data structures that can be quickly searched.

unordered_set : It is implemented using hash table where keys are hashed into indices of this hash table so it is not possible to maintain an order.
All operation on unordered_set takes constant time O(1) on an average which can go up to linear time in worst case which depends on the internally used hash function but practically they perform very well and generally provide constant time lookup operation.
The unordered-set can contain key of any type – predefined or user-defined data structure but when we define key of type user define type, we need to specify our comparison function according to which keys will be compared.

// C++ program to demonstrate various function of unordered_set 
#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    // declaring set for storing string data-type 
    unordered_set<string> stringSet; 
  
    // inserting various string, same string will be stored 
    // once in set 
    stringSet.insert("code"); 
    stringSet.insert("in"); 
    stringSet.insert("c++"); 
    stringSet.insert("is"); 
    stringSet.insert("fast"); 
  
    string key = "slow"; 
  
    //     find returns end iterator if key is not found, 
    //  else it returns iterator to that key 
    if (stringSet.find(key) == stringSet.end()) 
        cout << key << " not found\n\n"; 
    else
        cout << "Found " << key << endl << endl; 
  
    key = "c++"; 
    if (stringSet.find(key) == stringSet.end()) 
        cout << key << " not found\n"; 
    else
        cout << "Found " << key << endl; 
  
    // now iterating over whole set and printing its 
    // content 
    cout << "\nAll elements : "; 
    unordered_set<string> :: iterator itr; 
    for (itr = stringSet.begin(); itr != stringSet.end(); itr++) 
        cout << (*itr) << endl; 
}

Output :

slow not found
Found c++
All elements : 
is
fast
c++
in
code

unordered_map : unordered_map is an associated container that stores elements formed by combination of key value and a mapped value.
The key value is used to uniquely identify the element and mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined.
Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of hash table that is why performance of data structure depends on hash function a lot but on an average the cost of search, insert and delete from hash table is O(1).

// C++ program to demonstrate functionality of unordered_map 
#include <iostream> 
#include <unordered_map> 
using namespace std; 
  
int main() 
{ 
    // Declaring umap to be of <string, int> type 
    // key will be of string type and mapped value will 
    // be of double type 
    unordered_map<string, int> umap; 
  
    // inserting values by using [] operator 
    umap["Practice"] = 20; 
    umap["Contribute"] = 30; 
  
    // Traversing an unordered map 
    for (auto x : umap) 
      cout << x.first << " " << x.second << endl; 
  
}

Output :

Contribute 30
Practice 20