STL演算法和容器中的成員方法同名時，該如何選擇？

通過前面的學習，我們已經掌握了一些 STL 演算法的功能和用法。值得一提的是，STL 標準庫提供有 70 多種演算法函數，其中有些函數名稱和 STL 容器模板類中提供的成員方法名相同。

例如，STL 標準庫提供了 sort() 和 merge() 函數，而 list 容器模板類中也提供有同名的 sort() 和 merge() 成員方法。再比如，STL 標準庫提供有 count()、find()、lower_bound()、upper_bound() 以及 equal_range() 這些函數，而每個關聯式容器（除雜湊容器外）也提供有相同名稱的成員方法。

那麼，當某個 STL 容器提供有和演算法同名的成員方法時，應該使用哪一個呢？大多數情況下，我們應該使用 STL 容器提供的成員方法，而不是同名的 STL 演算法，原因包括：

雖然同名，但它們的底層實現並不完全相同。相比同名的演算法，容器的成員方法和自身結合地更加緊密。
相比同名的演算法，STL 容器提供的成員方法往往執行效率更高；

舉個例子：

#include <iostream>    // std::cout
#include <algorithm>   // std::find
#include <set>         // std::set
#include <string>      // std::string
using namespace std;
//為 set 容器自定義排序規則，即按照字串長度進行排序
class mycomp {
public:
    bool operator() (const string &i, const string &j) const {
        return i.length() < j.length();
    }
};

int main() {
//定義 set 容器，其排序規則為 mycomp
    std::set<string,mycomp> myset{"123","1234","123456"};
    //呼叫 set 容器成員方法
    set<string>::iterator iter = myset.find(string("abcd"));
    if (iter == myset.end()) {
        cout << "查詢失敗" << endl;
    }
    else {
        cout << *iter << endl;
    }

    //呼叫 find() 函數
    auto iter2 = find(myset.begin(), myset.end(), string("abcd"));
    if (iter2 == myset.end()) {
        cout << "查詢失敗" << endl;
    }
    else {
        cout << *iter << endl;
    }
    return 0;
}

程式執行結果為：

1234
查詢失敗

可以看到，程式中分別呼叫了 find() 函數和 set 容器自帶的 find() 成員方法，都用於查詢 "abcd" 這個字串，但查詢結果卻不相同。其中，find() 成員方法成功找到了和 "abcd" 長度相同的 "1234"，但 find() 函數卻查詢失敗。

之所以會這樣，是因為 find() 成員方法和 find() 函數底層的實現機制不同。前者會依照 mycomp() 規則查詢和 "abcd" 匹配的元素，而 find() 函數底層僅會依據 "==" 運算子查詢 myset 容器中和 "abcd" 相等的元素，所以會查詢失敗。

不僅如此，無論是序列式容器還是關聯式容器，成員方法的執行效率要高於同名的 STL 演算法。仍以 find() 函數和 set 容器中的 find() 成員方法為例。要知道，find() 函數是通過“逐個比對”來實現查詢的，它以線性時間執行；而由於 set 容器底層儲存結構採用的是紅黑樹，所以 find() 成員方法以對數時間執行，而非線性時間。

換句話說，對於含有一百萬個元素的 set 容器，如果使用 find() 成員方法查詢目標元素，其最差情況下的比對次數也不會超過 40 次（平均只需要比對 20 次就可以查詢成功）；而使用同名的 find() 函數查詢目標元素，最差情況下要比對一百萬次（平均比對 50 萬次才能查詢成功）。

所謂“最差情況”，指的是當前 set 容器中未儲存有目標元素。

並且需要注意的一點是，雖然有些容器提供的成員方法和某個 STL 演算法同名，但該容器只能使用自帶的成員方法，而不適用同名的 STL 演算法。比如，sort() 函數根本不能應用到 list 容器上，因為該型別容器僅支援雙向疊代器，而 sort() 函數的引數型別要求為隨機存取疊代器；merge() 函數和 list 容器的 merge() 成員方法之間也存在行為上的不同，即 merge() 函數是不允許修改源資料的，而 list::merge() 成員方法就是對源資料做修改。

總之，當讀者需要在 STL 演算法與容器提供的同名成員方法之間做選擇的時候，應優先考慮成員方法。幾乎可以肯定地講，成員方法的效能更優越，也更貼合當前要操作的容器。