标准库之 find() 和 find_if() 函数_list find_if 与 find 哪个效率高

0.1.1 标准库之 find 和 find_if 函数

find_if()

1 find()

C++ 标准库中的 find，find_if 函数可以用于对数组、容器等进行查找。
http://www.cplusplus.com/reference/algorithm/find/

头文件

1	#include <algorithm>

声明

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
//实现
template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

find 函数在 [first,last) 范围内，查找是否有值为 val 的位置，val 必须要能支持 operator==。

所以对于容器中的元素是基本类型时，可以直接使用 find 函数。
例如

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
int main() {
    list<int> lst{1,2,3,4};
    list<int>::iterator it = find(lst.begin(), lst.end(), 2); // 查找list中是否有元素“2”
    if (it != lst.end()) // 找到了
    {
        cout<<"find it"<<endl;
    }
    else // 没找到
    {
        cout<<"not find"<<endl;
    }
    system("pause");
    return 0;
}

如果容器里的元素是一个类，则需要对该类重载 == 操作符, 然后在用 find 查找，
例如

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;

class Person
{
public:
    Person(string name):m_name(name){}
    ~Person(void){}

public:
    string m_name; // 姓名

bool operator==(const Person& rhs) const{
    return (m_name==rhs.m_name);
}
};

int main() {
    list<Person> lst{Person("Mike"),Person("John"),Person("Bobby")};

    Person one("John");
    list<Person>::iterator it = find(lst.begin(), lst.end(), one); // 查找list中是否有元素one

    if (it != lst.end()) // 找到了
    {
        cout<<"find it"<<endl;
    }
    else // 没找到
    {
        cout<<"not find"<<endl;
    }
    system("pause");
    return 0;
}

2 find_if()

还有一种情况是，容器中是一个指向类的指针，那怎么查找呢？
注意我们想比较的是指针指向的对象是否相等，而不是指针本身。

例如 list<Person*>, 这个 list 中的每一个元素都是一个对象的指针，我们要在这个 list 中查找是否存在该指针指向的对象与给定对象相等（当然，这里对象相等由你自定义其含义），找到就返回指向该对象的指针。

这时候，不能再使用 find 函数了，因为比较的是 list<Person> 的元素 Person, 即它比较的是指针是否相等，这往往不是我们想要的。

这里，我们需要使用 find_if 函数
参考：http://www.cplusplus.com/reference/algorithm/find_if/

头文件

1	#include <algorithm>

定义

template <class InputIterator, class UnaryPredicate>
   InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
   
//实现
template<class InputIterator, class UnaryPredicate>
  InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    if (pred(*first)) return first;
    ++first;
  }
  return last;
}

find_if 在 [first,last) 范围内查找能使得 pred 返回 true 的值，并返回指向该值的迭代器。

所以我们先在外面定义一个的函数对象 fun, 如下

//函数对象
typedef struct fun{
    fun(string name):m_name(name){};
    bool operator()(Person* rhs)const {
        return (m_name==rhs->m_name);
    }
private:
    string m_name;
}fun;

然后利用 find_if() 函数查找，

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;

class Person
{
public:
    Person(string name):m_name(name){}
    ~Person(void){}

public:
    string m_name; // 姓名
};

//函数对象
typedef struct fun{
    fun(string name):m_name(name){};
    bool operator()(Person* rhs)const {
        return (m_name==rhs->m_name);
    }
private:
    string m_name;
}fun;

int main() {
    list<Person*> lst{new Person("Mike"),new Person("John"),new Person("Bobby")};

    list<Person*>::iterator it = find_if(lst.begin(), lst.end(), fun("John")); // 查找list中是否有元素能够使得fun(*it)返回true

    if (it != lst.end()) // 找到了
    {
        cout<<"find it"<<endl;
    }
    else // 没找到
    {
        cout<<"not find"<<endl;
    }

    //释放内存
    for(auto& i:lst){
        delete i;
        i=nullptr;
    }

    system("pause");
    return 0;
}