如何查找2張地圖中常見的所有鍵？

我有3個地圖：如何查找2張地圖中常見的所有鍵？

map<string, vector<int> > map1 
map<string, vector<int> > map2 
map<string, vector<int> > map3

我需要創建第三張地圖與現有的兩個MAP1和MAP2與它們對應的載體中的所有字符串。事情是，即使字符串是相同的，它們的向量可以不同，我必須將來自兩個常用字符串的所有向量附加到1個向量中。這就是我想，但我有種迷失：

for(map<string, vector<int> >::iterator it1=map1.begin(); it1 != map1.end(); it1++) 
{ 
    string name = (*it1).first; 
    for(map<string, vector<int> >::iterator it2=map2.begin(); it2 != map2.end(); it2++) 
    { 
     string name2 = (*it2).first; 
     if (name == name2) 
     { 
      map3[name2] = (*it2).second; 

     } 
    } 
}

非常感謝您的幫助！

來源

2012-10-11 snazziii

你是否正在做一組交叉鍵（結果只有那些存在於兩者中的鍵）或一組聯合（如果它出現在map1或map2或兩者中，結果將有一個鍵）。 –

@Dave S set union – snazziii

@sumrania：Union將是A中的所有鍵和B中的所有鍵，而不是僅在兩個集中的所有鍵。戴夫S是正確的。 –

由於地圖是有序的，你可以在線性時間內做到這一點。這是一種可能的方式做任務：

#include <map> 
#include <string> 
#include <vector> 

typedef std::vector<int> vec_t; 
typedef std::map<std::string, vec_t> map_t; 
typedef map_t::const_iterator iter_t; 

int main() 
{ 
    map_t map1, map2, map3; 

    iter_t it1 = map1.begin(); 
    iter_t it2 = map2.begin(); 

    while (it1 != map1.end() && it2 != map2.end()) { 
     if (it1->first < it2->first) { 
      ++it1; 
     } else if (it2->first < it1->first) { 
      ++it2; 
     } else { // equal keys 
      vec_t temp(it1->second); 
      temp.insert(temp.end(), it2->second.begin(), it2->second.end()); 
      map3[it1->first].swap(temp); // swap contents to new map entry 
      ++it1; 
      ++it2; 
     } 
    } 
}

注意，這是假定map關鍵字排序是默認less<Key>。

來源

2012-10-11 18:16:21 Blastfurnace

是不是it1-> first和it2-> first strings？你如何使用if條件來設置一個字符串比另一個字符串少？ – snazziii

@sumrania：是的，鍵是字符串。由於映射的內容是按鍵排序的，我只是使用__string comparison__來測試哪個字符串比其他字符串少。鑰匙沒有被改變，只是比較。（'std :: string'定義了一個'operator <'，它執行_less-than_比較）。 – Blastfurnace

你可以做

#include <algorithm> // for std::copy 
#include <iterator> // for std::back_inserter 
#include <map> 
... 

for(auto it = map1.begin(); it != map1.end(); ++it) 
{ 
    auto fit = map2.find(it->first); 
    if(fit != map2.end() 
    { 
     map3[it->first] = it->second; 
     std::copy(fit->second.begin(), fit->second.end(), std::back_inserter(map3[it->first])); 
    } 
}

來源

2012-10-11 16:48:47 Asha

一種解決方案是

map3 = map1; 
typedef map<string, vector<int> > map_type; 

for(map_type::iterator itr = map2.begin(); itr != map2.end(); ++itr) 
{ 
    vector<int>& ref = map3[itr->first]; 
    ref.insert(ref.end(), itr->second.begin(), itr->second.end()); 
}

這第一個副本從第1映射到目標的所有條目。然後，對於地圖中的每個條目，在輸出映射中查找相應條目。如果它不存在，它將創建一個新的矢量（通過map::operator[]），否則它將返回對現有的引用。然後將第二張地圖中的矢量附加到結果中已經存在的矢量上。

不利的一面是，你在目的地地圖中一遍又一遍搜索得到的地圖，這似乎有點過分。由於這兩個圖都是排序的，它應該能夠在線性時間內完成，而不是N-log-N時間。

來源

2012-10-11 16:49:57

如何查找2張地圖中常見的所有鍵？

回答

相關問題