9

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?

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
valentin
  • 2,596
  • 6
  • 28
  • 48

4 Answers4

11

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.

juanchopanza
  • 223,364
  • 34
  • 402
  • 480
  • Does your solution use const reference? – user2672165 Apr 19 '14 at 19:38
  • @sehe:I meant the capture. I was just a little ironic. – user2672165 Apr 19 '14 at 19:40
  • @user2672165 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. – juanchopanza Apr 19 '14 at 19:47
  • It is my understanding as well. – user2672165 Apr 19 '14 at 19:49
  • If you can make the data sorted on the `second` field, perhaps replace with binary searching: http://coliru.stacked-crooked.com/a/710af000893f3d4b – sehe Apr 19 '14 at 19:51
  • @juanchopanza 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 – sehe Apr 19 '14 at 19:51
  • @sehe 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.) – juanchopanza Apr 19 '14 at 20:01
  • @juanchopanza Wow. Now I'll have to check my understanding... :( Thanks for the heads up, will check things later. – sehe Apr 19 '14 at 20:14
  • 1
    @sehe 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`). – Angew is no longer proud of SO Apr 19 '14 at 20:25
  • @Angew Ah. I'd almost say /WHY/, but I remembered: [tag:c++] :) (I understand why, in case you were going to explain :)) – sehe Apr 19 '14 at 20:25
4

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
sehe
  • 374,641
  • 47
  • 450
  • 633
3

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; });
Daniel Laügt
  • 1,097
  • 1
  • 12
  • 17
2

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

Shoe
  • 74,840
  • 36
  • 166
  • 272
  • +1 for the observation. The have-your-cake-and-eat-it approach is in [my answer](http://stackoverflow.com/a/23174763/85371) now. – sehe Apr 19 '14 at 19:56