Algoritmalar

Önceki ders erase sonrası bir yineleyicinin okunmasının belirsiz olduğunu, erase’in döndürdüğü yeni yineleyicinin ise geçerli kaldığını gösterdi. O ders tek bir konumu izliyordu. Bu ders sınırı yeniden genişletiyor: standart kütüphanenin bir kapsayıcının tüm elemanları üzerinde çalışan hazır algoritmalarına geçiyor. std::sort bir vector’ü sıralarken kaynağa ne bırakıyor? Aynı soru bu dersteki her algoritma için tekrar sorulacak; bazı algoritmalar kaynağı okuyup hiç değiştirmezken bazıları kaynağın kendisini kalıcı olarak yeniden düzenler, ve bu fark algoritmanın adından değil standart tanımından çıkarılır.

std::sort: Yerinde Değiştiren Bir Algoritma

std::sort, verilen yineleyici aralığındaki elemanları belirtilen sıralama kuralına göre yerinde düzenler — yeni bir kapsayıcı döndürmez, verilen aralığın kendisini değiştirir. Varsayılan kural operator<’tir.

// sort-yerinde.cpp — std::sort bir vector'u nasil degistiriyor
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> sayilar{40, 10, 30, 20};

    std::sort(sayilar.begin(), sayilar.end());

    std::printf("siralanmis dizi:");
    for (int deger : sayilar) {
        std::printf(" %d", deger);
    }
    std::printf("\n");
    return 0;
}

siralanmis dizi: 10 20 30 40

KT13. std::sort çağrısından sonra sayilar’ın eleman sayısı değişmedi ama elemanların sırası değişti — bu işlemin sınıfı değişti. Standart, sıralamadan sonra hangi tam diziliş olacağını garanti eder (küçükten büyüğe, operator< kuralına göre), yani sonuç belirsiz değil, tam tersine öngörülebilir ve tekrarlanabilir. Bu, sort’u önceki dersteki erase’den ayıran şey: erase’in bıraktığı yineleyici belirsizdi, ama sort’un bıraktığı dizi tanımlıdır.

Salt Okuma Algoritmalar: Kaynağı Aynen Bırakanlar

Her algoritma kaynağı değiştirmez. std::count, verilen değere eşit eleman sayısını döndürür; std::find_if, bir yüklemi sağlayan ilk elemana bir yineleyici döndürür; std::accumulate, elemanları biriktirerek toplar. Üçü de aralığı yalnız okur.

// salt-okuma-algoritmalar.cpp — count, find_if, accumulate kaynagi degistiriyor mu
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> sayilar{4, 7, 2, 7, 9};
    auto once = sayilar;

    long adet = std::count(sayilar.begin(), sayilar.end(), 7);
    auto it = std::find_if(sayilar.begin(), sayilar.end(),
        [](int deger) { return deger > 8; });
    int toplam = std::accumulate(sayilar.begin(), sayilar.end(), 0);

    std::printf("7 adedi %ld\n", adet);
    std::printf("8'den buyuk ilk deger %d\n", *it);
    std::printf("toplam %d\n", toplam);
    std::printf("kaynak degisti mi %s\n", (sayilar != once) ? "evet" : "hayir");
    return 0;
}

7 adedi 2
8'den buyuk ilk deger 9
toplam 29
kaynak degisti mi hayir

KT14. Üç algoritma da sayilar’ı yalnız okudu; işlem sonunda kaynak işlem öncesindeki kopyasıyla eşit — sınıf aynen. Bu, std::sort’la doğrudan karşıtlık kurar: ikisi de aynı vector üzerinde çalışır, ama sort diziliş sırasını değiştirirken bu üç algoritma diziliş sırasına hiç dokunmaz. Bir algoritmanın adı genelde niyetini gösterir — count, find, accumulate fiilleri “sorgula” der, sort, reverse, transform fiilleri “değiştir” der — ama bu bir garanti değil, bir alışkanlıktır; kesin cevap her zaman ilgili algoritmanın standart tanımındadır.

