Odwracanie mapy odwrotnej

Question

Mam mapę od 1 do 1. Jaki jest najlepszy sposób, aby znaleźć klucze z wartościami,

tj

Przykłady jeśli mapa jest to

kluczową wartością

a 1 
b 2 
c 3 
d 4 

Chcę być w stanie znaleźć ten klucz odpowiadający 3 to C.

Dzięki!

Answer 1

Nie można wiele z tym zrobić. Masz opcje pracy z dwiema mapami, korzystaj z mapy wieloblokowej, np. Z biblioteki Boost Multi-Index, lub przeszukuj liniowo.

AKTUALIZACJA: Najbardziej lekkim rozwiązaniem z pudełka wydaje się być Boost.Bimap, co oznacza mapę dwukierunkową.

Answer 2

Najbardziej bezpośrednim sposobem byłoby zachowanie równoległej mapy, w której wartości i klucze są odwrócone (ponieważ relacja jest jeden do jednego).

Answer 3

Jeżeli mapa jest ogromna, lub masz jakiś inny sposób, wiedząc, że przeszukiwanie liniowe jest zbyt powolny, to bym zacząć przeszukiwanie liniowe:

#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

Innym rozwiązaniem byłoby wykorzystanie (mniej znanych ?) Boost.Bimap:

Boost.Bimap jest dwukierunkowe mapy biblioteka dla C++. Dzięki Boost.Bimap możesz tworzyć zbiorcze kontenery w , z których oba mogą być używane jako klucze. A bimap<X,Y> może być traktowana jako kombinacja i . Krzywa uczenia się bimap jest prawie płaska, jeśli wiesz, jak używać standardowych pojemników. W ramach projektu wprowadzono wielką próbę odwzorowania schematu nazewnictwa STL w pliku Boost.Bimap. Biblioteka jest zaprojektowana tak, aby pasowała do typowych kontenerów STL .

Answer 5

Powiedz, że masz mapę <X,Y>. Zbuduj drugą strukturę, być może mapę <Y*,X*,Deref>, która umożliwia odwrotne wyszukiwanie, ale unika podwojenia kosztu pamięci masowej, ponieważ za pomocą wskaźników nie ma potrzeby przechowywania dwóch X i Y dwa razy. Druga struktura ma po prostu wskaźniki w pierwszym.

Answer 6

Odmianą @ odpowiedź Robᵩ za wyżej który wykorzystuje 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"; 
} 

(dzięki @Nawaz dla jego/jej wkładu tutaj: https://stackoverflow.com/a/19828596/1650814)

Answer 7

wiem, że to jest bardzo stare pytanie, ale ten artykuł codeproject (http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map) jest całkiem dobrym przykładem dwukierunkowej mapy.

To jest przykładowy program, który pokazuje, jak łatwo jest:

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