淺析STL中的常用算法
一、非變異算法
是一組不破壞操作數(shù)據(jù)的模板函數(shù)，用來對序列數(shù)據(jù)進行逐個處理、元素查找、子序列搜索、統(tǒng)計和匹配。非變異算法具有極為廣泛的適用性，基本上可應用與各種容器。
1查找容器元素find
它用于查找等于某值的元素。它在迭代器區(qū)間[first,last)(閉開區(qū)間)上查找等于value值的元素，如果迭代器i所指的元素滿足*i=value，則返回迭代器i；未找到滿足條件的元素，返回last。函數(shù)原型：find( v1.begin(), v1.end(), num_to_find );
#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 << "未找到任何元素匹配 " << num_to_find << endl;
else
cout << "匹配元素的索引值是 " << result-v1.begin() << endl;
}
2條件查找容器元素find_if
利用返回布爾值的謂詞判斷pred，檢查迭代器區(qū)間[first,last)(閉開區(qū)間)上的每一個元素，如果迭代器i滿足pred（*i）＝true，表示找到元素并返回迭代值i（找到的第一個符合條件的元素）；未找到元素，返回末位置last。函數(shù)原型：find_if(v.begin(),v.end(),divby5);
#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<<"找到第一個能被5整除的元素："<<*ilocation<<endl<<"元素的索引位置是： "<<ilocation-v.begin()<<endl;
}
3統(tǒng)計等于某值的容器元素個數(shù)count
list<int> l;
count（l.begin（），l.end（），value）
4條件統(tǒng)計count_if
count_if（l.begin（），l.end()，pred）。謂詞pred含義同find_if中的謂詞。例子可以參考例2.
5子序列搜索search
search算法函數(shù)在一個序列中搜索與另一序列匹配的子序列。參數(shù)分別為一個序列的開始位置，結束位置和另一個序列的開始，結束位置。
函數(shù)原型：search(v1.begin(),v1.end(),v2.begin(),v2.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);
//注意：v1定義時沒有給定大小，因此這里不能直接使用賦值語句。
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的元素包含在v1中，起始元素為"<<"v1["<<ilocation-v1.begin()<<']'<<endl;
else
cout<<"v2的元素不包含在v1中"<<endl;
}
6重復元素子序列搜索search_n
search_n算法函數(shù)搜索序列中是否有一系列元素值均為某個給定值的子序列。函數(shù)原型：search_n(v.begin(),v.end(),3,8)，在v中找到3個連續(xù)的元素8
#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<<"在v中找到3個連續(xù)的元素8"<<endl;
else
cout<<"在v中未找到3個連續(xù)的元素8"<<endl;
}
7最后一個子序列搜索find_end
函數(shù)原型find_end(v1.begin(),v1.end(),v2.begin(),v2.end());在V1中要求的位置查找V2中要求的序列。
#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中找到最后一個匹配v2的子序列，位置在" <<"v1["<<i-v1.begin()<<"]"<<endl;
}
二、變異算法
是一組能夠修改容器元素數(shù)據(jù)的模板函數(shù)。copy(v.begin(),v.end(),l.begin());將v中的元素復制到l中。
1 元素復制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;
}
2 元素變換transform改變
函數(shù)原型：transform(v.begin(),v.end(),l.begin(),square);也是復制，但是要按某種方案復制。
#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 替換replace
replace算法將指定元素值替換為新值。
#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;
}
輸出結果為13 100 27 100 29
4 條件替換replace_if
函數(shù)原型：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;
}
5 n次填充fill_n
函數(shù)原型fill_n(v.begin(),5,-1)；向從v.begin開始的后面5個位置跳入-1
#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;
}
輸出結果：-1 -1 -1 -1 -1 0 0 0 0 0
6 隨機生成n個元素generate
函數(shù)原型：generate_n(v.begin(),5,rand);向從v.begin開始的后面5個位置隨機填寫數(shù)據(jù)。
#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;
}
7 條件移除remove_if
返回值相當于移除滿足條件的元素后形成的新向量的end（）值。
函數(shù)原型：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<<"移除前：";
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
result=remove_if(v.begin(),v.end(),even);
cout<<"移除后：";
for(ilocation=v.begin();ilocation!=result;ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
8 剔除連續(xù)重復元素unique
函數(shù)原型：unique(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(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;
}
輸出結果：2 6 9 6 3
三、排序算法
1、創(chuàng)建堆make_heap
2、元素入堆push_heap（默認插入最后一個元素）
3、元素出堆pop_heap（與push_heap一樣，pop_heap必須對堆操作才有意義）
#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 堆排序sort_heap
使用：
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;
}
輸出結果：
3 9 6 3 17 20 12
3 3 6 9 12 17 20
5 排序sort
函數(shù)原型：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());//比較函數(shù)默認
for(ilocation=v.begin();ilocation!=v.end();ilocation++)
cout<<*ilocation<<' ';
cout<<endl;
}
相關文章
本文主要介紹了C++?手擼簡易服務器，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
C語言數(shù)據(jù)結構中約瑟夫環(huán)問題探究
這篇文章主要介紹了C語言數(shù)據(jù)結構中約瑟夫環(huán)問題，總的來說這并不是一道難題，那為什么要拿出這道題介紹？拿出這道題真正想要傳達的是解題的思路，以及不斷優(yōu)化探尋最優(yōu)解的過程。希望通過這道題能給你帶來一種解題優(yōu)化的思路2023-01-01
這篇文章主要介紹了帶頭結點單鏈表?(詳解),需要的朋友可以參考下2023-07-07
深拷貝和淺拷貝可以簡單理解為：如果一個類擁有資源，當這個類的對象發(fā)生復制過程的時候，資源重新分配，這個過程就是深拷貝，反之，沒有重新分配資源，就是淺拷貝2013-09-09
如何選擇合適的C++/C語言書籍，是不是已經眼花繚亂，不知道該選擇哪本好了呢？今天我來為大家分享兩本不可錯過的優(yōu)秀書籍2017-09-09
本篇文章是對Visual C++進行串口通信編程進行了詳細的分析介紹，需要的朋友參考下2013-05-05
C++與QML進行數(shù)據(jù)交互實現(xiàn)方式介紹
迫于無奈開始寫android的程序，以前使用QWidget的方式試過，雖然界面可以實現(xiàn)，但是最后調用攝像頭時，未能成功，再沒有繼續(xù)。這幾天開始使用qml進行嘗試，在使用的過程中，其中的一個難點，就是在qml與c++中數(shù)據(jù)的交互2022-09-09
本文給大家介紹的是在C++中實現(xiàn)高效的vector四則運算的方法的相關資料,需要的朋友可以參考下2016-07-07
相對于其他語言來說，C語言的關鍵字算是少的了。在C98中關鍵子總共只有32個，我們來分析一下部分關鍵字在C/C++中它獨特的作用2022-05-05
本文主要介紹了HLSL實現(xiàn)簡單的圖像處理功能的方法，具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02