Containers in C++ STL

by anupmaurya
351 views

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; }
Code language: PHP (php)

Output :

The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
Code language: CSS (css)

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; }
Code language: PHP (php)

Output :

The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1
Code language: CSS (css)

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; }
Code language: PHP (php)

Output :

The stack is : 1 5 20 30 10 s.size() : 5 s.top() : 1 s.pop() : 5 20 30 10
Code language: CSS (css)

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; }
Code language: PHP (php)

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
Code language: CSS (css)

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; }
Code language: PHP (php)

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
Code language: JavaScript (javascript)

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; }
Code language: PHP (php)

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; }
Code language: PHP (php)

Output :

Contribute 30 Practice 20

You may also like