[C++] Raar vergelijkings probleem std::map

[Arjan]

Ik ben tegen een raar probleem aangelopen dat ik zo snel niet kan doorgronden. Gelukkig is het probleem makkelijk te reproduceren, zie onderstaande code:

C++:

#include <iostream>
#include <map>

typedef std::pair< int, int > Key;

struct vergelijk
{
    bool operator()( const Key &a, const Key &b )
    {
        return ( ( a.first == b.first ) && ( a.second == b.second ) );
    }
};

int main( int argc, char **argv )
{
    Key keyA( 1, 2 );

    Key keyB( 3, 4 );

    std::map< Key, int, vergelijk > verzameling;

    verzameling[ keyA ] = 5;
    verzameling[ keyB ] = 20;

    std::cerr << "aantal " << verzameling.size() << std::endl;
    std::cerr << verzameling[ keyA ] << std::endl;
    std::cerr << verzameling[ keyB ] << std::endl;

    return 0;
}

Als je dit compileert en uitvoert, dan krijg je het volgende resultaat:

aantal 1
0
0

Ik verwachtte echter:

aantal 2
5
20

Wie kan mij vertellen waar mijn verwachting de mist in gaat

[Woy]

Moet je niet operator== implementeren i.p.v. operator()

Te snel gelezen. Ik dacht dat je Vergelijk als Key gebruikte.

[ Voor 39% gewijzigd door Woy op 07-12-2010 12:09 ]

[Arjan]

Woy schreef op dinsdag 07 december 2010 @ 12:03:
Moet je niet operator== implementeren i.p.v. operator()

Ik had dit van een (gecachte) pagina van cppreference, maar inmiddels ben ik erachter dat de compare functie standaard gedefinieerd wordt mbv. de std::less functie. Als ik mijn vergelijk functie implementeer met kleiner dan, dan werkt het

[EddoH]

Even een vluchtig shot-in-the-dark: moet je geen insert() gebruiken?

[Arjan]

Voor de duidelijkheid, het probleem is opgelost als je op regel 10

C++:

return ( ( a.first == b.first ) && ( a.second == b.second ) );

vervangt met

C++:

return ( ( a.first < b.first ) && ( a.second < b.second ) );

Hoewel er gesproken wordt van een 'compare function' is het de bedoeling dat je er een std::less implementatie aan meegeeft.

[CoolGamer]

EddoH schreef op dinsdag 07 december 2010 @ 12:24:
Even een vluchtig shot-in-the-dark: moet je geen insert() gebruiken?

Je kan in een std::map ook waardes instellen m.b.v. de [] operator, niet alleen lezen. Dus om waardes erin te zetten heb je geen insert nodig.

[EddoH]

TheCoolGamer schreef op dinsdag 07 december 2010 @ 13:11:
[...]

Je kan in een std::map ook waardes instellen m.b.v. de [] operator, niet alleen lezen. Dus om waardes erin te zetten heb je geen insert nodig.

Aha. Nooit gebruikt std::map vandaar. Ik zie net dat het in Qt ook zo geimplementeerd is.

[MLM]

Je 3e template argument is om de interne tree mee te sorteren, niet om gelijkheid te testen (compare is vertaald "vergelijk"). Om een item in de map te vinden die voldoet aan gelijkheid, gebruik je find() en een equality operator op je key (een vrije bool operator ==(const Key &l, const Key &r) werkt volgens mij, maar misschien heeft std::pair die al)

[CoolGamer]

Volgens mij is dit geen goede less implementatie:

C++:

return ( ( a.first < b.first ) && ( a.second < b.second ) );

Wat nou als a.first < b.first && a.second > b.second, dan geeft hij altijd false, ook als de argumenten voor a en b worden omgedraaid.

De standaard compare voor pair vangt dat volgens mij wel af. Deze sorteert eerst op first. Indien first gelijk is, wordt pas gekeken naar second.

[MLM]

TheCoolGamer schreef op dinsdag 07 december 2010 @ 13:57:
Volgens mij is dit geen goede less implementatie:

C++:

return ( ( a.first < b.first ) && ( a.second < b.second ) );

Wat nou als a.first < b.first && a.second > b.second, dan geeft hij altijd false, ook als de argumenten voor a en b worden omgedraaid.

De standaard compare voor pair vangt dat volgens mij wel af. Deze sorteert eerst op first. Indien first gelijk is, wordt pas gekeken naar second.

Een compare voor map moet voldoen aan Strict Weak Ordering:

quote: Invariants van http://www.sgi.com/tech/stl/StrictWeakOrdering.html