Bu Kurs Saymaz: Ölçümün Ekseni Çalışma Sayısı Değildir

Trait'ler, Genellikler ve Hata Yönetimi (Rust, M10/K03) bir gövdenin kaç kez koştuğunu ölçerek soyutlamanın çalışma zamanı bedelini görünür kılıyordu — orada ölçülen şey bir çağrının kaç kez tekrarlandığıydı. Bu kurs farklı bir eksende çalışıyor ve saymaz: std::count’un döndürdüğü 2 gibi bir sayı, aranan değere kaç elemanın eşit olduğunu söyleyen bir sonuçtur, algoritmanın kaç kez çağrıldığını ya da bir gövdenin kaç kez çalıştığını sayan bir ölçüm değildir. Bu dersin sorduğu soru hep aynı: bir işlem kaynağı hangi sınıfa (aynen/değişti/boş/belirsiz) bıraktı? std::count’un kendisi bir kez çağrılır ve kaynağı aynen bırakır; içeride kaç karşılaştırma yaptığı bu ölçümün konusu değildir. Bir okurun iki kursu karıştırmaması için bu ayrım önemlidir: soyutlamanın çalışma zamanı bedelini öğrenmek isteyen rust-soyutlama’ya, bir işlemin kaynağı ne durumda bıraktığını öğrenmek isteyen bu kursa bakar.

Özel Karşılaştırma Yüklemi

std::sort’un üçüncü bir argümanı olabilir: iki elemanı karşılaştıran bir yüklem. Bu yüklem operator<’in yerine geçer ve sıralama kuralını programcı tanımlar.

// sort-yuklem.cpp — ozel karsilastirma ile buyukten kucuge siralama
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> sayilar{40, 10, 30, 20};

    std::sort(sayilar.begin(), sayilar.end(),
        [](int a, int b) { return a > b; });

    std::printf("buyukten kucuge:");
    for (int deger : sayilar) {
        std::printf(" %d", deger);
    }
    std::printf("\n");
    return 0;
}

buyukten kucuge: 40 30 20 10

KT15. Yüklem a > b döndürdüğünde a’nın b’den önce geleceğini belirtir; bu yüzden dizi büyükten küçüğe sıralandı. Bu işlemin sınıfı da değişti — önceki sort çağrısıyla aynı sınıfta, çünkü ikisi de aynı algoritmanın farklı bir kuralla çağrılmış hâli. Yüklemin kendisi sayilar’ı hiç okumadı ya da değiştirmedi; yalnız iki int değeri karşılaştırdı. Bu ayrım önemli: sort’u değiştirici yapan yineleyici aralığına yazması, yüklemi değiştirici yapmayan ise yalnız değer karşılaştırması olmasıdır.

Algoritmalar Yineleyici Çiftiyle Çalışır, Kapsayıcıyla Değil

Standart algoritmaların hiçbiri bir kapsayıcı tipi almaz; hepsi bir başlangıç ve bitiş yineleyicisi alır. Bu, aynı algoritmanın bir vector’ün tamamında, bir vector’ün bir alt aralığında ya da bir C dizisinde çalışabilmesini sağlar.

// yineleyici-cifti.cpp — ayni algoritma farkli araliklarda
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> sayilar{5, 3, 8, 1, 9, 2};

    std::sort(sayilar.begin(), sayilar.begin() + 3);

    std::printf("kismi siralanmis dizi:");
    for (int deger : sayilar) {
        std::printf(" %d", deger);
    }
    std::printf("\n");
    return 0;
}

kismi siralanmis dizi: 3 5 8 1 9 2

