存儲對

Question

我得對的映射存儲雙重映射最有效的方法：

boost::unordered_map<pair<int, int>, double> P; 

我發現訪問地圖是算法的瓶頸。

我只插入一次值（成千上萬對）。我有時更新值，有時只是查找。

什麼是優化查找和更新值的運行時間的方法？

編輯：

下面是我環路了數據：

p = make_pair(u, v); 
q = P[p]; 

我發現，第二行花費更多的時間做一對，因爲我仰視很多時候對於許多按鍵來說都需要很長時間。

Answer 1

你可以嘗試將兩個整數合併爲一個整數，並將其作爲一個鍵。如果使用的int整個值範圍（假設4個字節），一個long long（假定8個字節）可以含有2：

int a = ...; 
int b = ...; 
long long combined = (static_cast<long long>(a) << 32) | b; 

當然，如果該值將適合在short，則可以使用較小的數據類型。爲了清晰和便攜，建議使用固定尺寸的類型，如std::int32_t。

它已經足夠適應散列函數，以不同的方式組合std::pair的first和second成員。爲此，最好更準確地知道哪個部分佔用最多的時間。

如果散列函數本身不是問題，則可以嘗試使用不同的數據結構，如boost::flat_map。