Have Geek Brain

Using a map with set_intersection

Not used set_intersection before, but I believe it will work with maps. I wrote the following example code, but it doesn't give me what I expect:

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

Since the pair labeled (3) and (4) appears on both maps, I expected I would get 2 elements in the intersection, but no, I get:

intersection has 0 elements.

I'm sure it has something to do with the comparator on the map / pair, but can't figure it out.

+2


a source to share


2 answers 


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


If it's not a typo, you are just inserting stuff into map1 instead of inserting into map2. I checked it with corrected code and it printed "Intersection has 2 elements".

+5


a source


Nicky is definitely right about your typography - map2

blank here! However, you need to be careful about anything else.

Let's say your code looked like this:

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

Now what will happen? You will find that it out

will be empty because it set_intersection

uses std::less

elements to compare and the elements of your cards are pairs - thus (3, mn [3]) is different from (3, mn [4]).



Another way you could do this is to write

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

out

Will now contain two elements: (3, mn [3]) and (4, mn [4]), since their keys are the same. Items are always copied from the first range of iterators.

Note that cards are always sorted by the type map::value_compare

they contain. If you are using funky compare function set_intersection

will not work unless the comparison functor is explicitly specified, if the map elements are out of order relative std::less

.

+6


a source






More articles:


All Articles