首页 > 编程笔记 > C++笔记

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 算法与容器提供的同名成员方法之间做选择的时候，应优先考虑成员方法。几乎可以肯定地讲，成员方法的性能更优越，也更贴合当前要操作的容器。

STL算法和容器中的成员方法同名时，该如何选择？

所有教程

优秀文章