Author : MD. Rejaul Hasan
As said in the headline it is going to review the most used STL for problem-solving. I am not going to note their implementation details and the time complexity analysis. The purpose is to make the list for my personal use. If it helps anyone it will be a plus for me. There are much better repositories available. So you can checkout those also. Please check the Official documentation and gfg list. Those are helpful also.
- Iterators
- Containers
- Array
- Vector
- Set
- Unordered_set
- Multiset
- Map
- Unordered_map
- Multimap
- Stack
- Queue
- Dequeue
- [Priority Queue](#Priority Queue)
- bitset
- List
- Forward_list
- Algorithms
Iterators are just a pointer, which points to an address of whichever type it supports. 4 main functions are mainly used. Those are begin(), end(), rbegin(), rend(). rbegin(), rend() stands for reverse begin and reverse end. It means rbegin() are pointing to the last element of the container and when you make it ++ it will move towards the first element from the end. end() do not pointing the last element of a container. It points to the next address of the last element of the container. So to get the adress of last element you need to do something like that container.end()-1. Some example
array<int, 5> arr = {1, 2, 3, 4, 5};
for(auto it = arr.begin(); it!=arr.end();it++) {cout << *it << " ";} // 1 2 3 4 5
for (auto it = arr.rbegin(); it != arr.rend(); it++){cout << *it << " ";} //5 4 3 2 1
for(auto it = arr.end() - 1; it>=arr.begin();it--) {cout << *it << " ";} //5 4 3 2 1A contiguous block of memories of the same type. Methods fill(),at(index),size(),front(),back(). Iterators work with it.
array<int, 5> arr;
arr.fill(-1); // {-1,-1,-1,-1,-1}
for(int i = 0;i<5;i++) {
cout << arr.at(i) << " ";
}
cout << arr.size(); // size
cout << arr.front(); // front
cout << arr.back(); // backSome useful methods are size(), push_back(), pop_back(), clear(), vector_name(size, default_element), erase(), insert(position,new vector Start iterator position, end position). Iterators work with it.
vector<int> vec; // {}
cout << vec.size() << endl; //print 0
vec.push_back(0); //{0}
vec.push_back(2); //{0,2}
cout << vec.size() << endl; //print 2
vec.pop_back(); //pop from back {0}
cout << vec.size() << endl; //print 1
vec.push_back(2); //{0,2}
vec.clear(); //erase all elements {}
vector<int> vec1(4, 0); // {0,0,0,0}
vector<int> vec2(4, 1); // {1,1,1,1}
// copy the entire vec2 into vec3
vector<int> vec3(vec2.begin(), vec2.end()); // [ ) -> means copy from first element to end but not include end. As end refer to the next adress of last element.
vector<int> vec3(vec2); // it also copy all {1,1,1,1}
vector<int> vec3(vec1.begin(),vec1.begin()+2); //copy first 2 element {0,0}
vector<vector<int>> vec(3,vector<int> (3,0)); // to defining 2d vectors, 3*3 vector [[0,0,0],[0,0,0],[0,0,0]]
for(auto vctRow: vec) {
for(auto it: vctRow) {
cout << it << " ";
}
cout << endl;
}
vector<int> vec(5,-1); //{-1,-1,-1,-1,-1}
vec.erase(vec.begin()); // take pointer. erase first element from vector {-1,-1,-1,-1}
vec.erase(vec.begin(),vec.begin()+2); //erase a range. Here first 2 element. [)->{-1,-1}
vector<int> vecx = {1,2,3};
vector<int> vecy = {4,5,6};
vecy.insert(vecy.end(),vecx.begin(),vecx.end()); //{4,5,6,1,2,3}add vecx from the end of vecy
vecx.insert(vec.begin() + 1, 7); //{1,7,2,3}If your iterator point an element and you delete that element then the iterator autometically point the next element. What about you iterator point the last element? It will delete then also but if you print the current eterator value you will get last element value this time.
vector<int> data = {4,5};
vector<int>:: iterator it = data.begin();
data.erase(it);
cout<<*(it); // 5
vector<int> data = {4,5,6};
vector<int>:: iterator it = data.end()-1;
data.erase(it);
cout<<*(it); // 6Store unique elements in ascending sorted order. Default set is the order set. Methods are insert(), find(), erase(), size(), empty(), clear(), count(). Iterators work with set also.
set<int> data = {1,3,2,1,5,4}; //{1,2,3,4,5} -> sort ascending order and store unique value.
cout << data.size(); // 5
data.erase(data.begin()); //{2,3,4,5}
data.erase(data.begin(),data.find(5)); //{5} data.erase(startIterator, endIterator) [)
data.insert(3); //{3,5}
data.erase(7); // data.end() pointing as 7 is not in the set.
data.erase(5); //{3} -> data.erase(key) -> key = 5
data.find(3); //return iterator. Pointer of 3.
data.emplace(1); //{1,3} -> data.insert(1)
for(auto it=data.begin(); it!=data.end();it++) { // traverse all element.
cout << *it << " ";
}
cout<<endl;
cout<< data.count(3); // 1 -> as 3 present in the data. If not then return 0
cout << data.empty(); // false -> as the set is not empty.Store all unique element but does not secure the order. All method of set applied.
unordered_set<int> st;
st.insert(2);
st.insert(3);
st.insert(1);
st.insert(1);
st.insert(11);
for(auto it: st){ // 11 1 2 3
cout<< it << " ";
}Store value in ascending order but not unique. Same value can appear whatever time needed.
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(3);
ms.insert(2);
ms.insert(2); // ms.emplace(3) {1, 1, 2, 2, 3}
// traverse way
for(auto it=ms.begin(); it!=ms.end();it++) {
cout << *it << " ";
}
for(auto it : ms) {
cout << it << endl;
}
// finds how many times 2 occurs
cout<<ms.count(2);
auto it = ms.find(2); // returns an iterator pointing to the first element of 2
ms.erase(ms.find(2)); // first instances of 2 will be erased
ms.erase(2); // all the instances will be erased
ms.clear(); // deleted the entire set
ms.erase(ms.begin(), ms.end()); // deletes the entire set It store element in lexicographical order. There is no duplicate key for same name as it use hashing inside.
map<string, int> maap;
maap["a"] = 27;
maap["b"] = 31;
maap["c"] = 31;
maap["d"] = 67;
maap["e"] = 89;
maap["f"] = 29;
maap.emplace("f", 45);
maap.erase("b"); // maap.erase(key)
maap.erase(maap.begin()); // maap.erase(iterator)
maap.clear(); // clean all element
maap.erase(maap.begin(), maap.find("h")); // other way to clean all element //-> maap.begin()+2 not acceptable. Because it is biderectional.
auto it = maap.find("a"); // points to 'a'
auto it1 = maap.find("h"); // points to end since 'h' does not exists
if(maap.empty()) {
cout << "Yes it is empty";
}As the name suggest, it store data without folliowing any order.
unordered_map<int,int> mp;
for(int i = 10; i>5; i--){mp[i] = i;}
for(auto eachElement : mp){cout<<" Key = "<<eachElement.first<< " value = "<<eachElement.second;}// Key = 6 value = 6 Key = 7 value = 7 Key = 8 value = 8 Key = 10 value = 10 Key = 9 value = 9Multimap is similar to map with an addition that multiple elements can have same keys. Also, it is NOT required that the key value and mapped value pair has to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always.
multimap <int, int> mmap; // empty multimap container
// insert elements in random order
mmap.insert(pair <int, int> (1, 40));
mmap.insert(pair <int, int> (2, 30));
mmap.insert(pair <int, int> (3, 60));
mmap.insert(pair <int, int> (6, 50));
mmap.insert(pair <int, int> (6, 10));Container which is LIFO last in first out. Function call are using stack in a program.
std::stack<int> st;
st.push(1);
st.push(10);
st.push(1);
st.top(); // give top element
st.pop(); // delete from top
if(st.empty()){cout<< "empty";}
cout<<st.size();FIFO first in first out. functions push(), pop(), size(), front(), back(), empty().
std::queue<int> qe;
qe.push(10);
qe.push(101);
qe.push(12);
cout<< qe.size() << qe.empty() << qe.back()<< qe.front();
qe.pop();Double ended queues are sequence containers with the feature of expansion and contraction on both the ends.Double ended queues are a special case of queues where insertion and deletion operations are possible at both the ends. Important functions are push_back(),push_front(),front(),back(),pop_back(),pop_front(),begin(),rbegin(),end(),rend(),insert(it,value),empty(),size(),erase(),clear().
deque<int> dq;
dq.push_back(1); //{1}
dq.push_back(3); //{1,3}
dq.push_front(2); //{2,1,3}
cout<<dq.front()<<dq.back(); //2 3
auto it = dq.begin()+1; // point to index 1.
dq.insert(it,10); // {1,10,3,2} insert 10 is index 1.
dq.empty(); // false
dq.size(); // 4
dq.erase(dq.begin()); // erase the given iterator.
dq.erase(dq.begin(), dq.end()); // erase from start to end
dq.clear(); // clear all elementmin heap and max heap. O(log(n)) time complexity. functions push(),pop(),top(),empty(),size().
priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(2);
pq.push(10); //{10,2,2,1} max heap by default. Higher the value Higher the priority.
cout<< pq.top() << " "<< pq.empty() << " "<< pq.size(); //10 0(false) 4
// NOW WHAT ABOUT MIN HEAP.
priority_queue<int, vector<int>, greater<int>> pq1;/* template<class T, class Container = vector<T>,
class Compare = less<typename Container::value_type>>
class priority_queue;*/
pq1.push(10);
pq1.push(1);
pq1.push(2);
pq1.push(2); //{1,2,2,10} bitset<5> bt; // stores 1 or 0. take 5 bit.
cout << bt.all(); // returns a true or a false // all bit set then true else false.
// bt -> 10011
cout << bt.any(); //return true. Is their any bit set?
// false
cout << bt.any(); // bt -> 00000
// for bt -> 10100
cout << bt.count(); // print the number of set bits // 2
// flip
// bt -> 10100
bt.flip(2); // bt will become 10000
bt.flip(); // it flip all the bit 01111
// none
// if none is set, then true, else false
// bt -> 10000
cout << bt.none(); // false
// bt -> 00000
cout << bt.none(); //true
// set
bt.set(); // 11111 set all bit
bt.set(2); // set the 2nd index only
bt.set(2, 0); // set the 2nd index with 0 not 1
// reset
bt.reset() // turn all indexes to 0
bt.reset(2); // turn the 2nd index to 0
// size
cout << bt.size(); //5
// test
cout << bt.test(1); // check if the bit is set or not at index 1It is normally a double linked list.
// push_front()
// push_back()
// pop_front()
// pop_back()
// begin, end, rbegin, rend
// size
// clear
// empty
// at
// remove
//insert
//reverse
list<int> l;
l.push_back(1);
l.push_front(2);
l.remove(1);Forward list in STL implements singly linked list. reverse(),push_front(),pop_front(), insert_after(), erase_after(), remove(),front(), begin(), end().
REMAIN TO WRITE.