が 2 つあるとすると、次std::mapのように言います。
map<int, double> A;
map<int, double> B;
次の形式の 2 つのマップの交点を取得したいと思います。
map<int, pair<double,double> > C;
ここで、キーは と の両方の値であり、 値はそれぞれとの値のペアです。標準ライブラリを使用するクリーンな方法はありますか?ABAB
12108 次
9 に答える
17
template<typename KeyType, typename LeftValue, typename RightValue>
map<KeyType, pair<LeftValue, RightValue> > IntersectMaps(const map<KeyType, LeftValue> & left, const map<KeyType, RightValue> & right)
{
map<KeyType, pair<LeftValue, RightValue> > result;
typename map<KeyType, LeftValue>::const_iterator il = left.begin();
typename map<KeyType, RightValue>::const_iterator ir = right.begin();
while (il != left.end() && ir != right.end())
{
if (il->first < ir->first)
++il;
else if (ir->first < il->first)
++ir;
else
{
result.insert(make_pair(il->first, make_pair(il->second, ir->second)));
++il;
++ir;
}
}
return result;
}
私はこれをテストしたり、コンパイルしたりしていません...しかし、O(n)である必要があります。テンプレート化されているため、同じキー タイプを共有する 2 つのマップで動作するはずです。
于 2010-09-22T21:05:17.353 に答える
11
あなたが望むものを実装する純粋なSTLの方法はないと思います。手動での実装が複雑になりすぎないようにする必要があります。
std::set_intersection解決策ではないことに注意してください。主な理由は、逆参照された反復子を比較し、要素の 1 つを出力反復子にコピーすることです。
完全な逆参照されたイテレータの比較には関連する値が含まれますが (キーの一部とは見なしたくないと理解しています)、キーのみをテストする比較ファンクターを提供することで解決できます ( std::pair<const Key, Value>::first)、アルゴリズムの問題2 つの値の 1 つだけをコピーし、ソリューションを構成しないことは、外部から取り組むことはできません。
編集:関数の単純な線形時間実装:
@Mark Ransomがコメントしているように、このソリューションには追加の要件が追加されることに注意してください。キーは同等である必要があります。これは、彼のソリューションhereの問題ではありません。同様に、@Matthiew M の回答でも問題ありません。その修正でこのアルゴリズムを変更するのは恥ずべきことです:)
@Mark の実装のもう 1 つの大きな利点は、キーが同じである限り、異なる値の型を格納するマップから構成できることです (これは明らかな要件のようです)。そこで何度も賛成票を投じたいと思います..
template <typename Key, typename Value>
std::map<Key,std::pair<Value,Value> >
merge_maps( std::map<Key,Value> const & lhs, std::map<Key,Value> const & rhs )
{
typedef typename std::map<Key,Value>::const_iterator input_iterator;
std::map<Key, std::pair<Value,Value> > result;
for ( input_iterator it1 = lhs.begin(), it2 = rhs.begin(),
end1 = lhs.end(), end2 = rhs.end();
it1 != end1 && it2 != end2; )
{
if ( it1->first == it2->first )
{
result[it1->first] = std::make_pair( it1->second, it2->second );
++it1; ++it2;
}
else
{
if ( it1->first < it2->first )
++it1;
else
++it2;
}
}
return result;
}
于 2010-09-22T19:14:51.313 に答える
7
#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;
typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;
typedef pair< ValueType, ValueType > ValueTypePair;
typedef map< KeyType, ValueTypePair > MyMapIntersection;
int main() {
MyMap A;
MyMap B;
MyMapIntersection C;
// fill up A, B
for( MyMapConstIter cit = A.begin(); cit != A.end(); ++cit ) {
const KeyType x = cit->first;
MyMapConstIter found = B.find( x );
if( found != B.end() ) {
ValueTypePair valuePair =
ValueTypePair( cit->second, found->second );
C.insert( pair< KeyType, ValueTypePair>( x, valuePair ) );
}
}
}
于 2010-09-22T19:12:21.890 に答える
1
以下は私の前の答えを単純化したもので、主にset_intersectionを入力としてマップで使用できるという事実を利用していますが、出力をstd::pairsのセットにする場合に限ります。結果はまた、中間体を単一の「共通キー」リストに削減します。
#include <algorithm>
#include <map>
#include <set>
struct cK { //This function object does double duty, the two argument version is for
//the set_intersection, the one argument version is for the transform
std::map<int,double> &m1,&m2;
cK(std::map<int,double> &im1, std::map<int,double> &im2) : m1(im1), m2(im2)
std::pair<int,std::pair<double,double> > operator() (std::pair<int,double> v
return std::make_pair(v.first, std::make_pair(m1[v.first],m2[v.first]));
}
bool operator() (std::pair<int,double> v1, std::pair<int,double> v2) {
return v1.first < v2.first;
}
};
int main() {
std::map<int,double> m1, m2;
m1[0]=0;m1[1]=1; m1[2]=2; m1[3]=3;
m2[1]=11;m2[2]=12;m2[3]=13;m2[4]=14;
// Get the subset of map1 that has elements in map2
std::set<std::pair<int,double> > sIntersection;
cK compareKeys(m1,m2);
std::set_intersection(m1.begin(),m1.end(),m2.begin(),m2.end(),
std::inserter(sIntersection,sIntersection.begin()),compareKeys);
// Use a custom transform to produce an output set
std::map<int, std::pair<double,double> > result;
std::transform(sIntersection.begin(),sIntersection.end(),
std::inserter(result,result.begin()), compareKeys);
return 0;
}
于 2010-09-23T19:32:57.503 に答える
1
さて、あなたの手を汚す準備をしましょう:)
使用std::mismatchしますstd::transform
まず第一に、いくつかのタイプ：
typedef std::map<int, double> input_map;
typedef input_map::const_reference const_reference;
typedef input_map::const_iterator const_iterator;
typedef std::pair<const_iterator,const_iterator> const_pair;
typedef std::map<int, std::pair<double,double> > result_map;
次に述語
bool less(const_reference lhs, const_reference rhs)
{
return lhs.first < rhs.first;
}
result_map::value_type pack(const_reference lhs, const_reference rhs)
{
assert(lhs.first == rhs.first);
return std::make_pair(lhs.first, std::make_pair(lhs.second, rhs.second));
}
現在メイン：
result_map func(input_map const& m1, input_map const& m2)
{
if (m1.empty() || m2.empty()) { return result_map(); }
// mismatch unfortunately only checks one range
// god do I hate those algorithms sometimes...
if (*(--m1.end()) < *(--m2.end()) { return func(m2, m1); }
const_pair current = std::make_pair(m1.begin(), m2.begin()),
end = std::make_pair(m1.end(), m2.end());
result_map result;
// Infamous middle loop, the check is middle-way in the loop
while(true)
{
const_pair next = std::mismatch(p.first, end.first, p.second, less);
std::transform(current.first, next.first, current.second,
std::inserter(result, result.begin()), pack);
// If any of the iterators reached the end, then the loop will stop
if (next.first == end.first || next.second == end.second) { break; }
// Advance the lesser "next"
if (less(*next.first, *next.second)) { ++next.first; }
else { ++next.second; }
current = next;
}
return result;
}
私はこのソリューションが非常にエレガントだと思います...最初の範囲が2番目の範囲よりも速くなるようにする必要があるため、awkardのセットアップ部分にもかかわらずmismatch...
前進は本当にばかげていることに注意してください。ここでループすることができます*next.first.key == *next.second.keyが、ループが複雑になります。
私は本当にこれが手作りのループよりも優れているとは思いません...考えてみてください：
result_map func2(input_map const& lhs, input_map const& rhs)
{
result_map result;
for (const_iterator lit = lhs.begin(), lend = lhs.end(),
rit = rhs.begin(), rend = rhs.end();
lit != lend && rit != rend;)
{
if (lit->first < rit->first) { ++lit; }
else if (rit->first < lit->first) { ++rit; }
else
{
result[lit->first] = std::make_pair(lit->second, rit->second);
++lit, ++rit;
}
}
return result;
}
それははるかにコンパクトで、おそらくより効率的です...時々あなたが探している関数はSTLにあるほど一般的ではありません:)
于 2010-09-22T21:13:33.573 に答える
1
編集：これにはより良いSTLのような解決策があると確信していたので、私はそれを見つけました。別の回答として投稿しているのは十分に異なります。
これにはいくつかのコツがあります。まず、set_intersection を使用したいのですが、マップが 2 つあります。解決策は、カスタム コンパレータと std::transform アルゴリズムです。私よりも標準ライブラリに精通している人は、おそらくこれを最適化できますが、機能します。boost::bind を使用すると、これを機能させる愚かなヘルパー関数を削減できることに注意してください。
#include <algorithm>
#include <map>
#include <set>
bool myLess(const std::map<int,double>::value_type &v1,
const std::map<int,double>::value_type &v2) {
return v1.first < v2.first;
}
int getKey(const std::map<int,double>::value_type &v) {
return v.first;
}
struct functor {
std::map<int,double> &m1,&m2;
functor(std::map<int,double> &im1, std::map<int,double> &im2) : m1(im1), m2(im2) {}
std::pair<int,std::pair<double,double> > operator() (int x) {
return std::make_pair(x, std::make_pair(m1[x],m2[x]));
}
};
int main() {
std::map<int,double> m1, m2;
m1[0]=0;m1[1]=1; m1[2]=2; m1[3]=3;
m2[1]=11;m2[2]=12;m2[3]=13;m2[4]=14;
std::set<int> keys1,keys2,keys;
//Extract the keys from each map with a transform
std::transform(m1.begin(),m1.end(),std::inserter(keys1,keys1.begin()),getKey);
std::transform(m2.begin(),m2.end(),std::inserter(keys2,keys2.begin()),getKey);
//set_intersection to get the common keys
std::set_intersection(keys1.begin(),keys1.end(),keys2.begin(),keys2.end(),
std::inserter(keys,keys.begin()));
std::map<int, std::pair<double,double> > result;
functor f(m1,m2); //stash our maps into the functor for later use
//transform from the key list to the double-map
std::transform(keys.begin(),keys.end(),std::inserter(result,result.begin()),f);
return 0;
}
ほとんどの C++ と同様に、すべての最終的な使用法はかなり洗練されています (main() 内のすべて) が、セットアップは私たちが本当に望んでいるよりも冗長です。
于 2010-09-22T20:09:10.893 に答える
1
maps がソートされているという事実に基づく (より良い) ソリューション。(私がそれを見落としたことを恥じてください。) David Rodríguez に感謝します - 提案のための dribeas。
#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;
typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;
typedef pair< ValueType, ValueType > ValueTypePair;
typedef map< KeyType, ValueTypePair > MyMapIntersection;
void constructInsert( MyMapIntersection & c, MyMapConstIter const & acit,
MyMapConstIter const & bcit ) {
ValueTypePair valuePair = ValueTypePair( acit->second, bcit->second );
c.insert( pair< KeyType, ValueTypePair>( acit->first, valuePair ) );
}
int main() {
MyMap A;
MyMap B;
MyMapIntersection C;
// fill up A, B
MyMapConstIter acit, bcit;
for( acit = A.begin(), bcit = B.begin();
(acit != A.end()) && (bcit != B.end()); /* Inside loop */ ) {
const KeyType aKey = acit->first;
const KeyType bKey = bcit->first;
if( aKey < bKey ) {
++acit;
}
else if( aKey == bKey ) {
constructInsert( C, acit, bcit );
++acit;
++bcit;
}
else {
++bcit;
}
}
}
于 2010-09-22T21:10:00.217 に答える
0
ほぼ1年後...しかし、それでも:)
これはセット コンテナ用ですが、マップを使用するように簡単に変更できます。
template <class InputIterator, class OutputIterator>
OutputIterator intersect(InputIterator lf, InputIterator ll,
InputIterator rf, InputIterator rl,
OutputIterator result)
{
while(lf != ll && rf != rl)
{
if(*lf < *rf)
++lf;
else if(*lf > *rf)
++rf;
else
{
*result = *lf;
++lf;
++rf;
}
}
return result;
}
使用法：
intersect(set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter(output_container, output_container.begin()));
set1 と set2 は両方ともセット コンテナーですが、output_container はセット、リスト、配列などにすることができます。
inserterは挿入イテレータを生成します
于 2011-06-21T12:16:37.443 に答える