23.4 Egyenlőség, spaceship és rendezési kategóriák

Az összehasonlítás látszólag triviális téma, a rendszerprogramozásban mégis rendre ott hibázunk el, ahol egy adatszerkezet vagy algoritmus csendben megköveteli: a std::map, a std::sort, a std::unordered_set és a std::ranges::sort mindegyike egy szerződést vár a felhasználótól, nem pedig „valamilyen” összehasonlítást. C++20-ban a <=> (spaceship) és a defaulted tag-összehasonlítás ezt a szerződést részben gépre bízhatóvá tette, de a szemantika megválasztása továbbra is tervezői döntés: nem mindegy, hogy két különböző reprezentációjú érték egyenlő, ekvivalens vagy összemérhetetlen. Ebben az alfejezetben azt rendszerezzük, hogyan lesz egy típusból kiszámítható, konzisztens kulcs és rendezhető érték, és miért kerül bajba a double egy NaN-nal a std::map-ban.

Az operátorok deklarációs mechanikáját az Operátortúlterhelés és konverziós operátor (23.3) rész tárgyalta; itt azt feltételezzük, hogy az operátor mint tagfüggvény és mint szabad függvény közti választás már ismert. A lebegőpontos reprezentáció részleteihez Lebegőpontos reprezentáció és numerikus hibák (4.3), a hash-tábla komparátor-szerződéséhez Hash table, comparator és ownership (13.3) ad hátteret.

23.4.1 Az összehasonlítás mint szerződés

Egy == operátor akkor viselkedik ekvivalenciarelációként, ha reflexív ($a = a$), szimmetrikus ($a = b \Rightarrow b = a$) és tranzitív ($a = b \land b = c \Rightarrow a = c$). A standard tárolók és algoritmusok nagy része hallgatólagosan ezt feltételezi; ha a == nem tranzitív, a std::unordered_set viselkedése egyszerűen nem definiált.

Egy < operátor akkor strict weak ordering (szigorú gyenge rendezés), ha

1. irreflexív: $\lnot(a < a)$,
2. tranzitív: $a < b \land b < c \Rightarrow a < c$,
3. az ekvivalencia tranzitív, ahol $a \sim b$ jelentése $\lnot(a<b) \land \lnot(b<a)$; azaz $a \sim b \land b \sim c \Rightarrow a \sim c$.

A 2. és 1. együtt maga után vonja az aszimmetriát ($a<b \Rightarrow \lnot(b<a)$): ha $a<b$ és $b<a$ is fennállna, a tranzitivitásból $a<a$ következne. A std::sort, std::map, std::set és a standard bináris keresések komparátora ezt a tulajdonságot követelik meg; megsértésük nem definiált viselkedés, nem „csak” rossz sorrend.

Bizonyításvázlat. Azt állítjuk, hogy egy strict weak ordering a ~ ekvivalencia-osztályain teljes rendezést indukál. A ~ reláció ekvivalenciareláció a 3. feltétel miatt, tehát osztályokba rendez. Két különböző $[a] \ne [b]$ osztályra nem lehet egyszerre $\lnot(a<b)$ és $\lnot(b<a)$, mert az épp $a \sim b$, azaz $[a]=[b]$ lenne; aszimmetria miatt pedig nem állhat fenn mindkettő. Marad pontosan egy irány, tehát az osztályok rendezettek, és az algoritmusok particionálási és beszúrási érvelése érvényes. Ez a vázlat, nem teljes bizonyítás: az ekvivalencia tranzitivitását axiómának vettük, nem a < többi tulajdonságából vezettük le.

23.4.2 operator== és a defaulted összehasonlítás

C++20-tól egy osztály kérheti a tagonkénti összehasonlítást:

struct Version {
    int major = 0, minor = 0, patch = 0;
    bool operator==(const Version&) const = default;
    auto operator<=>(const Version&) const = default;
};

A defaulted operator== a nem statikus adattagokat deklarációs sorrendben hasonlítja össze ==-val (tömböknél elemenként). Feltétel: minden tag típusa rendelkezzen használható ==-val, és a függvénynek nincs constexpr/noexcept-ot sértő előfeltétele. A != nem kell külön: a túlterhelés-feloldás a !(a == b) átírt jelöltet (rewritten candidate) használja.

