locator - Búsqueda en C++ en un std:: vector

my ip location

Question

Digamos que tengo un vector como este:

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

Ahora quiero encontrar el elem que tiene el first igual a "ABC" . ¿Cómo puedo hacer esto fácilmente con los funtores y algoritmos que STL nos proporciona (find_if, is_equal ??). (Sin Boost por favor y sin C ++ nuevo)

EDITAR: ¿Es posible prescindir de definir un functor Predicado?

Answer 1

Algo como

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"));

o lambda, si 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";
});

realmente, hay una manera no-buena de hacer tal cosa, sin 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

Si necesita una búsqueda más rápida que O(N) , puede reemplazar vector con map (o agregar paralelo) para búsqueda O(log N) (u O(1) con map unordered_map ), no se necesita un functor:

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;

Y usando la biblioteca RO (plug vergonzoso), esto será justo:

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

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

Here / overloaded op que internamente llama a find_if ; _0 - referencia al primer elemento de la tupla (o par) en la expresión STO lambda; _0=="ABC" - expresión lambda que genera un predicado para find_if