两个'std::map'的交集

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

std::set_intersection

std::pair<const Key, Value>::first

here here

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

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

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

}

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

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

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

previous

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

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

inserter

template<typename K, typename V>
std::map<K, V> UnionMaps(const std::map<K, V> & left, const std::map<K, V> & right)
{
    std::map<K, V > result;
    typename std::map<K, V>::const_iterator il = left.begin();
    typename std::map<K, V>::const_iterator ir = right.begin();
    while (il != left.end() && ir != right.end())
    {
        if ((il->first < ir->first)){
            result.insert(make_pair(il->first, il->second));
            ++il;
        }else if ((ir->first < il->first)){
            result.insert(make_pair(ir->first, ir->second));
            ++ir;
        }else{
            result.insert(make_pair(il->first, il->second+ir->second));//add 
            ++il;
            ++ir;
        }
    }
    while (il != left.end() ){
        result.insert(make_pair(il->first, il->second));
        il++;
    }
    while (ir != right.end() ){
        result.insert(make_pair(ir->first, ir->second));
        ir++;
    }
    return result;
}