std :: configurado con tipo definido por el usuario, cómo asegurar que no haya duplicados

Así que tengo un std :: set que necesita mantener un orden específico así como no permitir duplicados de un tipo definido por el usuario (por mí). Ahora puedo hacer que la orden funcione correctamente al sobrecargar el operador ‘<' en mi tipo. Sin embargo, el conjunto no detecta adecuadamente duplicados, y para ser sincero, no estoy del todo seguro de cómo lo hace internamente. He sobrecargado el operador '==', pero de alguna manera no estoy seguro de que esto sea lo que realmente está usando el set? Entonces, la pregunta es ¿cómo determina el conjunto los duplicados cuando se agregan valores? Aquí está el código relevante:

El tipo definido por el usuario:

//! An element used in the route calculation. struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; 

Entonces los elementos son equivalentes cuando su posición es equivalente, y un elemento es menos que otro si su funcionalidad combinada es menor que la del otro. La clasificación funciona, pero el conjunto aceptará dos elementos de la misma posición.

operator== no es usado por std::set . Los elementos a y b se consideran iguales iff !(a < b) && !(b < a)

std::set admite la especificación de una función de comparación. El valor predeterminado es less que usará el operator < para verificar la igualdad. Puede definir una función personalizada para verificar la igualdad y usar esa en su lugar:

 std::set myset; 

Tenga en cuenta que no es posible separar la función de comparación de la función de clasificación. std::set es un árbol binario y si un elemento en un árbol binario no es más grande ni más pequeño que un elemento específico, debe estar en el mismo lugar. Hace algo como esto en el algoritmo de búsqueda de lugar:

 if (a < b) { // check the left subtree } else if (b < a) { // check the right subtree } else { // the element should be placed here. } 

El comparador de rlbond no evita la inserción de elementos que se comparan por igual. Aparentemente es difícil probar esto en los comentarios, dado el límite de caracteres, porque rlbond parece pensar que std :: set garantiza que nunca contendrá dos elementos con !compare(a,b) && !compare(b,a) para su comparador. Sin embargo, el comparador de rlbond no define un orden estricto y, por lo tanto, no es un parámetro válido para std :: set.

 #include  #include  #include  #include  struct BrokenOrder { int order; int equality; public: BrokenOrder(int o, int e) : order(o), equality(e) {} bool operator<(const BrokenOrder &rhs) const { return order < rhs.order; } bool operator==(const BrokenOrder &rhs) const { return equality == rhs.equality; } }; std::ostream &operator<<(std::ostream &stream, const BrokenOrder &b) { return stream << b.equality; } // rlbond's magic comparator struct LessThan : public std::binary_function { bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const { return !(lhs == rhs) && (lhs < rhs); } }; int main() { std::set s; for (int i = 0; i < 5; ++i) { s.insert(BrokenOrder(i,i)); } for (int i = 0; i < 5; ++i) { s.insert(BrokenOrder(10-i,i)); } std::copy(s.begin(), s.end(), std::ostream_iterator(std::cout, "\n")); } 

Salida:

 0 1 2 3 4 3 2 1 0 

Duplicados. El comparador mágico ha fallado. Los diferentes elementos en el conjunto tienen el mismo valor de equality , y por lo tanto, se puede comparar con el operator== , porque durante la inserción el conjunto nunca comparó el nuevo elemento con su duplicado. El único duplicado que se excluyó fue 4, porque los dos 4 tenían órdenes de clasificación 4 y 6. Esto los acercó lo suficiente en el conjunto para compararlos entre sí.

Del estándar de C ++: 25.3: 3 “Para que los algoritmos funcionen correctamente, comp debe inducir un orden estricto y débil sobre los valores”.

25.3: 4 “… los requisitos son que comp y equiv sean ambas relaciones transitivas:

 comp(a,b) && comp(b,c) implies comp(a,c)" 

Ahora, considere los elementos a = BrokenOrder(1,1) , b = BrokenOrder(2,2) , c = BrokenOrder(9,1) , y comp de curso igual al magic comparator. Entonces:

  • comp(a,b) es verdadero desde 1! = 2 (igualdad) y 1 <2 (orden)
  • comp(b,c) es verdadero desde 2! = 1 (igualdad) y 2 <9 (orden)
  • comp(a,c) es falso ya que 1 == 1 (igualdad)

La implementación del conjunto STL hace algo así como este concepto para detectar la igualdad:

 bool equal = !(a < b) && !(b < a); 

Es decir, si dos elementos no son menos que el otro, entonces deben ser iguales. Puede verificar esto configurando un punto de interrupción en su método operator==() y verificando si alguna vez se llama.

En general, sospecho de operadores de comparación que verifican cosas completamente diferentes. Su < operador se define en términos de dos cosas que están separadas de cómo se define su operador == . En general, deseará que tales comparaciones usen información coherente.

Podría intentar algo como lo siguiente:

 //! An element used in the route calculation. struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; struct CompareByPosition { bool operator()(const RouteElem &lhs, const RouteElem &rhs) { if (lhs.position.x != rhs.position.x) return lhs.position.x < rhs.position.x; return lhs.position.y < rhs.position.y; } }; // first, use std::set to remove duplicates std::set routeset; // ... add each RouteElem to the set ... // now copy the RouteElems into a vector std::vector routevec(routeset.begin(), routeset.end()); // now sort via operator< std::sort(routevec.begin(), routevec.end()); 

Obviamente está la copia en el medio, que parece lenta. Pero cualquier estructura que indexe elementos por dos criterios diferentes tendrá, por lo tanto, algún tipo de sobrecarga adicional por artículo en comparación con un conjunto. Todo el código anterior es O (n log n), suponiendo que su implementación de std :: sort utiliza introsort.

Si lo tiene, en este esquema puede usar unordered_set lugar de set para hacer la inicialización única. Como el hash solo debería depender de xey, debería ser más rápido que las comparaciones O (log N) requeridas para insertarse en un conjunto.

Editar: acaba de notar que dijiste que querías "mantener" el orden de clasificación, no que quisieras procesar todo en un lote. Lo siento por eso. Si desea mantener el orden de manera eficiente y excluir duplicados al agregar elementos, entonces recomendaría usar el conjunto o el conjunto desordenado que defino arriba, en función de la posición, y también un std::multiset , que mantendrá el operator< orden . Para cada nuevo elemento, haz:

 if (routeset.insert(elem).second) { routemultiset.insert(elem); } 

Aunque tenga en cuenta que esto no ofrece ninguna garantía de excepción. Si el segundo inserto se lanza, entonces el conjunto de rutas se ha modificado, por lo que el estado ya no es consistente. Así que supongo que realmente necesitas:

 if (routeset.insert(elem).second) { try { routemultiset.insert(elem); // I assume strong exception guarantee } catch(...) { routeset.erase(elem); // I assume nothrow. Maybe should check those. throw; } } 

O un equivalente con RAII, que será más detallado si solo hay un lugar en su código que alguna vez utilice la clase RAII, pero mejor si hay mucha repetición.

Ten cuidado con las ramificaciones de esto. Parece que estás intentando hacer algo como A *, y si tratas de insertar un “duplicado” se ignorará, incluso si hay una ruta “mejor”.

NOTA: esta solución no funciona, consulte la explicación de Onebyone a continuación

 struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; struct RouteElemLessThan : public std::binary_function { bool operator()(const RouteElem& lhs, const RouteElem& rhs) const { return !(lhs == rhs) && (lhs < rhs); } }; std::set my_set;