📌 Find Function
//For Maps
map<int,int>mp;
mp.insert({2,3});
mp.insert({1,5});
if(mp.find(2) != mp.end())
cout<<mp.find(2)->second; //Output = 3
else
cout<<"Not Found";
mp.find(3)->second //outputs 0, not present.
//Time Complexity = O(log N)
//For unordered_map, best case time Complexity = O(1)
//find for vectors
//find(firstItr, lastItr, val)
//search from [first,last); if not found returns last.
vector<int>v = {5,1,9,7,6,3};
auto it = find(v.begin(),v.end(), 9);
cout<<"Value 9 found at index "<<it-v.begin();
//Output = 2
//for a val not in vector, it will return v.end()
//Time Complexity = O(N)
//Auxiliary Space = O(1)
string str = "geeksforgeeks a computer science";
string str1 = "geeks";
// Find first occurrence of "geeks"
size_t found = str.find(str1); //default starting search position = 0
if (found != string::npos)
cout << "First occurrence is " << found << endl; //Output = 0
// Find next occurrence of "geeks". Note here we pass
// "geeks" as C style string.
char arr[] = "geeks";
found = str.find(arr, found+1); //str1 can also be passed
if (found != string::npos)
cout << "Next occurrence is " << found << endl; //output = 8
npos is a constant static member value with the highest possible value for an element of type size_t.
It actually means until the end of the string.
It is used as the value for a length parameter in the string’s member functions.
As a return value, it is usually used to indicate no matches.
//Find for sets
//same as maps
set<int> s;
s.insert(1);
s.insert(4);
s.insert(3);
//set = {1,3,4}
// iterator pointing to
// position where 3 is
auto pos = s.find(3);
//if not found, it will return s.end();
//Time Complexity = O(log N) as set is already sorted.
📌Comparators in C++
class comparator_class {
public:
// Comparator function
bool operator(object o1, object o2)
{
// There can be any condition implemented as per the need of the problem statement
return (o1.data_member== o2.data_member);
}
}
Comparators are mainly used in sorting
//Sort a map on the basis of values, and if values are same then on the decreasing order of keys
//Approach 1
//Let map be map<string,int>mp
//By using vector of key-value pairs
static bool cmp(pair<string,int>& a, pair<string,int>& b) {
if(a.second == b.second)
return a.first>b.first; //If we want ascending order of keys, then this statement is not needed
//as map is already sorted on keys, or we can write a.first<b.first
return a.second<b.second;
}
void sort(map<string, int>& mp)
{
// Declare vector of pairs
vector<pair<string, int> > A;
// Copy key-value pair from Map to vector of pairs
for (auto& it : mp) {
A.push_back(it);
}
// Sort using comparator function
sort(A.begin(), A.end(), cmp); //The map will remain the same, we can return the vector or write the code accordingly.
}
//Approach 2
//Using set of key-value pairs
struct comp {
template <typename T>
// Comparator function
bool operator()(const T& l,
const T& r) const
{
if (l.second == r.second) {
return l.first > r.first;
}
return l.second < r.second;
}
};
void sort(map<string, int>& mp)
{
// Declare set of pairs and insert pairs according to the comparator
// function comp()
set<pair<string, int>, comp> S(mp.begin(),mp.end());
}
NOTE: For inserting keys in descending order in a Map or set, greater keyword is used as map<int, int, greater<int> > mp.
📌Filling an array with a particular value
//integer array of size 100 filled with -1
//Method 1
int arr[100] = {-1};
//Method 2
array<int,100> a;
a.fill(-1);
//Method 3
int array[100];
fill(array,array+100,-1);
//If we want to fill first 5 elements with 0 and next 5 with 1, then
fill(array,array+5,0); //0 to 4 index-> value is 0
fill(array+5,array+10,1); //5 to 9 index->value is 1
📌User Input Strings
//cin considers space(whitespace,tabs,etc.)as aterminating characters.
//To take string in input, we use getline
string s;
getline(cin,s);
📌Range of data types
📌String to integer
//Using string stream
#include<sstream>
string s = "12345";
// object from the class stringstream
stringstream ss(s);
/*
OR
stringstream ss;
ss<<s;
*/
// The object has the value 12345 and stream it to the integer x
int x = 0;
ss >> x; //x will have value 12345.
//Using stoi
string s = "255";
int x = stoi(s); //x will have value 255
//**stoi -> string to integer -> can take 3 parameters: string.starting pos(default = 0), base(default = 10)**
📌Integer to String
//Using string stream
#include<sstream>
int k = 135;
stringstream ss;
ss<<k; //<< : Insertion operator
//>> : extraction operator
string s;
ss>>s; //s will have value "135"
//Using to_string() method
int i = 101;
string str = to_string(i); //str will have value "100"
📌String to char array
A character array terminates with a null character.
//Method 1
#include<cstring>
string s = "TechieGeeks";
int n = s.length();
// declaring character array
char char_array[n + 1];
// copying the contents of the string to char array
strcpy(char_array, s.c_str());
//Method 2
char* char_arr;
string str_obj("TechieGeeks");
char_arr = &str_obj[0];
//Method 3
string st = "TechieGeeks";
//the c_str() function returns a const pointer to null terminated contents.
const char *str = st.c_str();
📌Char array to string
//Can be done directly
//char* a is my char array
//Method 1
string s(a);
//Method 2
string s = a;
📌Binary String to Integer
string bin_str = "1011";
int num = stoi(bin_str,0,2);
📌Creating string with a specific number of characters
string s(10, 'a');
//the number of times and the character can be variable also
📌Integer to Binary string
int n = 100;
string s1=""
//Method 1:
string s1 = bitset<8>(n).to_string(); // 01100100
//Method 2
while(n) {
s1 += (n%2) + '0'; //(n&1) + '0'
n /= 2; //n = n<<1;
}
reverse(s1.begin(),s1.end()); // 1100100
📌Substrings in C++
string s = "Techie Geeks";
string r = s.substr(0,4); //r will be "Tech"
//substr(pos,len) -> start from position pos until length is 4
📌GCD of two numbers
//Method 1
int gcd(int a, int b)
{
int result=min(a,b); // Find Minimum of a nd b
while(result>0)
{
if(a%result==0 && b%result==0)
{
break;
}
result--;
}
return result; // return gcd of a and b
}
//Method 2
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
//Method 3: Memoization
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// if a value is already present in dp
if(dp[a][b] != -1)
return dp[a][b];
// a is greater
if (a > b)
dp[a][b] = gcd(a-b, b);
// b is greater
else
dp[a][b] = gcd(a, b-a);
// return dp
return dp[a][b];
}
//Method 4
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
📌Character Class Methods
#include<cctype>
isupper()
islower()
isdigit()
toupper()
tolower()
isblank() //space, tabs and EOF
isspace() //checks all tabs,whitespace,\r,\n,etc.
📌Priority Queue with comparators
struct cmp {
bool operator()(int a, int b)
{
return a<b;
}
};
bool compare(int a, int b)
{
return a<b;
}
int main()
{
priority_queue<int,vector<int>, cmp> numbers;
vector<int>v;
v.push_back(1);
v.push_back(20);
v.push_back(7);
sort(v.begin(), v.end(), compare);
numbers.push(1);
numbers.push(20);
numbers.push(7);
cout << "Priority Queue: ";
while(!numbers.empty()) {
cout << numbers.top() << ", ";
numbers.pop();
}
cout << endl;
cout<<"Vector: ";
int i=0;
while(i<v.size()) {
cout << v[i] << ", ";
i++;
}
cout << endl;
return 0;
}
//Output:
Priority Queue: 20, 7, 1,
Vector: 1, 7, 20,
//The same comparator gives reverse output in sort and priority queue.
//Priority Queue comparator works reverse
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
class Cell {
public:
int row,col;
Cell() {}
Cell(int row, int col) {
this->row = row;
this->col = col;
}
bool operator<(const Cell& b) const{
return this->row > b.row;
}
};
int main()
{
priority_queue<Cell> pq;
pq.push({2,3});
pq.push({1,6});
cout<<pq.top().row;
return 0;
}
//Output: 1
📌Memset
//To initialize a variable size array
int arr[n];
memset(arr,-1,sizeof(arr));
Â