C++ search in an std::vector

Question

Say I have a vector like this:

vector< pair<string, pair<int, int> > > cont;

Now I want in the cont find the elem which has its first equal to "ABC". How can I do this easily with the functors and algorithms that STL provides us with (find_if, is_equal??). (No Boost please and no new C++.)

EDIT: Is it possible to do without defining a Predicate functor?

Answer 1

Something like

typedef std::pair<std::string, std::pair<int, int> > pair_t;

struct Predicate : public std::unary_function<pair_t, bool>
{
public:
   Predicate(const std::string& s):value(s) { }
   result_type operator () (const argument_type& pair)
   {
      return pair.first == value;
   }
private:
   std::string value;
};

std::vector<pair_t>::const_iterator pos = std::find_if(cont.begin(), cont.end(),
Predicate("ABC"));

or lambda, if C++11.

auto pos = std::find_if(cont.begin(), cont.end(),
[](const std::pair<std::string, std::pair<int, int>>& pair)
{
    return pair.first == "ABC";
});

really, there is one not-good way to do such thing, without struct.

typedef std::pair<std::string, std::pair<int, int> > pair_t;

namespace std {
template<>
bool operator ==<> (const pair_t& first, const pair_t& second)
{
   return first.first == second.first;
}
}

std::vector<pair_t>::const_iterator pos = std::find_if(cont.begin(), cont.end(),
std::bind2nd(std::equal_to<pair_t>(), std::make_pair("ABC", std::make_pair(1, 2))));

Answer 2

If you need faster than O(N) search, you can replace vector with map (or add parallel) for O(log N) search (or O(1) with unordered_map), no functor is needed:

vector<pair<string, pair<int,int>>>  cont {{"ABC",{1,11}}, {"DFG",{2,22}}};
map        <string, pair<int,int>>   M(cont.begin(), cont.end());
cout << M["ABC"] << endl;

And using RO library (shameful plug), this will be just:

#include <sto/sto.h>
using namespace sto;

...
auto it = cont / (_0=="ABC");

Here / overloaded op which internally calls find_if; _0 - reference to first element of tuple (or pair) in STO lambda expression; _0=="ABC" - lambda expression which generates predicate for find_if