Using Sequential Containers and Analyzing Strings

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


Daha önceden yapmış olduğumuz öğrenci not programında, öğrencilerileri final notlarına göre sınıflandıralım. Ortalaması 60 altındaki öğrenciler başarısız olarak sınıflandırılsın. Hemen bunun için bir fonksiyon oluşturalım:


bool fgrade(const Student_info& s){
    return grade(s) < 60;
}
Öğrencilerin isimlerini notlarını vs. değiştirmeyeceğiz. Bu nedenle parametrenin başına const yazdık. Ayrıca bütün structın kopyalanmasını istemiyoruz. Bu nedenle referansını gönderdik. Şimdi öğrenci vektörünü alan ve öğrencileri sınıflandıran bir fonksiyon yazalım:


// first try
vector<Student_info> extractFails(vector<Student_info>& students){
    vector<Student_info> fails, pass;
    for(vector<Student_info>::size_type i=0; i != students.size(); i++){
	if(fgrade(students[i]))
	    fail.push_back(students[i]);
    	else
	    pass.push_back(students[i]);
    }   
    students = pass;
    return fail;
}
İlk olarak fails ve pass adında iki vektör oluşturduk. for döngüsü ile öğrencilerde gezindik ve başarıları bir vektöre başarızları bir vektöre attık. Başarısızları return ettik, başarılı öğrencilerin bulunduğu vektörü students vektörüne eşitledik. students vektörü referans olarak iletildiği için, fonksiyonda yaptığımız değişiklikler, fonksiyon dışında da geçerli. Bu bizim ilk yaklaşımımızdı. Burada bir sıkıntı mevcut, programımız çok fazla yer yiyor. Aynı anda hem öğrenci vektörü, hem başarısızlar, hem başarılılar oldukça maliyetli. Bunu gidermeyi deneyelim, başarılılar vektörünü hiç kullanmayalım. Başarısızları bir vektöre atalım, başarılılar aynı öğrenciler vektöründe kalsın. Başarısızları öğrenciler vektöründen silelim:


// second try
vector<Student_info> extract_fails(vector<Student_info>& students){
    vector<Student_info> fail;
    vector<Student_info>::size_type i = 0;
    while (i != students.size()) {
	if (fgrade(students[i])) {
	    fail.push_back(students[i]};
	    students.erase(students.begin() + i);
	} else
	    ++i;
    }
    return fail;
}
Burada erase() methodunu kullandık. Bu method dışında gözümüze çarpan ilk şey, i değişkeninin sadece else bloğunda artırılması. Bunun sebebi şudur, vektörden bir eleman silindiğinde, tüm elemanlar bir sola kaydırılarak, sildiğimiz elemanın yeri doldurulur. Yani i = 3 adımında bir eleman siliyorsak ve bir sonraki eleman 4. indexteyse, o eleman 3. indexe kaydırılır. Eğer bu aşamada i değişkenini bir artırırsak 4. indexteki elemana ulaşacağız fakat o eleman artık 3. indexte. Bu nedenle o elemanı kaçıracağız.

Her veri yapısı indexlerle çalışmaz. Bu methodda index ile çalışmıyor. Bu nedenle başlangıç objesi + index argümanı ile eleman siliyoruz. students.begin() dediğimizde, bir iter objesi return ediliyor. Iteratorlar bir STL containerların bellekteki yerlerini göstermede kullanılırlar. STL açılımı Standard Template Library'dir. Bu kütüphanede stackler, listeler, diziler gibi veri yapıları bulunur. Şimdi öğrencilerde iterator aracılığı ile gezinelim:


// third try
vector<Student_info> extract_fails(vector<Student_info>& students){
    vector<Student_info> fail;
    vector<Student_info>::iterator iter = students.begin();
    while (iter != students.end()) {
	if (fgrade(*iter)) {
	    fail.push_back(*iter);
	    iter = students.erase(iter);
	} else
	    ++iter;
    }
    return fail;
}
Burada *iter diyerek objeyi almış olduk. iter objesi, listedeki objeleri göstermekte. *iter diyerek dereference işlemi yapmış olduk yani objenin kendisini aldık. Bu fonksiyonu 3. kez yazdık. Ancak hala geliştirilebilir. vector veri yapısı yerine list veri yapısını kullanabiliriz.

