C ve C++’da Dinamik Dizi Veri Yapısı

7 min readOct 31, 2020

Dinamik dizi veri yapısı programlama dillerinde en çok kullanılan veri yapılarından bir tanesidir. Veri yapıları programlama dillerinden bağımsız olsa da bu yazıda C ve C++ dilleri ile genel olarak dinamik dizi veri yapısını tanıtmaya ve kullanımlarını anlatmaya çalışacağım.

C dilinde dinamik dizi veri yapısı standart kütüphane tarafından hazır olarak sunulmamaktadır. C++ dilinde ise standart kütüphane tarafından bu veri yapısını hazır olarak sunan araçlar bulunmaktadır. C++’da en çok kullanılan sınıflardan olan vector ve string sınıfları dinamik dizi veri yapılarıdır. String sınıfı yazı işlemleri için özelleştirilmişken vector sınıfı genel bir dinamik dizi sınıfıdır.

Dinamik dizi veri yapısı isminden de anlaşıldığı üzere sabit dizilerden farklı olarak kapasitesi çalışma sırasında değiştirilebilir bir veri yapısıdır. Sabit diziler gibi dinamik diziler de ardışık ve parçalı olmayan (contiguous) bir bellek alanında tutulur.

Dinamik dizi veri yapısında boyut (size) ve kapasite (capacity) kavramları çok önemlidir. Boyut veri yapısında kaç tane öğe bulunduğunu belirtirken kapasite ise fiilen ayrılmış bellek bloğunun kaç tane öğe tutabileceğini belirtmektedir. Dinamik dizi veri yapılarında tipik olarak veri yapısının bellekteki başlangıç adresini yani veri yapısındaki ilk öğenin adresini, veri yapısında yer alan en son öğenin adresini ve allocate edilmiş bellek bloğunun bittiği adresi tutan üç tane pointer bulunur. (Son ikisi pointer yerine tamsayi bir değişken de olabilir. Zaten başlangıç adresi bilindiği için bu adres üzerine tamsayı değeri eklenerek en son öğeye ve veri yapısı kapasitesinin sonuna ulaşılabilir)

Biz bir dinamik dizi oluşturduğumuzda veri yapısına koyacağımız öğelerin sığabileceği bir kapasite belirlenir. Yukarıdaki görseli referans alırsak kapasitemize göre 4 tane daha öğe ekleyebiliriz. Eğer kapasiteden daha fazla öğe eklememiz gerekirse yani boyutun kapasiteye eşit veya daha büyük olması gerektiği bir ekleme işlemi gerçekleştiğinde yeni öğelerin yerleştirilebilmesi için daha önceden ayrılan bellek bloğu yeniden yapılandırılır(reallocation). Bu işlem üç farklı şekilde sonuçlanabilir.

Aynı bellek alanı yeni kapasite ile genişletilir.
Aynı bellek alanında genişletme işlemi yapılamaz. Başka bir bellek alanı yeni kapasite ile allocate edilir. Veri yapısı öğeleri buraya kopyalanır ve eski bellek alanı serbest bırakılır.
Yeterli bellek alanı olmadığı için allocation süreci başarısız olur.

Peki hangi durumda var olan bellek alanı genişletilemiyor ve başka bir bellek alanı allocate edilmek zorunda kalınıyor hatta daha da ileri bir senaryoda allocation başarısız oluyor?

Dinamik bellek yönetiminde heap alanını yönetme algoritmaları programlamada üzerine en çok çalışılan konulardan bir tanesidir. Bu alanı yöneten algoritma ne kadar iyi olursa olsun eninde sonunda fragmentation oluşması mümkündür. Daha önceden ayrılmış bir bellek alanını büyültmek istediğimizde fragmentation’dan kaynaklı bütün olarak bir bellek alanı yer ayırabilmesi mümkün olamayabiliyor. Heap alanını yöneten fonksiyon bu durumda bellek alanında bütün olarak ayırabileceği bir yer varsa bu bellek alanını yeni kapasite ile ayırıp veri yapısının bütün elemanlarınını bu yeni bellek alanına taşıyor ve eski bellek alanını free/delete ediyor. Ancak yeni kapasite ile ayırabilecek bir bellek alanı bulamadıysa bu durumda reallocation süreci başarız olmaktadır. Reallocation tabiki sadece fragmentation yüzünden değil gerçekten bellek alanının yeni kapasite için yetersiz olmasından kaynaklı olarak da başarısız olabilir. Tipik olarak da C’de bu işlem realloc fonksiyonunun NULL pointer geri dönüşü ile sonuçlanırken C++’da da bad allocation exception throwing ile sonuçlanır.

Reallocation sürecinden sonra kapasitenin yeni değeri implementasyona bağlı olarak değişebilmekle birlikte genellikle eski kapasite değerinin 1.5 veya 2 katı olmaktadır. Bunu gösterebilmek için basit bir C++ programı yazabiliriz. Aşağıdaki kod parçasında vector sınıfı kullanarak dinamik dizi veri yapısının boyut ve kapasitesi arasındaki ilişkiyi görebilmemiz mümkündür. Test sonuçlarını da kodun sonunda bulabilirsiniz.

