查找向量是否包含第二个元素等于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

在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 2

如果您只想知道是否存在满足您的标准的元素，那么您的解决方案看起来很好。我会在循环中使用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 3

事实上，如果你可以根据vector字段对second对进行排序，你可以吃蛋糕并吃掉它。

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

看到它Live On 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 4

我认为你应该使用std::map代替，这将提供一个蓬松有效的std::map::find成员函数：

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

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