C++ STL find和find_if算法与bind、lambda组合使用

直接上代码，使用std::find、std::find_if来搜索匹配，代码确实比for循环变少和更好看了，但是时间复杂度还是O(n)，见下文。

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

class Item {
 private:
  int mId;
  std::string mName;

 public:
  Item(int id, std::string name) : mId(id), mName(name) {}

  std::string getName() const { return mName; }

  int getId() const { return mId; }

  bool operator==(const Item& obj2) const {
    return (this->getName().compare(obj2.getName()) == 0) &&
           (this->getId() == obj2.getId());
  }

  static bool Compare(const Item& obj1, const Item& obj2) {
    return (obj1.getName().compare(obj2.getName()) == 0) &&
           (obj1.getId() == obj2.getId());
  }
};

#define log(obj, pos)                                                      \
  do {                                                                     \
    if (it != sItemList.end()) {                                           \
      std::cout << "Found obj " << obj.getName() << ", id:" << it->getId() \
                << ",name: " << it->getName() << ",position:" << pos       \
                << std::endl;                                              \
    } else {                                                               \
      std::cout << "Not Found obj" << std::endl;                           \
    }                                                                      \
  } while (false)

std::vector<Item> sItemList = {{0, "A"}, {1, "B"}, {2, "C"}, {3, "D"}, {4, "E"},
                               {5, "E"}, {6, "G"}, {7, "H"}, {1, "B"}};

int main() {
  Item obj1(1, "B");
  Item obj2(8, "I");
  Item obj3(5, "E");
  Item obj4(7, "H");

  std::cout << "obj1 is equal obj1 : " << (obj1 == obj1) << std::endl;
  std::cout << "obj1 is equal obj2 : " << (obj1 == obj2) << std::endl;

  // 1. std::find 类重载运算符==，使用默认的比较函数查找等于的项
  std::vector<Item>::iterator it =
      std::find(sItemList.begin(), sItemList.end(), obj1);
  log(obj1, std::distance(sItemList.begin(), it));

  // 2. std::find 类重载运算符==，使用默认的比较函数d方向查找等于的项
  std::vector<Item>::reverse_iterator rit =
      std::find(sItemList.rbegin(), sItemList.rend(), obj1);
  log(obj1, (sItemList.size() - std::distance(sItemList.rbegin(), rit)));

  // 3. std::find_if 使用自定义的函数查找符合要求的项
  it = std::find_if(sItemList.begin(), sItemList.end(),
                    std::bind(Item::Compare, std::placeholders::_1, obj3));
  log(obj3, std::distance(sItemList.begin(), it));

  // 4. std::find_if使用 lambda 表达式查找符合的项
  it = std::find_if(
      sItemList.begin(), sItemList.end(),
      [&obj4](Item const& obj) { return Item::Compare(obj, obj4); });
  log(obj4, std::distance(sItemList.begin(), it));

  return 0;
}

编译运行结果：

$ g++ std_find.cpp  --std=c++11;./a.out
obj1 is equal obj1 : 1
obj1 is equal obj2 : 0
Found obj B, id:1,name: B,position:1
Found obj B, id:1,name: B,position:9
Found obj E, id:5,name: E,position:5
Found obj H, id:7,name: H,position:7

std::find算法的行为如下所示，时间复杂度为O(n):

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;
}