Checking if the entries of a map exist in another map

Question

I need to check if a map is subset of another map. For this, I have written the following code:

#include <string>
#include <iostream>
#include <map>

using namespace std;

/**
 * Checks if rhs is a subset of lhs
 */
template<class Map>
bool map_compare(Map &lhs, Map &rhs)
{
    if(rhs.size() > lhs.size() || rhs.empty()) return false;
    typename Map::iterator litr = lhs.begin();
    for (typename Map::iterator ritr = rhs.begin(); ritr != rhs.end(); ritr++)
    {
        if(litr == lhs.end() && ritr != rhs.end()) return false;
        while (litr != lhs.end())
        {
            if (litr->first == ritr->first)
            {
                if (litr->second == ritr->second)
                {
                    litr++;
                    break;
                }
                return false;
            }
            else
            {
                litr++;
            }
        }
    }
    return true;
}

int main()
{
    map<int, string> a, b;

    a[0] = "0";
    a[1] = "1";

    b[0] = "0";

    cout << "b ⊆ a? " << map_compare(a, b) << " (should be 1)\n";

    b[1] = "1";
    cout << "b ⊆ a? " << map_compare(a, b) << " (should be 1)\n";

    b[2] = "2";
    cout << "b ⊆ a? " << map_compare(a, b) << " (should be 0)\n";
}

I am looking for another implementation of map_compare which is either shorter or more efficient.

Answer 1

I believe you will find the standard library has the appropriate functions:

Includes

Includes tests whether one sorted range includes another sorted range. That is, it returns true if and only if, for every element in [first2, last2), an equivalent element [1] is also present in [first1, last1) [2]. Both [first1, last1) and [first2, last2) must be sorted in ascending order.

The two versions of includes differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using the function object comp.

You can see all the algorithms here

Your code would look like this:

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

int main()
{
    std::map<int, std::string> a;
    std::map<int, std::string> b;

    a[0] = "0";
    a[1] = "1";

    b[0] = "0";

    std::cout << "b ⊆ a? " << std::includes(a.begin(), a.end(), b.begin(), b.end()) << " (should be 1)\n";

    b[1] = "1";
    std::cout << "b ⊆ a? " << std::includes(a.begin(), a.end(), b.begin(), b.end()) << " (should be 1)\n";

    b[2] = "2";
    std::cout << "b ⊆ a? " << std::includes(a.begin(), a.end(), b.begin(), b.end()) << " (should be 0)\n";
}