查找向量中是否包含第二个元素等于X的对。

Question

我有一个向量：

using namespace std;

vector< pair<short, string> > vec = {};

我想找出是否存在一对 <a, b> 满足 b == X。

我知道有一个来自 <algorithm> 的 std::find，但不知道如何在这里应用它。

我应该编写自己的函数来完成这个任务吗？

bool is_in_vec(X)
{
    for (auto& e : vec)
        if (e.second == X)
            return true;
    return false;
}

这是否高效？

- valentin

Answer 1

如果您只想知道是否存在满足条件的元素，则您的解决方案看起来不错。在循环中，我会使用const引用，因为循环不应更改向量的元素：

for (const auto& e : vec) ....

如果你想使用标准库算法，可以尝试使用 std::find_if：

const std::string X{"foobar"};

auto it = std::find_if(vec.begin(), 
                       vec.end(), 
                      [&X](const pair<short, string>& p)
                      { return p.second == X; });

这里的it是指满足条件的第一个元素的迭代器，如果没有找到元素，则等于vec.end().

- juanchopanza

---

谢谢，这就是我要找的。 - valentin

@sehe：我指的是捕获。我只是有点讽刺。 - user2672165

现在它是“const”了 :-) 我的理解是，在捕获时，当引用者不是“const”时，没有机制可以将其捕获为“const”参考。 - juanchopanza

我也是这样理解的。 - user2672165

@sehe 按引用捕获总是非 const 的；默认情况下是按值捕获是 const 的（因为 lambda 的 operator() 是 const 的，除非 lambda 被声明为 mutable）。 - Angew is no longer proud of SO

Answer 2

事实上，如果你可以自由地按照第二个字段对成对的vector进行排序，那么你就可以既拥有蛋糕，又能吃到它。

在这种情况下，你最终会重新发明Boost称之为“flat_(multi_)map”的东西。显而易见的好处是，搜索可以在O(log(n))的时间内完成，而不是线性时间。

在Coliru上查看实现：实时演示。

using namespace std;

#include <utility>
#include <vector>
#include <string>
#include <algorithm>

typedef std::pair<short, std::string> Pair;

struct Cmp 
{
    bool operator()(Pair const& a, Pair const& b) const { return a.second < b.second; };
    bool operator()(Pair const& a, std::string const& b) const { return a.second < b; };
    bool operator()(std::string const& a, Pair const& b) const { return a < b.second; };
};

int main()
{
    std::vector<Pair> vec = { 
        { 1, "aap" }, 
        { 2, "zus" }, 
        { 3, "broer" }
    };

    Cmp cmp;
    std::sort(vec.begin(), vec.end(), cmp);

    auto it = std::binary_search(vec.begin(), vec.end(), std::string("zus"), cmp);

    std::cout << it->first << ": " << it->second << "\n";
}

打印

2: zus
42: zus

- sehe

---

+1，但我想您是指flat_(multi)map，而不是flat_(multi_)map ;) - Shoe

Answer 3

在C++11中，你也可以使用std::any_of。

std::string X{"foobar"};
return std::any_of(vec.begin(), vec.end(),
                   [&X](const pair<short, string>& p)
                   { return p.second == X; });

- Daniel Laügt

Answer 4

我认为你应该使用一个std::map，它将提供一个相当高效的std::map::find成员函数。请注意保留HTML标记。

std::map<std::string, short>
// …
auto it = map.find(X);

这是这种查找方式的最高效率（保证为O(log(N))）。

- Shoe

---

+1 对这个观察。现在“既要拥有蛋糕，还想吃蛋糕”的方法已经在我的答案中了。 - sehe