Analysis of common algorithms in STL
- 2020-04-02 01:37:38
- OfStack
I. non-mutation algorithm
Is a set of template functions that do not break the operation data and are used to process sequence data one by one, find elements, search subsequences, count and match. Non - mutation algorithm has a wide range of applicability, and can be applied to a variety of containers.
Find the container element
It's used to find elements that are equal to something. It looks for an element equal to value on the iterator interval [first,last)(closed open interval), and returns iterator I if the element referred to by iterator I satisfies * I =value; returns last if no element satisfies the condition.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
int num_to_find = 6;
vector<int> v1;
for( int i = 0; i < 10; i++ )
v1.push_back(2*i);
vector<int>::iterator result;
result = find( v1.begin(), v1.end(), num_to_find );
if( result == v1.end() )
cout << " No element matches were found " << num_to_find << endl;
else
cout << " The index value of the matched element is " << result-v1.begin() << endl;
}
Find the container element find_if conditionally
Pred is judged by the predicate that returns the Boolean value, and every element on the iterator interval [first, last) (closed open interval) is checked. If the iterator I satisfies pred (* I) = true, it finds the element and returns the iterator value I (the first element that meets the condition); if no element is found, it returns the last position last.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool divby5(int x)
{
return x%5?0:1;
}
void main()
{
vector<int> v(20);
for(int i=0;i<v.size();i++)
{
v[i]=(i+1)*(i+3);
cout<<v[i]<<' ';
}
cout<<endl;
vector<int>::iterator ilocation;
ilocation=find_if(v.begin(),v.end(),divby5);
if(ilocation!=v.end())
cout<<" Find the first one that can be 5 Divisible elements: "<<*ilocation<<endl<<" The index position of the element is: "<<ilocation-v.begin()<<endl;
}
Count the number of container elements equal to some value count
The list
<
int
>
L;
Count (l.begin (), l.nd (), value)
Count count_if
Count_if (l.begin (), l.ecnd (), pred). The predicate pred has the same meaning as the predicate in find_if. See example 2 for an example.
5 subsequence search
The search algorithm function searches one sequence for a subsequence that matches another. The parameters are the starting and ending positions of one sequence and the starting and ending positions of another sequence.
Function prototypes: search (v1. The begin (), v1. The end (), v2. The begin (), v2. The end ());
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v1;
cout<<"v1:";
for(int i=0;i<5;i++)
{
v1.push_back(i+5);
//Note: v1 is not defined with a given size, so an assignment statement cannot be used directly here.
cout<<v1[i]<<' ';
}
cout<<endl;
vector<int> v2;
cout<<"v2:";
for(i=0;i<2;i++)
{
v2.push_back(i+7);
cout<<v2[i]<<' ';
}
cout<<endl;
vector<int>::iterator ilocation;
ilocation=search(v1.begin(),v1.end(),v2.begin(),v2.end());
if(ilocation!=v1.end())
cout<<"v2 The element contained in v1 Where, the starting element is "<<"v1["<<ilocation-v1.begin()<<']'<<endl;
else
cout<<"v2 Is not contained in v1 In the "<<endl;
}
Search for search_n by repeating the sequence of elements
The search_n algorithm function searches for whether there is a sequence of subsequences in the sequence whose element values are all of a given value. Function prototype: search_n(v.egin (),v.end(),3,8), find 3 consecutive elements 8 in v
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(1);
v.push_back(8);
v.push_back(8);
v.push_back(8);
v.push_back(6);
v.push_back(6);
v.push_back(8);
vector<int>::iterator i;
i=search_n(v.begin(),v.end(),3,8);
if(i!=v.end())
cout<<" in v Found in the 3 It's a continuous element 8"<<endl;
else
cout<<" in v Not found in the 3 It's a continuous element 8"<<endl;
}
The last sequence searches for find_end
Function prototypes find_end (v1. The begin (), v1. The end (), v2. The begin (), v2. The end ()); Find the desired sequence in V2 at the desired location in V1.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v1;
v1.push_back(-5);
v1.push_back(1);
v1.push_back(2);
v1.push_back(-6);
v1.push_back(-8);
v1.push_back(1);
v1.push_back(2);
v1.push_back(-11);
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
vector<int>::iterator i;
i=find_end(v1.begin(),v1.end(),v2.begin(),v2.end());
if(i!=v1.end())
cout<<"v1 The last match is found in v2 The subsequence of " <<"v1["<<i-v1.begin()<<"]"<<endl;
}
Ii. Mutation algorithm
Is a set of template functions that modify container element data. Copy (what exactly do v.begin (), v.e nd (), l.b do v.begin ()); Copy the elements in v into l.
1 element copy
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(5);
list<int> l;
l.push_back(2);
l.push_back(4);
l.push_back(6);
l.push_back(8);
l.push_back(10);
copy(v.begin(),v.end(),l.begin());
list<int>::iterator i;
for(i=l.begin();i!=l.end();i++)
cout<<*i<<' ';
cout<<endl;
}
The element transform transform
Transform (v.begin(),v.end(),l.begin(),square); Copy, too, but in some way.
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
int square(int x)
{
return x*x;
}
void main()
{
vector<int> v;
v.push_back(5);
v.push_back(15);
v.push_back(25);
list<int> l(3);
transform(v.begin(),v.end(),l.begin(),square);
list<int>::iterator i;
for(i=l.begin();i!=l.end();i++)
cout<<*i<<' ';
cout<<endl;
}
3 to replace the replace
The replace algorithm replaces a specified element value with a new value.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(13);
v.push_back(25);
v.push_back(27);
v.push_back(25);
v.push_back(29);
replace(v.begin(),v.end(),25,100);
vector<int>::iterator i;
for(i=v.begin();i!=v.end();i++)
cout<<*i<<' ';
cout<<endl;
}
The output is 13, 100, 27, 100, 29
Replace replace_if with conditions
Function prototype: replace_if(v.begin(),v.end(),odd,100);
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool odd(int x)
{
return x%2;
}
void main()
{
vector<int> v;
for(int i=1;i<10;i++)
v.push_back(i);
replace_if(v.begin(),v.end(),odd,100);
vector<int>::iterator ilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
Fill_n is filled 5 n times
Function prototype fill_n(v.begin(),5,-1); Jump to -1 in the next 5 positions from v. egin
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v(10);
fill_n(v.begin(),5,-1);
vector<int>::iterator ilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
Output: -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0
6. Generate n elements randomly
Function prototype: generate_n(v.begin(),5,rand); Fill in the data at random to the next 5 positions starting from v. egin.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v(10);
generate_n(v.begin(),5,rand);
vector<int>::iterator ilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
The 7 condition removes remove_if
The return value is equivalent to the end () value of the new vector formed by removing the element that satisfies the condition.
Function prototype: remove_if(v.begin(),v.end(),even);
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool even(int x)
{
return x%2?0:1;
}
void main()
{
vector<int> v;
for(int i=1;i<=10;i++)
v.push_back(i);
vector<int>::iterator ilocation,result;
cout<<" Remove front: ";
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
result=remove_if(v.begin(),v.end(),even);
cout<<" Removed: ";
for(ilocation=v.begin();ilocation!=result;ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
Eliminate the continuously repeating element unique
Function prototype: unique(v.biegin (),v.end());
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(2);
v.push_back(6);
v.push_back(6);
v.push_back(6);
v.push_back(9);
v.push_back(6);
v.push_back(3);
vector<int>::iterator ilocation,result;
result=unique(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=result;ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
Output: 2, 6, 9, 6, 3
Three, sorting algorithm
Create a heap make_heap
Push_heap (insert the last element by default)
3. Element out of heap pop_heap (like push_heap, pop_heap must be meaningful for heap operations)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(5);
v.push_back(6);
v.push_back(4);
v.push_back(8);
v.push_back(2);
v.push_back(3);
v.push_back(7);
v.push_back(1);
v.push_back(9);
make_heap(v.begin(),v.end());
v.push_back(20);
push_heap(v.begin(),v.end());
vector<int>::iterator ilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
pop_heap(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
4 heap sort sort_heap
Use:
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(3);
v.push_back(9);
v.push_back(6);
v.push_back(3);
v.push_back(17);
v.push_back(20);
v.push_back(12);
vector<int>::iterator ilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
Output results:
3, 9, 6, 3, 17, 20, 12
3, 3, 6, 9, 12, 17, 20
5 sort sort
Function prototype: sort(v.begin(),v.end());
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void main()
{
vector<int> v;
v.push_back(2);
v.push_back(8);
v.push_back(-15);
v.push_back(90);
v.push_back(26);
v.push_back(7);
v.push_back(23);
v.push_back(30);
v.push_back(-27);
v.push_back(39);
v.push_back(55);
vector<int>::iterator ilocation;
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
sort(v.begin(),v.end());//Comparison function default
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}