Fontos csapda, és gyakran rosszul tanítják: a == jelöltjei között csak operator== (és annak fordított változata) szerepel, a <=> nem. Ha az osztály nem deklarál ==-t, de defaultolt <=>-t igen, a fordító implicit módon egy defaultolt operator==-t is deklarál ([C++20] [class.compare.default]); ezért egy csak auto operator<=>(const Version&) const = default; sort tartalmazó osztályon a v1 == v2 is lefordul. A saját, nem defaultolt <=> viszont nem ad ==-t: ilyenkor a v1 < v2 működik, a v1 == v2 nem fordul — ez a leggyakoribb C++20-as meglepetés. A fenti példában a két sor együtt a szándékot teszi explicitté, és akkor is helyes marad, ha a <=>-t később kézzel írjuk meg.

23.4.3 operator<=> és a rewritten candidate mechanizmus

A <=> eredménye nem bool, hanem egy rendezési kategória típus értéke. A a < b kifejezésre a fordító a következő jelölteket veszi sorra: a felhasználó által deklarált operator<, majd az átírt (a <=> b) < 0, végül a fordított 0 < (b <=> a). A nem átírt jelöltek elsőbbséget élveznek, ezért egy meglévő operator< továbbra is „felülírja” a <=>-t — hirtelen, csendben inkonzisztens párost kaphatunk, ha a kettő mást mond.

A kategória és a literál 0 összehasonlítása megengedett (< 0, <= 0, > 0, >= 0, == 0, != 0), a kategória bool-ként nem használható: if (a <=> b) nem fordul le. Helyesen: if ((a <=> b) < 0).

A std::partial_ordering négy értékének és a literál 0-nak az összehasonlítása ([C++20] [cmp.partialord]):

A fordított irány (0 == c, 0 < c stb.) ugyanezt adja a tükrözött operátorral: 0 < c ugyanaz, mint c > 0. Az unordered tehát nem egyenlő nullával, és egyetlen rendezési reláció sem igaz rá; csak a != 0 igaz. Ebből következik, hogy a !((a <=> b) < 0) nem jelenti azt, hogy a >= b: NaN esetén mindkettő hamis.

// partial_zero.cpp — C++20: partial_ordering és a literál 0
#include <compare>

using po = std::partial_ordering;

constexpr bool row(po c, bool eq, bool ne, bool lt,
                   bool le, bool gt, bool ge) {
    return (c == 0) == eq && (c != 0) == ne && (c < 0) == lt
        && (c <= 0) == le && (c > 0) == gt && (c >= 0) == ge;
}
//                            ==0    !=0   <0     <=0    >0     >=0
static_assert(row(po::less,       false, true, true,  true,  false, false));
static_assert(row(po::equivalent, true, false, false, true,  false, true));
static_assert(row(po::greater,    false, true, false, false, true,  true));
static_assert(row(po::unordered,  false, true, false, false, false, false));

// Fordított irány: 0 @ c ugyanaz, mint c @' 0 a tükrözött operátorral.
static_assert(!(0 == po::unordered) && (0 != po::unordered));
static_assert(!(0 < po::unordered) && !(0 >= po::unordered));
static_assert((0 > po::less) && (0 <= po::equivalent));

int main() {}

Buildjegyzőkönyv (lab-gcc profil). g++ -std=c++20 -Wall -Wextra -Wpedantic partial_zero.cpp figyelmeztetés nélkül fordul, tehát a táblázat minden cellája static_assert-tel ellenőrzött.

23.4.4 Strong, weak és partial ordering

A std::strong_ordering (less, equal, greater) esetén az egyenlőség felcserélhetőséget (substitutability) jelent: ha $a = b$, akkor minden megfigyelhető tulajdonságuk azonos. Egész számok, std::string, std::vector<int> ilyen.

A std::weak_ordering (less, equivalent, greater) esetén léteznek megkülönböztethető, de ekvivalensnek nyilvánított értékek. Klasszikus példa a kis-nagybetűt nem megkülönböztető név: a "OpenSSL" és az "openssl" ekvivalens, noha a bájtjaik eltérnek.

A std::partial_ordering (less, equivalent, greater, unordered) esetén bizonyos párok összemérhetetlenek. Ez a lebegőpontos NaN esete: sem nan < x, sem x < nan, sem nan == nan nem igaz.

A konverzió egyirányú: strong_ordering → weak_ordering → partial_ordering implicit módon átalakítható, visszafelé nem. Egy defaulted <=> visszatérési típusa a tagok kategóriáinak közös kategóriája, tehát ha bármelyik tag double, az egész osztály partial_ordering lesz — még akkor is, ha a gyakorlatban soha nem kerül NaN a mezőbe.

