Using Associative Containers

Kategori: C++ , 12 Kasım 2019 , JanFranco


Şuana kadar dizileri, vektörleri, listeleri vs. gördük. Bu yapılar sequentail yapılardır. Dizili olurlar, sıralı olurlar. Örneğin dizilerde her objenin bir indexi vardır fakat bir obje sildiğimizde, diğer objeler bir geri kaydırılır ve sildiğimiz objenin indexi artık başka bir objeyi tarif etmektedir. Bu yapıları oldukça sık kullansak da ve işimize yarasa da yavaş çalışırlar. Örneğin 42 sayısını bir dizide aratacağımız zaman en baştan sona kadar aratmamız gerekir. Sequential yapılar yerine daha etkili yapıları kullanabiliriz: associative containers

Associative yani ilişkisel yapılarda anahtar - değer (key - value) ilişkisi vardır. Diziye veya yapıya bir obje eklediğimizde bu objeye otomatik olarak bir key atanır. Dizide işlemler yapacağımız zaman (silme, arama gibi) bu anahtar değerleri kullanılır. C++'da bu yapıları kütüphanesinde hazır olarak bulabiliriz.

Sequential ve associative yapılar arasında iki temel fark vardır. Birincisi, sequential yapılarda index değerleri vardır ve bu değerler integer yani tam sayı olmalıdır. İlişkisel yapılarda anahtar değeri vardır ve bu değer tam sayı, string hatta obje bile olabilir. Bir diğer fark ise düzenli bir yapıda olmadıklarından, sequential yapılar için yazılmış algoritmalar bu yapılarda kullanılamazlar. Bir örnek yapalım:


#include <iostream>
#include <map>

using namespace std;

int main()
{
    string s;
    map<string, int> counters;

    while(cin >> s){
        if(s == "end"){
            break;
        }
        ++counters[s];
    }

    for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); it++){
        cout << it->first << "\t" << it->second << endl;
    }

    return 0;
}
Burada ilk olarak bir map oluşturduk. Değerlerin string, anahtarların int tipinde saklanacağını söyledik. counters[s] diyerek aldığımız değerleri counters'a attık. ++counters diyerek default olarak 0 olan anahtar değerini her seferinde bir artırdık. Daha sonra da it->first ve it->second diyerek sırasıyla değerleri ve anahtarları bastırdık.

Örneği biraz değiştirelim. Kelime girmek yerine cümleler girelim. Daha önce yazdığımız split fonksiyonunu kullanarak cümleleri kelimelere ayıralım. Bu kelimelerin hangi satırlarda geçtiğini bulalım:


#include <map>
#include <vector>
#include <iostream>

using namespace std;

vector<string> split(const string& s)
{
    vector<string> ret;
    typedef string::size_type string_size;
    string_size i = 0;

    while(i != s.size()) {
        while (i != s.size() && isspace(s[i]))
            i++;
        string_size j = i;
        while (j != s.size() && !isspace(s[j]))
            j++;
        if (i != j) {
            ret.push_back(s.substr(i, j - i));
            i = j;
        }
    }
    return ret;
}

map<string, vector<int> > xref(istream& in, vector<string> find_words(const string&) = split)
{
    string line;
    int lineNumber = 0;
    map<string, vector<int> > ret;

    while(getline(in, line)){
        if(line == "end"){
            break;
        }
        lineNumber++;
        vector<string> words = find_words(line);
        for(vector<string>::const_iterator it = words.begin(); it != words.end(); it++){
            ret[*it].push_back(lineNumber);
        }
    }

    return ret;
}

int main()
{
    map<string, vector<int> > ret = xref(cin);

    for(map<string, vector<int> >::const_iterator it = ret.begin(); it != ret.end(); it++){
        cout << it->first << " occurs on line(s): ";
        vector<int>::const_iterator line_it = it->second.begin();
        cout << *line_it;

        line_it++;

        while(line_it != it->second.end()){
            cout << ", " << *line_it;
            line_it++;
        }

        cout << endl;
    }

    return 0;
}
Fonksiyonlarda daha önce görmediğimiz bir olayı görüyoruz: default parameter. xref() fonksiyonun ikinci parametresinde, vektöre bir fonksiyon atadık. Bu atama işlemini parametre tanımladığımız kısımda, parantezlerin arasında yaptık. Bu durumda xref() fonksiyonu tek argüman ile çalışabilir. İkinci bir argüman gönderilmedikçe de ikinci parametrenin değeri split olarak kalır. Bu yeni özelliğimizin dışında xref() fonksiyonu while döngüsü ile sürekli satırları okuyor. Her adımda lineNumber değeri bir artıyor ve her adımda split fonksiyonu ile kelimeleri alıyoruz. lineNumber değerleri vektöre atılıyor. Bu vektör key, kelimeler ise value. main() fonksiyonunda da ilk olarak değeri yani kelimeyi yazıyoruz, sonrasında iterator ile key olan vektörde gezinerek kelimelerin hangi satırlarda geçtiğini yazıyoruz.


Sonraki Yazı: Writing Generic Functions
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın