Find if one map is subset of another

Question

I have two STL maps std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}; and std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}};

I want to find if bar is a subset of foo.

Since the elements are sorted in map, I would think to find the first element from bar in foo, and then find consecutive elements from bar in foo from that location.

The problem here is I'm not able to figure out a way to do that with STL maps in cpp. Can I reduce the search range in map for every find from a location in map to the end of the map?

I hope I explained the problem.

Answer 1

Use std::includes algorithm with a custom comparator that compares only the keys:

#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

You could extract key sets (set1 and set2) of both maps (foo and bar), and as long as they are sorted, you can do the following:

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

See std::includes.