El uso de un vector (matemática) en un std :: mapa

Question

relacionados: what can I use as std::map keys?

que necesitaba para crear una asignación en lugares clave específicas en el mapa espacio a las listas de objetos. std::map parecía la manera de hacerlo.

Así que estoy tecleando un std::map en una xyz Vector

class Vector 
{ 
    float x,y,z 
} ; 

, y estoy haciendo un std::map<Vector, std::vector<Object*> >. Así que tenga en cuenta que la clave aquí no es a std::vector, es un objeto de class Vector que es solo un vector math xyz de mi propia creación.

para producir una "orden estrictamente débil" He escrito el siguiente sobrecarga para operator<:

bool Vector::operator<(const Vector & b) const { 
    // z trumps, then y, then x 
    if(z < b.z) 
    { 
     return true ; 
    } 
    else if(z == b.z) 
    { 
     if(y < b.y) 
     { 
     // z == b.z and y < b.y 
     return true ; 
     } 
     else if(y == b.y) 
     { 
     if(x < b.x) 
     { 
      return true ; 
     } 
     else if(x == b.x) 
     { 
      // completely equal 
      return false ; 
     } 
     else 
     { 
      return false ; 
     } 
     } 
     else 
     { 
     // z==b.z and y >= b.y 
     return false ; 
     } 
    } 
    else 
    { 
     // z >= b.z 
     return false ; 
    } 
    } 

Es un poco largo, pero básicamente lo hace tan consistentemente cualquier vector puede decirse que es menos que cualquier otro vector ((-1, -1, -1) < (-1, -1,1) y (-1, -1, 1)> (-1, -1, -1) por ejemplo).

Mi problema es que esto es realmente artificial y aunque lo he codificado y funciona, estoy descubriendo que "contamina" mi clase Vector (matemáticamente) con esta noción realmente extraña, artificial y no matemática de "menos que" para un vector.

Pero necesito crear una asignación donde las ubicaciones de teclas específicas en el espacio se asignan a ciertos objetos, y std :: map parece la manera de hacerlo.

Sugerencias? ¡Soluciones listas para usar!

Answer 1

En lugar de definir operator< para su clase de clave, puede asignar al mapa un comparador personalizado. Este es un objeto de función que toma dos argumentos y devuelve true si el primero viene antes del segundo. Algo como esto:

struct CompareVectors 
{ 
    bool operator()(const Vector& a, const Vector& b) 
    { 
     // insert comparison code from question 
    } 
}; 

typedef std::map<Vector, Value, CompareVectors> VectorValueMap; 

Answer 2

Creo que su enfoque es bueno. Si usted está preocupado acerca de la contaminación del clase Vector, entonces creo que una función independiente funcionará igual de bien:

bool operator<(const Vector& lhs, const Vector& rhs) 
{ 
    ... 
} 

Pero sólo una palabra de advertencia: lo que está haciendo aquí es bastante arriesgado. A menudo hay errores en los cálculos de coma flotante. Supongamos que inserta algún punto en su mapa. Luego calcula un punto y verifica el mapa para ver si está allí. Incluso si, desde un punto de vista estrictamente matemático, el segundo punto es el mismo que el primero, no hay garantía de que lo encuentres en el mapa.

Answer 3

Creo que std::tr1::unordered_map es justo lo que necesita. No se requerirá un orden estricto y débil. GCC tiene algo similar en el espacio de nombres tr1 también. O vaya por Boost.Unordered.

Las contrapartes no ordenadas de la más pedestre map o set le ofrece dos ventajas:

• No es necesario definir un operador menor que donde no tiene sentido

• Las tablas hash puede realizar mejor que los árboles binarios equilibrados, este último es el método preferido para implementar las estructuras map o set ordenadas. Pero eso depende de su patrón/requisitos de acceso a los datos.

lo tanto, sólo seguir adelante y utilizar:

typedef std::tr1::unordered_map<Vector, std::vector<Object *> > VectorMap; 

Esto hace uso de una función hash por defecto que se encarga de inserción/búsqueda de su mapa.

PD: el > > cosita será corregido en la próxima norma y por lo tanto las futuras versiones del compilador.

Answer 4

Usted puede separarlo de la clase. Luego especifíquelo como operador de comparación para std :: map.

std::map<Vector,std::vector<Object*>,Compare> data; 

Dónde Comparar es una función (o funtor) que se puede comparar objetos de remolque del vector.
También creo que puede simplificar su operación de comparación.

bool Compare<(const Vector& lhs, const Vector& rhs) 
{ 
    // z trumps, then y, then x 
    if(lhs.z < rhs.z) 
    { return true ; 
    } 
    else if (lhs.z > rhs.z) 
    { return false; 
    } 
    // Otherwise z is equal 
    if(lhs.y < rhs.y) 
    { return true ; 
    } 
    else if(lhs.y > rhs.y) 
    { return false; 
    } 
    // Otherwise z and y are equal 
    if (lhs.x < rhs.x) 
    { return true; 
    } 
    /* Simple optimization Do not need this test 
     If this fails or succeeded the result is false. 
    else if(lhs.x > rhs.x) 
    { return false; 
    }*/ 
    // Otherwise z and y and x are all equal 
    return false; 
} 

Fíjate que probamos por menos de lo que sea y luego fracasamos por igual. Personalmente, me gusta la simplicidad de este estilo. Pero a menudo veo que esto se comprime así:

bool Compare<(const Vector& lhs, const Vector& rhs) 
{ 
    // Note I use three separate if statements here for clarity. 
    // Combining them into a single statement is trivial/ 
    // 
    if ((lhs.z < rhs.z)          ) {return true;} 
    if ((lhs.z == rhs.z) && (lhs.y < rhs.y)     ) {return true;} 
    if ((lhs.z == rhs.z) && (lhs.y == rhs.y) && (lhs.x < rhs.x)) {return true;} 

    return false; 
} 

Answer 5

Es normal que encuentre que su clase está contaminada por esto. También está contaminado desde un punto de vista de CS.

La manera normal de definir un operador tal es a través de (potencialmente amigo) funciones libres.

Sin embargo, la primera pregunta que debe hacerse es: ¿tiene sentido. El problema es que ha definido un método para su clase que solo es significativo en un contexto limitado pero accesible en todas partes. Es por eso que los "contaminación" patadas sensación en

Ahora, si yo fuera a necesitar dicha asignación de un Vector a una colección de Object s, aquí están las preguntas que me preguntaba a mí mismo:.

• Do I necesita el Vector para ordenar? Sí: std::map, no: std::unordered_map o std::tr1::unodered_map o std::hash_map o boost::unordered_map.
• ¿Esta colección posee la Object? Sí: boost::ptr_vector<Object> o std::vector< std::unique_ptr<Object> >, no: std::vector<Object*>

Ahora, en ambos casos (map y unordered_map), necesitaré algo para transformar mi llave. La colección proporciona un argumento de plantilla suplementario que toma un tipo de Functor.

Cuidado: como se mencionó en otra respuesta, la representación de coma flotante es incómoda en una computadora, por lo tanto, probablemente deba relajar el significado de igualdad e ignorar los dígitos de orden inferior (cuántos dependen de sus cálculos).