c++ - Inserción en un desordenado_set con función hash personalizada

c++11 unordered-set

Question

Tengo el siguiente código para hacer un unordered_set<Interval> . Esto compila bien.

struct Interval {
  unsigned int begin;
  unsigned int end;
  bool updated;   //true if concat.  initially false
  int patternIndex;  //pattern index. valid for single pattern
  int proteinIndex;   //protein index.  for retrieving the pattern
};

struct Hash {
  size_t operator()(const Interval &interval);
};

size_t Hash::operator()(const Interval &interval){
  string temp = to_string(interval.begin) + to_string(interval.end) + to_string(interval.proteinIndex);
  return hash<string>()(temp);
}

unordered_set<Interval, string, Hash> test;

Sin embargo, no puedo compilar cuando intento insertar usando este código:

for(list<Interval>::iterator i = concat.begin(); i != concat.end(); ++i){
  test.insert((*i));
}

Además, no puedo determinar cuál es el problema de los mensajes de error, por ejemplo:

note: candidate is:
note: size_t Hash::operator()(const Interval&)
note:   candidate expects 1 argument, 2 provided  

Pensé que sólo proporcioné 1 argumento ...

¿Cuál es el problema con mi código de inserción?

Aquí está el nuevo código de unordered_set<Interval, Hash> test; instancias: unordered_set<Interval, Hash> test; Sin embargo, todavía estoy recibiendo una gran cantidad de mensajes de error, por ejemplo:

note: candidate is:
note: size_t Hash::operator()(const Interval&) <near match>
note:   no known conversion for implicit ‘this’ parameter from ‘const Hash*’ to ‘Hash*’

Answer 1

Creo que Andy Prowl solucionó perfectamente los problemas con su código. Sin embargo, agregaría la siguiente función de miembro a su Interval , que describe qué hace que dos intervalos sean idénticos:

std::string getID() const { return std::to_string(b) + " " + std::to_string(e) + " " + std::to_string(proteinIndex); }

Tenga en cuenta que también seguí la sugerencia de Andy Prowl y cambié el nombre de los miembros que begin por b y end por e . A continuación, puede definir fácilmente las funciones hash y de comparación utilizando expresiones lambda . Como resultado, puede definir su unordered_set siguiente manera:

auto hash = [](const Interval& i){ return std::hash<std::string>()(i.getID()); };
auto equal = [](const Interval& i1, const Interval& i2){ return i1.getID() == i2.getID(); };
std::unordered_set<Interval, decltype(hash), decltype(equal)> test(8, hash, equal);

Finalmente, por razones de legibilidad, convertí su bucle for en un bucle for basado en rango:

std::list<Interval> concat {{1, 2, false, 3, 4}, {2, 3, false, 4, 5}, {1, 2, true, 7, 4}};

for (auto const &i : concat)
    test.insert(i);

for (auto const &i : test)
    std::cout << i.b << ", " << i.e << ", " << i.updated << std::endl;

Salida (acabo de imprimir los primeros tres miembros de cada Interval ):

2, 3, 0
1, 2, 0

Como puede ver, solo hay dos intervalos impresos. El tercero ( {1, 2, true, 7, 4} ) no se insertó para concat , porque su b , e y proteinIndex son iguales a los del primer intervalo ( {1, 2, false, 3, 4} ).

Código en Ideone

Answer 2

Primer problema:

Está pasando una string como el segundo argumento de plantilla para su creación de instancias de la plantilla de clase unordered_set<> . El segundo argumento debe ser el tipo de su functor hasher , y std::string no es un objeto llamable.

Tal vez la intención de escribir:

unordered_set<Interval, /* string */ Hash> test;
//                      ^^^^^^^^^^^^
//                      Why this?

Además, sugeriría utilizar nombres distintos a los de begin y end para sus variables (miembro), ya que son nombres de algoritmos de la biblioteca estándar de C ++.

Segundo problema:

Debe tener en cuenta que la función hasher debe calificarse como const , por lo que su functor debe ser:

struct Hash {
   size_t operator() (const Interval &interval) const {
   //                                           ^^^^^
   //                                           Don''t forget this!
     string temp = to_string(interval.b) + 
                   to_string(interval.e) + 
                   to_string(interval.proteinIndex);
     return (temp.length());
   }
};

Tercer problema:

Finalmente, si desea que std::unordered_set pueda trabajar con objetos de tipo Interval , debe definir un operador de igualdad coherente con su función hash. De forma predeterminada, si no especifica ningún argumento de tipo como el tercer parámetro de la plantilla de clase std::unordered_set , se utilizará el operator == .

Actualmente no tiene ninguna sobrecarga de operator == para su Interval clase, por lo que debe proporcionar uno. Por ejemplo:

inline bool operator == (Interval const& lhs, Interval const& rhs)
{
    return (lhs.b == rhs.b) && 
           (lhs.e == rhs.e) && 
           (lhs.proteinIndex == rhs.proteinIndex); 
}

Conclusión:

Después de todas las modificaciones anteriores, puede ver su compilación de código en este ejemplo en vivo .