Trova se uno mappa è sottoinsieme di un altro

Question

Ho due mappe STL std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}; e std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}};

voglio trovare se bar è un sottoinsieme di foo.

Poiché gli elementi sono ordinati in carta, penserei per trovare il primo elemento da bar di foo, e poi trovare elementi consecutivi da bar in foo da quella posizione.

Il problema qui è che non sono in grado di trovare un modo per farlo con le mappe STL in cpp. Posso ridurre l'intervallo di ricerca nella mappa per ogni risultato da una posizione sulla mappa alla fine della mappa?

Spero di aver spiegato il problema.

Answer 1

Usa std::includes algoritmo con un comparatore personalizzato che confronta soltanto i tasti:

#include <map> 
#include <algorithm> 
#include <iostream> 

int main() 
{ 
    std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}; 
    std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}}; 
    typedef std::pair<int,int> pair; 

    std::cout << 
     std::includes(foo.begin(), foo.end(), bar.begin(), bar.end(), 
      [](const pair& p1, const pair& p2) 
      { 
       return p1.first < p2.first; 
      }); 
} 

Answer 2

Si potrebbe estrarre set di chiavi (set1 e set2) di entrambe le mappe (foo e bar), e nella misura in cui sono ordinati, è possibile effettuare le seguenti operazioni:

if (std::includes(set1.begin(), set1.end(), 
        set2.begin(), set2.end())) { 
    // ... 
} 

Vedi std::includes.

Answer 3

Un modo semplice è quello di utilizzare Boost.Range in combinazione con boost::includes:

using namespace boost::adaptors; 
bool result = includes(foo | map_keys, bar | map_keys); 

Ecco come un minimo di programma, completo potrebbe assomigliare (valori mappati vengono ignorati):

#include <map> 
#include <iostream> 
#include <boost/range.hpp> 
#include <boost/range/adaptors.hpp> 
#include <boost/range/algorithm.hpp> 

int main() 
{ 
    std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}; 
    std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}}; 

    using namespace boost::adaptors; 
    std::cout << includes(foo | map_keys, bar | map_keys); 
} 

Ecco a live example.