Irreflexivity: f(x, x) must be false.
Antisymmetry: f(x, y) implies !f(y, x)
Transitivity: f(x, y) and f(y, z) imply f(x, z).
Transitivity of equivalence: Equivalence (Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself.) is transitive: if x is equivalent to y and y is equivalent to z, then x is equivalent to z. (This implies that equivalence does in fact satisfy the mathematical definition of an equivalence relation.)

Je hebt dus gelijk, Arjans's less is voldoet niet aan "Antisymmetry".

Maar std::pair heeft gewoon een less operator, die prima werkt zolang de types gebruikt in de pair ook een less operator hebben (in Arjan's voorbeeld met std::pair<int, int> werkt dat dus prima). std::less zal dan ook gewoon die operator pakken, en het default template argument voor de map is std::less.

De simpelste oplossing is dan ook gewoon dat hele vergelijk ding weghalen en je map gewoon als std::map<Key, int> te maken, dat werkt prima

Als een side-note, een std::unordered_map gebruikt wel een compare function die test op gelijkheid.

[ Voor 5% gewijzigd door MLM op 07-12-2010 14:38 ]

[.oisyn]

unordered_map heeft daarnaast dan ook weer een hash-functie nodig.

[Arjan]

MLM schreef op dinsdag 07 december 2010 @ 14:34:
[...]


Een compare voor map moet voldoen aan Strict Weak Ordering:

[...]

De simpelste oplossing is dan ook gewoon dat hele vergelijk ding weghalen en je map gewoon als std::map<Key, int> te maken, dat werkt prima

Bovenstaande code was natuurlijk maar een voorbeeld

[MLM]

Arjan schreef op dinsdag 07 december 2010 @ 15:25:
[...]

Bovenstaande code was natuurlijk maar een voorbeeld

Zolang als de types in je pair maar een operator less hebben, hoef je in elk geval geen speciale compare functors te gaan bouwen, dat was mijn punt. De less implementatie van std::pair voldoet al aan strict weak ordering.

Als je het toch zelf wilt doen, kan je iets doen als:

code:

if(a.first < b.first) return true;
if(a.first == b.first) return a.second < b.second;
return false;

[Olaf van der Spek]

MLM schreef op dinsdag 07 december 2010 @ 15:31:
Als je het toch zelf wilt doen, kan je iets doen als:

return a.first < b.first || a.first == b.first && a.second < b.second;

[Arjan]

Olaf van der Spek schreef op woensdag 08 december 2010 @ 18:46:
[...]

return a.first < b.first || (a.first == b.first && a.second < b.second );

Met haakjes dus, anders krijg je alsnog een andere variatie

[Soultaker]

Nee, conjunctie heeft voorrang boven disjunctie, dus Olaf's code wordt op dezelfde manier geparset. Maar haakjes maken het geheel wel duidelijker natuurlijk.

Als we toch variaties op dezelfde constructie aan het posten zijn; ik ben wel fan van deze:

C++:

if (a.first  != b.first)  return a.first  < b.first;
if (a.second != b.second) return a.second < b.second;
return false;

Dit is eenvoudig uitbreidbaar naar willekeurig grote tuples, zonder onleesbaar te worden. De code wordt bovendien efficiënt uitgevoerd omdat je voor N velden maximaal N+1 vergelijkingen doet, terwijl sommige van de variaties 2N-1 kunnen doen in sommige gevallen.

[ Voor 14% gewijzigd door Soultaker op 08-12-2010 19:50 ]

[.oisyn]

Hey da's wel een mooie. Ik gebruik meestal Olaf's methode, voor meer dan twee elementen wordt dat dan zoiets:

C++:

return
    a1 < b1 || a1 == b1 &&
    (a2 < b2 || a2 == b2 &&
    (a3 < b3 || a3 == b3 &&
    a4 < b4));

Wel makkelijk uitbreidbaar, maar intuitief niet direct duidelijk dat het ook echt klopt en je zit met die geneste haakjes. En idd, 2N-1.

[MSalters]

Het belangrijkste nadeel van Soultaker's "if (a.first != b.first) return a.first < b.first;" vorm is dat je elementen ook nog een operator!= nodig hebben; ik gebruik daarom nog wel eens

C++:

if (a.first  < b.first)  return true;
if (b.first  < a.first)  return false;
return a.second < b.second;

Net zo makkelijk uit te breiden, en gebruikt alleen operator<. De kosten van de tweede operator< zijn in de praktijk meestal te verwaarlozen omdat cache effecten domineren.