C++'ın türden bağımsız toplulukları (generic containers)

[Bur2]

Bu yazıda standart C++ kütüphanesinde bulunan toplulukları kısaca tanıtmak istiyorum.

Çoğu program, aynı türden birden fazla nesneyi daha sonradan üzerlerinde işlem yapmak amacıyla bir araya getirir. Örneğin, tanıdık ödev programlarından olan öğrenci notlama programı; öğrencileri bir öğrenciler topluluğunda, her öğrencinin
derslerini bir dersler topluluğunda ve her derste aldığı notları da bir notlar topluluğunda tutar.

Nesneleri böyle bir araya getiren çeşitli veri yapıları vardır.
Bu tür veri yapılarına, bu yazı içinde C++ dünyasında kullanılan 'container'ın karşılığı olarak 'topluluk' diyeceğim.


C programlama dili, yalnızca bir tane topluluk sunar: dizi.
Dizi, C'nin temel dil olanaklarındandır. C'nin standart kütüphanesi topluluklar konusunda hiçbir yardımda bulunmaz. Ne yazık ki C'nin dizileri, kendi büyüklüklerinden bile haberleri
olmayan çok basit yapılardır.

C++, C'nin topluluklar konusundaki bu eksikliğini şablon (template) olanağı yardımıyla büyük ölçüde giderir ve programcılara ustalar tarafından tasarlanmış, yazılmış ve
denenmiş topluluklar ve algoritmalar sunar.

C++ standart kütüphanesinde bulunan topluluklar çok kısaca şöyle tanıtılabilirler:

- vector
Gelişmiş C dizileri gibi düşünülebilirler. Genelde, yeni ögelerin topluluğun sonuna eklendikleri ve herhangi bir anda herhangi bir ögeye (rastgele) hızlıca erişimin gerektiği
durumlara uygundurlar. Topluluktaki ögeler, girildikleri sırayı koruyacak şekilde tutulurlar. Araya öge eklemek, genelde sona öge eklemekten çok daha pahalı bir işlemdir. vector herhangi bir anda, topluluk içinde o anda bulunan ögeler için gerekenden çok daha fazla belleği elinde tutuyor (harcıyor) olabilir. Ögelerini
bellekte peş peşe tuttuğu için, C dizileri bekleyen C işlevleriyle de kullanılabilir. vector'ün varlığı nedeniyle, C++ programlarında C dizilerinin kullanılmalarına neredeyse hiç gerek kalmaz.

- list
Çift bağlı bir liste gerçeklemesidir. Ögeler vector'dekinden farklı olarak, aralara da hızlıca eklenebilirler; ancak, rastgele erişim söz konusu değildir. Her öge için, ögenin kendi nesnelerine ek olarak, bellekten en azından bir çift gösterge de ayrılır. Buna rağmen, bilinen hiçbir list gerçeklemesi vector'ün hızlı olabilmek için yaptığı savurganlığı göstermez: bellekten her defasında yalnızca bir tane öge için yer ayrılır.

- deque
Adı, 'çift uçlu kuyruk' olarak çevrilebilecek 'double-ended queue'dan gelir ve 'dek' şeklinde okunur. İki uçlu vector gibidir: yeni ögeler topluluğun hem sonuna hem de başına hızlıca eklenebilirler. vector gibi, dizi erişim işlecini (operator[]) sunar; bellek kullanımında vector'den çok daha iyidir; ancak, nesneleri peş peşe tutma gibi bir zorunluluğu olmadığı için, C dizileri bekleyen işlevlerle kullanılamazlar.

- stack
Bir yığıt gerçeklemesidir. Ögeleri üst üste koyulmuş gibi düşünülebilecek bir topluluktur. Yalnızca en üstteki ögeyle işlem yapılabilir.

- queue
Bir kuyruk gerçeklemesidir. Ögeler kuyruğun sonuna eklenirler;
baş taraftan erişilirler ve çıkartılırlar.

- priority_queue
queue'nun ögelerine öncelik hakkı tanıyan türüdür. Ögeler kuyruğa önceliklerine göre eklenirler. Yüksek öncelikli ögeler düşük öncelikli ögelerden daha öne koyulurlar.

- map
İlişkili dizi (associative array) gerçeklemesidir. Ögelerine bir C dizisinde olduğu gibi, dizi erişim işleci ile erişilebilir. Bu erişimde C'den üstünlüğü, erişimin öge numarası ile kısıtlı
olmamasıdır. Ögelere herhangi bir türle, örneğin bir 'string'le erişilebilir. Her öge iki parçadan oluşur: ögenin adı (veya erişim anahtarı) ve değeri.

Böyle kullanıldığında bir sözlük veya çizelge gibi de düşünülebilir. Örneğin, telefon numaraları tutan ve numaralara kişilerin adlarıyla erişilen bir uygulamaya çok elverişlidir:

rehber["Ali"] = "123 4567";

yazıldığında "Ali" adlı ögesine "123 4567" değerini atar.

