C++ Dilinde lexicographical compare ve lexicographical_compare_three_way

C++ dilinde, karşılaştırma işlemleri genellikle iki değerin büyüklüğünü veya eşitliğini kontrol etmek için kullanılır. Özellikle array ve diğer sequence containers ile çalışırken, "lexicographical compare" kavramı önemli bir yer tutar. Bu makalede, lexicographical karşılaştırma ve C++20 ile birlikte gelen "lexicographical_compare_three_way" fonksiyonları üzerinde duracağız.

Lexicographical Compare https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare

Lexicographical compare, bir diziyi (veya diğer sequence containers) bir kelime listesi gibi değerlendirme yöntemidir. Bu, karakter dizilerini veya diğer sıralı nesneleri ele alırken, öğelerin sırasını belirlemek için kullanılır. Örneğin, "elma" kelimesi "muz" kelimesinden önce gelir, çünkü ilk karakter olan 'e', 'm'den önce gelir.

C++ dilinde, lexicographical compare için <algorithm> başlık dosyasında yer alan std::lexicographical_compare fonksiyonu kullanılabilir. Bu fonksiyon, iki sıralı aralık (genellikle iki container) alır ve ilk aralığın ikinci aralıktan önce gelip gelmediğini belirler.

template <class InputIt1, class InputIt2 >
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2);

(1)	(constexpr since C++20)
template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare(ExecutionPolicy&& policy,
                             ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2);
(2)	(since C++17)
template <class InputIt1, class InputIt2, class Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2,
                             Compare comp);

(3)	(constexpr since C++20)
template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare>
bool lexicographical_compare(ExecutionPolicy&& policy,
                             ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2,
                             Compare comp);

Parametre	Açıklama
first1	İlk aralığın başlangıcını gösteren bir işaretçi (iterator). Bu, karşılaştırılacak ilk öğenin yerini belirtir.
last1	İlk aralığın sonunu gösteren bir işaretçi. Bu, karşılaştırılacak son öğeden sonraki öğeyi belirtir.
first2	İkinci aralığın başlangıcını gösteren bir işaretçi. Bu, karşılaştırılacak ikinci öğenin yerini belirtir.
last2	İkinci aralığın sonunu gösteren bir işaretçi. Bu, karşılaştırılacak son öğeden sonraki öğeyi belirtir.
policy	Kullanılacak yürütme politikası. Yürütme politikaları, işlemlerin nasıl yürütüleceğini belirler (örneğin, seri veya paralel).
comp	Karşılaştırma işlevi nesnesi. Bu, iki öğeyi karşılaştıran ve ilk argümanın ikinci argümandan küçük olduğunu belirten bir işlevdir.

Return Value

• Eğer birinci aralık, ikinci aralıktan sözcüksel olarak (lexicographically) küçükse true, aksi takdirde false döner.

Complexity

Exceptions

int main()
{
    std::vector<int> x(100'000, 5);
    std::vector<int> y{6, 8};

    std::boolalpha(std::cout);
    
    std::cout << (y > x);
}
*****************************     
AÇIKLAMA : karşılaştırma lexicographical compare ile yapılır.    
yani hem size degeri hem de karşılıklı bütün verilerin eşit olması gerekir.
*****************************     
CEVAP : true
*****************************

#include <iostream>
#include <list>
#include <vector>

int main()
{
    std::vector vec{ 3, 4, 7, 8 };
    std::list lst{ 3, 4, 8, 8 };

    std::boolalpha(std::cout);
    
    std::cout << (vec > lst);
}
*****************************     
AÇIKLAMA : error: no match for ‘operator>’ (operand types are ‘std::vector >’ and ‘std::__cxx11::list >’)
*****************************     
CEVAP : syntax error
*****************************

#include <iostream>
#include <list>
#include <vector>

int main()
{
    std::vector vec{ 3, 4, 7, 8 };
    std::list lst{ 3, 4, 8, 8 };

    std::boolalpha(std::cout);
    
    cout << std::lexicographical_compare(lst.begin(), lst.end(), vec.begin(), vec.end());
}
*****************************     
AÇIKLAMA : default less compare kullanılır.
*****************************     
CEVAP : false
*****************************

std::lexicographical_compare_three_way https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare_three_way

C++20 ile birlikte gelen lexicographical_compare_three_way, lexicographical karşılaştırmayı üç yönlü (<=, ==, >=) bir karşılaştırma ile birleştirir. Bu fonksiyon, iki diziyi karşılaştırırken hem eşitlik hem de sıralama bilgisi sağlar. Böylece, std::strong_ordering türünde bir değer döner. <algorithm> başlık dosyasındadır.

template <class InputIt1, class InputIt2, class Cmp>
constexpr auto lexicographical_compare_three_way(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Cmp comp ) -> decltype(comp(*first1, *first2));

(1)	(since C++20)
template <class InputIt1, class InputIt2>
constexpr auto lexicographical_compare_three_way(InputIt1 first1, InputIt1 last1, InputIt2                                first2, InputIt2 last2);

• comp işlevine göre her iki aralıkta bulunan ilk eşit olmayan eleman çifti arasında bir sıra döner. Eğer bir aralık, diğerinin ön eki ile eşit ise, bu durumda her iki aralığın uzunlukları arasındaki sıralama döner. Bu, dizilerin karşılaştırılmasında önemli bir özellik sunar.

• Bu std::lexicographical_compare_three_way(first1, last1, first2, last2, std::compare_three_way()) ifadesine eşdeğerdir. Eğer dönüş tipi, üç karşılaştırma kategorisinden biri değilse, program hatalı olur. Bu kategoriler şunlardır:

  
  

  • std::strong_ordering: Kesin bir sıralama sağlar.

  • std::weak_ordering: Zayıf bir sıralama sağlar; eşitlik durumunu dikkate alır.

  • std::partial_ordering: Kısmi bir sıralama sağlar; bazı öğeler karşılaştırılamayabilir.

std::ostream& operator<<(std::ostream& os, std::strong_ordering sval)
{
    return os << (sval == 0 ? "equal" : sval < 0 ? "less" : "greater");
}

int main()
{
    std::vector vec{ 3, 4, 7, 8 };
    std::list lst{ 3, 4, 8, 8 };
    
    auto ret = 
        lexicographical_compare_three_way(lst.begin(), lst.end(), vec.begin(), vec.end());

    std::cout << ret;
}
*****************************     
AÇIKLAMA : std::strong_ordering
İki aralık (list ve vector) karşılaştırılırken, ilk iki öğe (3 ve 4) eşit olduğu için dikkate alınmaz. Ancak, lst içinde 8 ve vec içinde 7 olduğu için:
->lst'nin 3. öğesi (8) > vec'in 3. öğesi (7) olduğu için, lst 'nin sıralaması vec'den daha büyüktür.
->Ancak, yazdırılma biçimi nedeniyle karşılaştırma sonucu less olarak döner; çünkü lst'de 8, vec'de 7'den büyük olduğu için sıralama vec'e göre daha küçüktür.
*****************************     
CEVAP : less
*****************************