KT16. std::sort(sayilar.begin(), sayilar.begin() + 3) yalnız ilk üç elemanı sıraladı; kalan üç eleman (1 9 2) girdi sırasında kaldı. Bu, aynı std::sort çağrısının farklı bir aralıkla farklı bir sonuç ürettiğini gösteriyor — algoritma kapsayıcının tamamını değil, kendisine verilen yineleyici çiftini görüyor. Bu işlemin sınıfı yine değişti, çünkü sayilar’ın bir kısmı (ilk üç eleman) diziliş olarak değişti; ancak değişikliğin kapsamı bu kez kapsayıcının bütünü değil, verilen aralıkla sınırlı. Bu tasarımın bir sonucu, algoritmaların kapsayıcı sınırlarını hiç bilmemesidir: std::sort’a verilen sayilar.begin() + 3 yineleyicisi kapsayıcının kendi sonunu değil, çağıranın belirttiği sınırı gösteriyor. Aynı algoritma bir ham C dizisi üzerinde de, işaretçi çiftiyle çağrılarak aynı şekilde çalışır — kapsayıcı kavramı algoritmanın arayüzünde hiç yer almaz, yalnız yineleyici kategorisi (burada rastgele erişim) arayüzün gerektirdiği şeydir.

std::transform: Yeni Bir Hedefe Yazan Algoritma

std::sort kaynak aralığın kendisini değiştiriyordu. std::transform farklı bir kalıp sunar: kaynağı okur, her elemana bir işlev uygular ve sonucu ayrı bir hedefe yazar. Kaynak, hedeften ayrı bir kapsayıcı olduğu sürece std::transform kaynağa hiç dokunmaz.

// transform-ayri-hedef.cpp — std::transform kaynagi mi hedefi mi degistiriyor
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> kaynak{1, 2, 3, 4};
    std::vector<int> hedef(kaynak.size());

    std::transform(kaynak.begin(), kaynak.end(), hedef.begin(),
        [](int deger) { return deger * deger; });

    std::printf("kaynak:");
    for (int deger : kaynak) {
        std::printf(" %d", deger);
    }
    std::printf("\n");

    std::printf("hedef:");
    for (int deger : hedef) {
        std::printf(" %d", deger);
    }
    std::printf("\n");
    return 0;
}

kaynak: 1 2 3 4
hedef: 1 4 9 16

KT17. kaynak işlem sonunda hâlâ 1, 2, 3, 4 — std::transform kaynağı yalnız okudu, hiç yazmadı; kaynağın sınıfı aynen. hedef ise kareler dizisiyle dolduruldu. std::transform’un üçüncü argümanı hedefin başlangıç yineleyicisidir; bu argüman kaynağın kendisi (kaynak.begin()) olarak da verilebilir — bu durumda algoritma her elemanı okuyup aynı konuma geri yazar ve kaynak bu kez değişti sınıfına girer. Hangi sınıfın geçerli olduğu hedefin kaynakla aynı aralık olup olmadığına bağlıdır; bu ders ikisini ayrı tutarak std::transform’un varsayılan davranışını, yani kaynağı okuyup ayrı bir yere yazmayı gösteriyor. std::transform’un hedef argümanı bir yineleyici olduğu için hedefin önceden yeterli boyutta ayrılmış olması çağıranın sorumluluğundadır — algoritma hedefe eleman eklemez, yalnız var olan konumlara yazar; hedef kaynak kadar büyük değilse yazma, ayrılmış bellek sınırının dışına taşar ve bu da tanımsız davranıştır. Bu ders hedef’i her zaman kaynak.size() ile boyutlandırarak bu riski hiç oluşturmuyor.

std::stable_sort: Eşit Elemanların Sırasını Koruyan Sıralama

std::sort, eşit kabul edilen iki eleman arasındaki göreli sırayı korumayı garanti etmez — bu, algoritmanın izin verilen bir yan etkisidir, bir hata değildir. std::stable_sort aynı sıralama işini yapar ama ek bir garanti taşır: karşılaştırma yüklemine göre eşit sayılan elemanlar, girdi sırasındaki göreli konumlarını korur. Bu garanti bedelsiz değildir — std::sort ortalama O(n log n) karmaşıklıkla çalışırken std::stable_sort yeterli ek bellek yoksa O(n log² n)’e düşebilir; ek bellek varsa yine O(n log n) sağlar.

