C++使用無序鍵組合進行地圖查找

我想創建一個unordered_map，其中鍵是兩個整數的組合。由於鍵值順序應比較時被忽略，我想用一個unordered_set像這樣關鍵的：C++使用無序鍵組合進行地圖查找

#include <unordered_set> 
#include <unordered_map> 

using namespace std; 

int main() 
{ 
    unordered_set<int> key_set1 = {21, 42}; 
    unordered_map<unordered_set<int>, char> map; 
    map[key_set1] = 'a'; 
    ... 
    unordered_set<int> key_set2 = {42, 21}; 
    if(map[key_set2] == map[key_set2]) 
     success(); 
}

在它看起來像一些問題與哈希函數編譯時間：

error: no match for call to ‘(const std::hash<std::unordered_set<int> >) (const std::unordered_set<int>&)’ 
    noexcept(declval<const _Hash&>()(declval<const _Key&>()))>

如何我能解決這個問題嗎？還是有更好的方法/數據結構？

來源

2016-07-05 Corbie

你可能會想std :: ints對，但你需要爲此添加一個散列。或者將您的密鑰更改爲64位整數，並將您的2整數與1 64位整數相結合。 – paulm

使用'set'作爲密鑰在這裏除了減慢程序速度外沒有任何其他用途。 –

其目的是，關鍵值可以無序。所以我的回答中的比較是真實的。 – Corbie

正如前面指出的那樣，直接使用std::pair作爲一個鍵，你需要爲它明確定義一個散列函數。如果你想避免這種情況，你可以做2個無符號整數，逐位組合成1：

uint64_t makeKey(uint32_t a, uint32_t b) 
{ 
    return a < b ? (static_cast<uint64_t>(a) << 32) + b : (static_cast<uint64_t>(b) << 32) + a; 
} 

int main() 
{ 
    auto key_set1 = makeKey(21, 42); 

    unordered_map<uint64_t, char> map; 
    map[key_set1] = 'a'; 
    //... 

    auto key_set2 = makeKey(42, 21); 
    if(map[key_set1] == map[key_set2]) 
     std::cout << "success" << std::endl; 
}

來源

2016-07-05 11:03:16 Smeeheey

可能是我認爲最高效的方法:) – paulm

這對於嘗試以隨機順序查找密鑰沒有幫助，但首先對它們進行排序似乎是最高效的方式;-) – Corbie

問題是unordered_set沒有被構建爲用作無序容器中的鍵。

如果你總是使用正好兩個整數，這將是更經濟，爲您使用一對整數作爲重點，並增加一個功能，使一個正常有序對由兩個整數：

pair<int,int> unordered_key(int a, int b) { 
    return a<b?make_pair(a, b):make_pair(b, a); 
}

來源

2016-07-05 10:54:51 dasblinkenlight

但他說整數的順序並不重要。 –

（我認爲這意味着無序的整數_does_問題） –

如果沒關係，那麼使用一對更好......那麼爲什麼它很重要？ – paulm

unordered_set沒有預定義的散列函數，所以你必須實現你自己的;這裏有文檔http://en.cppreference.com/w/cpp/utility/hash。

基本上你需要：

// custom specialization of std::hash can be injected in namespace std 
namespace std 
{ 
    template<> struct hash<unordered_set<int>> 
    { 
     std::size_t operator()(unordered_set<int> const& s) const 
     { 
      std::size_t hash = 0; 
      for (auto && i : s) hash ^= std::hash<int>()(i); 
      return hash; 
     } 
    }; 
}

現在xor不結合散列函數推薦的方式，但它應該在這種情況下工作，特別是因爲這既是無序和設置。因爲它是無序的，你需要一個可交換的函數。推薦的哈希組合器沒有這個屬性，因爲您通常希望「abc」以與「bca」不同的哈希值。其次，這是一套確保你不會有任何重複元素的事實。這可以使您的散列函數免於失敗，因爲x^x == 0。

我還應該提到你想在cpp文件中定義這個，所以你不要在std類型中向每個人公開這個特定的哈希實現。

來源

2016-07-05 10:55:58 csiz

這實際上非常有幫助。雖然我認爲訂購和組合鍵是單一的更高性能。 – Corbie

如果你的鑰匙總是一對，那絕對是更好的解決方案。你可能想要定義一個'unordered_pair'類型來使你的意圖更清晰。或'使用unordered_key = uint64_t'。 – csiz

我認爲你有UB專門'散列'不適合你的類型。 – Jarod42

由於訂單在這裏並不重要，你可以使用std::pair用定製的工廠強迫命令兩個整數的：

std::pair<int, int> make_my_pair(int x, int y) { 
    return std::make_pair(std::min(x, y), std::max(x, y)); 
}

當然，這隻會如果你使用make_my_pair始終如一地工作。

或者，您可以定義您自己的具有類似屬性的關鍵類。

來源

2016-07-05 11:06:47

這會導致同樣的問題。由於沒有適當的散列函數，該對還不能用作映射的鍵。 – Corbie

那麼我的理解是你想使用'unordered_map'，因爲順序並不重要，但只要鍵被正確定義，你也可以使用'map'。當然，除非選擇無序容器有其他原因。 –

C++使用無序鍵組合進行地圖查找

回答

相關問題