Tra cứu bản đồ đảo ngược

Question

Tôi có bản đồ 1 đến 1. Có gì cách tốt nhất để tìm chìa khóa từ giá trị,

tức

Đối với ví dụ nếu bản đồ là

KEY VALUE này

a 1 
b 2 
c 3 
d 4 

Tôi muốn để có thể thấy rằng chìa khóa tương ứng với 3 là C.

Cảm ơn!

Answer 1

Không có nhiều việc bạn có thể làm. Bạn có các tùy chọn để làm việc với hai bản đồ, sử dụng bản đồ nhiều phím như một từ thư viện Boost Multi-Index hoặc thực hiện tìm kiếm tuyến tính.

CẬP NHẬT: Giải pháp nhẹ nhất trong số hộp có vẻ là Boost.Bimap, viết tắt của bản đồ hai chiều.

Answer 2

Cách trực tiếp nhất là duy trì một bản đồ song song nơi các giá trị và khóa được đảo ngược (vì mối quan hệ là một với một).

Answer 3

Trừ khi bản đồ là rất lớn, hoặc bạn có một số cách khác biết rằng tìm kiếm tuyến tính là quá chậm, tôi muốn bắt đầu với việc tìm kiếm tuyến tính:

#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

Một giải pháp sẽ được sử dụng (ít được biết đến ?) Boost.Bimap:

Boost.Bimap là một bản đồ hai chiều thư viện cho C++. Với Boost.Bimap bạn có thể tạo vùng chứa liên kết trong cả hai loại có thể được sử dụng làm khóa. A bimap<X,Y> có thể được coi là kết hợp của std::map<X,Y> và std::map<Y,X>. Đường cong học tập của bimap gần như bằng phẳng nếu bạn biết cách để sử dụng các vùng chứa tiêu chuẩn. Một nỗ lực tuyệt vời của đã được đưa vào ánh xạ sơ đồ đặt tên của STL trong Boost.Bimap. Thư viện là được thiết kế để khớp với các container STL phổ biến.

Answer 5

Giả sử bạn có bản đồ <X,Y>. Xây dựng cấu trúc thứ hai, có lẽ là bản đồ <Y*,X*,Deref> cho phép tra cứu ngược lại nhưng tránh tăng gấp đôi chi phí lưu trữ, bởi vì, sử dụng con trỏ, không cần lưu trữ từng X và Y hai lần. Cấu trúc thứ hai chỉ đơn giản là có con trỏ vào đầu tiên.

Answer 6

Một biến thể của @ câu trả lời Robᵩ của trên có sử dụng một 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"; 
} 

(nhờ @Nawaz cho/đóng góp của ông bà ở đây: https://stackoverflow.com/a/19828596/1650814)

Answer 7

Tôi biết đây là một câu hỏi thực sự cũ nhưng bài viết này (http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map) là một ví dụ khá tốt về bản đồ hai chiều.

Đây là một chương trình ví dụ cho thấy cách dễ dàng là:

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