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を使用して、これに適した機能を提供します。この出力反復子に割り当てられるものは何でも、ラップする単項関数に引数として渡されます。ラムダと組み合わせると、これは非常に簡単です。

#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

m13 番目のステップでは、 にあるが にないキーにゼロを追加します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

素朴な方法は、最初に宛先マップにすべてのキーを追加することです。次に、宛先マップの各キーに対して、最初のマップから対応する値を追加します。キーが見つからない場合はゼロを追加します。次に、2 番目のマップで同じことを行います。

于 2013-02-05T13:24:26.683 に答える
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 つの異なるケース) 実行されるため、おそらく単純化してコードの行数を減らすことができます...

ここでの実行時間は、(m1 の #)+(m2 の #)-(両方の #) です。おそらく、これは 1 つのセットの違い (または 1 つのマージ) とほぼ同じです。

ライブワークスペース

于 2013-02-06T11:55:46.443 に答える
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 に答える