STL演算法詳解 - tw511教學網

STL 提供能在各種容器中通用的演算法（大約有70種），如插入、刪除、查詢、排序等。演算法就是函數模板。演算法通過疊代器來操縱容器中的元素。

許多演算法操作的是容器上的一個區間（也可以是整個容器），因此需要兩個引數，一個是區間起點元素的疊代器，另一個是區間終點元素的後面一個元素的疊代器。例如，排序和查詢演算法都需要這兩個引數來指明待排序或待查詢的區間。

有的演算法返回一個疊代器。例如，find 演算法在容器中查詢一個元素，並返回一個指向該元素的疊代器。

演算法可以處理容器，也可以處理普通的陣列。

有的演算法會改變其所作用的容器。例如：

copy：將一個容器的內容複製到另一個容器。
remove：在容器中刪除一個元素。
random_shuffle：隨機打亂容器中的元素。
fill：用某個值填充容器。

有的演算法不會改變其所作用的容器。例如：

find：在容器中查詢元素。
count_if：統計容器中符合某種條件的元素的個數。

STL 中的大部分常用演算法都在標頭檔案 algorithm 中定義。此外，標頭檔案 numeric 中也有一些演算法。

下面介紹一個常用演算法 find，以便對演算法是什麼、怎麼用有一個基本的概念。find 演算法和其他演算法一樣都是函數模板。find 模板的原型如下：

template <class InIt, class T>
InIt find(InIt first, InIt last, const T& val);

其功能可以是在疊代器 first、last 指定的容器的一個區間 [first, last) 中，按順序查詢和 val 相等的元素。如果找到，就返回該元素的疊代器；如果找不到，就返回 last。

[first, last) 這個區間是一個左閉右開的區間，即 last 指向的元素其實不在此區間內。

find 模板使用==運算子判斷元素是否相等。因此，如果 [first, last) 區間中存放的是物件，則==運算子應該被適當過載，使得兩個物件可以用==運算子比較。

注意：上一段話說的是“其功能可以是”，而不是“其功能就是”。這是因為模板只是一種程式碼形式，這種程式碼形式具體能完成什麼功能，取決於程式設計師對該模板寫法的了解及其想象力。按照語法，呼叫 find 模板時，first 和 last 只要型別相同就可以，不一定必須是疊代器。

演示 find 用法的程式如下：

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()  {
    int a[10] = {10,20,30,40};
    vector<int> v;
    v.push_back(1);    v.push_back(2);
    v.push_back(3);    v.push_back(4); //此後v裡放著4個元素：1,2,3,4
    vector<int>::iterator p;
    p = find(v.begin(),v.end(),3); //在v中查詢3
    if(p != v.end()) //若找不到,find返回 v.end()
        cout << "1) " <<  * p << endl; //找到了
    p = find(v.begin(),v.end(),9);
    if(p == v.end())
        cout << "not found " << endl; //沒找到
    p = find(v.begin()+1,v.end()-1,4); //在,3 這兩個元素中查詢4
    cout << "2) " << * p << endl;
    int * pp = find(a,a+4,20);
    if(pp == a + 4)
        cout << "not found" << endl;
    else
        cout << "3) " <<* pp << endl;
}

程式的輸出結果是：
1) 3
not found
2) 4
3) 20

第 11 行，要查詢的區間是 [v.begin(), v.end( ))，v.end() 不在查詢範圍內，因此沒有問題。本行的查詢會成功，因此 p 指向找到的元素 3。

第 17 行，因為要查詢的區間是 [v.begin()+l，v.end()-1)，這個區間中只有 2、3 這兩個元素，因此查詢會失敗，p 的值變為 v.end() - 1，因此 p 正好指向 4 這個元素。

第 19 行，陣列 a 是一個容器。陣列名 a 的型別是 int *，可以做疊代器使用，表示式a+4的型別也是 int*，因此也能做疊代器。本次呼叫 find,查詢區間是 [a, a+4)，即陣列 a 的前 4 個元素。如果查詢失敗，find 就會返回 a+4。

STL 中還有一個常用的演算法 sort，用於對容器排序，其原型為：

template<class_RandIt>
void sort(_RandIt first, _RandIt last);

該演算法可以用來對區間 [first, last) 從小到大進行排序。下面兩行程式就能對陣列 a 排序：

int a[4] = {3, 4, 2, 1};
sort(a, a+4);