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

Çoğu progr*** 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 progr*** 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.
Daha önce de değindiğim gibi, programlarda kullanılan bazı işlevler bir grup nesne üzerinde çalışırlar. Bir grup nesneyi bir işleve göndermek için C dünyasında benimsenen yöntem, işleve dizinin ilk ögesini gösteren bir gösterge göndermektir. Onun yanında bir de dizideki öge adedini gösteren bir parametre kullanılınca, bütün nesneler belirlenmiş olurlar.

Örneğin, standart C kütüphanesinin qsort işlevi, dizideki nesnelerin başlangıcını ve dizideki nesne adedini böyle iki parametre ile alır (Konuyla ilgisi olmayan parametreleri
göstermiyorum):

void qsort(void * bas, size_t adet, /* ... */);

Ne var ki; aynı bilgiyi birisi dizinin başını, diğeri de dizinin son ögesinden bir sonrayı gösteren iki gösterge ile de verebiliriz. Eğer qsort bu ikinci yöntemle tasarlanmış olsaydı, parametreleri şöyle olabilirdi:

void qsort(void * bas, void * son, /* ... */);

Standart C++ kütüphanesi, işte bu ikinci yöntemi benimsemiştir.
Bir grup nesne alan işlevler, nesnelerin başını ve sonunu böyle iki erişici ile öğrenirler. Örneğin, qsort'un C++'taki karşılığı olan sort işlevinin bildirimi şöyledir (Konuyla ilgili olmayan parametreleri burada da göstermiyorum):

template
void sort(Erisici bas, Erisici son, /* ... */);

'bas' erişicisi ilk ögeyi gösterir. 'son' erişicisi ise üzerinde işlem yapılacak ögelerin sonuncusundan bir sonraki ögeyi gösterir. Çoğu durumda, sonuncu ögeden sonra geçerli bir öge bulunmadığı için, 'son' erişici hiçbir zaman bir ögeye erişmek için kullanılmaz.

Kendisine verilen bir grup ögeyi standart çıkışa gönderen bir işlevi bu yönteme uygun olarak şöyle yazabiliriz:

void cikisaYazdir(Erisici bas, Erisici son)
{
for ( ; bas != son; ++bas)
{
cout << *bas;
}
}


Döngü kontrol ifadesinde C'den alışık olduğumuz '<' işlecinin değil, '!=' işlecinin kullanıldığına dikkat edin. Bu da C++ standardının C'den farklıca benimsediği bir yöntemdir. Bunun nedeni, 'operator<' işlecinin, yani bir sıralama ilişkisinin her erişici türüne uygun olmamasıdır.

Topluluk ögesi olma koşulları


Her ne kadar toplulukların 'türden bağımsız' olduklarını söylesem de aslında standart topluluklarla birlikte kullanılacak türlerin sağlamaları gereken bazı koşullar vardır. Bu koşulları, Nicolai Josuttis'in C++ standart kütüphanesini çok güzel bir şekilde anlattığı 'The C++ Standard Library' kitabına bakarak yazıyorum:

1) Kopyalanabilirlik: Ögelerin kopyalanabilir olmaları gerekir. Bir ögenin her iki kopyası, program içinde birbirlerine eşit olarak kabul edilebilmeli ve eşit davranış göstermelidir. Bir başka deyişle, ögelerin kopyalama kurucusu, kopyalama işleminden bekleneceği gibi çalışmalıdır.

Standartta bulunan tek akıllı gösterge olan auto_ptr, en azından bu koşulu sağlamadığı için standart topluluk ögesi olarak kullanılamaz.

2) Atanabilirlik: Ögelere kendi türlerinden başka bir ögenin değeri atanabilmelidir. Bir başka deyişle, ögeler operator=işlecini desteklemelidirler.

3) Bozulabilirlik: Ögelerin temizlikleri; zaten olması gerektiği gibi, bozucu işlevlerinde yapılabilmelidir. Bunun için; bozucu işlev genel arayüzde tanımlı, yani çağrılabilir olmalıdır.

Bütün bu koşullar, zaten bütün temel türler ve kullanıcı türleri için doğal olarak sağlanırlar. Kullanıcı türleri için kopyalayıcı, atama işleci ve bozucunun yazılmalarının gerektiği durumlarda ise; o işlevlerin beklendikleri gibi davranmalarını sağlamak, topluluk ögesi olma koşullarını yerine getirmek için yeterlidir.

