地図が少ない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
これを行う最良の方法は何ですか?
最初に頭に浮かぶのは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
m1
3 番目のステップでは、 にあるが にないキーにゼロを追加します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で完全な例を参照してください。
素朴な方法は、最初に宛先マップにすべてのキーを追加することです。次に、宛先マップの各キーに対して、最初のマップから対応する値を追加します。キーが見つからない場合はゼロを追加します。次に、2 番目のマップで同じことを行います。
価値のあるものとして、少し高速に実行できる単純なブーストなしのソリューションを次に示します(大きな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 つのマージ) とほぼ同じです。
次のようなヘルパー関数はどうですか。
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 );