// STL is provided in the following headers:
// Containers data structures template classes
<vector>, <list>, <deque>, <queue>, <stack>, <map>, <set>, <bitset>, <forward_list> (C++11), <unordered_map> (C++11), <unordered_set> (C++11), <array> (C++11)
// Iterator for transversing the elements in a container
<iterator>
// Algorithm and function objects
<algorithm>, <numeric>, <functional>, <utility>
<initializer_list> (C++11), <memroy> (C++11).
#include<array>
array<int, 5> a = {1, 2, 3, 4, 5}; //need to specify size at compile time
a.fill(2); // {2, 2, 2, 2, 2}
a.front();
a.back();
a.size();
a.max_size();
a[0];
a.at(0);
a.empty();
#include<utility>
pair<int, int> p = {1, 3};
// pair<int, int> p {1, 3};
// pair<int, int> p (1, 3);
// pair<int, int> p(p1);
// prints 1 3
cout << p.first << " " << p.second;
pair<int, pair<int, int>> p = {1, {3, 4}};
// prints 1 4 3
cout << p.first << " " << p.second.second << " " << p.second.first;
pair<int, int> arr[] = { {1, 2}, {2, 5}, {5, 1}};
// Prints 5
cout << arr[1].second;
// Comparison among pairs
// To compare two pairs, first element is compared and if they're equaL that tie is broken using second element
#include<vector>
vector<int> v = {1, 2, 3};
// vector<int> v {1, 2, 3}
// Caution: below doesn't work since () are required for special use in vector
// vector<int> (1, 2, 3);
vector<int> v(5, 100); // {100, 100, 100, 100, 100}
vector<int> v(5); // {0, 0, 0, 0, 0}, compiler-dependent
vector<int> v(v1);
// Take the vector to be {10, 20, 30, 40}
vector<int>::iterator it = v.begin();
it++;
cout << *(it) << " "; // prints 20
it = it + 2;
cout << *(it) << " "; // prints 30, inderection using *
vector<int>::iterator it = v.end();
vector<int>::iterator it = v.rend();
vector<int>::iterator it = v.rbegin();
// NOTE: begin() points to memory address before 10 and end() points to address after 40
// rbegin() points to address after 40, rend() points to address before 10
// Accessing
v[0] // first element
v.at(0)
g1.front()
v.back() // last element
v.size() // size
// Ways to print the vector
for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
cout << *(it) << " ";
}
for (auto it = v.begin(); it != v.end(); it++) {
cout << *(it) << " ";
}
for (auto it : v) {
cout << it << " ";
}
// Deletion
v.erase(v.begin()) //erases v[0]
v.erase(v.begin()+3) //erases v[3]
v.erase(v.begin()+1, v.begin()+3) //range erase, won't delete last element in rage; include-exclude range
// Insertion
v.push_back({1, 2}); // inserts at right hand side
v.emplace_back(1, 2); // same as push_back
vector<int>v(2, 100); // {100, 100}
v.insert(v.begin(), 300); // {300, 100, 100};
v.insert(v.begin() + 1, 2, 10); // {300, 10, 10, 100, 100}
(start, count, element)
vector<int> copy(2, 50); // {50, 50}
v.insert(v.begin(), copy.begin(), copy.end()); // {50, 50, 300, 10, 10, 100, 100}
(start, start_other, end_other)
//{10, 20}
v.pop_back(); // {10}
// v1 -> {10, 20}
// v2 -> {30, 40}
v1.swap(v2); // v1 -> {30, 40} , v2 -> {10, 20}
v.clear(); // erases the entire vector
cout << v.empty(); // true
Same as a vector but we can push elements at the front with built-in method push_front unlike vector. Also non-contiguous memory allocation.
#include<list>
list<int> ls;
ls.push_back(2); // {2}
ls.emplace_back(4); // {2, 4}
ls.push_front(5); // {5, 2, 4};
ls.emplace_front(6); // {6, 5, 2, 4}
ls.reverse(); // {4, 2, 5, 6}
ls.sort(); // {2, 4, 5, 6}
// rest functions same as vector
// begin, end, rbegin, rend, clear, insert, size, swap
Double ended queue
#include<deque>
deque<int> dq;
dq.push_back(1); // {1}
dq.emplace_back(2); // {1, 2}
dq.push_front(4); // {4, 1, 2}
dq.emplace_front(3); // {3, 4, 1, 2}
dq.pop_back(); // {3, 4, 1}
dq.pop_front(); // {4, 1}
dq.back();
dq.front();
// rest functions same as vector
// begin, end, rbegin, rend, clear, insert, size, swap
LIFO
#include<stack>
// can't initialize stacks
stack<int> st;
st.push(1); // {1}
st.push(2); // {2, 1}
st.push(3); // {3, 2, 1}
st.push(3); // {3, 3, 2, 1}
st.emplace(5); // {5, 3, 3, 2, 1}
cout << st.top(); // prints 5 "** st[2] is invalid **"
st.pop(); // st looks like {3, 3, 2, 1}
cout << st.top(); // 3
cout << st.size(); // 4
cout << st.empty();
stack<int>st1, st2;
st1.swap(st2);
FIFO
#include<queue>
queue<int> q;
q.push(1); // {1}
q.push(2); // {1, 2}
q.emplace(4); // {1, 2, 4}
q.back() += 5
cout << q.back(); // prints 9
// Q is {1, 2, 9}
cout << q.front(); // prints 1
q.pop(); // {2, 9}
cout << q.front(); // prints 2
// size(), swap(), and empty() are same as stack
Min/Max Heap
#include<queue>
// default is Max Heap
priority_queue<int> pq;
pq.push(5); // {5}
pq.push(2); // {5, 2}
pq.push(8); // {8, 5, 2}
pq.emplace(10); // {10, 8, 5, 2}
cout << pq.top(); // prints 10
pq.pop(); // {8, 5, 2}
cout << pq.top(); // prints 8
// size swap empty function same as others
// Minimum Heap
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(5); // {5}
pq.push(2); // {2, 5}
pq.push(8); // {2, 5, 8}
pq.emplace(10); // {2, 5, 8, 10}
cout << pq.top(); // prints 2
#include<set>
set<int> st;
st.insert(1); // {1}
st.emplace(2); // {1, 2}
st.insert(2); // {1, 2}
st.insert(4); // {1, 2, 4}
st.insert(3); // {1, 2, 3, 4}
// Always rearrages in ascending order
// begin(), end(), rbegin(), rend(), size(),
// empty() and swap() are same as those of above
// {1, 2, 3, 4, 5}
auto it = st.find(3); // returns an address
// {1, 2, 3, 4, 5}
auto it = st.find(6); // will return st.end() if element is never found in st
// {1, 4, 5}
st.erase(5); // erases 5 // takes logarithmic time
int cnt = st.count(1); // for sets it will either be 0 or 1
auto it = st.find(3);
st.erase(it); // it takes constant time
// {1, 2, 3, 4, 5}
auto it1 = st.find(2);
auto it2 = st.find(4);
st.erase(it1, it2); // after erase {1, 4, 5} [first, last)
// lower_bound() and upper_bound() function works in the same way
// as in vector it does.
// This is the syntax
auto it = st.lower_bound(2);
auto it = st.upper_bound(3);
#include<set>
// Everything is same as set
// only stores duplicate elements also
multiset<int> ms;
ms.insert(1); // {1}
ms.insert(1); // {1, 1}
ms.insert(1); // {1, 1, 1}
ms.erase(1); // all 1's erased
int cnt = ms.count(1);
// only a single one erased
ms.erase(ms.find(1));
ms.erase(ms.find(1), ms.find(1)+2);
// rest all function same as set
#include<unordered_set>
unordered_set<int> st;
// lower_bound and upper_bound function
// does not works, rest all functions are same
// as above, it does not stores in any
// particular order it has a better complexity
// than set in most cases, except some when collision happens
Stores unique key-value pairs only.
// {key, value}
map<int, int> mpp;
// map<int, pair<int, int>> mpp;
// map< pair<int, int>, int> mpp;
// key values can be anything
mpp[1] = 2; // mpp[key] = value
mpp.emplace({3, 1});
mpp.insert({2, 4});
mpp[{2,3}] = 10;
/* Map stores in sorted order just like Set
{
{1, 2}
{2, 4}
{3, 1}
}
*/
for(auto it : mpp) {
cout << it.first << " " << it.second << endl;
}
// same options for using iterators
// as we did in vector for the insert function
cout << mpp[1]; // prints 2
cout << mpp[5]; // prints 0, since it does not exists
auto it = mpp.find(3); // points to the position where 3 is found
cout << *(it).second;
auto it = mpp.find(5); // points to the mpp.end() since 5 not there
// lower_bound and upper_bound works exactly in the
// same way as explained in the other video
// This is the syntax
auto it = mpp.lower_bound(2);
auto it = mpp.upper_bound(3);
// erase, swap, size, empty, are same as above
#include<map>
// everything same as map, only it can store multiple keys
// only mpp[key] cannot be used here
#include<unordered_map>
// same as set and unordered_set
sort()#include<algorithm>
sort(a, a+n); // [first, last)
sort(a+2, a+5); // sort in range
//desc
sort(a, a+n, greater<int>);
// custom sort
pair<int,int> a[] = {{1,2}, {2, 1}, {4, 1}};
// sort it according to second element
// if second element is same, then sort
// it according to first element but in descending
// {4,1}, {2, 1}, {1, 2}};
sort(a, a+n, comp)
bool comp(pair<int,int>p1, pair<int,int>p2) {
if(p1.second < p2.second) {
return true;
} else if(p1.second == p2.second){
if(p1.first>p2.second) return true;
}
return false;
}
int maxi = *max_element(a, a+n);
int mini = *min_element(a, a+n);
int maxi = *max_element(v.begin(), v.end());
int mini = *min_element(v.begin(), v.end());
// reverse() (in place reversal)
reverse(arr, arr+n);
reverse(v.begin(), v.end());
long sum = accumulate(v.begin(), v.end(), 0); // 0 is initial sum
int cnt = count(v.begin(), v.end(), 2); // 2 is element to search in vector
auto it = find(v.begin(), v.end(), 2); // return address
int num = 7; // 111
int cnt = __builtin_popcount(num); // 3
// for very large numbers
long long num = 165786578687;
int cnt = __builtin_popcountll(num);
// Syntax
[](arg1, arg2) { /*body*/ }
// Definition and call together
cout << [](int a, int b){ return a+b; }(2, 4); // 6
// we can pass this as comparator in sort(arr, arr+n, [](arg1, arg2) { })
all_of(v.begin(), v.end(), lambda); // returns true if ALL elements in range satisfy lambda
any_of(v.begin(), v.end(), lambda); // returns true if ATLEAST ONE elements in range satisfy lambda
none_of(v.begin(), v.end(), lambda); // returns true if NONE of the elements in range satisfy lambda