Find if vector contains pair with second element equal to X

Question

I have this vector:

using namespace std;

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

And I want to find out if exists a pair <a, b> with b == X.

I know about std::find from <algorithm> but don't know how to apply it here.

Should I write my own function to do that?

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

Is that efficient?

Answer 1

Your solution looks fine if you only want to know if there is an element satisfying your criteria present. I would use const references in the loop, because the loop should not change the elements of the vector:

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

If you want to use a standard library algorithm, you can try 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; });

Here, it is an iterator to the first element satisfying the condition, or equal to vec.end() if no element is found.

Answer 2

In fact you can have your cake and eat it, if you are free to sort the vector of pairs based on the second field.

In this case you end up reinventing what Boost calls flat_(multi_)map. The obvious benefit is that searching can be done in O(log(n)) instead of linear time.

See it 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";
}

Prints

2: zus
42: zus