🎺Algorithm

演算法

在STL中除了提供容器(類別樣板), 尚提供演算法(函式 樣板)以供操作之資料

需 include <algorithm>

常用演算法:

• find

• count

• search

• merge

• sort

• for_each

• transform

• upper_bound

• lower_bound

find

用法 :

find(first, last, val)

• [first]: iterator

• [last]: iterator

• [val]: target value type

• [回傳值]: iterator

針對某個container做搜尋,區間由first及last這兩個iterator指定,目標值為val,找到後回傳其所在元素指標(也是以iterator表示)，也就是尋找元素在容器中第一個出現的位子。

陣列搜尋

ex9.cpp

#include<iostream>
#include<algorithm>
using namespace std;
int main( )
{
    int l[7] = { 1, 3, 2, 5, 1, 2, 1 };
    int *it ;
    it = find(&l[0], &l[7], 5);
    if ( it == l+7)
        cout << "data not found\n" ;
    else
        cout << *it << endl;
    // output : 5
    return 0;
}

vector搜尋

ex10.cpp

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
int main( )
{
    list<int> L;
    list<int>::iterator it;
    L.push_back(10) ;
    L.push_back(20);
    L.push_back(30);
    it = find(L.begin( ), L.end( ), 30);
    if ( it == L.end( ))
        cout << "data not found\n";
    else
        cout << *it << endl;
    //output : 30
    return 0;
}

count

count(first, last, val)

• [first]: iterator

• [last]: iterator

• [val]: target value type

• [回傳值]: int

針對某個container做搜尋,區間由first及last這兩個iterator指定,目標值為val,回傳container中元素值為val的個數，也就是統計在容器中共有幾個「指定的元素」。

ex11.cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int a[7] = { 1, 3, 2, 4, 1, 2, 1};
    vector<int> v(a,a+7);
    int count_of_1;
    count_of_1 = count(v.begin(), v.end(), 1);
    cout << "count of 1 = " <<count_of_1<<endl;
    // output : count of 1 = 3
    return 0;
}

search

search(s_first , s_last , t_first , t_last)

• [s_first] [t_first] : iterator

• [s_last] [t_last] : iterator

• [回傳值] : iterator

找尋某一資料序列是否出現在另一個容器中。

範例 : list容器中做搜尋

ex12.cpp

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
int main( )
{
    int a[7] = { 1, 3, 2, 5, 1, 2, 1};
    vector<int> v(a,a+7) ;
    vector<int>::iterator it ;
    list<int> L ;
    L.push_back(5);
    L.push_back(1);
    L.push_back(2);
    it = search(v.begin(), v.end(), L.begin(), L.end());
    if (it != v.end()) //有找到
        cout << *it << " " << *(it+1) << " " << *(it+2) << endl ;
    // output : 5 1 2
    return 0;
}

merge

merge(s1_first, s1_last, s2_first, s2_last, t_first)

• [s1_first] [s2_first]: iterator

• [s1_last] [s2_last]: iterator

• [t_first] : iterator

• [回傳值] : iterator

合併s1與s2兩資料於t

ex13.cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main( )
{
    int a[7] = { 3, 2, 5, 1, 2, 1, 8 } ;
    int b[4] = { 1, 7, 4, 9 } ;
    vector<int> v1(a,a+7) ;
    vector<int> v2(b,b+4) ;
    vector<int> v3(v1.size() + v2.size()) ;
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(), v3.begin());
    for (int i=0 ; i<v3.size() ; i++ )
        cout << v3[i] << " " ;
    cout << endl;
    // output : 1 3 2 5 1 2 1 7 4 8 9
    return 0;
}

sort

sort(first, last)

• sort(first, last, f)

• [first]: iterator

• [last]: iterator

• [f]: 函式 (可有可無)

• [回傳值]: void

資料排序 (預設由小到大)

ex14.cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool mygreater(int x, int y) //←改成結構試試看
{
    return x>y;
}
int main()
{
    int a[7] = { 8, 1, 3, 2, 5, 1, 4};
    vector<int> v(a,a+7);
    vector<int>::iterator it ;
    sort(v.begin(), v.end()) ; //由小排到大
    for ( it = v.begin(); it != v.end() ; it++)
        cout << *it <<" ";
    cout << endl;
    // output : 1 1 2 3 4 5 8
    sort(v.begin(), v.end(), mygreater); //mygreater 由大排到小
    for ( it = v.begin( ); it != v.end() ; it++)
        cout << *it <<" ";
    cout << endl;
    // output : 8 5 4 3 2 1 1
    return 0;
}

for_each

for_each(first, last, f)

• [first] : iterator

• [last] : iterator

• [f] : 函式

• [回傳值] : 函數物件指標

對container中從first 所指的元素起到last為止,其間每一個元素做某個動作(由函數f指定)

ex15.cpp

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
void print(int &x)
{
    cout << x << " ";
}
void add(int &x)
{
    x = x+5;
}
int main( )
{
    list<int> L ;
    L.push_back(10);
    L.push_back(20) ;
    L.push_back(30) ;
    for_each(L.begin( ), L.end( ), print) ;
    cout << endl;
    for_each(L.begin( ), L.end( ), add) ;
    for_each(L.begin( ), L.end( ), print) ;
    cout << endl;
    return 0;
}
// output : 10 20 30
//          15 25 35

transform

transform(first, last, output, f)

• [first] : iterator

• [last] : iterator

• [output] : container

• [f] : 函式

• [回傳值] : 函數物件指標

同for_each,但會把結果放在output容器中

ex16.cpp

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
void print(int &x) {
    cout << x << " ";
}
int add(int x) {
    return x+5;
}
int main() {
    list<int> L;
    vector<int> v(3);
    L.push_back(10);
    L.push_back(20);
    L.push_back(30);
    transform(L.begin(), L.end(), v.begin(), add);
    for_each(L.begin(), L.end(), print);
    cout << endl;
    for_each(v.begin(), v.end(), print);
    cout << endl;
    return 0;
}
// output : 10 20 30
//          15 25 35

upper_bound & lower_bound

首先，使用的前提是排好序的非遞減陣列。lower_bound( )和upper_bound( )都是利用二分查詢的方法在一個排好序的陣列、容器中進行查詢的。

lower_bound( begin,end,num)：從陣列的begin位置到end-1位置二分查詢第一個大於或等於num的數字，找到返回該數字的地址，不存在則返回end。通過返回的地址減去起始地址begin,得到找到數字在陣列中的下標。

upper_bound( begin,end,num)：從陣列的begin位置到end-1位置二分查詢第一個大於num的數字，找到返回該數字的地址，不存在則返回end。通過返回的地址減去起始地址begin,得到找到數字在陣列中的下標。

ex17.cpp

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[1001]={1,1,2,3,4,5,7,8,10,15};
    sort(a,a+10);
    int l=lower_bound(a,a+10,5)-a;    
    //返回陣列中第一個大於或等於查詢數(5)的值
	int r=upper_bound(a,a+10,5)-a;    
	//返回陣列中第一個大於查詢數的值
    cout<<l<<" "<<a[l]<<endl;
    cout<<r<<" "<<a[r];
    return 0;
}
// output : 5 5
//          6 7