std::vector ileri düzey işlemleri

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.

Arama

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'ün C işlevleriyle kullanılması

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;
}

Bellek kullanımı

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;
}

Özet

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.

Teşekkür

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.


Ali Çehreli - acehreli@yahoo.com