Yukarıdakilere ek olarak, bazı topluluklar için şu işlevlerin varlığı da gerekebilir:

- Varsayılan kurucu (default constructor)

- Eşitlik karşılaştırması işleci (operator==)

- Sıra karşılaştırması işleci (operator<)

Toplulukları anlamak için gereken bir başka bilgi de, toplulukların ögelerini kopyalayarak sakladıklarıdır. Standart topluluklar, her zaman için ögelerin kendilerine ait kopyaları
üzerinde çalışırlar. O ögeleri gerektikleri zaman kurar ve gerektikleri zaman bozarlar.


Şablonlarla (template) ilgili küçük bir hatırlatma

Yazının bundan sonrasında şablonların en azından ne olduklarının bilindiğini varsayıyorum. Şimdilik, şablonların türden bağımsız olarak yazılmış sınıflar ve işlevler olduklarını düşünebilirsiniz.

Türden bağımsız olarak yazılmış sınıflara 'sınıf şablonu' (class template), işlevlere de 'işlev şablonu' (function template) denir.

Küçük bir şablon örneğini

http://ceviz.net/index.php?case=article&id=170

adresinde bulabilirsiniz. O yazının eksik bıraktığı ek bir bilgiyi de şurada okuyabilirsiniz:

http://forum.ceviz.net/showthread.php?s=&threadid=3992


Sınıf şablonlarına parametrelerinin açıkça bildirilmeleri gerekir
----------------------------------------------------------------
Sınıf şablonlarının işlev şablonlarından bir farkı, şablon parametrelerinin derleyici tarafından çıkarsanamamalarıdır. Sınıf şablonlarının hangi türle çalışacaklarının programcı tarafından açıkça bildirilmesi gerekir.

Bunun nasıl yapıldığını görmek için, küçük bir sınıf şablonu örneği vermek istiyorum. Bütün işi, herhangi türden iki nesneyi barındırmak ve istendiği zaman o iki nesneyi parantez içinde ve aralarında virgül olacak şekilde yazdırmak olan bir sınıf şablonu olsun:
#include
#include

using namespace std;

template
class Cift
{
Tur birinci_;
Tur ikinci_;

public:

Cift(Tur const & birinci, Tur const & ikinci)
:
birinci_(birinci),
ikinci_(ikinci)
{}

void yazdir(ostream & cikis) const
{
cikis << '(' << birinci_ << ',' << ikinci_ << ')';
}
};

int main()
{
Cift tamsayiCifti(1, 2);
tamsayiCifti.yazdir(cout);
cout << '
';

Cift dizgiCifti("Ali", "Veli");
dizgiCifti.yazdir(cout);
cout << ' ';

return 0;
}



'main'in içindeki kullanımlardan da görüldüğü gibi, sınıf şablonlarının hangi türlerle çalışacaklarını açılı parantezler arasında bildirmemiz gerekir. Bu programa bakarak, Cift
şablonunun bir kere 'int' türü ile, bir kere de 'string' türü ile kullanıldığını söyleyebiliriz.

Standart topluluklar da sınıf şablonu olarak gerçeklendikleri için, hangi türden nesneler barındıracaklarını açıkça bildirmek gerekir. Bazı topluluklar yalnızca tek türle çalıştıkları için, tek bir şablon parametresi bildirmek yeterlidir. Örneğin,

vector intToplulugu;
list dizgiToplulugu;

satırlarından birincisi, içinde 'int' nesneler barındıracak olan ve adı 'intToplulugu' olan bir vector topluluğunu tanımlar.
İkinci satır ise içinde 'string' nesneler barındıran bir bağlı liste topluluğu tanımlar.

map ve hash_map iki türle çalışırlar. Birinci tür nesnelerin adlarının türünü; ikinci tür ise, nesnelerin değerlerinin türünü belirler. Örneğin, yukarıda kısaca değinilen 'rehber'
topluluğunun tanımı şöyle olabilirdi:

map rehber;

Her iki şablon parametresinin de 'string' olması, bu örnekteki 'rehber'in ögelerinin hem adlarının hem de değerlerinin 'string' türünde olduklarını gösterir.

Özet

Bu yazıda standart C++ topluluklarını (generic containers) ve onların ögelerine erişim sağlayan erişicileri (iterator) çok kısaca tanıtmaya çalıştım.
_________________