2

我的地图很少std::map< char, int >

First map:
a - 1
b - 2
c - 3

Second map:
a - 5
c - 6
e - 7

我想将它们连接成std::map< char, std::vector< int > >

a - 1 5
b - 2 0
c - 3 6
e - 0 7

最好的方法是什么？

4

4 回答 4

3

首先想到的是std::merge算法。不幸的是，源和目标范围的值类型不兼容，所以我们需要一些可以为我们转换它的东西。Boost 通过Function Output Iterator为此提供了一个很好的工具。分配给此输出迭代器的任何内容都作为参数传递给它包装的一元函数。与 lambdas 一起，这非常简单：

#include <boost/function_output_iterator.hpp>

std::map<char, int> m1 { {'a',1}, {'b',2}, {'c',3} };
std::map<char, int> m2 { {'a',5}, {'c',6}, {'e',7} };

std::map<char, std::vector<int>> m3;

typedef std::map<char, int>::value_type source_type;
auto push_value =
    [&m3](const source_type& p) { m3[p.first].push_back(p.second); };

std::merge(m1.begin(), m1.end(), m2.begin(), m2.end(),
    boost::make_function_output_iterator(push_value));

这还不是我们想要的。m3看起来像这样：

a - 1 5
b - 2
c - 3 6
e - 7

对于在m2但不在的键，m1我们需要在向量的前面挤压一个零。我们可以set_difference在合并之前做到这一点。我们需要使用只比较地图键的自定义比较器：

auto push_zero =
    [&m3](const source_type& p) { m3[p.first].push_back(0); };
auto cmp =
    [](const source_type& p1, const source_type& p2) { return p1.first < p2.first; };

std::set_difference(m2.begin(), m2.end(), m1.begin(), m1.end(),
    boost::make_function_output_iterator(push_zero), cmp);

m3就是现在：

a - 1 5
b - 2
c - 3 6
e - 0 7

在第三步中，我们为 inm1但不在 in的键添加一个零m2：

std::set_difference(m1.begin(), m1.end(), m2.begin(), m2.end(),
    boost::make_function_output_iterator(push_zero), cmp);

现在我们有了我们想要的：

a - 1 5
b - 2 0
c - 3 6
e - 0 7

请参阅LiveWorkspace上的完整示例。

于 2013-02-05T19:53:01.513 回答
2

天真的方法是首先在目标映射中添加所有键。然后为目标映射中的每个键添加第一个映射中的相应值，如果未找到该键，则添加零。然后对第二张地图做同样的事情。

于 2013-02-05T13:24:26.683 回答
0

像这样的辅助函数怎么样：

void one_map ( const std::map <char, int> &source, std::map<char, std::vector<int> > &dest, size_t idx )
    for ( auto const &p : source )
        dest [ p.first ] [ idx ] += 1;
    }

void fill_map ( const std::map <char, int> &source, std::map<char, std::vector<int> &dest , const std::vector<int> &zeroes ) {
    for ( auto const &p : source )
        if ( !dest.find ( p.first ))
            dest [ p.first ] = zeroes;
    }

然后你可以写：

std::vector<int> z (3, 0);  // three zeros
fill_map ( a, dest, z );
fill_map ( b, dest, z );
fill_map ( c, dest, z );

one_map  ( a, dest, 0 );
one_map  ( b, dest, 1 );
one_map  ( c, dest, 2 );
于 2013-02-05T21:35:19.437 回答
0

对于它的价值，这是一个简单的无提升解决方案，它可能会运行得更快一些（不是在大 O 中，而是在总迭代次数中）：

   std::map<char,int>::iterator i,j;
   i = m1.begin(); j = m2.begin();

   while (i!=m1.end() || j!=m2.end()) {
      if (j==m2.end() || (i!=m1.end()&&(i->first < j->first))) {
         m3[i->first].push_back(i->second);
         m3[i->first].push_back(0);
         i++;
      } else if (i==m1.end() || (i->first > j->first)) {
         m3[j->first].push_back(0);
         m3[j->first].push_back(j->second);
         j++;         
      } else if (i->first == j->first) {
         m3[i->first].push_back(i->second);
         m3[j->first].push_back(j->second);
         i++;j++;
      } 
   }

可能可以简化以减少代码行数，因为 push_backs 每次执行 3 次（3 种不同情况）......

这里的运行时间是 (# in m1)+(# in m2)-(# in both)。很可能，这大致等于单个集合差异（或单个合并）。

现场工作空间

于 2013-02-06T11:55:46.443 回答