Recherche de carte inversée

Question

J'ai une carte de 1 à 1. Quelle est la meilleure façon de trouver les clés de valeurs,

-à-dire

Pour des exemples si la carte est cette

VALEUR CLÉ

a 1 
b 2 
c 3 
d 4 

Je veux être en mesure de trouver cette clé correspondant 3 est C.

Merci!

Answer 1

Il n'y a pas grand chose à faire à ce sujet. Vous avez des options pour travailler avec deux cartes, utilisez une carte multi-clés comme celle de la bibliothèque Boost Multi-Index, ou faites une recherche linéaire.

MISE À JOUR: Le plus léger de la solution de la boîte semble être Boost.Bimap, qui signifie carte bi-directionnelle.

Answer 2

La manière la plus directe serait de maintenir une carte parallèle où les valeurs et les clés sont inversées (puisque la relation est un à un).

Answer 3

À moins que la carte est énorme, ou si vous avez une autre façon de savoir que la recherche linéaire est trop lent, je commence par la recherche linéaire:

#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

Une autre solution serait d'utiliser (moins connue ?) Boost.Bimap:

Boost.Bimap est une carte bidirectionnelle bibliothèque C++. Avec Boost.Bimap vous pouvez créer des conteneurs associatifs dans dont les deux types peuvent être utilisés comme clé. Un bimap<X,Y> peut être considéré comme une combinaison d'un std::map<X,Y> et un std::map<Y,X>. La courbe d'apprentissage de bimap est presque plat si vous savez comment utiliser pour utiliser des conteneurs standard. Un grand effort de a été mis en cartographie le schéma de nommage de la STL dans Boost.Bimap. La bibliothèque est conçue pour correspondre aux conteneurs communs STL .

Answer 5

Disons que vous avez une carte <X,Y>. Construire une deuxième structure, peut-être une carte <Y*,X*,Deref> qui permet la recherche inversée, mais évite de doubler la surcharge de stockage, car, en utilisant des pointeurs, il n'est pas nécessaire de stocker chaque X et Y deux fois. La deuxième structure a simplement des pointeurs dans le premier.

Answer 6

Une variante de @ réponse de Robᵩ ci-dessus qui utilise 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"; 
} 

(grâce à @Nawaz pour son/sa contribution ici: https://stackoverflow.com/a/19828596/1650814)

Answer 7

Je sais que c'est une question très ancienne, mais Cet article codeproject (http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map) est un très bon exemple d'une carte bidirectionnelle.

Ce programme est un exemple qui montre combien il est facile:

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