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?

Cherian

Answer 1

In C++11, you can use also 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; });

Feline

Answer 2

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.

Mathamathe

Does your solution use const reference? – Superstitious

@sehe:I meant the capture. I was just a little ironic. – Superstitious

@Superstitious It is const now :-) My understanding is that there is no mechanism to capture as "reference to const when the referee is not const in the context in which it is captured. – Mathamathe

It is my understanding as well. – Superstitious

If you can make the data sorted on the second field, perhaps replace with binary searching: coliru.stacked-crooked.com/a/710af000893f3d4b – Estrada

@Mathamathe It is my understanding that the reference is implicitly const - unless you would have marked the lambda as mutable :) But you knew that, right o.O – Estrada

@Estrada No, that was not what I knew. I thought there was some non-intuitive wishy-washiness that meant that in fact the reference is taken as non-const. Either that is right or my gcc (4.8.1.) and clang (3.4) are broken (and I hope they are, and that I am wrong, becuause I would not want this to be the correct behaviour.) – Mathamathe

@Mathamathe Wow. Now I'll have to check my understanding... :( Thanks for the heads up, will check things later. – Estrada

@Estrada By-reference captures are always non-const; it's the by-value captures that are const by default (because the lambda's operator() is const unless the lambda is declared mutable). – Angy

@Angew Ah. I'd almost say /WHY/, but I remembered: c++ :) (I understand why, in case you were going to explain :)) – Estrada

Answer 3

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

Estrada

+1, but I believe you mean flat_(multi)map, not flat_(multi_)map ;) – Gamble

Answer 4

I think that you should use an std::map instead, which will provide a preffy efficient std::map::find member function:

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

This is as efficient as it goes for this kind of lookup (which is guaranteed to be O(log(N))).

Gamble

+1 for the observation. The have-your-cake-and-eat-it approach is in my answer now. – Estrada