比較兩個（非STL）地圖是否相等

我們使用的第三方庫基本上是地圖/字典。它沒有提供任何平等測試兩個對象的方式，我們需要這樣做。比較兩個（非STL）地圖是否相等

更具體地，兩個映射S1 & S2被視爲相等，如果：

在S1每個鍵是在S2中的一個關鍵
在S2每個鍵是在S1
密鑰對於每一個鍵K in S1 S1 [K] == S2 [K]

注意，每張圖的內部排序是不相關的，可能不會被依賴，因此內部結構/成員的直接比較是不可能的。我們確實有辦法比較鍵和值的相等性。

什麼是最好的算法呢？僞C++就好了，因爲set類的確切API足夠接近std :: map我可以翻譯。

來源

2013-06-21 Mr. Boy

你可以通過一種方式遍歷集合來保證鍵的詞法順序嗎？ – Bathsheba

請參閱編輯 - no。 API不提供對內部結構的訪問。 –

簡單的蠻力？ –

比較大小

如果大小相等
- 迭代的第一組和每個按鍵的鍵：
  - 檢查的關鍵存在於第二套
  - 檢查，對於關鍵的元素相等
如果至少有一個元素是不相等的，在第一組的一個密鑰不在所述第二存在或大小不相等，則套是不平等的。

來源

2013-06-21 11:12:54 utnapistim

你打算如何比較不同集合中的元素是否相等？一個集合只會比較元素的等價性（例如，使用'<'） – TemplateRex

@TemplateRex，如果John詢問「對於S1中的每個密鑰K，S1 [K] == S2 [K]」，我將假設都獲得他的公共接口支持來自按鍵設置的值以及比較相等的值。我不確定你在問什麼（「一組只是比較元素的等價性」 - 你是指'std :: set's？） – utnapistim

如果集合通常是相等的，即不同是異常，那麼它可能是在迭代第一組中的密鑰之後，檢查組*的大小更有效。 –

那麼只要存儲在該集合中的最大值是正確的，那麼這種方法是有效的。取一個大小爲maximum value+1的數組，並將其初始化爲0。然後遍歷第一組和increment'key'位置的數組值，其值爲value。

現在通過第二組通過其value迭代並decrement的數組中的值的索引key在。

最後檢查所有數組值是否爲zero。如果不是，那麼他們是unequal，否則他們是equal。

時間複雜度：O(N)

內存：O(max_value)

來源

2013-06-21 11:16:04 nitish712

您提出的算法只檢查集具有相同的鍵，而不是相同的值。它也可以通過在任何迭代之前比較集合的大小來優化。 – utnapistim

@utnapistim我已經對其進行了相應的編輯。謝謝。 – nitish712

假設你的地圖API有迭代器（或指數），是有序的，不包含任何重複，並且還存儲了密鑰和映射類型爲嵌套類型定義，你可以實施std::map::operator==相同的語義在O(N)時間：

#include <functional> // less 
#include <algorithm> // includes 

// O(N) complexity 
template<class MyMap, class KeyCmp = std::less<typename MyMap::key_type, class TCmp = std::equal<typename MyMap::mapped_type> > 
bool set_equality(MyMap const& lhs, MyMap const& rhs, KeyCmp keycmp, TCmp tcmp) 
{ 
    typedef typename MyMap::value_type Pair; 

    return 
     lhs.size() == rhs.size() && 
     std::includes(
      lhs.begin(), lhs.end(), 
      rhs.begin(), rhs.end(), 
      [](Pair const& p1, Pair const& p2){ 
      return keycmp(p1.first, p2.first) && tcmp(p1.second, p2.second); 
     }) 
    ; 
}

來源

2013-06-21 11:30:29 TemplateRex

我認爲，一個主要的問題回答是多麼昂貴那本詞典STR單查詢ucture是。如果你有例如一個HashMap的O（1），比如utnapistim建議的比較循環的複雜度爲O（n）* O（1）= O（n）。如果底層字典是一個std :: map，那麼您將有O（log n）查找，從而使其整體爲O（n * log n）。如果你的字典是在一個未排序的數組或列表的基礎上實現的，你將會有O（n）查找，使得它總體上是O（n^2）。

我提到這些的原因是，您還可以對兩個詞典進行排序並比較結果。對它們進行排序是O（n * log n），就像std :: map一樣，所以在不知道查找的複雜性的情況下，您無法決定對序列進行排序是多少還是比較便宜。

我還想提及另一方面，那就是字典的排序。你說你不能假設任何東西，但只有一個我知道的共同結構不能保證相等的內容意味着平等的秩序，未排序的數組或鏈表。但是，由於查找是O（n），因此該字符執行效果不如字典，所以有人將其選爲底層容器的可能性很小。寫這個，我想知道hashmaps是否能夠保證它們是否有不同的桶尺寸和歷史，我真的不確定。我相信雖然最好的算法取決於字典查找的複雜性，所以我會試着找出更多關於這個的。即使是測量，也會比不了解任何事情更好。恕我直言，恕我直言，可以接受的是一種依賴特定行爲來表現的記錄完備的黑客行爲。

來源

2013-06-21 16:18:44

比較兩個（非STL）地圖是否相等

回答

相關問題