// stable-sort-esitlik.cpp — esit elemanlarin sirasi std::sort ile stable_sort arasinda nasil farkli
#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, char>> kayitlar{
        {2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};

    std::stable_sort(kayitlar.begin(), kayitlar.end(),
        [](const auto& sol, const auto& sag) { return sol.first < sag.first; });

    std::printf("siralanmis kayitlar:");
    for (const auto& kayit : kayitlar) {
        std::printf(" (%d,%c)", kayit.first, kayit.second);
    }
    std::printf("\n");
    return 0;
}

siralanmis kayitlar: (1,b) (1,d) (2,a) (2,c)

KT18. Anahtara göre eşit sayılan {1, 'b'} ve {1, 'd'} çifti, sıralamadan sonra da girdideki göreli sırasını korudu — b hâlâ d’den önce geliyor. Aynı şey {2, 'a'} ve {2, 'c'} için de geçerli. Bu işlemin sınıfı da değişti — dizi baştan sona yeniden düzenlendi — ama std::sort’tan farkı, eşitler arasındaki göreli sıranın da korunmuş olduğu ek bir garantidir. std::sort aynı girdide (1,d) ile (1,b)’yi ters sırada bırakabilirdi; bu, std::sort’un ihlal ettiği bir kural değil, hiç vermediği bir sözdür.

std::list Neden Kendi sort’unu Taşır

std::sort, rastgele erişim yineleyicisi gerektirir — ortalama O(n log n) karmaşıklığını sağlayabilmek için elemanlar arasında sabit zamanlı atlama yapması gerekir. Bu yüzden std::sort, std::list’in çift yönlü yineleyicisiyle derlenmez. Standart kütüphane bu durum için ayrı bir üye işlev sağlar: std::list::sort.

// list-sort-uye-islevi.cpp — list icin ayri bir sort neden gerekli
#include <cstdio>
#include <list>

int main() {
    std::list<int> degerler{40, 10, 30, 20};

    // Asagidaki satir derlenmez, cunku std::sort rastgele erisim yineleyicisi ister:
    // std::sort(degerler.begin(), degerler.end());

    degerler.sort();

    std::printf("siralanmis liste:");
    for (int deger : degerler) {
        std::printf(" %d", deger);
    }
    std::printf("\n");
    return 0;
}

siralanmis liste: 10 20 30 40

std::list::sort’un ayrı bir üye işlev olarak var olmasının nedeni bu kısıtlama: list’in düğümleri bitişik bellekte durmadığı için genel std::sort algoritması onlar üzerinde çalışamaz, ama list kendi düğümlerinin bağlantılarını yeniden kurarak aynı sonucu farklı bir karmaşıklıkla üretebilir. Bu, “her kapsayıcı her algoritmayla çalışmaz” kuralının somut bir örneği. Aynı kısıtlama diğer rastgele-erişim-isteyen algoritmalar için de geçerlidir: std::nth_element ve ikili aramaya dayanan std::binary_search, std::lower_bound gibi algoritmalar da std::list üzerinde doğrudan çağrılamaz; standart kütüphane bu boşluğu her kapsayıcı için ayrı bir üye işlevle doldurmaz, yalnız list::sort, list::merge, list::unique ve list::remove gibi düğüm bağlantısı gerektiren birkaç işlemi üye olarak sunar. Kapsayıcı seçimi bu yüzden yalnız karmaşıklık garantilerini değil, hangi standart algoritmaların doğrudan kullanılabileceğini de belirler.

Sınırlayıcı Ölçüm

Aynı veri, aynı anahtara göre karşılaştırma yüklemiyle iki farklı algoritmaya verildiğinde kaynağın ne kadarı güvenilir biçimde okunabilir sorusu algoritmanın adına bağlıdır. std::sort, eşit anahtarlı elemanlar arasındaki göreli sırayı korumayı garanti etmez — bu yüzden o sırayı yazdırmak, standardın vermediği bir sözü varmış gibi göstermek olur. Aynı veriyi bir de std::stable_sort ile sıralayıp iki sonucu karşılaştıralım:

