intersección de dos mapas STL

Question

Dado que tengo dos mapas STL, por ejemplo:

map<int, double> A; 
map<int, double> B; 

me gustaría llegar a la intersección de los dos mapas, algo de la forma:

map<int, pair<double,double> > C; 

Donde las claves son los valores en ambos A y B y el valor es un par de los valores de A y B, respectivamente. ¿Hay una manera limpia de STL para hacer esto?

Answer 1

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

No he probado esto, ni siquiera lo compilé ... pero debería ser O (n). Debido a que tiene una plantilla, debería funcionar con dos mapas que comparten el mismo tipo de clave.

Answer 2

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

Answer 3

No creo que haya una forma pura de STL de implementar lo que desee. La implementación manual no debería ser demasiado complicada.

Tenga en cuenta que std::set_intersection no es una solución. La razón principal es que compara los iteradores desreferenciados y luego copia uno de los elementos al iterador de salida.

Mientras comparación del iterador sin referencia completa incluye el valor asociado (que entiendo que no quiere considerar como parte de la clave), se puede resolver proporcionando un funtor comparación que sólo se pondría a prueba la tecla (std::pair<const Key, Value>::first), el problema del algoritmo que copia solo uno de los dos valores y no compone la solución no puede abordarse externamente.

EDITAR: Una simple aplicación de tiempo lineal de la función:

Nota, como comentarios @ Marcos Ransom, que esta solución añade un requisito adicional: las claves debe ser la igualdad comparables. Eso no es un problema con su solución here, o similar en la respuesta de @Matthiew M here. Sería vergonzoso modificar este algoritmo con esa corrección :)

Otra gran ventaja de la implementación de @Mark es que puede componer desde mapas que almacenan diferentes tipos de valores, siempre y cuando las claves sean las mismas (lo cual parece obvio requisito). Me gustaría que se upvote más de una vez allí ..

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

Answer 4

EDIT: Ya que estaba bastante seguro de que era una mejor solución STL similar a este, pensé que uno fuera. Es lo suficientemente diferente como para publicarlo como una respuesta separada.

Hay algunos trucos para esto. En primer lugar, te gustaría usar set_intersection, pero tienes dos mapas. La solución es un comparador personalizado y el algoritmo std :: transform. Alguien más familiarizado con la biblioteca estándar que yo probablemente pueda optimizar esto, pero funciona. Tenga en cuenta que boost :: bind le permitirá reducir las tontas funciones de ayuda que hacen que esto funcione.

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

Al igual que gran parte de C++, el uso final de todo lo que es bastante resbaladiza (todo en main()), pero la configuración es más detallado de lo que realmente nos gustaría.

Answer 5

Una (mejor) solución basada en el hecho de que map s están ordenados. (Lástima que lo haya pasado por alto.) Gracias a David Rodríguez - dribeas por la sugerencia.

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

} 

Answer 6

bien, vamos a estar listos para ensuciarse las manos :)

voy a estar utilizando std::mismatch y std::transform

En primer lugar, algunos tipos:

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; 

Entonces predicados

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

0 Ahora

principal:

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

Me parece una solución muy elegante ... a pesar de la parte de instalación awkard ya que necesitamos para asegurar que la primera gama termina más rápido que la segunda causa de mismatch ...

Observe que el avance es realmente estúpido, podríamos recorrer específicamente aquí hasta que tuviéramos *next.first.key == *next.second.key pero complicaría el ciclo.

Realmente no encuentran esto mejor que un lazo hecho a mano, aunque ... tener en cuenta:

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

Es mucho más compacto, probablemente más eficiente ... a veces las funciones que usted está buscando no son generales suficiente para estar en el STL :)

Answer 7

La siguiente es una simplificación de mi respuesta previous, principalmente aprovechando el hecho de que set_intersection PUEDE ser utilizado con mapas como entrada, pero solo si haces que la salida sea un conjunto de std: : pares El resultado también reduce intermedios a una sola lista de "teclas comunes".

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

Answer 8

Casi un año después ... pero sin embargo :)

Esta es para un recipiente conjunto, pero se puede cambiar fácilmente para usar un mapa:

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

Uso:

intersect(set1.begin(), set1.end(), 
      set2.begin(), set2.end(), 
      inserter(output_container, output_container.begin())); 

set1 y conjunto2 son ambos recipientes conjunto mientras output_container se puede ajustar, de la lista, de matriz etc ..

inserter genera un iterador de inserción

Answer 9

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