¿Cuál es la mejor manera de usar dos claves con un std :: map?

Question

Tengo un std :: map que estoy usando para almacenar valores para x & y coordenadas. Mis datos son muy escasos, por lo que no quiero utilizar matrices o vectores, lo que resultaría en una pérdida masiva de memoria. Mis datos oscilan entre -250000 y 250000 pero solo tendré unos pocos miles de puntos como máximo.

Actualmente estoy creando una cadena estándar con las dos coordenadas (es decir, "12x45") y utilizándola como clave. Esto no parece ser la mejor manera de hacerlo.

Mis otros pensamientos fueron utilizar un int64 y meter los dos int32s en él y usarlo como clave.

O para usar una clase con las dos coordenadas. ¿Cuáles son los requisitos de una clase que se utilizará como clave?

¿Cuál es la mejor manera de hacerlo? Prefiero no usar un mapa de mapas.

Answer 1

uso std :: par < int32, int32> para la clave:

std::map<std::pair<int,int>, int> myMap; 

myMap[std::make_pair(10,20)] = 25; 
std::cout << myMap[std::make_pair(10,20)] << std::endl; 

Answer 2

Boost tiene un recipiente mapa que utiliza uno o más índices.

Multi Index Map

Answer 3

por lo general puedo solucionar este tipo de problema como este:

struct Point 
{ 
    Point() : x(), y() {} 
    Point(int x, int y) : x(x), y(y) {} 
    int x, y; 
}; 

bool operator<(const Point & lhs, const Point & rhs) // lhs = left-hand side 
                 // rhs = right-hand side 
{ 
    if (lhs.x != rhs.x) 
    { 
     return lhs.x < rhs.x; 
    } 
    else 
    { 
     return lhs.y < rhs.y; 
    } 
} 

int main() 
{ 
    Point p1(0, 1); 
    Point p2(0, 2); 
    std::map<Point, std::string> mapping; 
    mapping[p1] = "p1"; 
    mapping.insert(std::make_pair(p2, "p2")); 
} 

Answer 4

¿Cuáles son los requisitos de una clase que se va a utilizar como la clave?

El mapa tiene que ser capaz de decir si el valor de una clave es menor que el valor de otra de las claves: por defecto, esto significa que (key1 < clave2) debe ser una expresión lógica válida, es decir, que el tipo de clave debe poner en práctica el operador 'menos que'.

La plantilla de mapa también implementa un constructor sobrecargado que le permite pasar una referencia a un objeto de función de tipo key_compare, que puede implementar el operador de comparación: para que la comparación pueda implementarse como un método de esta función externa objeto, en lugar de tener que ser cocido al horno de cualquier tipo que sea su clave.

Answer 5

Usar std :: pair. Mejor incluso use QHash<QPair<int,int>,int> si tiene muchas de esas asignaciones.

Answer 6

En primer lugar, deshazte de la cuerda y usa 2 ints, que bien podrías haber hecho hasta ahora. Felicitaciones por descubrir que un árbol es la mejor manera de implementar una matriz dispersa. Por lo general, parece ser un imán para malas implementaciones.

FYI, una clave compuesta triple también funciona, y supongo que también un par de pares.

Sin embargo, hace algunas sub-secuencias de comandos feas, así que un poco de macro magia hará su vida más fácil. Dejé este propósito general, pero la creación de argumentos en la macro es una buena idea si creas macros para mapas específicos. El TresKey12 está probado y funcionando bien. QuadKeys también debería funcionar.

NOTA: Siempre que sus piezas clave sean tipos de datos básicos, NO necesita escribir nada más. AKA, no hay necesidad de preocuparse por las funciones de comparación. El STL te tiene cubierto. Solo codifícalo y déjalo explotar.

using namespace std; // save some typing 
#define DosKeys(x,y)  std::make_pair(std::make_pair(x,y)) 
#define TresKeys12(x,y,z) std::make_pair(x,std::make_pair(y,z)) 
#define TresKeys21(x,y,z) std::make_pair(std::make_pair(x,y),z)) 

#define QuadKeys(w,x,y,z) std::make_pair(std::make_pair(w,x),std::make_pair(y,z)) 


map<pair<INT, pair<ULLNG, ULLNG>>, pIC_MESSAGE> MapMe; 
MapMe[TresKey12(Part1, Part2, Part3)] = new fooObject; 

Si alguien quiere impresionarme, me muestran cómo hacer un operador de comparación para TresKeys que no se basa en los pares de anidación para que pueda utilizar una sola struct con 3 miembros y utilizar una función de comparación.

PS: TresKey12 me dio problemas con un mapa declarado como par, z, ya que hace x, par, y esos dos no juegan bien. No es un problema para DosKeys o QuadKeys. Sin embargo, si es un verano caluroso el viernes, puede encontrar un efecto secundario inesperado al escribir DosEquis ... err .. Dos veces un par de veces, es una sed de cerveza mexicana. Caveat Emptor. Como dice Sheldon Cooper, "¿Qué es la vida sin extravagancia?".

Answer 7

Esto rellenará varias claves enteras en un entero grande, en este caso, un _int64. Se compara como _int64, AKA long long (La declaración más fea de todos los tiempos, corta, corta, corta, solo sería ligeramente menos elegante. Hace 10 años se llamaba vlong. Mucho mejor. Mucho para "progreso"), así que no hay comparación la función es necesaria.

#define ULNG unsigned long 
#define BYTE unsigned char 
#define LLNG long long 
#define ULLNG unsigned long long 

// -------------------------------------------------------------------------- 
ULLNG PackGUID(ULNG SN, ULNG PID, BYTE NodeId) { 
    ULLNG CompKey=0; 

    PID = (PID << 8) + NodeId; 
    CompKey = ((ULLNG)CallSN << 32) + PID; 

    return CompKey; 
} 

haber proporcionado esta respuesta, no creo que esto va a funcionar para usted, ya que necesita dos teclas separadas y distintas para navegar dentro de 2 dimensiones, X e Y.

Por otro lado, si ya tiene la coordenada XY, y solo quiere asociar un valor con esa clave, esto funciona espectacularmente, porque una comparación _int64 lleva el mismo tiempo que cualquier otra comparación entera en chips Intel X86: 1 reloj.

En este caso, la comparación es 3 veces más rápida en esta clave sintética, frente a una clave compuesta triple.

Si utilizo esto para crear una hoja de cálculo escasamente poblada, usaría RX 2 árboles distintos, uno anidado dentro del otro. Haga que la dimensión Y sea "el jefe", y busque primero el espacio Y en la resolución antes de proceder a la dimensión X. Las hojas de cálculo son más altas que anchas, y siempre quiere que la 1ª dimensión en cualquier tecla compuesta tenga la mayor cantidad de valores únicos.

Esta disposición crearía un mapa para la dimensión Y que tendría un mapa para la dimensión X como datos. Cuando llegue a una hoja en la dimensión Y, comenzará a buscar su dimensión X para la columna en la hoja de cálculo.

Si desea crear un sistema de hoja de cálculo muy poderoso, agregue una dimensión Z de la misma manera, y use eso para, por ejemplo, unidades organizativas. Esta es la base de un sistema de presupuestación/previsión/contabilidad muy poderoso, que permite a las unidades administrativas contar con un montón de detalladas cuentas para rastrear los gastos de administración, y no tener esas cuentas ocupando espacio para unidades de línea que tienen sus propios tipos de detalles para rastrear.

Answer 8

Esperamos que encuentre útil:

map<int, map<int, int>> troyka = { {4, {{5,6}} } }; 
troyka[4][5] = 7;