Использование карты с set_intersection - PullRequest
Новая
       23

Использование карты с set_intersection

3 голосов
/ 14 апреля 2010

Ранее не использовал set_intersection, но я верю, что он будет работать с картами. Я написал следующий пример кода, но он не дает того, что я ожидал: 

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

using namespace std;

struct Money
{
    double amount;
    string currency;

    bool operator< ( const Money& rhs ) const
    {
        if ( amount != rhs.amount )
            return ( amount < rhs.amount );
        return ( currency < rhs.currency );
    }
};

int main( int argc, char* argv[] )
{
    Money mn[] =
    {
        { 2.32,  "USD" },
        { 2.76,  "USD" },
        { 4.30,  "GBP" },
        { 1.21,  "GBP" },

        { 1.37,  "GBP" },
        { 6.74,  "GBP" },
        { 2.55,  "EUR" }
    };

    typedef pair< int, Money > MoneyPair;
    typedef map< int, Money > MoneyMap;

    MoneyMap map1;
    map1.insert( MoneyPair( 1, mn[0] ) );
    map1.insert( MoneyPair( 2, mn[1] ) );
    map1.insert( MoneyPair( 3, mn[2] ) );  // (3)
    map1.insert( MoneyPair( 4, mn[3] ) );  // (4)

    MoneyMap map2;
    map2.insert( MoneyPair( 3, mn[2] ) );  // (3)
    map2.insert( MoneyPair( 4, mn[3] ) );  // (4)
    map2.insert( MoneyPair( 5, mn[4] ) );
    map2.insert( MoneyPair( 6, mn[5] ) );
    map2.insert( MoneyPair( 7, mn[6] ) );

    MoneyMap out;
    MoneyMap::iterator out_itr( out.begin() );
    set_intersection( map1.begin(), map1.end(), map2.begin(), map2.end(), inserter( out, out_itr ) );

    cout << "intersection has " << out.size() << " elements." << endl;
    return 0;
}

Поскольку пары с метками (3) и (4) появляются на обеих картах, я ожидал, что на пересечении я получу 2 элемента, но нет, получу: 

intersection has 0 elements.

Я уверен, что это как-то связано с компаратором на карте / паре, но не могу понять.

Ответы [ 2 ]

6 голосов
/ 14 апреля 2010

Ники, безусловно, прав насчет вашей опечатки - map2 здесь пусто! Однако нужно быть осторожным с чем-то другим.

Допустим, ваш код выглядел так: 

MoneyMap map1;
map1.insert( MoneyPair( 1, mn[1] ) );
map1.insert( MoneyPair( 2, mn[2] ) );
map1.insert( MoneyPair( 3, mn[3] ) );  // (3)
map1.insert( MoneyPair( 4, mn[4] ) );  // (4)

MoneyMap map2;
map2.insert( MoneyPair( 3, mn[4] ) );  // (3)
map2.insert( MoneyPair( 4, mn[3] ) );  // (4)
map2.insert( MoneyPair( 5, mn[6] ) );
map2.insert( MoneyPair( 6, mn[5] ) );
map2.insert( MoneyPair( 7, mn[1] ) );

MoneyMap out;
MoneyMap::iterator out_itr( out.begin() );
set_intersection(map1.begin(), map1.end(), 
                 map2.begin(), map2.end(), 
                 inserter( out, out_itr ) );

Теперь, что случилось бы? Вы обнаружите, что out будет пустым, потому что set_intersection использует std::less для сравнения элементов, а элементы ваших карт являются парами - таким образом (3, mn [3]) отличается от (3, mn [4 ]).

Другой способ сделать это - написать 

set_intersection(map1.begin(), map1.end(), 
                 map2.begin(), map2.end(), 
                 inserter( out, out_itr ), map1.value_comp() );

Теперь out будет содержать два элемента: (3, mn [3]) и (4, mn [4]), потому что их ключи совпадают. Элементы всегда копируются из первого диапазона итератора.

Обратите внимание, что карты всегда сортируются по типу map::value_compare, который они содержат. Если вы используете необычную функцию сравнения, set_intersection не будет работать без явно предоставленного функтора сравнения, если элементы карты оказались не в порядке относительно std::less.

5 голосов
/ 14 апреля 2010 
MoneyMap map2;
map1.insert( MoneyPair( 3, mn[3] ) );  // (3)
map1.insert( MoneyPair( 4, mn[4] ) );  // (4)
map1.insert( MoneyPair( 5, mn[5] ) );
map1.insert( MoneyPair( 6, mn[6] ) );
map1.insert( MoneyPair( 7, mn[7] ) );

Если это не опечатка, вы просто вставляете материал в map1 вместо того, чтобы вставлять в map2. Я протестировал его с исправленным кодом, и он вывел «Пересечение имеет 2 элемента».

...