Znajdź jeśli mapa jest podzbiorem innego

Question

Mam dwie mapy STL std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}; i std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}};

Chcę się dowiedzieć, czy pasek jest podzbiorem foo.

Ponieważ elementy są posortowane na mapie, uważam, że znalazł pierwszy element z paska w foo, a następnie znajdował kolejne elementy z paska w foo z tej lokalizacji.

Problem polega na tym, że nie jestem w stanie znaleźć sposobu, aby to zrobić z mapami STL w cpp. Czy mogę zmniejszyć zakres wyszukiwania na mapie dla każdego znaleziska z lokalizacji na mapie do końca mapy?

Mam nadzieję, że wyjaśniłem problem.

Answer 1

Zastosowanie std::includes algorytm z niestandardowym komparatora, który porównuje tylko kluczy:

#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

Można wyodrębnić kluczowe zestawy (set1 i set2) obu mapach (foo i bar), i tak długo jak są one sortowane, można wykonać następujące czynności:

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

Zobacz std::includes.

Answer 3

Prostym sposobem jest użycie Boost.Range w połączeniu z boost::includes:

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

Oto jak minimal, kompletny program mógłby wyglądać (odwzorowane wartości są brane pod uwagę):

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

Oto a live example.