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:
|
1 2 3 4 5 |
partition stable_partition is_partitioned (C++11) partition_copy (C++11) partition_point (C++11) |
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:
|
1 2 |
template<class ForwardIt, class UnaryPredicate> ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p); |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <forward_list> #include <algorithm> #include <iterator> using namespace std; int main() { forward_list<int> mylist{ 1, 56, 23, 5, 2, 8, 7, 9, 20, 41, 13, 4, 12 }; auto iter = partition(mylist.begin(), mylist.end(), [](int x){return x % 2 == 0; }); copy(mylist.begin(), mylist.end(), ostream_iterator<int>(cout, " ")); //56 2 8 20 4 12 7 9 5 41 13 1 23 cout << endl; copy(mylist.begin(), iter, ostream_iterator<int>(cout, " ")); //56 2 8 20 4 12 cout << "\n"; copy(iter, mylist.end(), ostream_iterator<int>(cout, " ")); //7 9 5 41 13 1 23 return 0; } |
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.) :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
template<class ForwardIt, class UnaryPredicate> ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p) { first = std::find_if_not(first, last, p); if (first == last) return first; for (ForwardIt i = std::next(first); i != last; ++i){ if (p(*i)){ std::iter_swap(i, first); ++first; } } return first; } |
Şimdi de aşağıdaki kodu inceleyelim:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cctype> using namespace std; int main() { vector<string> svec{ "murat", "berk", "oguz", "gul", "hasan", "ece", "mustafa","necati", "sadullah", "tan", "mert", "necmettin", "niyazi", "saadet","ali", "kaya", "gizem", "murtaza", "su", "tayyip", "cinali"}; size_t len; cout << "uzunluk degerini giriniz : "; cin >> len; auto iter = partition(svec.begin(), svec.end(), [len](const string &s){return s.length() < len; }); if (iter != svec.end()) { transform(iter->begin(), iter->end(), iter->begin(), ::toupper); } for (const auto &s : svec) cout << s << " "; cout << endl; return 0; } |
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:
|
1 2 |
template<class BidirIt, class UnaryPredicate> BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p); |
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:
|
1 |
gul, ece, tan, ali, su |
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:
|
1 2 |
template<typename InputIt, typename UnaryPredicate> bool is_partitioned(InputIt first, InputIt last, UnaryPredicate p); |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { list<int> ilist{ 12, 24, 18, 6, 48, 7, 17, 13, 19, 55, 25}; int ival; cout << "kaca tam bolunenler : "; cin >> ival; cout << boolalpha << is_partitioned(ilist.begin(), ilist.end(), [ival](int x) {return x % ival == 0; }); return 0; } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 |
template<typename InputIt, typename UnaryPredicate> bool is_partitioned(InputIt first, InputIt last, UnaryPredicate p) { for (; first != last; ++first) if (!p(*first)) break; for (; first != last; ++first) if (p(*first)) return false; return true; } |
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:
|
1 2 3 4 5 6 7 8 9 10 |
remove_copy remove_copy_if replace_copy replace_copy_if reverse_copy rotate_copy partial_sort_copy partition_copy sort_copy unique_copy |
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:
|
1 2 3 4 5 6 |
template<typename InpuIt, typename OutputIt1, typename OutputIt2, typename UnaryPredicate > std::pair<OutputIt1, OutputIt2> partition_copy(InputIt first, InputIt last, OutputIt1 d_first_true, OutputIt2 d_first_false, UnaryPredicate p); |
İş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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
template<typename InputIt, typename OutputIt1, typename OutputIt2, typename UnaryPredicate> std::pair<OutputIt1, OutputIt2> partition_copy(InputIt first, InputIt last, OutputIt1 d_first_true, OutputIt2 d_first_false, UnaryPredicate p) { while (first != last) { if (p(*first)) { *d_first_true = *first; ++d_first_true; } else { *d_first_false = *first; ++d_first_false; } ++first; } return std::pair<OutputIt1, OutputIt2>(d_first_true, d_first_false); } |
Aşağıdaki örneği inceleyin:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <list> #include <vector> #include <deque> #include <algorithm> #include <iterator> using namespace std; int main() { list<int> ilist{ 3, 5, 23, 4, 6, 87, 90, 30, 42, 26}; vector<int>ivec(10); deque<int>ideque(10); int ival; cout << "bir tamsayi girin : "; cin >> ival; auto p = partition_copy(ilist.begin(), ilist.end(), ivec.begin(), ideque.begin(), [ival](int x) {return x > ival; }); cout << "vector'e " << distance(ivec.begin(), p.first) << " oge deque'e " << distance(ideque.begin(), p.second) << " oge yazildi" << endl; ostream_iterator<int> osit(cout, " "); copy(ivec.begin(), ivec.end(), osit); cout << endl; copy(ideque.begin(), ideque.end(), osit); cout << endl; return 0; } |
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
|
1 2 |
template<class ForwardIt, class UnaryPredicate> ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPredicate p); |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <algorithm> #include <deque> #include <cstdlib> #include <ctime> #include <iterator> using namespace std; int main() { deque<int> mydeque; srand(static_cast<unsigned>(time(nullptr))); for (int k = 0; k < 20; ++k) { int val = rand() % 100; if (val % 2 == 0) { mydeque.push_front(val); } else { mydeque.push_back(val); } } copy(mydeque.begin(), mydeque.end(), ostream_iterator<int>(cout, " ")); cout << "\n"; auto iter = partition_point(mydeque.begin(), mydeque.end(), [](int x) {return x % 2 == 0; }); if (iter != mydeque.end()) { cout << "ilk tek sayi : " << *iter << endl; cout << "indeks : " << distance(mydeque.begin(), iter) << endl; } return 0; } |
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.
