STL bölümleme (partition) algoritmaları

Uygulamalarda en sık gereksinim duyulan işlemlerden birisi bölümleme (partitioning). Bölümleme, bir veri yapısında tutulan öğeleri bir koşulu sağlayan ve sağlamayanlar olarak iki kısma ayırma işlemi. STL‘de bölümleme ile ilgili algoritmalar şunlar:

partition algoritması ile başlıyoruz. Doğrusal karmaşıklıktaki paritition algoritması ile bir aralığı (range) bir koşulu sağlayanlar ve sağlamayanlar olara iki bölüme ayırabiliyoruz. Algoritmamızın şablon bildirimi şöyle:

Birinci şablon tür parametresi üzerinde işlem yapılacak aralığın türü. Bildirimde kullanılan ismin de ifade ettiği gibi algoritmamız en az forward_iterator kategorisinde bir iterator istiyor. C++11 öncesinde bu algoritma bidirectional_iterator kategorisinde bir iterator gerektiriyordu. C++11 ile yapılan bu değişiklik ile artık bu algoritmayı bir forward_list kabına ilişkin bir aralık üzerinde de koşturabiliyoruz. Algoritmanın ikinci şablon tür parametresi, sınanacak koşulu ifade eden tek parametreli sorgulayıcının (predicate) türü. Bu türden olan işlevimizin üçüncü parametresine, benzer algoritmalarda olduğu gibi bir işlev adresi, bir lambda, ya da bir işlev nesnesi (functor) gönderebiliriz. Doğal olarak burada çağrılacak işlevin geri dönüş değeri bool türden (ya da bool‘a dönüştürebilecek) olmalı. İşlevin geri dönüş değeri bölümleme noktası olan konuma ilişkin iterator. Bu değer, koşulu sağlayan öğelerin aralığı için end konumu olarak ya da koşulumuzu sağlamayanlar için begin konumu olarak kullanılabilir. Aşağıdaki kodu inceleyelim:

Yukarıdaki kodda mylist isimli forward_list nesnesinde tutulan tamsayıları, değerlerin çift olup olmamasına göre iki kısma ayırdık. İşlev çağrısında işlevin üçüncü parametresine bir lambda ifadesi gönderdiğimizi görüyorsunuz. İşlevin geri dönüş değerini iter isimli iterator nesnesinde tuttuk. Daha sonra copy algortimasına yaptığımız çağrılarla sırasıya, listedeki öğelerin tümünü, yalnızca ikiye tam bölünenleri ve sonra da yalnızca ikiye tam bölünmeyenleri standart çıkış akımına yazdırdık. partition algoritması şu şekilde kodlanabilir (kodu cppreference.com sitesinden aldım.) :

Şimdi de aşağıdaki kodu inceleyelim:

Yukarıdaki kodda svec isimli vector nesnesinde tutulan isimleri uzunluğu len değerinden küçük olanlar ve olmayanlar olarak iki bölüme ayırdık. Koşulu sağlamayan ilk ismi (eğer böyle bir isim varsa) transform algoritmasıyla büyük harfe dönüştürdük. Kapta tutulan isimlerin uzunluğunun len değerinden küçük olup olmadığını sınamak için bir lambda ifadesi kullandık.

stable_partition algoritması

Algoritmamızın şablon bildirimi şöyle:

Bildirimden algoritmanın minimal olarak bidirectional_iterator kategorisinde bir iteratör talep ettiğini görüyorsunuz. Yani bu algoritmayı örneğin, forward_iterator kategorisinde iteratörlere sahip olan foreward_list kapları için çalıştırma girişimimiz sentaks hatası oluştururdu. STL‘de isminde stable geçen iki algortima var : stable_sort ve stable_partition. Çalıştıkları aralık üzerinde değişiklik yapan bu algoritmalar, verilen kritere göre eşdeğer olan öğelerin işlem öncesindeki görece sıralarını işlem sonrasında koruma garantisini sağlıyorlar.

Örneğin yukarıdaki kodda sıralamadan önce 4 karakterden daha kısa olan isimler (sırasıyla) şunlar:

partition algoritmasını uzunluğu yazıların uzunluğunun 4‘ten küçük olma koşulu ile çalıştırırsak bölümleme işleminden sonra bu sıranın korunma garantisi verilmiyor. Ancak aynı aralığı aynı lambda ifadesi ile stable_partition algortimasıyla bölümlerseniz işlem öncesi sıralamanın korunduğunu göreceksiniz.

is_partitioned algoritması

Bu algoritma C++11 standartları ile dile eklendi. is_partitioned algoritması ile bir aralığın verilen bir koşula göre bölümlenmiş olup olmadığını sınayabiliyoruz. İşlev şablonumuzun bildirimi şöyle:

