C++ İle Vektör Yapısı
Herkese merhaba. Bu yazı C++ ile örnekler vererek pekiştireceğim, veri yapıları konusunun alt başlıklarından olan vektör yapısı hakkında olacaktır. Problemleri çözmek adına oluşturulan algoritmalarda sık sık karşımıza çıkan veri yapıları (vektörler, listeler, kuyruklar, yığınlar, ağaçlar) ile bir seri oluşturmaya karar verdim. Vektör ile başlayalım.
Vektörler, bir öge eklendiğinde veya silindiğinde kendini otomatik olarak yeniden boyutlandırma yeteneğine sahip dinamik dizilerle aynıdır. Vektör ögeleri, yineleyiciler (iterators) kullanılarak erişilip üzerinden geçilebilmesi için bitişik depoya (contiguous storage) yerleştirilir.
Vektörlerde, veriler sona eklenir. Sondan ekleme, bazen dizinin genişletilmesi gerekebileceğinden, farklı zaman alır. Yeniden boyutlandırma olmadığı için son ögeyi kaldırmak yalnızca sabit bir zaman (O(1)) alır. Başına-ortasına ekleme veya silme, zaman içinde doğrusaldır (O(n)).
Diziler de bir pointer olduğundan vektörleri oluştururken pointer ile oluşturmak en doğrusu olacaktır. Data isimli bir vektör oluşturduktan sonra yine private alanda capacity ve index değişkenlerini oluşturuyoruz. Capacity değişkeni vektörün alabileceği değer sayısını belirtirken, index değişkeni veri eklenmek istenen indisi tutar. Kurucu fonksiyonda vektörü boş olarak oluşturduğumuzdan capacity değişkenine 1, index değişkenine 0 değeri atanır. Cap() fonsksiyonu capacity değerini, size() fonksiyonu ise index değerini döndürür.
BELLEK BÜYÜTME (Push_back())
Vektöre bir değer eklemek istendiğinde tahsis edilmiş olan kapasiteyi aşarsa bellek büyütme işlemi yapılmalıdır. Push_back metodu ile vektörün sonuna eklenen değer dizinin sınırları içinde değil ve eklenen index başka bir programa tahsis edilmiş ise o dizinin bozulmasına neden olabilir. Kapasite arttırılarak bu durum önlenmiş olur. Index değeri kapasite değerine eşit veya bu değerden büyükse dinamik olarak büyüme işlemi yapılmalıdır. Kapasite istenilen orantıda büyüyebilir.
Yeni kapasite değerine eşit elemanlı bir geçici dizi oluşturularak eleman kaybına sebep olmamak adına dizinin elemanları yeni diziye kopyalanır. Eski dizi serbest bırakılarak alan kaybından kurtulunur. Data dizisini tmp dizisine eşitleyerek nereyi gösterdiğini belli etmemiz gerekir. Sadece silinirse dizi bir daha ulaşılamaz hale gelir.
Data dizisi oluşturulduğunda kurucu fonksiyonda verilmiş değerler bastırılır. Size: 0, Capacity: 1 çıktıları buradan gelir. Push_back metodu ile veri eklendiğinde index değeri 1 artar fakat growth fonksiyonu önce çağrıldığı için index, kapasite değerine eşit olmaz bu yüzden dizi dinamik olarak büyümez. Size: 1, Capacity: 1 çıktıları alınır. Tekrar push_back yapıldığında capacity ve index değerleri birbirine eşit olduğu için kapasite değeri 2 katı artar. Bu durumda Size: 2, Capacity: 4 olur. Tekrar push_back yapıldığında index değeri 1 artar fakat index değeri kapasite değerinden az olduğu için kapasite değeri artmaz. Pop_back methodu ise sondan eleman siler ve index değeri 1 azalır.
BELLEK KÜÇÜLTME (Pop_back())
Vektörden bir değer silmek istendiğinde index sayısı kapasitenin yarısından (büyüme oranına göre) az olduğunda dizinin gerekenden fazla yer kaplamaması adına bellek küçültme işlemi yapılmalıdır. Pop_back metodu ile dizinin sonunda bulunan değer silinir. Index değeri kapasite değerine eşit veya bu değerden küçükse dinamik olarak küçülme işlemi yapımalıdır. Kapasite istenilen orantıda küçülebilir. Hataya yol açmaması adına büyüdüğü oranda küçülmesi gerekir.
Growth fonksiyonundan farklı olarak index değeri, kapasite değerinin büyüdüğü oranda bölümüne eşit ve küçük olması durumunda shrink fonksiyonu aktif hale gelir. Kapasite değeri yine aynı oranda küçülerek bu değere eşit eleman içeren geçici bir dizi oluşturulur.
Push_back metodu ile diziye 6 veri eklenir ve büyüme işlemi yapılır. Pop_back metodu ile sondan başlayarak veri silindiğinde index değeri (5) kapasite değerinin yarısına eşit veya küçük olmadığından dinamik küçülme işlemi yapılmaz. Shrink fonksiyonu sonradan çağrılır çünkü önce index değerinin eksilmesi ve bu değere göre dizinin küçülüp küçülmeyeceğine bakılır. Tekrar pop_back yapıldığında index değeri (4) kapasite değerinin yarısına eşit olduğu için dizinin küçülmesi beklenir ve kapasite değeri yarısı kadar azalarak index değerine eşit olur.
BEGİN() — END() ~FRONT() — BACK()
Begin fonksiyonu bir vektörün ilk elemanına işaret eden yineleyiciyi elde etmek için kullanılır. End fonksiyonu vektörün sondaki elemanına işaret eden yani dizinin bittiği yeri işaret eden yineleyiciyi almak için kullanılır. Front fonksiyonu vektörün ilk elemanını döndürür. Back fonksiyonu vektörün son elemanını yani vektörün en son adresinin nerde bittiğini döndürür bu sayede dizinin nerede bittiği takip edilir. Hiçbiri içerisine parametre almaz.
Bu işlevler genellikle aynı sonucu sağlamak için karıştırılır ancak aralarındaki fark, vektörün ilk ve son adresindeki değeri döndürmek için front() ve back() işlevlerinin kullanılmasıdır. Öte yandan, vektörün ilk ve son adresini döndürmek için begin() ve end() işlevleri kullanılır.
Yukarda görüldüğü üzere front vektörün ilk elemanına, back ise son elemanına eşittir. Begin ve end fonksiyonları vektörün ilk ve son adreslerini döndürür. Adreslerin değerini döndürmek istediğimizde ise begin fonksiyonu ilk elemanı verirken, end fonksiyonu random bir değer döndürür. Bunun nedeni vektörün bittiği yeri işaret etmesinden kaynaklıdır. Yani 10 değerinin adresi 00E3F300, 20 değerinin adresi 00E3F304 iken vektörün bitiş adresi olan ve belli bir değeri olmayan 00E3F308 ise belirsiz bir sayı döndürür.
Integer türünden bir pointer oluşturarak begin fonksiyonuna eşitlenir. Dizinin ilk elemanının adresine eşitlenerek for döngüsü dizinin boyutu kadar devam eder ve bu süreçte begin arttırılarak pointer aritmetiği ile bir sonraki elemanın adresine işaret eder. *begin ile bu adresin değeri bastırılır.
AT() VE OPERATOR AŞIRI YÜKLEME
At metodu istenilen indisteki değeri veren fonksiyondur. Geri dönüş değeri integer tipinin referansı şeklinde olacaktır. Hem okuma hem yazma işlemi yapılabilmesi için referans türünden bir değer döndürülmesi gerekmektedir.
C++’ta, nesneler ve yapılar gibi kullanıcı tanımlı türler için operatörlerin çalışma şeklini değiştirebiliriz. Bu, operatör aşırı yüklemesi olarak bilinir. Aşırı yüklenmiş operatörler, özel adlara sahip fonksiyonlardır. ‘operator’ anahtar sözcüğü ile istenilen aşırı yükleme yapılacak operator sembolü yazılarak oluşturulur.
Yukarda görüldüğü üzere indisin, dizinin boyutu sınırları içinde olması gerektiğinden 0'dan büyük eşit ve dizinin boyutundan küçük eşit olması gerekmektedir. at ve operator overloading ile 2. ve 4. indisteki elemanın değeri, istenilen değere eşitlenmiş ve dizi güncel şekilde tekrar bastırılmıştır.
INSERT
Vektörün başına, sonuna ya da ara indexine eleman eklemek istendiğinde insert metodu kullanılabilir. Eklenen eleman sona eklenmediyse, bu elemandan sonraki elemanların indexi bir artar, önceki elemanlar ise sabit kalır.
Vektörden bağımsız olarak bir swap fonksiyonu oluşturalım. Verileri kaybetmeden değiştirme işlemi yapmak adına vereceğimiz parametreler referans şeklinde olmalıdır bu sayede 2 veri bağımsız olarak yer değiştirebilir.
Ekleme işlemi yapacak olan insert fonksiyonu parametre olarak içerisine eklenmek istenen integer tipinde bir pointer olan indis ve referans olarak value değerini alır. İndis, vektörün sınırları içerisinde olmalıdır. Eklenen elemandan sonra dinamik büyüme işlemi yapılır. Nindis değişkeni ile eklenmek istenen indis belirlendikten sonra push_back metodu ile istenen veri sona eklenir. Daha sonra eklenen elemandan sonraki elemanların yer değiştirmesi ve bir aşağı kayması için for döngüsü ile swap işlemi yapılır. İ değeri size()-1'e eşitlenir çünkü vektörümüzün boyutu eleman eklendiği için büyüdüğünden ve sona eklenen eleman istenilen indise ulaştığında yer değiştirmeyeceği için bir önceki boyuta göre işlem yapılması gerekir. Sona eklenen elemanımız bir önceki elemanla yer değiştirerek eklenmesi istenilen indise ulaşır. İ değeri azalarak elemanın ekleneceği indise eşitlendiğinde döngü sonlanır.
Yukarıda görüldüğü gibi push_back metoduyla elemanları ekledik ve ekrana bastırdık. Daha sonra insert metodu ile istenilen indisi ve elemanı yazdık görüldüğü gibi 60 sayısı 1. indise eklenmek istenmiş ve güncel vektörümüz başarıyla yazdırılmış. Bu işlem şöyle gerçekleşmiş; 15 78 658 60 →15 78 60 658 → 15 60 78 658. Başa eklenmek istenen 785 sayısı için de aynı işlem yapılmış ve güncel vektör ekrana bastırılmıştır.
ERASE
Vektörün başından, sonundan ya da ara indexinden eleman çıkarılmak istendiğinde erase metodu kullanılabilir. Sondan eleman silinmediyse, bu elemandan sonraki elemanların indexi bir azalır, önceki elemanlar ise sabit kalır. Birnevi insert metodunun tersi işlevindedir.
Silme işlemi yapacak olan erase fonksiyonu parametre olarak içerisine silinmek istenen integer tipinde bir pointer olan indisi alır. İndis yerine referans olarak value değeri de yazılabilir. Aynı sayıdan birden fazla eleman varsa hem indis hem de value paramtelerini alabilir. Silinen elemandan sonra dinamik büyüme işlemi yapılır. Silinmek istenen eleman swap işlemi ile vektörün sonuna taşınır ve pop_back metodu ile silinir.
Push_back metodu ile vektörümüzü oluşturduk ve ekrana bastırdık. Daha sonra silmek istediğimiz elemanın indisini referans şeklinde vererek erase fonksiyonunu çağırdık. Görüldüğü gibi ekrana bastırdığımız 2. dizide 1. indisteki yani 78 sayısı silindi. Dizinin ilk elemanını silmek istediğimizde de indisi begin fonksiyonu ile belirterek ekrana güncel diziyi bastırmış olduk.
STL kütüphanesi kullanılarak bu işlemler direk çağırılabilir fakat bazen hocalarımız stl kütüphanesini kullanmamamızı istediğinden arka planda ne olduğunu ve nasıl çalıştıklarını göstermek amacıyla yazdığım bu yazı umarım işinize yarar. Bir sonraki yazımda görüşmek üzere. :)
P.S. Örneklere erişebilmek için GitHub hesabıma bakabilirsiniz. https://github.com/yamurko
