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

tengo un std::map que estoy usando para almacenar valores para las coordenadas x e y. Mis datos son muy escasos, por lo que no quiero usar 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 un std::string con las dos coordenadas (es decir "12x45") y usarlo como clave. Esta no parece la mejor manera de hacerlo.

Mis otros pensamientos fueron usar un int64 y meter los dos int32 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.

Utilice std::pair 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;

Normalmente resuelvo este tipo de problema así:

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

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

Mapa de índice múltiple

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

El mapa debe poder decir si el valor de una clave es menor que el valor de otra clave: por defecto, esto significa que (clave1

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: de modo que, alternativamente, la comparación se puede implementar como un método de este objeto de función externo, en lugar de necesita ser horneado en cualquier tipo de clave.

Esto introducirá múltiples claves enteras en un entero grande, en este caso, un _int64. Se compara como un _int64, también conocido como long long (la declaración de tipos más fea que existe. short short short short, solo sería un poco menos elegante. Hace 10 años se llamaba vlong. Mucho mejor. Tanto para “progreso”), así que no hay comparación se necesita la función.

#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 teclas separadas y distintas para navegar en 2 dimensiones, X e Y.

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

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

Si usa esto para crear una hoja de cálculo escasamente poblada, haría RX usando 2 árboles distintos, uno anidado dentro del otro. Haga que la dimensión Y sea “el jefe” y busque primero el espacio Y hasta la resolución antes de pasar a la dimensión X. Las hojas de cálculo son más altas que anchas, y siempre desea que la primera dimensión en cualquier clave compuesta tenga la mayor cantidad de valores únicos.

Este arreglo crearía un mapa para la dimensión Y que tendría un mapa para la dimensión X como sus datos. Cuando llega a una hoja en la dimensión Y, comienza a buscar en la dimensión X la columna en la hoja de cálculo.

Si desea crear un sistema de hoja de cálculo muy potente, agregue una dimensión Z de la misma manera y utilícela, como ejemplo, para las unidades organizativas. Esta es la base de un sistema de presupuesto/pronóstico/contabilidad muy poderoso, uno que permite que las unidades de administración tengan muchas cuentas de detalles sangrientos para rastrear los gastos de administración y demás, y que esas cuentas no ocupen espacio para las unidades de línea que tienen sus propios tipos. de detalle a rastrear.

Creo que para su caso de uso, std::pair, como se sugiere en la respuesta de David Norman, es la mejor solución. Sin embargo, desde C++11 también puedes usar std::tuple. Las tuplas son útiles si tiene más de dos claves, por ejemplo, si tiene coordenadas 3D (es decir, x, yy z). Entonces no tiene que anidar pares o definir un comparador para un struct. Pero para su caso de uso específico, el código podría escribirse de la siguiente manera:

int main() {
    using tup_t = std::tuple<int, int>;
    std::map<tup_t, int> m;

    m[std::make_tuple(78, 26)] = 476;
    tup_t t = { 12, 45 }; m

    for (auto const &kv : m)
        std::cout << "{ " << std::get<0>(kv.first) << ", "
                          << std::get<1>(kv.first) << " } => " << kv.second << std::endl;
    return 0;
}

Producción:

{ 12, 45 } => 102
{ 78, 26 } => 476

Nota: Ya que C++17 trabajar con tuplas se ha vuelto más fácil, especialmente si desea acceder a múltiples elementos simultáneamente. Por ejemplo, si usa encuadernación estructuradapuede imprimir la tupla de la siguiente manera:

for (auto const &[k, v] : m) {
    auto [x, y] = k;
    std::cout << "{ " << x << ", " << y << " } => " << v << std::endl;
}

Código en Coliru

Utilice estándar::par. Mejor incluso usar QHash<QPair<int,int>,int> si tiene muchas de esas asignaciones.