23.4.5 NaN, unordered és a hash konzisztencia

Két külön szerződés él egymás mellett. A konténer-komparátor csak a <-et használja, tehát strict weak orderinget kell adnia. A hash-tároló a ==-t és a hash-t használja, és megköveteli: $a = b \Rightarrow h(a) = h(b)$.

A NaN mindkettőt megzavarja. A std::map<Measurement, int> NaN kulccsal nem definiált viselkedésű, mert a < nem strict weak ordering rajta. A -0.0 == 0.0 viszont igaz, ezért a -0.0 és a 0.0 hash-értékének azonosnak kell lennie; ha valaki std::bit_cast<std::uint64_t>-tal a nyers bitmintát hash-eli, ezt megsérti, és a std::unordered_map elveszíti a kulcsot.

A <compare> header C++20-ban std::strong_order, std::weak_order és std::partial_order customization pointokat kínál, amelyekkel a lebegőpontos értékek teljes rendezésbe kényszeríthetők. A std::strong_order az IEEE totalOrder predikátumhoz igazodik: megkülönbözteti a -0.0-t a +0.0-tól és a különböző NaN reprezentációkat is. Könyvtártámogatását érdemes compile probe-bal ellenőrizni (feature-test makró: __cpp_lib_three_way_comparison).

Itt egy tudatos döntést kell hozni: ha a std::map kulcsa Measurement, akkor a tároló ekvivalenciafogalma a strong_order szerinti lesz, ami nem esik egybe a == szerinti fogalommal (-0.0 és +0.0). Ugyanarra a domainre ne keverjünk map-et unordered_map-pel, vagy dokumentáljuk, melyik a kanonikus reláció.

23.4.6 Pointerek és összetett domain értékek

A beépített pointer-összehasonlítás pointerekre C++20-ban is megengedett, de ha a két pointer nem ugyanazon tömb elemeire (illetve nem ugyanarra az objektumra) mutat, az eredmény meghatározatlan (unspecified), nem pedig konzisztens rendezés. Teljes rendezéshez std::less<Pointer> kell, amely garantáltan strict total ordert ad.

Összetett domain értéknél (például Endpoint{addr, port}) a tagonkénti, deklarációs sorrendű összehasonlítás általában pontosan az, amit akarunk: előbb a cím, aztán a port. Ha viszont a domain szemantikája más (például a port szerint akarunk elsődlegesen rendezni), a defaulted operátor rossz sorrendet ad — ilyenkor kézzel kell megírni, és gondoskodni kell a ==-vel való konzisztenciáról.

23.4.7 Kidolgozott példa

A példa három domaint mutat: erős rendezésű verziószámot, gyenge rendezésű csomagnév-halmazt és egy lebegőpontos mérést. A buildparancs és a „várt” kimenet illusztráció; a kódot ebben a fejezetben nem futtattuk, így a kimenet nem mért eredmény.

// compare_demo.cpp  --  C++20
#include <algorithm>
#include <cctype>
#include <compare>
#include <cstddef>
#include <iostream>
#include <map>
#include <string>
#include <type_traits>
#include <unordered_set>

struct Version {
    int major = 0, minor = 0, patch = 0;
    bool operator==(const Version&) const = default;
    auto operator<=>(const Version&) const = default;   // std::strong_ordering
};

struct CaseInsensitiveLess {
    std::weak_ordering operator()(char a, char b) const noexcept {
        const auto la = static_cast<unsigned char>(
            std::tolower(static_cast<unsigned char>(a)));
        const auto lb = static_cast<unsigned char>(
            std::tolower(static_cast<unsigned char>(b)));
        return la <=> lb;                               // strong -> weak
    }
};

struct PackageName {
    std::string text;

    bool operator==(const PackageName& other) const noexcept {
        return (*this <=> other) == 0;                  // weak: ekvivalencia
    }
    std::weak_ordering operator<=>(const PackageName& other) const noexcept {
        return std::lexicographical_compare_three_way(
            text.begin(), text.end(),
            other.text.begin(), other.text.end(),
            CaseInsensitiveLess{});
    }
};

