Как эффективно сравнить две карты строк в C++

Question

Мне интересно, если только с помощью некоторых стандартных алгоритмов можно написать короткую функцию, которая сравнивает два std::map<string, string> и возвращает true, если все пары ключ-значение (но некоторые) верны.

Например, эти две карты должны быть оценены как равные

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";

Предположим, что две карты имеют одинаковый размер, и все их элементы должны сравниваться попарно, кроме значения, хранящегося в ключе "X" и ключе "Y". Первая попытка была бы очень неэффективным двойным вложенным циклом. Я уверен, что лучшее решение может быть достигнуто.

Answer 1

Я не уверен, что именно вы ищете, поэтому позвольте мне сначала дать полное равенство, а затем ключевое равенство. Возможно, последнее уже соответствует вашим потребностям.

Полное равенство

Полное равенство можно проверить с помощью std::equal а также std::operator== за 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";
}

Ключевое равенство

C++2003

На основе приведенного выше кода мы можем добавить предикат к std::equal вызов:

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)

Используя новые лямбда-выражения, вы можете сделать это:

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)

^{добавлено 2014-03-12}

Используя новые общие лямбда-выражения, вы можете сделать это:

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

В зависимости от стиля вы также можете встроить лямбда-выражения в C++ 11 и C++ 14 непосредственно в качестве параметра:

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

Answer 2

Ответ очень прост: мы можем напрямую сравнивать две карты с помощью оператора отношения эквивалентности ("=="), точно так же, как мы сравниваем две переменные.

      #include<bits/stdc++.h>
using namespace std;
int main()
{
map<string,int> m1;
map<string,int> m2;

m1["str1"]=47;
m1["str2"]=87;

m2["str1"]=47;
m2["str2"]=87;

if(m1==m2)
cout<<"maps are equal"<<endl;
else
cout<<"maps are not equal"<<endl;   
}

Вывод: https://stackru.com/images/4e16e61d0ca64962f20ec7ab003c33c0090b3d45.png

Answer 3

http://www.cplusplus.com/reference/map/map/operator=/

if (m1 == m2)
  cout << "Equal" << endl;
else
  cout << "Not Equal" << endl;

Answer 4

Я думаю, что если вы пытаетесь получить доступ к двум, трем или большему количеству карт одинакового размера одновременно, вам следует создать и itr1, itr2 и таким образом пройти по всей карте.

           map<char, int> :: iterator itr1, itr2;
     itr1=first.begin();
     itr2=last.begin();
     
     while(itr1!=first.end() && itr2!=last.end())
     {
         if(itr1->first!=itr2->first || itr1->second!=itr2->second)
         {
          cout<<"Akash Musky"<<endl;
         }
         else 
         {
           cout<<"Love is hard to find"<<endl;
           cout<<"You can't force anyone to love"<<endl;
          }
         itr1++;
         itr2++;
     }