//STL ALGORITHM APPLICATION ON SEQUENCE CONTAIERS
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<char>vc;
vc.push_back('a');
vc.push_back('b');
vc.push_back('c');
vc.push_back('d');
//first occurrence and iterator
vector<char>::iterator it = find(vc.begin(),vc.end(),'c');
cout<<"c is at position "<<it - vc.begin() + 1<<endl;
vc.push_back('c');
vc.push_back('c');
vc.push_back('c');
//Counting number of appearances
int cnt = count(vc.begin(),vc.end(),'c');
cout<<"c appeared "<<cnt<<" times\n";
//Searching a subsequence
vector<int>v_prime;
v_prime.push_back(3);
v_prime.push_back(4);
v_prime.push_back(5);
v_prime.push_back(6);
v_prime.push_back(7);
v_prime.push_back(8);
v_prime.push_back(9);
vector<int>v_sec_1;
v_sec_1.push_back(7);
v_sec_1.push_back(8);
v_sec_1.push_back(9);
vector<int>v_sec_2;
v_sec_2.push_back(3);
v_sec_2.push_back(5);
v_sec_2.push_back(6);
//An iterator to the first element of the first occurrence of [first2,last2) in [first1,last1).
//If the sequence is not found, the function returns last1.
//SEARCH S FOR SUBSEQUENCE
if(search(v_prime.begin()+2,v_prime.end(),v_sec_1.begin(),v_sec_1.end())!=v_prime.end())
cout<<"Found sequence\n";
else
cout<<"Not Found sequence\n";
if(search(v_prime.begin()+2,v_prime.end(),v_sec_2.begin(),v_sec_2.end())!=v_prime.end())
cout<<"Found sequence\n";
else
cout<<"Not Found sequence\n";
cout<<*min_element(v_prime.begin(),v_prime.end())<<endl;
return 0;
}
শনিবার, ২৬ সেপ্টেম্বর, ২০১৫
STL C++ algorithm
STL C++ list 2
STL list part 2 :
//STL Container list part 2
#include <bits/stdc++.h>
#define p_l_i(l) for(list<int>::iterator it = l.begin();it!=l.end();it++)cout<<*it<<" ";cout<<endl;
using namespace std;
bool r_i_t_i_t(const int& val)
{
if(val>40 && val<90)
return true;
return false;
}
int main()
{
list<int>l1;
list<int>l2;
l1.push_back(34);
l1.push_back(4);
l1.push_back(3);
l1.push_back(41);
l2.push_back(31);
l2.push_back(20);
l2.push_back(91);
l2.push_back(16);
//Merging 2 lists O(n)
//Without sorting
l1.merge(l2);
p_l_i(l1); //Weird ordering
if(l2.empty())
cout<<"l2 is empty!\n";
//merging with sorting
list<int>l3;
list<int>l4;
l3.push_back(34);
l3.push_back(4);
l3.push_back(3);
l3.push_back(41);
l4.push_back(31);
l4.push_back(20);
l4.push_back(91);
l4.push_back(16);
l3.sort(); //this is the min to max sort version
l4.sort(); //this is the min to max sort version
p_l_i(l3);
p_l_i(l4);
l3.merge(l4);
p_l_i(l3);
if(l4.empty())
cout<<"l4 is empty!\n";
//Erasing elements O(1)
//3 4 16 20 31 34 41 91
list<int>::iterator it= l3.begin(); //^
list<int>::iterator it2;
advance(it,4); //advancing iterator // ^ (4 steps ahead from begin)
cout<<*it<<endl;
it2 = l3.erase(it); //3 4 16 20 34 41 91 ....<><><>.... [31] it pointing to 31 still
//but l3 itself doesn't contain 31
p_l_i(l3);
cout<<*it<<endl; //prints 31 invalidated reference
//But it2 prints 34 previous position of 31
cout<<*it2<<endl;
//Can erase a range of elements
list<int>::iterator it3 = l3.begin(); //pointing to 3
list<int>::iterator it4 = l3.end() ; //pointing to next position of 91
it4--; //pointing to 91
it4--; //pointing to 41
advance(it3,3);//pointing to 20
l3.erase(it3,it4); //deleting 20 to 34 (34 is just before 41)
p_l_i(l3);
//removing all elements with a certain value
l3.push_back(3); //3 4 16 41 91 3
p_l_i(l3);
l3.remove(3);
p_l_i(l3); //4 16 41 91
//Can come in handy while pruning
//removing with a condition
l3.remove_if(r_i_t_i_t); //remove if this is true //See the syntax not r_i_t_i_t()
p_l_i(l3);//no elements in (40,90)
//Splicing O(1)
//listX -------transferring-------->>>> listY
//merging whole list
//splice(the iterator of listX where I want to merge listY(or part of it) , name of listY(ref))
//merging just 1 element
//splice( || , || , the iterator of listY pointing to that element)
//merging a range of elements from listY
//splice( || , || , starting iterator , ending iterator )
l4.push_back(-12);
l4.push_back(-98);
l4.push_back(-67);
l4.push_front(445);
l4.push_front(345);
l4.push_front(125);
it4 = l3.begin();
it4++; //pointing to 16
cout<<*it4<<endl; //16
l3.splice(it4,l4); // merging whole list
p_l_i(l3);
if(l4.empty())
cout<<"l4 is now empty\n";
l4.push_back(-12);
l4.push_back(-98);
l4.push_back(-67);
l4.push_front(445);
l4.push_front(345);
l4.push_front(125);
l3.splice(it4,l4,l4.begin());//it4 still pointing to 16 .... just adding 125 in the position of 16
p_l_i(l3);
l4.push_back(999);
l4.push_back(99);
l4.push_back(9);
l3.splice(it4,l4,l4.begin(),l4.end()--); //Still adding 9 post increment ;-)
p_l_i(l3);
l4.push_back(888);
l4.push_back(88);
l4.push_back(8);
l3.splice(it4,l4,l4.begin(),--l4.end()); //Not adding 8 pre increment ;-)
p_l_i(l3);
//Keeping just unique values : Only works on sorted list
l3.sort();
l3.unique();
p_l_i(l3);
return 0;
}
STL C++ List
STL list intro :
//STL Container list
#include <bits/stdc++.h>
#define p_l_i(l) for(list<int>::iterator it = l.begin();it!=l.end();it++)cout<<*it<<" ";cout<<endl;
using namespace std;
int main()
{
list<int>l1;
list<int>l2(9);
list<int>l3(7,45);
list<int>l4(l3.begin(),l3.end()); //Can't do list<int>l4(l3.begin() + 2 ,l3.end() - 1);
list<int>l5(l3);
if(l1.empty())
cout<<"l1 is empty!\n";
p_l_i(l2);
p_l_i(l3);
p_l_i(l4);
p_l_i(l5);
//FOR ALL SEQUENCE CONTAINERS v1=v2;d1=d2;l1=l2 is valid where v1 takes all values of v2 or v1 is transformed into v2
l2.push_back(3);
l2.push_front(6);
p_l_i(l2);
l3.pop_back();
l3.pop_front();
p_l_i(l3);
//Inserting just 1 element
//First construct the proper iterator
list<int>::iterator lit = l2.begin(); //l2 : 6 0 0 0 0 0 0 0 0 0 3
lit++; //after this instruction lit will point to 2nd position ^
l2.insert(lit,99); //l2 : 6 99 0 0 0 0 0 0 0 0 0 3
p_l_i(l2); //lit points to ^
//So,if I insert 3 at lit it'll be inserted at position 3 (not 2)
l2.insert(lit,3); //l2 : 6 99 3 0 0 0 0 0 0 0 0 0 3
p_l_i(l2); //lit points to ^
l2.push_back(23);
l2.push_back(45);
l2.push_back(77); //l2 : 6 99 3 0 0 0 0 0 0 0 0 0 3 23 45 77
//Lets insert 65 at the third position from last (where is 23?)
lit = l2.end(); //It points to next slot to the last position
lit--; //It 'll now point to the last position (where is 77?)
for(int a=0;a<2;a++) //how many steps does it take to move from 77 to 23 .Yeah,it's 2 !
lit--; //equivalent to lit-=3 But can't do that
l2.insert(lit,65); ////l2 : 6 99 3 0 0 0 0 0 0 0 0 0 3 65 23 45 77
p_l_i(l2); //lit now points to ^
//Inserting more than 1 element
l2.insert(lit,4,8); //Inserting 4 8s in the position of 23
p_l_i(l2); //l2 : 6 99 3 0 0 0 0 0 0 0 0 0 3 65 8 8 8 8 23 45 77
// ^
vector<int>vi;
vi.push_back(12);
vi.push_back(13);
vi.push_back(14);
vi.push_back(15);
vi.push_back(16);
vi.push_back(17);
//Inserting a total vector or part of it
l2.insert(--lit,vi.begin()+2,vi.end());//inserting 14 15 16 17 where the last 8 is (pre-incremented)
//l2 : 6 99 3 0 0 0 0 0 0 0 0 0 3 65 8 8 8 14 15 16 17 8 23 45 77
// ^
p_l_i(l2);
return 0;
}
C++ STL Deque
The Duque Use :
//STL CONTAINER Deque
#include <bits/stdc++.h>
#define p_d_i(d) for(deque<int>::iterator it= d.begin();it!=d.end();it++)cout<<*it<<" ";cout<<endl;
using namespace std;
int main()
{
//same as vector
deque<int>d1;
deque<int>d2(7,89);
deque<int>d3(d2.begin()+2,d2.end()-1);
deque<int>d4(d2);
if(d1.empty())
cout<<"d1 is empty!\n";
cout<<d2[3]<<endl;
deque<int>d5(9); //size:9 all 0s
cout<<"Size of d5 is "<<d5.size()<<endl;
p_d_i(d5);
d4.push_back(13);
d4.push_back(52);
d4.push_front(976);
d4.push_front(56);
p_d_i(d4);
d4.pop_back();
p_d_i(d4);
d4.pop_front();
p_d_i(d4);
return 0;
} --------------------------------------------------------------------------------------------
//STL CONTAINER Deque
#include <bits/stdc++.h>
#define p_d_i(d) for(deque<int>::iterator it= d.begin();it!=d.end();it++)cout<<*it<<" ";cout<<endl;
using namespace std;
int main()
{
//same as vector
deque<int>d1;
deque<int>d2(7,89);
deque<int>d3(d2.begin()+2,d2.end()-1);
deque<int>d4(d2);
if(d1.empty())
cout<<"d1 is empty!\n";
cout<<d2[3]<<endl;
deque<int>d5(9); //size:9 all 0s
cout<<"Size of d5 is "<<d5.size()<<endl;
p_d_i(d5);
d4.push_back(13);
d4.push_back(52);
d4.push_front(976);
d4.push_front(56);
p_d_i(d4);
d4.pop_back();
p_d_i(d4);
d4.pop_front();
p_d_i(d4);
d4.insert(d4.begin()+4,-12345);
d4.erase(d4.end()-1);
p_d_i(d4);
d4.erase(d4.end()-5);//Clear when erasing elements
//erase(begin) deletes the first element . But end -1 deletes the last element
p_d_i(d4);
d4.push_front(0);
p_d_i(d4);
d4.erase(d4.begin()); //deletes the first element
d4.push_back(67);
p_d_i(d4);
d4.erase(d4.end()-1); //deletes the last element
p_d_i(d4);
d4.clear();
if(d4.empty())
cout<<"d4 is empty too!\n";
return 0;
}
C++ STL Vector
Vector template :
//TEMPLATE PROGRAM FOR STL SEQUENCE CONTAINER Vector
#include <bits/stdc++.h>
using namespace std;
///vector : p_v(vector) print_vector(vector)
#define p_v_i(v) for(vector<int>::iterator it = v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
#define p_v_b(v) for(vector<bool>::iterator it = v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
///vector : saa_v(vector_to_be_searched,value); search_all_appearances_vector(vector_to_be_searched,value)
// searches all appearances of value in the vector and returns them in a vector
/*
template<typename T>
vector<int> sas_v(vector<T>vT,T val)
{
vector<int>il; //index_list
for(int a=0; a<vT.size(); a++)
{
if(vT[a]==val)
il.push_back(a); //0 based indexing
}
return il;
}
*/
template<typename T>
vector<int> sas_v(vector<T>vT,T val)
{
vector<int>il; //index_list
typename vector<T>::iterator it; //See how used typename infront of it declaration
for(it = vT.begin(); it!=vT.end(); it++)
{
if(*it==val)
il.push_back(it-vT.begin()); //0 based indexing
}
return il;
}
int main()
{
vector<int> v1; //Don't use v1() empty constructors . They are evil!!!
vector<int> v2(10,-5); //10 elements with value -5
vector<int> v3(v2.begin(),v2.end());
vector<int>::iterator it = v2.begin()+2;
vector<int> v4(it , v2.end()); //Even though I added 2 elements to v2 later But those were not added to v4
vector<int> v5(v4); //copy if v4
v2.push_back(3);
v2.push_back(7);
//v1 should be empty
if(v1.empty())
cout<<"v1 is empty!\n";
//traversing a vector sequentially using iterators
for(vector<int>::iterator it = v2.begin(); it!=v2.end(); it++)
cout<<*it<<" ";
cout<<endl;
for(vector<int>::iterator it = v3.begin(); it!=v3.end(); it++)
cout<<*it<<" ";
cout<<endl;
//traversing a vector sequentially using index [array]
for(int a=0; a<v4.size(); a++)
cout<<v4[a]<<" ";
cout<<endl;
for(int a=0; a<v5.size(); a++)
cout<<v5[a]<<" ";
cout<<endl;
//Searching 1 : binary search is effective if only the sureness of existence of a value is needed not the position
//or the number of appearance of the value
///WORKS ONLY ON SORTED SEQUENCE
sort(v2.begin(),v2.end()); //funny the vector was already in the sorted form
bool bs_6_v2 = binary_search(v2.begin(),v2.end(),6);
if(bs_6_v2)
cout<<"6 found in v2\n";
else
cout<<"6 not found in v2\n";
bool bs_3_v2 = binary_search(v2.begin(),v2.end(),3);
if(bs_3_v2)
cout<<"3 found in v2\n";
else
cout<<"3 not found in v2\n";
bool bs_3_v2_er = binary_search(v2.begin(),v2.end() - 2,3); //Edited Range : See how range works here with iterators
if(bs_3_v2_er)
cout<<"3 found in edited range of v2 \n";
else
cout<<"3 not found in edited range of v2\n";
//So from this edited range we get that begin points to first element begin + 1 points to second element
//end points to last element . end - 1 points to the second last element
//Searching 2 : If I also need the position of the first appearance then can use find
vector<int>::iterator it2 = find(v2.begin(),v2.end()-1 , 3);
if(it2!=v2.end()-1)
{
cout<<"3 found at position "<<it2 - v2.begin() + 1<<endl;
}
else
cout<<"3 not found."<<endl;
//Searching 3 : If I need all the position of the appearance
int val = 3;
vector<int>aa = sas_v(v2,val); //all_appearance
cout<<"All the appearance Of "<<val<<" :";
for(vector<int>::iterator it = aa.begin(); it!=aa.end(); it++)
cout<<*it<<" ";
cout<<endl;
v2.push_back(-2);
v2.push_back(999);
//sorting min to max
sort(v2.begin(),v2.end());
p_v_i(v2);
//sorting max to min
sort(v2.rbegin(),v2.rend());
p_v_i(v2);
///Reversing elements of vector
///Comment : You don't need to reverse just when traversing go from rbegin to rend
for(vector<int>::iterator it = v2.end()-1; it>=v2.begin(); it--)//See the ranges
cout<<*it<<" ";
cout<<endl;
///Inserting an element in the middle O(n)
vector<int>::iterator pos = v2.begin() + 5 ; //inserting element at pos 6 [if first element has pos 1]
v2.insert(pos,456);
p_v_i(v2);
cout<<endl;
///Erasing an element from the middle O(n)
vector<int>::iterator n_pos = v2.begin() + 5 ; //inserting element at pos 6 [if first element has pos 1]
v2.erase(n_pos); // 1 deleted
p_v_i(v2);
cout<<endl;
v2.erase(n_pos,v2.end()-3); //all deleted from pos 6 to last_pos - 3
p_v_i(v2);
cout<<endl;
v2.clear(); //O(n) Generally not used ! Use if same vector is used more than once in different test cases for data storage
///Vector of bools
vector<bool>vb;
vb.push_back(true);
vb.push_back(false);
vb.push_back(false);
vb.push_back(true);
vb.push_back(false);
p_v_b(vb);
vb.flip(); //flipping all bits;
p_v_b(vb);
return 0;
}
এতে সদস্যতা:
পোস্টগুলি (Atom)