std::rotate algoritması

STL, kaplarda (container) tutulan ögeleri işlemek için bazı standart algoritmalar sunar. Bu algoritmalar arama (sorting), kopyalama (copying), yeniden düzenleme (rearrangement), değiştirme (modifying) ve sayısal işleme (numeric processing/numeric algorithms) gibi temel işlemler gerçekleştirir.

Standart algoritmaları kullanmak için <algorithm> başlık dosyası eklenmelidir. Algoritmalar kapların üye işlevleri değildir. Bir ya da birden fazla aralıkla (range) çalışan global işlev şablonlarıdır (template functions). İşlev şablonu olmaları, algoritmaların programcı tarafından tanımlanan türler (user-defined types) ile de kullanılabilmelerini sağlar.

Yeniden düzenleme algoritmaları -bunlara değiştirme algoritmaları da (mutating algorithms) denilmektedir- ögelerin sırasını atama (assign) ve takas (swap) ile değiştiren algoritmalardır. Yeniden düzenleme algoritmaları, sıralı ve sıralı olmayan ilişkisel kaplarla (ordered associative containers/unordered associative containers) kullanılamazlar çünkü bu tür kaplarda tutulan ögelerin sıraları içsel olarak belirlenmiştir.

rotate algoritması en sık kullanılan yeniden düzenleme algoritmalarındandır. İngilizcede rotate “döndürmek” veya “çevirmek” manalarına gelmektedir. Görsel olarak düşünüldüğünde, rotate algoritması verilen bir aralıktaki ögeleri, aralığı ilk ve son ögenin bitiştiği bir çembermiş gibi görüp, bu aralıktaki ilk öge olması istenilen öge en başa gelinceye kadar sola doğru döndürür.

rotate işlev şablonunun imzası şöyledir:
template<typename ForwardIt>
ForwardIt rotate(ForwardIt f, ForwardIt m, ForwardIt l);

f:
aralığın başlangıcı.
m:
[f, l) aralığında yer alan ve döndürme işlemi bittiğinde en başta olması istenilen ögeyi gösteren adımlayıcı (iterator).
l:
aralığın sonu.
Geri Dönüş Değeri:
Aralığın döndürme işleminden önceki ilk ögesinin döndürme işleminden sonraki yeni pozisyonu. C++11’den önce bu işlevin geri dönüş değeri void’dur.

circle

Yukarıda gösterilen işlemin kodu aşağıdaki gibidir:

rotate algoritması bir başka açıdan bakıldığında da, ardışıl iki aralığın yerini değiştirir. Bu şekilde düşünüldüğünde f parametresi ilk aralığın başı, m parametresi ilk aralığın sonu ve ikinci aralığın başı, l parametresi ikinci aralığın sonu olarak; geri dönüş değeri de yer değiştirme işleminden önceki ilk aralığın ilk ögesinin, yer değiştirme işleminden sonraki yeni pozisyonu olarak düşünülebilir.

exchange

rotate algoritmasında ögeler takas yöntemiyle taşınır. Her algoritmada olduğu gibi, standart rotate algoritmasına argüman olarak geçilen aralığın geçerliliği çağıranın sorumluluğundadır. rotate, doğrusal karmaşıklıkta bir algoritmadır.

rotate algoritması temelde silme ve ekleme işlemlerinin birleşimi olarak düşünülebilir. Ne zaman ki bir sırasal kapta (sequential container) bir yerden silme ve başka bir yere ekleme işlemleri birlikte aynı öge veya ögeler üzerinde kullanılıyorsa, orada rotate kullanılabilir.

erase_insert

Yukarıdaki görselde yapılan silme ve ekleme işlemi rotate algoritması ile şu şekilde yapılabilirdi:

rotate algoritması birçok başka algoritmada da kullanılır. Örneğin sıralama algoritmalarından araya ekleme sıralaması algoritması (insertion sort) rotate algoritması kullanılarak gerçekleştirilebilir.

Tarayıcılarda bir sekmeyi sürükleyerek başka bir yere taşıma özelliği rotate algoritmasına gerçek bir örnek olarak gösterilebilir. Google Chrome tarayıcısında bu taşıma Shift tuşu ile çoklu seçilen sekmeler üzerinde de uygulanabilir.

Soru:

question

Yukarıdaki resimde renklendirilmiş ögeler rotate algoritması kullanılarak nasıl ok ile gösterilen pozisyona taşınabilir?

Kaynakça:

Josuttis, Nicolai M. 2012. The C++ Standart Library – A Tutorial and Reference (2nd edition). Addison Wesley
Parent, Sean 2013. C++ Seasoning. GoingNative
Stepanov, Alexander A. and McJones, Paul 2009. Elements of Programming. Addison Wesley
Stroustrup, Bjarne 2013. The C++ Programming Language (4th edition). Addison Wesley

Cavit Sina Dogru

Arkel Elektrik Elektronik'te C/C++ programcısı olarak çalışıyor.

Bunlar da ilginizi çekebilir

Bir Cevap Yazın

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

Kod Eklemek İçin Okuyun