Ögeler, girildikleri sıradan bağımsız olarak, her zaman için küçükten büyüğe doğru sıralı olarak tutulurlar.

- multimap
map gibi çalışır; ek olarak, aynı ada sahip birden fazla ögenin varlığına da izin verir.

- set
map gibi, ögelerini belli bir sıralama kuralına uygun olarak tutan bir topluluktur. map'ten bir farkı, ögelerin ayrıca erişim anahtarı bulunmamasıdır; ögelerin değerleri, erişim anahtarı görevini de görürler. En uygun oldukları uygulamalar, ögelerin
her zaman için sıralı olmalarını gerektiren uygulamalardır.

- multiset
set gibi çalışır; ek olarak, aynı değerdeki ögeden birden fazla sayıda bulunmasına izin verir.

Yukarıdakilerden başka, tam olarak topluluk sayılmasalar da, yine de topluluk gibi kullanılmaya elverişli başka yapılar da vardır.

- string
Karakterleri bir arada tutmaya yarayan dizgi gerçeklemesidir.

- C dizileri
Bunlar da C++ algoritmalarıyla birlikte C++ toplulukları gibi
kullanılabilirler.

- valarray
Sayısal uygulamalara elverişli vector gibi düşünülebilir.

- bitset
Her bir ögesi bir bit olan (değeri ancak 0 veya 1 olabilen) bir topluluktur.

- hash_map
Geç önerildiği için standart kütüphanede yer alamamış olsa da her derleyici tarafından ek olarak verilen bir topluluktur. map gibi çalışır ama ögelerine ortalamada daha hızlı erişim sağlamak uğruna onları sırasız olarak tutar.


Erişiciler


Programcının sorunları çözerken kullandığı en etkin yöntemlerden birisi, parçalama yöntemidir. Büyük sorunlar küçük alt sorunlar olarak ayrılırlar ve teker teker çözülürler. Nesneleri bir topluluk içinde bir araya getiren bir program, doğal olarak sonradan o nesnelere erişmek ve üzerlerinde işlem yapmak isteyecektir.

Standart C++ kütüphanesi, nesneleri bir araya getirme ve o nesneler üzerinde işlem yapma işlerini birbirlerinden ustaca ayırmıştır. Bu ayrım sonucunda da ne toplulukların
algoritmalardan, ne de algoritmaların topluluklardan haberleri vardır; birbirlerinden bağımsız olarak çalışırlar. (Standart, bu ayrımın uygun olmadığı durumlarda istisnalar da sunar.)

Bu bağımsızlık, kullanıcılara standart kütüphane ile uyumlu olarak çalışan yeni topluluklar ve algoritmalar yazma olanağı sağlar. Sonuçta, belirli bazı koşullar yerine geldiği sürece, her topluluk her algoritmayla, her algoritma da her toplulukla
çalışabilir.

Topluluk ve algoritmaların birbirleriyle uyumlu olarak çalışmalarını sağlayan yapılara 'erişici' (iterator) denir.
Algoritmalar da erişicilerle çalışacak şekilde tasarlandıkları için, üzerlerinde çalıştıkları toplulukların iç yapılarını bilmek zorunda kalmazlar.

Topluluklar ögelerine erişimi kendilerine özgü erişiciler aracılığıyla sağlarlar. Her topluluk, bu erişimi sağlayan erişici türlerini kendi içinde tanımlar. Her topluluk dört erişici türü tanımlasa da, programlarda çoğunlukla ilk ikisi kullanılır:

iterator
const_iterator
reverse_iterator
const_reverse_iterator

Erişiciler göstergelerin bir genellemesidir. Ancak; hangi türden ve tam olarak hangi topluluk için çalıştıkları gibi bilgileri de tutabildikleri için, genelde göstergelerden daha karmaşıktırlar.

Nesnelere erişmek için göstergelere 'operator*' veya 'operator->' işleçlerini uygularız.

struct BirYapi
{
int birOge;
};

void foo(int * sayi, BirYapi * yapi)
{
*sayi = yapi->birOge;
}

foo işlevi, nesnelere gösterge kullanarak nasıl erişildiğini gösteriyor. 'sayi' göstergesinin gösterdiği tamsayıya 'operator*' ile, 'yapi' göstergesinin gösterdiği nesnenin bir ögesine de 'operator->' ile erişiyoruz. Topluluk erişicileri de gösterge gibi çalışırlar ve gösterdikleri ögelere bu iki işleçle erişim sağlarlar.

Yine göstergelerde olduğu gibi, erişiciler bir önceki ve bir sonraki ögeyi göstermek için de 'operator--' ve 'operator++' işleçlerini desteklerler.

Programlarımızı yazarken erişicilerin iç yapılarını bilmek zorunda değilizdir. Tek bilmemiz gereken, her erişicinin belli bir anda bir ögeyi gösterdiği ve o ögeye erişim sağladığıdır

[Neutralizer]

paylaşım için tşkrlr