反向地圖查找

Question

我有1對1的地圖。什麼是找到值的鍵的最佳方式，

即

爲例子，如果地圖是這個

KEY VALUE

a 1 
b 2 
c 3 
d 4 

我希望能夠找到對應於該關鍵3是C.

謝謝！

Answer 1

你可以做的事情不多。您可以選擇使用兩張地圖，使用來自Boost Multi-Index庫的多密鑰地圖，或進行線性搜索。

更新：最輕量級的開箱即用解決方案似乎是Boost.Bimap，它代表雙向地圖。

Answer 2

最直接的方法是維護一個平行的地圖，其中的值和關鍵是相反的（因爲關係是一對一的）。

Answer 3

除非地圖是巨大的，或者你有知道線性搜索太慢的一些其他的方式，我開始與線性搜索：

#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

另一種解決方案是使用（鮮爲人知？）Boost.Bimap：

Boost.Bimap是雙向映射 庫C++。通過Boost.Bimap，您可以在 中創建關聯容器，這兩種類型都可以用作關鍵字。 A bimap<X,Y>可以被認爲是std::map<X,Y>和 std::map<Y,X>的組合 。 bimap的學習曲線幾乎是平坦的，如果你知道如何使用標準容器 。一個很好的 努力已被放入 映射Boost.Bimap中的STL 的命名方案。該庫是 設計用來匹配常見的STL 容器。

Answer 5

假設你有一張地圖<X,Y>。構建第二個結構，可能是地圖<Y*,X*,Deref>，它使反向查找成爲可能，但避免了雙倍的存儲開銷，因爲使用指針不需要將每個X和Y存儲兩次。第二個結構只是指向第一個結構。

Answer 6

上@Robᵩ的回答上面使用拉姆達的變化：

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

（感謝@Nawaz爲他/她的貢獻在這裏：https://stackoverflow.com/a/19828596/1650814）

Answer 7

我知道這是一個非常古老的問題，但這個codeproject文章（http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map）是雙向映射的一個很好的例子。

這是一個示例程序，說明它是多麼容易：

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