Strict Weak Ordering

Strict Weak Ordering Nedir?
Strictk Weak Ordering key değerlerinin karşılaştırılması için "<" işlemini kullanması anlamına gelir.

Hangi Veri Yapıları Kullanır?
std::map ve std::set elemanların eşitliği için bu yöntemi kullanır. Tüm veri yapıları için Compare kavramına bakmak gerekir.

Hangi Algoritmalar Kullanır?
std::sort sıralama için bu yöntemi kullanır. Tüm veri yapıları için Compare kavramına bakmak gerekir.

Java'da Nasıldır?
Java'da elemanların eşitliğ için nesnenin equals() metodu kullanılır.

Strict Weak Ordering Tablosu

Bir tablo haline dökersek şöyle gösteririz

For all a, comp(a,a)==false
If comp(a,b)==true then comp(b,a)==false
if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

veya şöyle gösteririz

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

En Çok Yapılan Hata - İki Nesne Eşitse

Kural şudur. Yani kısaca iki nesne eşitse false dönmek gerekir.

they are equivalent if !comp(a,b) && !comp(b,a)

Aynı kuralın bir başka şekilde ifade edilişi de şöyle

In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a)

Şöyle de ifade edilebilir.

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. 

Örnek - Yanlış Kullanım

Şu kod yanlış. Çünkü comp(a,a) false döneceğine true dönüyor.

bool comp (string s1, string s2) {
  if (s1.size() < s2.size())
    return false;
  else
    return true;
}

sort ile comparator sınıfı kullanmak

Örneğin yeni bir b key değerini eklerken mevcut a key değeri ile karşılaştırma yapılır. a < b ifadesinin false olması a'nın b'den küçük olmasını garanti etmek için yeterli değildir. Aynı zamanda b < a ifadesinin de false olması gerekir. Eğer bu ikinci karşılaştırma da false dönerse a = b sonucu çıkarılır ve map insert() metodu yeni girdiyi kabul etmez.

Yani < karşılaştırması map'e yeni bir değer eklerken biraz daha fazla karşılaştırma yapılmasına sebep olur.

< Nasıl Kodlanır
Normalde kalıtım kullanmaya pek ihtiyaç olmaz. Ancak kalıtım kullanan bir örnek göstermek istedim. Şöyle yaparız.

class Base
{
public:
  virtual bool operator<(Base & other) const
  {
    std::cout << "Base";
  }
};

class Derived : public Base
{
public:
  bool operator<(Base & other) const override
  {
    std::cout << "Derived";
  }
};

int main()
{
  Derived a;
  Derived b;
  a < b; //prints "Derived"
  a.Base::operator <(b); //prints "Base"
}