przecięciu dwóch mapach STL

Question

Zważywszy, że mam dwie mapy STL, powiedzieć:

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

Chciałbym uzyskać przecięcie dwóch mapach, coś w postaci:

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

Gdzie klucze są wartościami zarówno A i B, a wartość jest parą wartości odpowiednio z A i B. Czy istnieje sposób czysty STL-like to o tym?

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

Nie przetestowałem tego ani nawet nie skompilowałem ... ale powinien to być O (n). Ponieważ jest szablonem, powinien działać z dowolnymi dwiema mapami, które mają ten sam typ klucza.

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

Nie sądzę, że istnieje czysty sposób STL realizacji tego, co chcesz. Ręczna realizacja nie powinna być zbyt skomplikowana.

Należy pamiętać, że std::set_intersection nie jest rozwiązaniem. Głównym powodem jest to, że porównuje on iteratory dereferencyjne, a następnie kopiuje jeden z elementów do iteratora wyjściowego.

Choć porównanie pełnej dereferencjonowane iterator zawiera skojarzony wartość (co rozumiem, że nie chcesz, aby rozważyć jako część kluczowego), może być rozwiązany przez dostarczenie porównania funktor że przetestowania tylko klawisz (std::pair<const Key, Value>::first), problem algorytmu kopiowania tylko jednej z dwóch wartości i nie komponowania rozwiązania nie może być rozwiązany zewnętrznie.

EDIT: prosty Czas liniowy realizacja funkcji:

Note, jak @Mark Ransom komentarzach, że rozwiązanie to stanowi dodatkowy wymóg: klawisze musi być równość porównywalne. To nie jest problem z jego rozwiązaniem here, lub podobnie w odpowiedzi @Matthiew M here. Byłoby haniebnie zmodyfikować ten algorytm z tą poprawką :)

Kolejną wielką zaletą implementacji @ Mark jest to, że potrafi komponować z map przechowujących różne typy wartości, o ile klucze są takie same (co wydaje się oczywiste wymaganie). Żałuję, że upvote więcej niż raz tam ..

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: Ponieważ byłem całkiem pewien, że było lepiej STL-podobne rozwiązanie do tego, pomyślałem jednego. Jest na tyle różny, że ogłaszam to jako osobną odpowiedź.

Jest kilka sztuczek do tego. Po pierwsze, chcesz użyć set_intersection, ale masz dwie mapy. Rozwiązaniem jest niestandardowy komparator i algorytm std :: transform. Ktoś bardziej zaznajomiony ze standardową biblioteką niż ja może prawdopodobnie to zoptymalizować, ale działa. Zauważ, że boost :: bind pozwoliłoby ci zredukować głupie funkcje pomocnicze, które sprawiają, że to działa.

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

Tak samo jak C++, końcowe wykorzystanie wszystkiego jest dość śliski (wszystko w main()), ale konfiguracja jest bardziej gadatliwy niż naprawdę chcielibyśmy.

Answer 5

A (lepsze) rozwiązanie oparte na tym, że sortowane są numery map. (Wstyd mi, że przeoczyłem to.) Dzięki David Rodríguez - dribeas za sugestię.

#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

Ok, przejdźmy gotowy, aby dostać swoje ręce brudne :)

będę używając std::mismatch i std::transform

Przede wszystkim, niektóre typy:

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; 

Następnie predykaty:

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

Teraz główny:

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

Uważam to rozwiązanie dość eleganckie ... Niezależnie od awkard części instalacji, ponieważ musimy zapewnić, że pierwsza oferta kończy się szybciej niż drugi z powodu mismatch ...

Zauważcie, że zaliczka jest naprawdę głupia, moglibyśmy w tym miejscu użyć pętli, dopóki nie mielibyśmy *next.first.key == *next.second.key, ale to by skomplikowało pętlę.

I naprawdę nie znaleźć to lepiej niż ręcznie pętli choć ... rozważenia:

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

To znacznie bardziej kompaktowy, prawdopodobnie bardziej wydajne ... czasami funkcje jesteś patrząc nie są ogólnie wystarczy być w STL :)

Answer 7

Poniżej znajduje się uproszczenie mojej odpowiedzi previous, głównie korzystając z faktu, że set_intersection MOŻE być używany z mapami jako danymi wejściowymi, ale tylko wtedy, gdy robisz wyjście jako zestaw std: : pary. Wynik zmniejsza również półprodukty do jednej listy "wspólnych kluczy".

#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

Prawie rok po ... ale mimo wszystko :)

Ten jest przez określony pojemnika, ale można łatwo zmienić go używać mapę:

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

Zastosowanie:

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

set1 i set2 są ustawione pojemniki podczas output_container można ustawić list, tablic itp ..

inserter generuje iterator insert

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