Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.3k views
in Technique[技术] by (71.8m points)

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

I'm wondering if only by applying some standard algorithms is possible to write a short function which compare 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.

question from:https://stackoverflow.com/questions/8473009/how-to-efficiently-compare-two-maps-of-strings-in-c-only-for-a-subset-of-the-k

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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)
";
    b["Foo"] = "1";
    cout << "a == b? " << map_compare (a,b) << " (should be 0)
";

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

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)
";
    b["Foo"] = "1";
    cout << "a == b? " << key_compare (a,b) << " (should be 1)
";

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

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...