淺析STL中的常用算法

2020-01-26 15:49:17

字體：大中小

來源：轉載

供稿：網友

一、非變異算法

是一組不破壞操作數據的模板函數，用來對序列數據進行逐個處理、元素查找、子序列搜索、統計和匹配。非變異算法具有極為廣泛的適用性，基本上可應用與各種容器。

1查找容器元素find

它用于查找等于某值的元素。它在迭代器區間[first,last)(閉開區間)上查找等于value值的元素，如果迭代器i所指的元素滿足*i=value，則返回迭代器i；未找到滿足條件的元素，返回last。函數原型：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，檢查迭代器區間[first,last)(閉開區間)上的每一個元素，如果迭代器i滿足pred（*i）＝true，表示找到元素并返回迭代值i（找到的第一個符合條件的元素）；未找到元素，返回末位置last。函數原型：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統計等于某值的容器元素個數count

list<int> l;
count（l.begin（），l.end（），value）

4條件統計count_if

count_if（l.begin（），l.end()，pred）。謂詞pred含義同find_if中的謂詞。例子可以參考例2.

5子序列搜索search

search算法函數在一個序列中搜索與另一序列匹配的子序列。參數分別為一個序列的開始位置，結束位置和另一個序列的開始，結束位置。

函數原型：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算法函數搜索序列中是否有一系列元素值均為某個給定值的子序列。函數原型：search_n(v.begin(),v.end(),3,8)，在v中找到3個連續的元素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(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個連續的元素8"<<endl;

else

cout<<"在v中未找到3個連續的元素8"<<endl;

}

7最后一個子序列搜索find_end

函數原型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;

}

二、變異算法

是一組能夠修改容器元素數據的模板函數。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改變

函數原型：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

函數原型：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

函數原型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

函數原型：generate_n(v.begin(),5,rand);向從v.begin開始的后面5個位置隨機填寫數據。

復制代碼代碼如下:

#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（）值。

函數原型：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 剔除連續重復元素unique

函數原型：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(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、創建堆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

函數原型：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());//比較函數默認

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<' ';

cout<<endl;

}

上一篇：關于STL中vector容器的一些總結

下一篇：STl中的排序算法詳細解析

學習交流

羅技g502鼠標靈敏度怎么設置?

羅技g502鼠標靈敏度怎么設置?...

熱門圖片

猜你喜歡的新聞

猜你喜歡的關注

新聞熱點

淘寶春晚數據公布：660億人次互動清空購物車最高2.3萬元

2020-01-25 16:46:55

搜狐宣布私有化收購暢游預計二季度完成

2020-01-25 16:38:41

谷歌CEO：AI給人類文明帶來的影響將比火或電更深刻

2020-01-22 22:00:12

特斯拉市值首破1000億美元馬斯克成全美薪酬最高CEO

2020-01-22 21:50:38

劉熾平親述騰訊投資風向小程序生態影響投資決策

2020-01-21 18:21:45

達沃斯前瞻：阿里巴巴董事局主席張勇談平臺經濟普惠之道

2020-01-21 18:18:31

疑難解答

圖片精選

網友關注