How to efficiently compare two maps of strings in C++ only for a subset of the keys

Question

I'm wondering if only by applying some standard algorithms is possible to write a short function which compares two std::map<string, string> and returns true if all the key-value (but some) pairs are true.

For example, these two maps should be evaluated as equal

map<string,string> m1, m2;

m1["A"]="1";
m2["A"]="1";

m1["B"]="2";
m2["B"]="2";

m1["X"]="30";
m2["X"]="340";

m1["Y"]="53";
m2["Y"]="0";

Suppose that the two maps have same size and all their elements must be pairwise compared except the value stored by the key "X" and key "Y". A first attempt would be a very inefficient double nested for loop.

I'm sure a better solution can be achieved.

Solution

I am not sure what exactly you are looking for, so let me first give complete equality and then key equality. Maybe the latter fits your needs already.

Complete Equality

(While standard equivalence can be tested using std::map's own comparison operators, the following can be used as a base for a comparison on a per-value basis.)

Complete equality can be tested using std::equal and std::operator== for std::pairs:

#include <utility>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>

template <typename Map>
bool map_compare (Map const &lhs, Map const &rhs) {
    // No predicate needed because there is operator== for pairs already.
    return lhs.size() == rhs.size()
        && std::equal(lhs.begin(), lhs.end(),
                      rhs.begin());
}

int main () {
    using namespace std;

    map<string,string> a, b;

    a["Foo"] = "0";
    a["Bar"] = "1";
    a["Frob"] = "2";

    b["Foo"] = "0";
    b["Bar"] = "1";
    b["Frob"] = "2";

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

    map<string,string> c;
    cout << "a == c? " << map_compare (a,c)  << " (should be 0)\n";
}

Key Equality

C++2003

Based on the above code, we can add a predicate to the std::equal call:

struct Pair_First_Equal {
    template <typename Pair>
    bool operator() (Pair const &lhs, Pair const &rhs) const {
        return lhs.first == rhs.first;
    }
};

template <typename Map>
bool key_compare (Map const &lhs, Map const &rhs) {
    return lhs.size() == rhs.size()
        && std::equal(lhs.begin(), lhs.end(),
                      rhs.begin(),
                      Pair_First_Equal()); // predicate instance
}

int main () {
    using namespace std;

    map<string,string> a, b;

    a["Foo"] = "0";
    a["Bar"] = "1";
    a["Frob"] = "2";

    b["Foo"] = "0";
    b["Bar"] = "1";
    b["Frob"] = "2";

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

    map<string,string> c;
    cout << "a == c? " << key_compare (a,c)  << " (should be 0)\n";
}

C++ (C++11)

Using the new lambda expressions, you can do this:

template <typename Map>
bool key_compare (Map const &lhs, Map const &rhs) {

    auto pred = [] (decltype(*lhs.begin()) a, decltype(a) b)
                   { return a.first == b.first; };

    return lhs.size() == rhs.size()
        && std::equal(lhs.begin(), lhs.end(), rhs.begin(), pred);
}

C++ (C++14)

^{added 2014-03-12}

Using the new generic lambda expressions, you can do this:

template <typename Map>
bool key_compare (Map const &lhs, Map const &rhs) {

    auto pred = [] (auto a, auto b)
                   { return a.first == b.first; };

    return lhs.size() == rhs.size()
        && std::equal(lhs.begin(), lhs.end(), rhs.begin(), pred);
}

As a style-matter, you can also inline the lambda expressions in C++11 and C++14 directly as a parameter:

bool key_compare (Map const &lhs, Map const &rhs) {
    return lhs.size() == rhs.size()
        && std::equal(lhs.begin(), lhs.end(), rhs.begin(), 
                      [] (auto a, auto b) { return a.first == b.first; });
}

Comments

[linello]

and maybe also a key-value equality, by comparing lhs.second == rhs.second This is a very complete answer, thank you!

[NOhs]

One can also use the std::equal variant that checks automatically that the two maps have the same length.

[Andrew]

Correct me if I'm wrong but that's not a valid way to compare maps. Advised comparison is vector-like comparison. I mean that members (pairs) might go in different order but maps will be equal.

[Sebastian Mach]

@luizfls: Thanks for your edit stackoverflow.com/revisions/8473603/4, but it is not valid in this case, as the asker wanted to customize the comparison. Also, the code you removed served as a basis for the remainder of the answer - please read the question more carefully before attempting to edit existing answers. And please read the whole answer before editing. Just blindly bursting into fragments of text is not good at all.

[luizfls]

@SebastianMach You're welcome. The question is hard to understand as you pointed out in the first sentence of your answer. The first algorithm you presented works exactly the same as == so I thought it'd be better to use it. And I didn't break the linearity of the answer because I did read the whole answer before editing and made sure the linearity wasn't broken.

[J. Doe]

std::equal-based solution cannot be used for unordered containers (std::unordered_map, std::unordered_set and so on). For better safety, key_compare template should contain corresponding static_assert to make sure that it may be used only with allowed containers. Otherwise, it is easy to make invalid code.

[zkoza]

A solution that prints out the name of the contributor can be considered as nothing but spam. Also, even though it is essentially correct, it gives nothing beyond the accepted answer.

[cigien]

This is a very poor technical solution when there are standard algorithms available for this purpose.