4

我有 3 张地图：

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;

        }
    }
}

非常感谢你的帮助！！

4

3 回答 3

4

由于地图是有序的，您可以在线性时间内完成此操作。这是完成任务的一种可能方法：

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

请注意，这假定映射键顺序是默认值less<Key>。

于 2012-10-11T18:16:21.093 回答
2

你可以做

#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-11T16:48:47.790 回答
1

一种解决方案是

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());
}

这首先将所有条目从第一个映射复制到目标。然后，对于映射中的每个条目，它会在输出映射中查找相应的条目。如果它不存在，它会创建一个新向量（通过map::operator[]），否则，它会返回对现有 on 的引用。然后将第二个映射中的向量附加到结果中已经存在的向量。

缺点是您在目标地图中一遍又一遍地搜索结果地图，这似乎有点过分。由于两个地图都是排序的，它应该能够在线性时间内完成，而不是 N-log-N 时间。

于 2012-10-11T16:49:57.843 回答