struct PackageNameHash {
    std::size_t operator()(const PackageName& p) const noexcept {
        std::size_t h = 1469598103934665603ull;         // FNV-1a offset basis
        for (char c : p.text) {
            h ^= static_cast<unsigned char>(
                std::tolower(static_cast<unsigned char>(c)));
            h *= 1099511628211ull;                      // FNV prime
        }
        return h;
    }
};

int main() {
    static_assert(std::is_same_v<decltype(Version{} <=> Version{}),
                                 std::strong_ordering>);

    std::map<PackageName, int> installed;
    installed[PackageName{"OpenSSL"}] = 1;
    installed[PackageName{"openssl"}] = 2;              // ugyanaz az osztály: felülír
    std::cout << installed.size() << '\n';              // várható: 1

    std::unordered_set<PackageName, PackageNameHash> seen;
    seen.insert(PackageName{"OpenSSL"});
    seen.insert(PackageName{"OPENSSL"});                // azonos hash -> ütközés
    std::cout << seen.size() << '\n';                   // várható: 1

    std::cout << (Version{1, 4, 2} < Version{1, 10, 0}) << '\n';  // várható: 1
}

g++-13 -std=c++20 -Wall -Wextra -Wpedantic -O2 -o compare_demo compare_demo.cpp
# vagy: clang++-17 -std=c++20 -Wall -Wextra -Wpedantic -O2 -o compare_demo compare_demo.cpp

Két megjegyzés a hordozhatósághoz. A 1469598103934665603ull konstans 32 bites std::size_t esetén csonkolódik; ez nem hiba, csak eltérő hash-eloszlás. A static_cast<unsigned char> a std::tolower előtt kötelező, mert negatív char értéket átadva a viselkedés nem definiált.

A NaN-kezelés külön példa:

struct Measurement {
    double value;
    bool operator==(const Measurement&) const = default;
    auto operator<=>(const Measurement&) const = default;   // std::partial_ordering
};

struct TotalMeasurementOrder {
    bool operator()(const Measurement& a, const Measurement& b) const {
        return std::strong_order(a.value, b.value) < 0;     // teljes rendezés
    }
};
// std::map<Measurement, int, TotalMeasurementOrder>  -> definiált viselkedés

23.4.8 Tipikus hibák

A leggyakoribb, hogy valaki saját, nem defaultolt operator<=>-t ír, és csodálkozik, hogy az == nem fordul (defaultolt <=> mellett a fordító implicit ==-t is deklarál). A második, hogy a <=>-t bool-ként próbálja használni if-ben. A harmadik, hogy double tagot tesz std::map kulcsába, és a NaN miatt nem definiált viselkedést kap; itt vagy szűrjük a bemenetet, vagy std::strong_order-t használó komparátort adunk. A negyedik, hogy a hash-t a nyers bitmintára írjuk, és elbukik a -0.0/0.0 eset. Végül gyakori, hogy a felhasználó ír egy operator<-et, ami inkonzisztens a ==-vel: az egyik szerint két érték egyenlő, a másik szerint az egyik kisebb — az ilyen kulcs a std::map-ben és std::set-ben is megkettőződik vagy elvész.

23.4.9 Összefoglaló

Az összehasonlítás nem esztétikai kérdés, hanem szerződés: a ==-nek ekvivalenciarelációnak, a <-nek strict weak orderingnek kell lennie, és a hash-nek konzisztensnek kell lennie az egyenlőséggel. C++20-ban a defaulted operator== és operator<=> a tagonkénti eseteket ingyen adja, de a kettőt együtt kell deklarálni, és a visszatérési kategória (strong/weak/partial) megválasztása tudatos döntés. A NaN és a -0.0 olyan részletek, amelyek a rendezést és a hash-t egyszerre törik el; a <compare> total-order segédfüggvényei jelentik a kiutat, ám ezek szemantikája eltér a ==-tól, amit dokumentálni kell.

23.4.10 Feladatok

1. feladat (diagnosztika). Adott:

struct Point {
    int x = 0, y = 0;
    constexpr std::strong_ordering operator<=>(const Point& o) const {
        if (auto c = x <=> o.x; c != 0) return c;
        return y <=> o.y;
    }
};

A p1 < p2 lefordul, a p1 == p2 nem. Magyarázd meg, miért, és add meg a minimális javítást! Mi változna, ha a <=> = default lenne? Milyen kategóriát ad a <=>?

