c++ - C++ 在 std::vector 中搜索

Question

假设我有一个这样的向量：

vector< pair<string, pair<int, int> > > cont;

现在我想cont找到first等于的元素"ABC"。如何使用 STL 提供给我们的函子和算法（find_if、is_equal??）轻松做到这一点。（请不要使用 Boost，也不要使用新的 C++。）

编辑：是否可以不定义谓词函子？

Answer 1

就像是

typedef std::pair<std::string, std::pair<int, int> > pair_t;

struct Predicate : public std::unary_function<pair_t, bool>
{
public:
   Predicate(const std::string& s):value(s) { }
   result_type operator () (const argument_type& pair)
   {
      return pair.first == value;
   }
private:
   std::string value;
};

std::vector<pair_t>::const_iterator pos = std::find_if(cont.begin(), cont.end(),
Predicate("ABC"));

或 lambda，如果是 C++11。

auto pos = std::find_if(cont.begin(), cont.end(),
[](const std::pair<std::string, std::pair<int, int>>& pair)
{
    return pair.first == "ABC";
});

真的，有一种不好的方法来做这样的事情，没有结构。

typedef std::pair<std::string, std::pair<int, int> > pair_t;

namespace std {
template<>
bool operator ==<> (const pair_t& first, const pair_t& second)
{
   return first.first == second.first;
}
}

std::vector<pair_t>::const_iterator pos = std::find_if(cont.begin(), cont.end(),
std::bind2nd(std::equal_to<pair_t>(), std::make_pair("ABC", std::make_pair(1, 2))));

Answer 2

如果您需要比O(N)搜索更快的速度，您可以vector 用map（或添加并行）O(log N)搜索（或O(1)用unordered_map）替换，不需要仿函数：

vector<pair<string, pair<int,int>>>  cont {{"ABC",{1,11}}, {"DFG",{2,22}}};
map        <string, pair<int,int>>   M(cont.begin(), cont.end());
cout << M["ABC"] << endl;

并使用RO 库（可耻的插件），这将是：

#include <sto/sto.h>
using namespace sto;

...
auto it = cont / (_0=="ABC");

这里/重载了内部调用的 op find_if; _0- 在 STO lambda 表达式中引用元组（或对）的第一个元素；_0=="ABC"- 生成谓词的 lambda 表达式find_if