1
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

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";
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.