c++ - oda - Buscar en el mapa inverso

oda decompiler

Question

Tengo un mapa de 1 a 1. ¿Cuál es la mejor forma de encontrar claves a partir de valores?

es decir

Por ejemplo, si el mapa es este

VALOR CLAVE

a    1
b    2
c    3 
d    4

Quiero poder encontrar que la clave correspondiente a 3 es C.

¡Gracias!

Answer 1

A menos que el mapa sea enorme, o si tiene alguna otra forma de saber que la búsqueda lineal es demasiado lenta, comenzaría con la búsqueda lineal:

#include <iostream>
using std::cout;

#include <map>
using std::map;

#include <algorithm>
using std::find_if;

#include <boost/assign/list_of.hpp>
using boost::assign::map_list_of;

typedef map<char, int> Map;
typedef Map::key_type Key;
typedef Map::value_type Pair;
typedef Map::mapped_type Value;


struct finder {
    const Value v;
    finder(const Value& v) : v(v) {}
    bool operator()(const Pair& p) {
        return p.second == v;
    }
};

Map m = map_list_of(''a'', 1)(''b'', 2)(''c'', 3)(''d'', 4)(''e'', 5);

int main() {
    Pair v = *find_if(m.begin(), m.end(), finder(3));
    cout << v.second << "->" << v.first << "/n";
}

Answer 2

Digamos que tienes un mapa <X,Y> . Cree una segunda estructura, tal vez un mapa <Y*,X*,Deref> que habilite la búsqueda inversa, pero evite doblar la sobrecarga de almacenamiento, ya que, usando punteros, no hay necesidad de almacenar cada X e Y dos veces. La segunda estructura simplemente tiene punteros en la primera.

Answer 3

La manera más directa sería mantener un mapa paralelo donde los valores y las claves se invierten (ya que la relación es uno a uno).

Answer 4

No hay mucho que puedas hacer al respecto. Tiene opciones para trabajar con dos mapas, usar un mapa de varias teclas como uno de la biblioteca Boost Multi-Index o hacer una búsqueda lineal.

ACTUALIZACIÓN: La solución más liviana Boost.Bimap con Boost.Bimap , que significa mapa bidireccional.

Answer 5

Otra solución sería usar (¿la menos conocida?) Boost.Bimap :

Boost.Bimap es una biblioteca de mapas bidireccionales para C ++. Con Boost.Bimap puede crear contenedores asociativos en los que ambos tipos se pueden usar como clave. Un bimap<X,Y> puede considerarse como una combinación de un std::map<X,Y> y un std::map<Y,X> . La curva de aprendizaje de bimap es casi plana si sabe cómo usar contenedores estándar. Se ha dedicado un gran esfuerzo al mapeo del esquema de nombres del STL en Boost.Bimap. La biblioteca está diseñada para coincidir con los contenedores comunes de STL.

Answer 6

Sé que esta es una pregunta muy antigua, pero este artículo del proyecto de código ( http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map ) es un buen ejemplo de un mapa bidireccional.

Este es un programa de ejemplo que muestra lo fácil que es:

 #pragma warning(disable:4503)

    #include "bimap.h"
    #include <iostream>
    #include <string>

    using codeproject::bimap;

    int main(void)
    {
      bimap<int,std::string> bm;

      bm[1]="Monday";
      bm[2]="Tuesday";
      bm[3]="Wednesday";
      bm[4]="Thursday";
      bm[5]="Friday";
      bm[6]="Saturday";
      bm[7]="Sunday";

      std::cout<<"Thursday occupies place #"<<bm["Thursday"]<<
                 " in the week (european style)"<<std::endl;
      return 0;
    }

Answer 7

Una variación de la respuesta de @ Robᵩ anterior que utiliza una lambda:

map<char, int> m = {{''a'', 1}, {''b'', 2}, {''c'', 3}, {''d'', 4}, {''e'', 5}};

int findVal = 3;
auto it = find_if(m.begin(), m.end(), [findVal](const Pair & p) {
    return p.second == findVal;
});
if (it == m.end()) {
    /*value not found*/
    cout << "*value not found*";
}
else {
    Pair v = *it;
    cout << v.second << "->" << v.first << "/n";
}

(gracias a @Nawaz por su contribución aquí: https://.com/a/19828596/1650814 )