2. feladat (kódolás). Készíts Endpoint értéktípust std::uint32_t addr és std::uint16_t port tagokkal, lexikografikus erős rendezéssel és konzisztens hash-sel! Bizonyítsd (vagy ellenőrizd static_assert-tel), hogy a <=> kategóriája std::strong_ordering, és hogy az egyenlő értékek hash-e azonos!

3. feladat (diagnosztika + javítás). Egy mérési naplóhoz ezt a komparátort írták:

struct BadCmp {
    bool operator()(const Measurement& a, const Measurement& b) const {
        return a.value <= b.value;
    }
};

Miért nem definiált a std::sort(begin, end, BadCmp{}) viselkedése? Adj két különböző javítást eltérő szemantikával, és mondd meg, melyiknél mi lesz a NaN és a -0.0 sorsa!

23.4.11 Megoldások

1. megoldás. A <=> nem jelölt a == számára: a p1 == p2 feloldásakor csak operator== (és fordítottja) jön szóba. Mivel a <=> itt saját, nem defaultolt függvény, a fordító nem deklarál mellé implicit ==-t, tehát nincs használható jelölt (GCC 13.3: no match for 'operator=='). A minimális javítás egyetlen sor az osztályban:

bool operator==(const Point&) const = default;

Ha a <=> maga lenne = default, a javítás nem kellene: a defaultolt <=> implicit módon defaultolt ==-t is deklarál. A kategória std::strong_ordering, mert ezt deklaráltuk, és az int tagok <=>-ja is az; defaultolt <=> esetén a common_comparison_category szintén ezt adná. Ellenőrzési feltétel — a javított osztályra:

static_assert(std::is_same_v<decltype(Point{} <=> Point{}),
                             std::strong_ordering>);
static_assert(Point{1, 2} != Point{1, 3});   // !(a == b) átírt jelöltként
static_assert(Point{1, 2} <  Point{1, 3});

Buildjegyzőkönyv (lab-gcc profil). A javított Point a fenti static_assert-ekkel g++ -std=c++20 -Wall -Wextra -Wpedantic alatt figyelmeztetés nélkül fordul; a bool operator== sor nélkül a p1 == p2 a fenti hibát adja, a defaultolt <=>-os változaton pedig javítás nélkül is fordul.

2. megoldás.

#include <compare>
#include <cstdint>
#include <cstddef>
#include <type_traits>

struct Endpoint {
    std::uint32_t addr = 0;
    std::uint16_t port = 0;
    bool operator==(const Endpoint&) const = default;
    auto operator<=>(const Endpoint&) const = default;   // addr, majd port
};

struct EndpointHash {
    std::size_t operator()(const Endpoint& e) const noexcept {
        std::size_t h = static_cast<std::size_t>(e.addr);
        h ^= static_cast<std::size_t>(e.port) + 0x9e3779b9u
             + (h << 6) + (h >> 2);
        return h;
    }
};

static_assert(std::is_same_v<decltype(Endpoint{} <=> Endpoint{}),
                             std::strong_ordering>);

Indoklás: az integrális tagok <=>-ja std::strong_ordering, a tagonkénti lexikografikus összehasonlítás tranzitív és irreflexív, tehát strict weak ordering — sőt teljes rendezés az (addr, port) párokon. A hash csak a két tag értékétől függ, ezért $a = b \Rightarrow h(a) = h(b)$ automatikusan teljesül. Ellenőrzési feltétel: két azonos (addr, port) párra a == b igaz és h(a) == h(b), valamint !(a < b) && !(b < a) is igaz.

3. megoldás. A <= nem irreflexív: a <= a igaz, így az 1. feltétel sérül, a komparátor nem strict weak ordering, a std::sort viselkedése nem definiált (jellemző tünet: túlindexelés vagy „érvénytelen komparátor” futásidejű diagnosztika).

Javítás A — szigorú <, NaN kizárása: return a.value < b.value; és a bemenet validálása (std::isnan esetén hiba vagy kihagyás). Itt a NaN be sem kerül, a -0.0 és 0.0 ekvivalens marad, ami egyezik a ==-vel.

Javítás B — teljes rendezés: return std::strong_order(a.value, b.value) < 0;. Ez minden double-re definiált, de a -0.0 kisebb lesz a +0.0-nál, és a NaN-ok is helyet kapnak, tehát a tároló ekvivalenciafogalma eltér a ==-tól. Ezt dokumentálni kell, és ugyanarra a kulcsra nem szabad unordered_map-et használni, mert ott az == dönt.