std, boost u otra implementación generalizada de un contenedor de tabla hash con claves implícitas

Si lo entiendo correctamente, std :: map y std :: unordered_map almacenan claves explícitamente (almacena pares de claves/valores). ¿Hay algún otro contenedor listo para usar (std, boost u otra implementación generalizada) que no almacene la clave, sino que permita derivar la clave del valor almacenado utilizando una función (es decir, para utilizar la clave implícita?).std, boost u otra implementación generalizada de un contenedor de tabla hash con claves implícitas

Fuente

2012-01-19 Suma

std::set o std::unordered_set, con función de comparación y/o hash adecuada para el tipo de valor almacenado.

Sin embargo, la búsqueda se realizará por el tipo de valor almacenado, no por la clave, por lo que también necesitará una forma de fabricar un objeto temporal a partir de una clave.

Fuente

2012-01-19 12:24:55

¿Esto le permite hacer búsquedas * solo con una tecla *, en lugar de necesitar un objeto completo? –

@ R.MartinhoFernandes: Supongo que no; quizás malentendí la pregunta. Pero este podría ser un enfoque sensato, siempre que pueda crear fácilmente un objeto temporal a partir de una clave. –

@ R.MartinhoFernandes que sería (mi entendimiento) una pregunta/requisito diferente. Fuera de la caja, podría crear un objeto parcial con la información suficiente para la generación de claves. Por otra parte, en la mayoría de los casos no extremos, seguiría almacenando la clave de todos modos (la memoria es barata hoy en día) –

Todos los contenedores ordenados en la biblioteca C++ p. std::set permitir menos rasgo de plantilla de comparación, pasarlo como un segundo parámetro de plantilla (my_less en el ejemplo a continuación). . Si no lo hace, operator< se buscará a través de ADL y se usará si se encuentra (error de compilación si no es así); debería ser apropiado para muchos casos.

Su propio rasgo o operator< se puede utilizar para definir el orden de acuerdo con los datos almacenados en un conjunto, es decir, sin clave. No se copian datos para realizar esta comparación, tenga en cuenta que requiere referencias.

Si no desea crear el objeto pila y prefiere utilizar punteros montón lugar, es obvio que puede almacenar en boost::shared_ptr contenedor estándar ordenado y escribir su menos comparación rasgo en consecuencia. En este caso también se puede considerar el uso boost ptr containers

Ejemplo:

#include <boost/shared_ptr.hpp> 
#include <set> 
#include <iterator> 
#include <iostream> 

struct order_by_AB { int a; int b; int c; 
    order_by_AB(int a, int b, int c) : a(a), b(b), c(c) {} 
}; 

struct my_less 
{ 
    bool operator()(const boost::shared_ptr<order_by_AB>& lh, const boost::shared_ptr<order_by_AB>& rh) 
    { 
    if (lh->a == rh->a) 
     return lh->b < rh->b; 
    return lh->a < rh->a; 
    } 
}; 

std::ostream& operator<< (std::ostream& os, const boost::shared_ptr<order_by_AB>& rh) 
{ 
    os << "(" << rh->a << "," << rh->b << "," << rh->c << ")"; 
    return os; 
} 

int main() 
{ 
    std::set<boost::shared_ptr<order_by_AB>, my_less> data; 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 1, 2))); 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 3, 2))); 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 3, 2))); 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 1, 2))); 
    std::copy(data.begin(), data.end(), std::ostream_iterator<boost::shared_ptr<order_by_AB>>(std::cout, "\n")); 
    return 0; 
}

Editado para dar ejemplo de funtor especificado por el usuario para la comparación. Editado añadir boost::shared_ptr en un recipiente

Fuente

2012-01-19 12:32:12 bronekk

Como mencioné en otra respuesta, el problema es que necesita un objeto completo para realizar búsquedas. No puede hacer una búsqueda con solo una clave, como puede hacerlo con el mapa. –

No entiendo algo. ¿De qué quieres derivar tu clave y quién debería hacer esta derivación? El código anterior deriva la clave del valor almacenado. Esto se puede delegar si es necesario, p. a la función miembro de una clase almacenada en contenedor. ¿Desea obtener la clave sin acceder realmente al valor? De ser así, ¿dónde se obtendrían los datos necesarios para derivar el valor clave? – bronekk

¿Se puede hacer 'data [x]' donde 'x' no es un objeto' order_by_AB' completo? Debido a que un objeto completo puede ser difícil de conseguir a veces: imagine si el objeto tenía algún recurso. –

Usted podría estar buscando Boost.Intrusive. Los contenedores Boost Intrusive "enganchan" sus tipos de valor para proporcionar las características de un determinado contenedor (por ejemplo, conjunto, lista, árbol AVL, etc.) directamente desde los objetos.

Consulte Differences between intrusive and non-intrusive containers para obtener una descripción general de las diferencias entre los contenedores STL y los contenedores Boost Intrusive.

Fuente

2012-01-19 12:36:14

std, boost u otra implementación generalizada de un contenedor de tabla hash con claves implícitas

Respuesta

Cuestiones relacionadas