Yukarıda da görüldüğü gibi boyutun kapasiteye ulaştığı her durumda kapasite iki katına çıktı. Bu katsayı önceden söylediğim gibi implementasyona göre değişmektedir ancak benim hem clang hem de g++ ile yaptığım testlerde bu katsayıyı 2 olarak gözlemledim.

C++’da yukarıda örneği yapılan vector sınıfı haricinde string sınıfı da bir dinamik dizi veri yapısıdır. String sınıfı ile de benzer bir örneği yapmak mümkün ama örneği yapmadan önce string sınıflarında derleyicilerin büyük çoğunluğunun desteklediği özel bir optimizasyondan bahsetmek istiyorum. String nesnelerin içinde dinamik dizi veri yapısının yönetimi için kullanılan pointerların veya değişkenlerin yanında bir de küçük stringlerin tutulabilmesi için sabit boyutta char dizi bulunmaktadır. Kısa stringler dinamik bellek yönetimine ihtiyaç duyulmadan direk bu alanda tutulur böylelikle dinamik bellek yönetiminin getirdiği yüksek maliyet küçük stringler için optimize edilmiş olunur. Bu optimizasyona Small String Optimization veya Short String Optimization denilmektedir. Char diziye sığmayacak bir string yerleştirilmek istendiğinde ise dinamik bellek yönetimi ile bu string’in sığabileceği bir kapasite ile bellek alanı tahsis edilir.

Bu yüzden bir string nesnesi hayata getirdiğimizde string uzunluğuna bağlı olarak direk dinamik bellek yönetimi yapılıp bir yer ayrılmaz. Bu durumu kanıtlamak için de new ve delete operatör fonksiyonlarını kendimiz yükleyerek aşağıdaki gibi bir test kodu yazabilmemiz mümkündür. Ayrıca aynı kod içerisinde dinamik dizi veri yapısının boyut ve kapasite ilişkisini de inceleyebiliriz. Aşağıda görüldüğü gibi string nesnesini ilk hayata getirdiğimizde herhangi bir allocation yapılmadı ve kendi sınıfı içerisinde tanımlı sabit boyutlu dizinin boyutu varsayılan kapasite olarak ele alındı ancak string uzunluğu belli bir boyutu geçtiği zaman yani kapasiteye eşit ve büyük olduğu zaman görüldüğü gibi artık dinamik bellek yönetimi ile eski kapasitenin iki katı kadar yeni bir bellek alanı tahsis edildi.

C’de ise dinamik dizi veri yapısı C++’daki gibi standart kütüphane tarafından hazır olarak sunulmamaktadır ancak dinamik dizi veri yapısını implemente eden üçüncü parti kütüphaneler mevcuttur. Profesyonel bir projede kullanılacak ise güvenilir kütüphaneler tercih etmek doğru bir yaklaşım olacaktır ancak kendimiz implemente etmek isteseydik C’de çok temel olarak bir kaç tane operasyonu destekleyen ve int türünü tutan bir dinamik dizi veri yapısını aşağıdaki gibi bir tasarım ile yazabilirdik. (Bu kod sadece gösterim amaçlı yazılmıştır.)

Her ne kadar yazının konusu bu olmasa da bahsetmekte fayda var. Gömülü sistemlerde dinamik dizi veri yapıları heap fragmentation sorunu nedeniyle hard real time sistemlerde kullanılmamaktadır bunun yerine belli bir sayıda veri elemanı alabilecek şekilde sınırlandırılarak fixed size array veri yapısı kullanılmaktadır ancak hard real time sistemler dışında dinamik dizi veri yapısının zorunlu bir ihtiyaç haline gelmesi durumunda custom allocator yapıları yazılarak dinamik dizi veri yapısı kullanılabilmektedir. Gömülü sistemleri hem bare-metal ve RTOS tabanlı sistemler hem de embedded linux tabanlı sistemlerin birleşimi olarak görmemiz gerekiyor bu yüzden gömülü sistemlerde kesinlikle dinamik dizi veri yapıları kullanılmaz gibi bir genelleme tamamen yanlıştır. Güvenlik kritik uygulamalar ve dinamik bellek yönetiminin kodlama standartı olarak yasaklandığı uygulamalar dışında bu veri yapılarının kullanımları gömülü sistemlerde de olmaktadır. Bu tarz kullanımlarda da heap fragmentation sorunu non-fragmenting allocator tasarımları ile önlenmeye çalışılmaktadır. Tipik bir kullanımı genellikle fixed-size buffer pool oluşturarak dinamik bellek yönetiminin memory pool üzerinden yapılmasıdır. Diğer bir yaklaşım da sadece initialization sürecinde dinamik bellek yönetimine izin verilmesi ancak çalışma sırasında dinamik bellek yönetiminin yasaklanmasıdır. Böylelikle sistemin çalışması sırasında herhangi bir heap fragmentation’dan kaynaklı sorun oluşmayacağı garanti altına alınmış olunuyor.

