c++ - geeksforgeeks - ¿Cuál es la mejor manera de usar dos teclas con un std:: map?

stl map

Question

Tengo un std :: map que estoy usando para almacenar valores para coordenadas xey. 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 std :: 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 usar 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 hacer esto? Prefiero no usar un mapa de mapas.

Answer 1

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

El mapa necesita saber si el valor de una clave es menor que el valor de otra clave: por defecto, esto significa que (clave1 <clave2) debe ser una expresión booleana válida, es decir, que el tipo de clave debe implementar el operador ''menor que''.

La plantilla de mapa también implementa un constructor sobrecargado que le permite transferir una referencia a un objeto de función de tipo key_compare, que puede implementar el operador de comparación: para que alternativamente la comparación se pueda implementar como un método de este objeto de función externo, en lugar de necesitando ser horneado al tipo de llave que sea.

Answer 2

Boost tiene un contenedor de mapas que usa uno o más índices.

Mapa de índice múltiple

Answer 3

En primer lugar, deshazte de la cuerda y usa 2 ints, lo cual es muy posible que ya hayas hecho. 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, crea algunas sub-secuencias de comandos feas, por lo que una pequeña macro magia te hará la 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: Mientras sus partes 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, TresKeys cómo hacer un operador de comparación para TresKeys que no dependa de pares de anidamiento, así que puedo usar una sola struct con 3 miembros y usar una función de comparación.

PD: 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. DosKeys un montón de veces, es una sed de cerveza mexicana. Caveat Emptor. Como dice Sheldon Cooper, "¿Qué es la vida sin extravagancia?".

Answer 4

Espero que lo encuentres útil:

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

Answer 5

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;
}

Habiendo proporcionado esta respuesta, dudo que esto funcione para usted, ya que necesita dos claves separadas y distintas para navegar en 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 úselo 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 6

Por lo general, resuelvo este tipo de problema de esta manera:

struct Point {
    int x;
    int y;
};

inline bool operator<(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}

Answer 7

Use std :: pair <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 8

Use std :: pair. Mejor aún use QHash<QPair<int,int>,int> si tiene muchas de esas asignaciones.