#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, char>> anahtarli{
        {2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};
    std::vector<std::pair<int, char>> kararli = anahtarli;

    std::sort(anahtarli.begin(), anahtarli.end(),
        [](const auto& sol, const auto& sag) { return sol.first < sag.first; });
    std::stable_sort(kararli.begin(), kararli.end(),
        [](const auto& sol, const auto& sag) { return sol.first < sag.first; });

    std::printf("sort anahtar sirasi:");
    for (const auto& kayit : anahtarli) {
        std::printf(" %d", kayit.first);
    }
    std::printf("\n");

    std::printf("stable_sort tam sira:");
    for (const auto& kayit : kararli) {
        std::printf(" %d%c", kayit.first, kayit.second);
    }
    std::printf("\n");
    return 0;
}

sort anahtar sirasi: 1 1 2 2
stable_sort tam sira: 1b 1d 2a 2c

anahtarli üzerinde yalnız anahtarları (1 1 2 2) yazdırdık; harfleri yazdırmadık, çünkü std::sort’un eşit anahtarlar arasında hangi harfi önce bıraktığı standart tarafından tanımlanmayan bir ayrıntıdır — aynı derleyici bile farklı girdi boyutlarında farklı bir iç sıralama uygulayabilir. kararli üzerinde ise tam kayıtları yazdırabildik, çünkü std::stable_sort eşit anahtarların girdideki göreli sırasını korumayı garanti eder: 1b her zaman 1d’den önce, 2a her zaman 2c’den önce gelir. İki çağrı da aynı veriyi değişti sınıfına taşır — kaynak yerinde yeniden düzenlenir — ama kaynağın hangi ayrıntısının güvenle okunup bildirilebileceğini algoritmanın adı belirler: sort yalnız nihai anahtar sırasını, stable_sort ise anahtar sırasıyla birlikte eşitler arası göreli konumu da garanti eder.

Özet

• std::sort, verilen yineleyici aralığındaki elemanların sırasını yerinde değiştirir; bu dersin merkezi ölçümünün sınıfı değişti. Özel bir karşılaştırma yüklemi vermek sıralama kuralını değiştirir ama yüklemin kendisi kaynağı okumaz ya da değiştirmez; std::stable_sort ise eşit sayılan elemanların göreli sırasını da korur, bu ek garanti yeterli ek bellek yoksa O(n log² n)’e çıkan bir karmaşıklık bedeliyle gelir. Sınırlayıcı ölçüm: aynı veri std::sort ve std::stable_sort’a verildiğinde ikisi de kaynağı değişti sınıfına taşır, ama kaynağın hangi ayrıntısı güvenle bildirilebilir sorusu algoritmanın adına bağlıdır — sort yalnız anahtar sırasını garanti eder, stable_sort eşitler arası göreli sırayı da.
• std::count, std::find_if, std::accumulate gibi salt okuma algoritmalar kaynağı aynen bırakır.
• Bu kurs çalışma sayısı saymaz: rust-soyutlama’nın “kaç kez koştu” ekseni bu kursun ölçüm ekseni değildir; burada ölçülen şey kaynağın hangi sınıfta kaldığıdır.
• Algoritmalar bir kapsayıcı tipi değil, bir yineleyici çifti alır; aynı algoritma farklı aralıklarla farklı kapsamda çalışır.
• std::transform, kaynağı okuyup ayrı bir hedefe yazdığında kaynağın sınıfı aynen kalır; hedefi kaynağın kendisi yapmak sınıfı değişti’ye çevirir.
• std::sort, rastgele erişim yineleyicisi ister ve std::list üzerinde derlenmez; list bunun yerine kendi sort üye işlevini sağlar.

Sonraki Adım

Bu ders std::sort’un bir kapsayıcıyı yerinde nasıl değiştirdiğini gösterdi. Sonraki ders bir kapsayıcıdan eleman kaldırmanın iki adımlı bir deyim gerektirdiğini ele alıyor: std::remove, elemanları neden gerçekten silmiyor da yalnız kuyruğa doğru taşıyor?