Bildirimden de görüldüğü gibi, algoritmada kullanılacak iteratör türünün input_iterator kategorisinde olması yeterli. Eğer işlem aralığı boş ise ya da verilen aralık üçüncü parametreye geçilen koşula göre bölümlenmiş ise işlevimiz true değeri aksi halde false değeri döndürüyor. Aşağıdaki kodu inceleyelim:

Yukarıdaki kodda ilist içinde tutulan tamsayıların ival değerine tam bölünüp bölümlenmediklerine göre bölümlenmiş olup olmadığını sınıyoruz.
is_partioned algoritması aşağıdaki biçimde kodlanabilir:

partition_copy algoritması

Bu algoritma da dile C++11 standartlarıyla eklendi. STL‘deki bazı algoritmalar yüklendikleri işi, aldıkları aralık üstünde gerçekleştirmek yerine, elde edilecek sonucu başka bir aralığa kopyalıyorlar. Bu algoritmaların isimleri tipik olarak copy ya da copy_if sözcüklerini içeriyor. STL‘de bu şekide çalışan algoritmalar şunlar:

Doğrusal karmaşıklıkta olan partition_copy algoritması kaynak olarak kullanacağı bir aralıktaki değerlerden, bir koşulu sağlayanları bir hedef aralığa, sağlamayanları bir başka hedef aralığa kopyalıyor. Biraz karmaşık görünen aşağıdaki bildirim gözünüzü korkutmasın, partition_copy kullanımı son derece kolay olan bir algoritma:

İşlevimiz [first last) aralığındaki değerleri, p tek parametreli sorgulayıcısına (unary predicate) argüman olarak gönderiyor. Sorgulayıcının true değer döndürdüğü değerler d_first_true konumundan başlayan aralığa,  sorgulayıcının false değer döndürdüğü değerler d_first_false konumundan başlayan aralığa kopyalanıyor. İşlevimizin geri dönüş değeri olan pair nesnesinin first öğesi birinci hedef aralığa (d_first_true) yazılan son değerden sonraki değerin konumu (yazılmış aralığın end konumu).
Geri döndürülen pair nesnesinin second öğesi ise ikinci hedef aralığa (d_first_false) yazılan son değerden sonraki değerin konumu (yazılmış aralığın end konumu)
İşlev şablonumuz şu şekilde kodlanabilir:

Aşağıdaki örneği inceleyin:

Yukarıdaki kodda, partition_copy algoritması ile ilist kabında tutulan öğelerden ival değişkeninin değerinden büyük olanlar ivec kabına büyük olmayanlar ise ideque kabına kopyalanıyor.

partition_point algoritması

C++11 standartları ile dile eklenen bir başka algoritma partition_point.
Algoritmamızın şablon bildirimi şöyle

Algoritmamız belirli bir koşula göre bölünmlenmiş bir aralığa ilişkin bölümlenme noktasını döndürüyor. İşlevin geri dönüş değeri, p koşulunu sağlamayan ilk öğenin konumuna ilişkin iteratör. Bu amaçla şüphesiz standart find_if_not algoritmasını da kullanabilirdik. Ancak partition_point algoritması, eğer kendisine gönderilen aralık, ilgili koşula göre bölümlenmiş ise bölümlenme noktasına ilişkin konumu logaritmik karmaşıklıkta hesaplıyor. Tabi eğer algoritmada kullanılan iteratör türü random_access_iterator kategorisinde değilse iteratör arttırma işlemlerinin doğrusal karmaşıklıkta olacağı unutulmamalı. Aşağıdaki kodu inceleyelim:

Yukarıdaki kodda for döngüsü içinde ürettiğimiz rastgele tamsayılardan çift olanları mydeque kabına baştan tek olanları ise sondan ekledik. Bu durumda doğal olarak kabımızdaki tam sayılar çift olup olmadıklarına göre bölümlenmiş oldular. Daha sonra partition_point algoritmasıyla kabımızda tutulan ilk tek sayının konumunu bulmuş olduk.

Necati Ergin

C ve Sistem Programcıları Derneğinde eğitmen olarak çalışıyor.

Bunlar da ilginizi çekebilir

STL bölümleme (partition) algoritmaları” için 2 yorum

  1. Necati Bey selamlar,
    Problem 1)Yukarıdaki kodda, partition_copy algoritması ile ilist kabında tutulan öğelerden ival değişkeninin değerine tam bölünenler ivec kabına tam bölünmeyenler ise ideque kabına kopyalanıyor.
    1-)ival değişkeninden büyük olanlar ve olmayanlar şeklinde olması gerekmiyor mu?

    Problem 2)

    kodun

    şeklinde değiştirilmesi gerekiyor. //Cpp std::transform and toupper why does this fail?
    detaylı bilgi için : stackoverflow.com/questions/1489313/c-stdtransform-and-toupper-why-does-this-fail

    iyi çalışmalar

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Kod Eklemek İçin Okuyun