Vektörlerde random-access olayı mevcut. Yani students[5] diyerek o öğrenciye erişebilirim. Bunun sebebi vektörlerde bir silme veya araya ekleme işlemi yapıldığında, eklenen veya silinen yerin öncesi veya sonrası tamamen kaydırılıyor. Bu verilere direk indis ile erişebilmemizi sağlıyor. Bu güzel bir özellik olarak görünebilir ancak 1 milyon verili bir vektörde ortalardaki bir elemanı sildiğimizi düşünürsek oldukça maliyetli. Bu veri yapısı yerine list veri yapısını kullanabiliriz. List veri yapısında objeler birbirini gösterir. Ortadaki bir objeyi silersek, objenin öncesindeki obje, sildiğimiz objenin bir önündeki objeyi göstermeye başlar. Çok az maliyetle objeleri bu şekilde silebiliriz. Fonksiyonu yeniden yazmadan önce performans karşılaştırması yapalım:


File size 	list 	vector
735 		0.1 	0.1
7,350 		0.8 	6.7
73,500	 	8.8 	597.1
Eğer veri büyüklüğümüz az ise vektör daha hızlı çalışır. Ancak büyük verilerde list yapısını kullanmak daha avantajlıdır. Şimdi fonksiyonu yeniden yazalım:


// fourth try
list<Student_info> extract_fails(list<Student_info>& students){
    list<Student_info> fail;
    list<Student_info>::iterator iter = students.begin();
    while (iter != students.end()) {
	if (fgrade(*iter)) {
	    fail.push_back(*iter);
	    iter = students.erase(iter);
	} else
	    ++iter;
    }
    return fail;
}
Şu ana kadar diziler, vektörler, listeler gibi veri yapıları gördük. Aslında bunlara ek olarak bir de string yapısını gördük. Stringlerde aslında karakterleri tutan yapılardır. Bu yapılarda s[4] şeklinde index belirterek karakterlere erişebiliriz. Bir örnek yapalım, yazacağımız fonksiyon bir string alsın ve bu stringi boşluğa göre bölsün. Örneğin "jan franco jan franco" şeklinde bir argüman gönderdiğimde bana "jan" "franco" "jan" "franco" stringlerini barındıran bir vektör dönsün:


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;
}
Burada s stringini aldık. Bu stringde herhangi bir oynama yapmayacağız ve tüm stringin kopyalanmasını istemiyoruz. Bu nedenle const anahtar kelimesini ve referans sembolünü kullandık. ret adında bir vektör oluşturduk. Bir while döngüsü açtık. Döngüde her bir karakterde gezineceğiz, stringin sonuna geldiğimizde while döngüsü sonlanacak. "jan franco" şeklinde bir argüman gönderdiğimizi düşünelim. İlk adımda içteki ilk while döngüsü çalışmayacak. İkinci while döngüsünde j değişkeninin değeri 3 olacak. i değişkeninin değeri 0 idir. Bu iki değer karşılaştırıldığında if bloğ çalışacak ve substr() methodu ile aldığımız jan kelimesi ret vektörüne atılacak. Dıştaki while döngüsünün ikinci adımında ilk döngü çalışacak ve i değeri 4 olacak. Daha sonra ikinci while döngüsü çalışacak ve ikinci kelime alınarak vektöre atılacak. Son olarak vektör return edilecek. Fonksiyonu test edelim, tüm program:


#include <iostream>
#include <vector>
#include <cctype>

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

int main()
{
    string s;
    while(getline(cin, s)){
        vector<string> v = split(s);

        for(vector<string>::size_type i = 0; i != v.size(); i++){
            cout << v[i] << endl;
        }
    }
    return 0;
}


Sonraki Yazı: Using Library Algorithms
Yorumlar

Henüz bir yorum bulunmuyor.