Son olarak dinamik veri yapısının avantajlarından ve dezavantajlarından bahsetmek istiyorum.

Veri yapısındaki elemanlara indeks ile erişim O(1) karmaşıklığına sahiptir. Buradaki O(1) Big-O notasyonundan gelmektedir. O(1) de sabit zaman (constant time) erişim anlamına gelmektedir. Bu algoritma karmaşıklıkları içerisinde zaten olabilecek en mükemmel senaryodur.
Sondan ekleme ve silme işlemleri yine O(1) sabit zaman karmaşıklığına sahiptir. Burada önemli bir nokta var sondan ekleme işlemine O(1) karmaşıklığı dedik ama yazımda da bahsettiğim gibi ekleme sonrasında veri yapısının boyutu kapasiteye eşit olur ya da fazla olursa reallocation gerektiriyordu. Bu da maliyetli bir işlem yani ekleme sırasında reallocation süreci gerçekleşirse bu işlem sabit zaman karmaşıklığında olmuyor. Reallocation her zaman da olmayacağı için buradaki ekleme işlemi amortised constant time olmaktadir.
Veri yapılarında günümüz bilgisayar sistemlerinde en fazla belirleyici faktörlerden birisi cache miss / cache hit oranıdır. Veri yapılarının performansını belirleyen en önemli faktörlerden bir tanesidir. Dinamik dizi veri yapısında bu oran yüksektir. Bu oran ne kadar yüksekse veri yapısı o kadar cache friendly olmaktadir.
Dinamik dizi veri yapısında sadece sondan ekleme/silme işlemleri constant time onun haricindeki ekleme/silme işlemleri O(n) linear karmaşıklığa sahiptir. Örneğin Bağlı Liste (Linked List) veri yapısında bu işlem O(1) sabit zaman karmaşıklığına sahiptir.
Dinamik dizi veri yapısında kendi içinde gerçekleştirilecek takas işlemlerinde kopyalama maliyeti ortaya çıkıyor ancak örneğin bir linked list veri yapısında takas işleminde sadece adresleri takas ettiğiniz için bu maliyet oldukça düşüktür.
Son olarak da belki direk dinamik dizi veri yapısının dezavantajı demek doğru olmayabilir ancak yazılımcı olarak bizlerin uygulamada yaptığımız bazı hatalar yüzünden dezavantaj haline getirdiğimiz bir konu var. Örneğin şöyle bir senaryo düşünelim. String ve vector container sınıflarından nesnelerimiz var. Bu veri yapılarına programın çalışma süresince sürekli veri ekleniyor ancak bir süre sonra bu veriler kullanıcı tarafından siliniyor ve uygulama senaryosuna göre de çok uzun süre ya da artık hiç bu veri yapılarına veri girişi olmayacak. Eğer kullanıcı tarafından özel olarak kapasite düşürülmez ise bu kapasite en son değerinde kalır. Yani veri yapısında hiç veri olmasa bile var olan kapasite shrink-to-fit edilmediği için program hiç gerekli olmadığı halde büyük bir bellek alanını boş yere işgal edebilir.
Yukarıda açıklaması yapılan uygulama hatasını şununla karıştırmamak gerekir. Öyle bir uygulama olur ki çalışma senaryosunda veri yapısına sürekli artan bir şekilde veri girişi yapılacağı bellidir. Bu yüzden sürekli reallocation yapılması yerine veri yapısı maksimum bir kapasite ile hayata getirilir yani belli bir kapasite daha en baştan rezerve (reserve) edilir ve böylelikle kapasite dolana kadar hiç reallocation işlemi yapılmamış olunur. Bu performansı arttırmaya yönelik programcı tarafından bilerek ve istenerek yapılan birşeydir.

C++’da dinamik dizi veri yapısı dilin bir standart kütüphanesi ile sunulan bir araç olduğu için o kadar iyi optimize ediliyor ki dinamik dizi veri yapısının getirdiği dezavantajları da optimize edebiliyor.

Bir veri yapısının bizim uygulamamız için uygun olup olmayacağı sorusuna sadece yukarıdaki teorik bilgilerden yola çıkarak net bir cevap vermemiz mümkün değildir. Çünkü veri yapısının büyüklüğüne göre bu avantaj ve dezavantajlar değişebilmektedir. Uygulamamız için uygun veri yapısına karar vermenin en iyi yollarından bir tanesi profiling yapmak ve yazılımı minimum, ortalama ve maksimum veri öğeleri ekleyerek çalıştırıp benchmarking yaparak sonuçları gözlemlemektir.

Diğer yazılarımda görüşmek üzere…

Referanslar

C ve C++’da Dinamik Dizi Veri Yapısı

Written by Serbay Özkan