Buscar en el mapa inverso

Question

Tengo un mapa de 1 a 1. ¿Cuál es la mejor manera de encontrar las claves de valores,

es decir

Para ejemplos, si el mapa es este

VALOR CLAVE

a 1 
b 2 
c 3 
d 4 

Quiero ser capaz de encontrar esa tecla correspondiente a 3 es C.

¡Gracias!

Answer 1

No hay mucho que pueda 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 ligera de la caja parece ser Boost.Bimap, que significa mapa bidireccional.

Answer 2

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

Answer 3

A menos que el mapa es enorme, o si tiene alguna otra forma de saber que la búsqueda lineal es demasiado lento, me gustaría empezar 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 4

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

Boost.Bimap es un bidireccionales mapas biblioteca de C++. Con Boost.Bimap usted puede crear contenedores asociativos en que ambos tipos pueden usarse como clave. Un bimap<X,Y> se puede considerar 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 conoce cómo para utilizar contenedores estándar. Un gran esfuerzo de se ha puesto en mapeando el esquema de nombres del STL en Boost.Bimap. La biblioteca es diseñada para coincidir con los contenedores STL comunes.

Answer 5

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

Answer 6

Una variante de @ respuesta de Robᵩ anterior que utiliza un 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/su contribución aquí: https://stackoverflow.com/a/19828596/1650814)

Answer 7

Sé que esto es una pregunta muy viejo, 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.

Se trata de 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; 
    }