Bu yazıda vector'ün biraz daha ileri düzey kabul edilebilecek olan olanaklarına değinmek istiyorum. Temel olanaklarını görmek için bir önceki yazıma bakabilirsiniz.
Ben vector şablonundan bu güne kadar çoğunlukla nesneleri bir araya getirmek ve baştan sona bütün nesneleri bir şekilde kullanmak için yararlandım. vector'ü, içine yerleştirdiğim nesnelerde arama yapmak için hemen hemen hiç kullanmadım. Bu iş için genellikle ögelerini zaten belirli bir sırada sıralanmış olarak tutan set, map, hash_map gibi toplulukları kullandım. Yine de, bir topluluğun ögeleri içinde arama yapmak doğal bir işlem olduğu için, vector'ün bu amaçla nasıl kullanıldığını da göstermek istiyorum.
Daha önce de dediğim gibi, vector'ün ögeleri, programda girildikleri sırada tutulurlar. Bu yüzden, istediğimiz ögeyi bulmak için baştan sona doğru bütün ögelere bakmaktan başka çaremiz yoktur. Böyle sırayla aramak (linear search), bütün ögelere bakmayı gerektirdiği için yavaş olacağından, kalabalık vector topluluklarına uygun değildir. Eğer kalabalık bir topluluk kullanılacaksa ve ögeler arama yapmadan önce sıralanmayacaklarsa, vector bu iş için uygun değildir.
Standart kütüphane, birçok arama algoritması sunar. Konudan fazla ayrılmamak için, ben bu yazıda yalnızca 'find' işlevini kullanacağım.
Bu program, girişten gelen sayıları kullanarak bir topluluk oluşturuyor ve o topluluğun icinde 7 değerini arıyor. Girişi sonlandırmak için bir önceki yazıda da değindiğim gibi, yine Ctrl-Z veya Ctrl-D tuşlarını kullanmanız gerekebilir.
#include <vector>
#include <iostream>
using namespace std;
typedef vector<int> Sayilar;
Sayilar giristenOku()
{
Sayilar sayilar;
int sayi = 0;
while (cin >> sayi)
{
sayilar.push_back(sayi);
}
return sayilar;
}
int main()
{
int const bulunacakDeger = 7;
cout << "Giristen tamsayilar okuyacak\n"
<< "ve aralarinda " << bulunacakDeger
<< " olup olmadigini soyleyecegim...\n";
Sayilar const sayilar = giristenOku();
/*
'find' algoritmasi, kendisine verilen iki
erisici ile belirlenen aralik icerisinde
yine kendisine verilen degeri arar.
Bu algoritma da, ikinci erisiciyi hicbir
ogeye erismek icin kullanmaz. Cunku, ikinci
erisici araligin disindadir. Hatta o erisici
cogu durumda topluluk ogelerinin sonuncusundan
daha sonrayi gosterdigi icin, gosterdigi
gecerli bir nesne bile olmayabilir.
Aranan nesneyi buldugunda o nesneyi gosteren
bir erisiciyi, bulamadiginda ise o ikinci ozel
erisiciyi (bu ornekte sayilar.end()) dondurur.
Yazi icinde de soyledigim gibi, standart
topluluklar, erisici turlerini kendi iclerinde
tanimlarlar.
find algoritmasinin donus turu, calistigi
erisicilerle ayni turdendir. 'sayilar' toplulugu
programin bu noktasinda sabit (const) bir
topluluk oldugu icin, 'begin' ve 'end' islevleri
onun const_iterator turunden olan erisiciler
dondururler.
Dolayisiyla, find algoritmasinin donus turu de
'const_iterator'dir.
*/
Sayilar::const_iterator const sonuc =
find(sayilar.begin(), sayilar.end(), bulunacakDeger);
if (sonuc == sayilar.end())
{
cout << "Sayilarin arasinda "
<< bulunacakDeger << " yok\n";
}
else
{
cout << "Buldum: " << *sonuc << '\n';
}
return 0;
}
Ögeleri normalde sıralı olmayan vector, kalabalık olduğunda içinde arama yapmaya elverişli olmasa da; ögeleri bir kere sıralandıktan sonra en hızlı arama algoritması olan ikili arama (binary search) için çok elverişli hale gelir.
Eğer ögelerin bir kere baştan girildikleri ve ondan sonra bir çok kere kullanıldıkları bir toplulukla ilgileniyorsak; vector'ü ikili arama algoritmasıyla çok etkin bir şekilde kullanabiliriz. Standart kütüphanede vector erişiceleriyle birlikte kullanıldığında ikili arama algoritması olarak çalışan işlevin adı lower_bound'dur. Bu işlevin arkadaşları olan upper_bound, equal_range ve binary_search algoritmaları hakkında da bilgi toplamak isteyebilirsiniz.
Aşağıdaki program, komut satırında ona bildirilen bir sözcüğü, girişinden aldığı sözcüklerin (string) içinde arar:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
typedef vector<string> Sozcukler;
Sozcukler giristenOku()
{
Sozcukler sozcukler;
string sozcuk;
while (cin >> sozcuk)
{
sozcukler.push_back(sozcuk);
}
return sozcukler;
}
void okuSiralaAra(string const & aranacakSozcuk)
{
// Giristeki butun sozcukleri okuyoruz
Sozcukler sozcukler = giristenOku();
// Siraliyoruz
sort(sozcukler.begin(), sozcukler.end());
cout << "Su sozcukleri okudum ve soyle siraladim: ";
/*
Bir araliktaki nesnelerin hepsini cikisa gondermek
icin 'copy' algoritmasi da kullanilabilir. Bu, C++'in
standart kutuphanesine ve onun yontemlerine yabanci
olanlar icin bastan oldukca karmasik gelebilir.
Yine de hic olmazsa "cikisa gondermenin" aslinda
"cikisa kopyalamak" olarak da algilanabileceginin
bir ornegi olarak kabul edebilirsiniz.
*/
copy(sozcukler.begin(), sozcukler.end(),
ostream_iterator<string>(cout, " "));
cout << '\n';
/*
lower_bound algoritmasi, rastgele erisim
saglayan erisicilerle kullanildiginda ikili
arama algoritmasini uygular.
Kendisine bildirilen nesneyle ayni degere sahip
olan ilk nesneyi, yine kendisine bildirilen
aralik icinde arar.
lower_bound, aradigi nesnenin aralikta siralamayi
bozmayacak bir sekilde bulunmasi gereken noktayi
dondurur. Yani nesne aralikta bulunmasa bile,
yasal bir erisici dondurebilir.
Onun icin, lower_bound'u bu sekilde
kullandigimizda, dondurdugu erisicinin
gercekten aradigimiz nesneyi gosterip
gostermedigine bakmamiz gerekir.
*/
Sozcukler::iterator const sonuc =
lower_bound(sozcukler.begin(),
sozcukler.end(),
aranacakSozcuk);
if ((sonuc != sozcukler.end()) &&
*sonuc == aranacakSozcuk)
{
/*
distance algoritmasi, kendisine verilen iki
erisici arasinda kac adim bulundugunu verir.
vector erisicileri gibi rastgele erisim saglayan
topluluk erisicilerine uygulandiginda, bu
algoritma cok hizli calisir.
*/
cout << "En az bir tane "
<< aranacakSozcuk << " buldum! "
<< distance(sozcukler.begin(), sonuc) + 1
<< ". sirada duruyor\n";
}
else
{
cout << aranacakSozcuk << " sozcugunu bulamadim\n";
}
}
int main(int argc, char * argv[])
{
if (argc != 2)
{
cerr << "Lutfen hangi sozcugun aranacagini bildirin\n"
<< "Dogru kullanim:\n"
<< " " << argv[0] << " <sozcuk>\n";
return 1;
}
okuSiralaAra(argv[1]);
return 0;
}
vector, ögelerine rastgele erişimi sabit zamanda sağlayabilmek için, onları kendi içinde barındırdığı birleşik bir bellek alanında tutar (bir C dizisi gibi). Bu sayede, vector ögelerini C dizileriyle çalışan işlevlerle de kullanabiliriz:
#include <vector>
#include <iostream>
#include <string>
using namespace std;
/*
Her bir ogrencinin bir adi, bir de yasi var.
*/
class Ogrenci
{
string ad_;
int yas_;
friend ostream & operator<< (ostream &, Ogrenci const &);
public:
Ogrenci(string const & ad, int yas)
:
ad_(ad),
yas_(yas)
{}
};
/*
Siradan bir yazdirma islevi
*/
ostream & operator<< (ostream & cikis, Ogrenci const & ogrenci)
{
return cikis << ogrenci.yas_ << " yasinda bir "
<< ogrenci.ad_;
}
/*
Bu islev, parametre olarak bir vector<Ogrenci> degil,
siradan bir C dizisi aliyor.
C dizisini tanimlayan iki parametre var:
1) Dizinin basini belirten bir gosterge
2) Dizideki oge adedini belirten bir sayi
*/
void ogrencileriTanit(Ogrenci const * dizi, size_t adet)
{
for (size_t i = 0; i != adet; ++i)
{
cout << i << ": " << dizi[i] << '\n';
}
}
int main()
{
// Bos bir topluluk olusturuyoruz ...
vector<Ogrenci> ogrenciler;
// Icini dolduruyoruz ...
ogrenciler.push_back(Ogrenci("Ali", 10));
ogrenciler.push_back(Ogrenci("Veli", 11));
ogrenciler.push_back(Ogrenci("Zilli", 12));
/*
Bu vector'u asagida C dizileriyle calisan bir
isleve gonderecegimiz icin, icindeki ogelere
bir C dizisi gibi erisim saglayan
&ogrenciler[0]
yontemini kullaniyoruz.
Dikkat ederseniz ogrenciler[0], toplulugun
birinci ogesidir. Ogelerin bellekte ardarda
bulunduklarinin garanti edildigini bildigimiz
icin, o birinci ogenin adresini alarak
bir C dizisi elde ederiz.
*/
Ogrenci const * diziBasi = &ogrenciler[0];
/*
Simdi diziBasi, birinci ogeyi gosteriyor
ve ogeler art ardalar... Bu zaten C dizilerinin
tanimidir.
Oge adedini de 'size' ile elde ediyoruz:
*/
ogrencileriTanit(diziBasi, ogrenciler.size());
return 0;
}
Dikkat ederseniz, 'vector'ü kullanırken bellek yönetimiyle hiç ilgilenmedik. Yukarıdaki programda hiç bellek kaygımız olmadan, push_back işlevini çağırarak nesnelerimizi vector'ün sonuna ekledik. Çünkü, içinde barındırdığı nesnelerin nerelere yerleştirilecekleri ve ne zaman ortadan kaldırılacakları vector'ün kendi sorumluluğundadır. vector bizi bu konular üstünde zaman harcamaktan ve hata yapmaktan kurtarır.
vector, baştan bir miktar bellek ayırır ve eklenecek ögeleri o bellek alanı içinde kurar. Belli bir noktada o bellek tükendiğinde daha büyük bir bellek alanı ayırır, eski ögeleri sırayla yeni belleğe kopyalar ve eski belleği geri verir. Araya eklenen ögeler için çoğu zaman bellek ayırmaya gerek olmaz. Yine de, eklenen ögeden sonraki bütün ögelerin bir hane kaydırılmaları gerekeceği için, bu işlem de sona öge eklemekten çok daha pahalıdır.
Bellek ayırmak genelde pahalı bir iş olduğu için, vector akıllı davranarak her defasında daha büyük bir bellek alanı ayırır. Çok kullanılan bir yöntem, eski bellek alanının iki katı kadar yeni bellek alanı ayırmaktır. Dolayısıyla başlangıçta tek bir öge için yeri olan bir vector'ün ayıracağı bellek alanları sırasıyla 2, 4, 8, vs. gibi olacaktır. Bu değerleri yalnızca örnek olarak veriyorum; baştan ve sonradan ne kadar bellek ayrıdığı vector'ün kendi işidir. Zaten genelde bunları bilmemiz de beklenmez.
Yine de, vector'ün toplam kaç tane öge tutacağını baştan bildiğimiz durumlarda, ondan o kadar öge için yer ayırmasını isteyebiliriz. Böyle yaparak, vector'ün olası birçok sayıda bellek ayırmasını ve ögeleri gereksiz yere eski bellek alanından yeni bellek alanına kopyalamasını engelleyebiliriz. Bu, özellikle ögelerinin kopyalanmaları uzun zaman alan vector'lerde yararlı olabilir.
Ögeler için yer ayırmasını vector'e 'reserve' işlevi ile bildiririz. Ancak, yukarıda da belirtmeye çalıştığım gibi, bunu yapmak zorunda değilizdir. Doğrudan push_back (veya 'insert') işlevlerini kullanarak ögelerimizi ekleyebiliriz.
'capacity' işlevi ise vector'ün belli bir anda kaç öge kapasitesi olduğunu bildirir.
Bu iki işlevin kullanımlarını gösteren bir program da şöyle yazılabilir:
#include <vector>
#include <iostream>
using namespace std;
size_t const ogeAdedi = 10000;
int main()
{
// Bir gercel sayi toplulugu
vector<double> gerceller;
cout << "Baslangictaki kapasite: "
<< gerceller.capacity() << '\n';
/*
Biraz sonra 'ogeAdedi' adet oge eklenecegini
bildigimiz icin, vector'un gereksiz yere
bellek ayirmasini ve oge kopyalamasini
engellemek icin kapasitesini arttiriyoruz.
*/
gerceller.reserve(ogeAdedi);
cout << "Yeni kapasite: "
<< gerceller.capacity() << '\n';
for (size_t i = 0; i != ogeAdedi; ++i)
{
double const sayi = static_cast<double>(i) / 10;
gerceller.push_back(sayi);
}
// 'front' en bastaki, 'back' de en sondaki ogeyi verir
cout << "Bastaki ve sondaki ogeler: "
<< gerceller.front() << ' '
<< gerceller.back() << '\n';
return 0;
}
vector'ün bellek kullanımıyla ilgili ilginç başka bir bilgi de, öge adedi düştüğü halde elinde tuttuğu belleği küçültmeyeceğidir. Bir anlamda vector, yaşamı süresince ihtiyaç duyduğu en büyük bellek ne kadarsa, hep o kadar bellek tutacaktır.
Hem bu özelliğini, hem vector'den öge silmek için kullanılan 'erase' işlevini, hem de vector'ün erişicilerinin nasıl açıkça oluşturulacağını gösteren bir örneğe geçiyorum.
vector'ün ögelerini gösteren bazı erişiciler, vector üzerinde yapılan bazı işlemler sonucunda geçersiz hale gelirler. vector'den öge çıkartmak, o ögeyi ve o ögeden sonraki bütün ögeleri gösteren bütün erişicileri geçersiz hale getirir. Bunun nedeni, o ögeden sonraki bütün ögelerin bellekte bir hane kaydırılmalarının gerekmesidir.
Aşağıdaki program, erişici kullanırken bu noktaya da dikkat ediyor:
#include <vector>
#include <iostream>
using namespace std;
typedef vector<int> Sayilar;
/*
Topluluklar, erisicilerinin turlerini de
kendileri tanimlarlar.
Butun standart topluluklarin ogelerinde degisiklik
yapmaya izin veren erisicilerine 'iterator', izin
vermeyenlerine 'const_iterator' denir. Duruma gore,
bu iki erisiciden birisi kullanilir.
Bu ornekteki vector<int>'in bu iki tur erisicisini
soyle kullanabiliriz:
vector<int>::iterator erisici;
vector<int>::const_iterator sabitErisici;
Ancak cogu zaman, onlari programda bir cok yerde
bu karmasik yazimlariyla kullanmak yerine, yine
'typedef'le adlandirma yontemini kullaniriz.
Yine kodun okunmasini kolaylastiran bir adim olarak,
bu iki ture de yeni adlar veriyorum:
*/
typedef Sayilar::iterator SayiErisici;
typedef Sayilar::const_iterator SayiSabitErisici;
Sayilar olustur(size_t adet)
{
Sayilar sayilar;
for (size_t i = 0; i != adet; ++i)
{
int const sayi = i % 10;
sayilar.push_back(sayi);
}
return sayilar;
}
void bilgiVer(Sayilar const & sayilar)
{
cout << "Toplam oge: " << sayilar.size() << '\n'
<< "Kapasite : " << sayilar.capacity() << '\n'
<< "Ogeler : ";
/*
Bilgi verdigimiz bu islev icinde, 'sayilar' parametresi
dogal olarak sabit bir referans olarak alinmis. Cunku,
bu islevde bilgisini verdigimiz bu vector'de degisiklik
yapmiyoruz.
'begin' islevi, sabit bir topluluk referansi ile
kullanildiginda const_iterator turunde bir erisici
dondurur. O yuzden, burada SayiErisici (aslinda iterator)
degil, SayiSabitErisici (aslinda const_iterator)
kullanmamiz gerekir.
*/
for (SayiSabitErisici simdiki = sayilar.begin();
simdiki != sayilar.end(); ++simdiki)
{
cout << *simdiki << ' ';
}
cout << '\n';
}
/*
Bu islev kendisine verilen vector'de degisiklik yapacagi
icin, onu sabit olmayan bir referans olarak aliyor.
*/
void yedileriCikart(Sayilar & sayilar)
{
SayiErisici simdiki = sayilar.begin();
while (simdiki != sayilar.end())
{
if (*simdiki == 7)
{
/*
vector'un 'erase' islevi, kendisine verilen
erisicinin gosterdigi ogeyi topluluktan
cikartir.
Ogesi topluluktan cikartilan bir erisici
artik gecersiz sayildigi icin (burada
'simdiki'), artik o erisiciyi kullanamayiz.
Ornegin, bir sonraki ogeye gecmek icin
artik
++simdiki;
yazamayiz.
Bu konuda yardimci olmak icin 'erase',
topluluktaki bir sonraki ogeyi gosteren bir
erisici dondurur. Biz de artik gecersiz olan
erisicimize 'erase'in yeni dondurdugu degeri
atariz:
*/
simdiki = sayilar.erase(simdiki);
}
else
{
++simdiki;
}
}
}
int main()
{
size_t const ogeAdedi = 30;
Sayilar sayilar = olustur(ogeAdedi);
bilgiVer(sayilar);
cout << '\n';
yedileriCikart(sayilar);
bilgiVer(sayilar);
return 0;
}
Bu yazıda vector'ün çok daha az kullanıldıklarını düşündüğüm arama, silme, C dizileri gibi kullanma ve hızlı bellek ayırma gibi olanaklarına değindim. Umarım bu ve bir önceki yazım C++ programlarınızda C dizileri yerine vector kullanmaya başlamanız için yeterli temel oluşturmuştur.
Bundan sonraki yazılarımda başka standart topluluklarla ilgili örnekler vermek istiyorum.
Yazının taslakları üzerinde yaptıkları yararlı eleştirilerden dolayı Volkan Uzun'a ve Ersin Er'e teşekkür ederim. Daha önceden gözardı ettiğim bir çok önemli ayrıntıyı onların uyarılarından sonra ekledim.