c++ - 查找向量是否包含第二个元素等于 X 的对

Question

我有这个向量：

using namespace std;

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

我想知道是否存在一<a, b>对b == X。

我知道std::find从<algorithm>但不知道如何在这里应用它。

我应该编写自己的函数来做到这一点吗？

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

那效率高吗？

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()

Answer 2

事实上，如果您可以vector根据second领域自由地对配对进行分类，您可以吃蛋糕并吃掉它。

在这种情况下，您最终会重新发明 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

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

Answer 4

我认为您应该使用 an std::map，它将提供一个高效的std::map::find成员函数：

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

这与这种查找一样有效（保证是O(log(N))）。