Defining Abstract Data Types

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


C++'da hazır olarak bir vektör sınıfı bulunuyor. Bu vektör sınıfından vektör objeleri üretebiliriz. Bu bölümde bu vektör sınıfını baştan sona kendimiz yazacağız. Başlangıç olarak hazır vektör sınıfı ile neler yapabileceğimize bakalım:


vector<Student_info> vs; // empty vector
vector<double> v(100); // vector with 100 elements

vector<Student_info>::const_iterator b, e;
vector<Student_info>::size_type i = 0;

for (i = 0; i != vs.size(); ++i)
cout << vs[i].name();

b = vs.begin(); e = vs.end();
Objeleri argümanlı veya argümansız oluşturabiliyoruz. Argüman olarak boyut bilgisini verebiliriz. Objeleri dilediğimiz tipi tutabilecek şekilde oluşturabiliyoruz. const_iterator ve size_type özelliklerimiz var. size() methodu ile boyut bilgisini alabiliyoruz, [i] şeklinde indeksleme yapabiliyoruz. begin() ve end() methodları ile iterator return edebiliyoruz. Bu bilgiler eşliğinde kendi sınıfımızı artık açabiliriz:


template <class T> class Vec {
    public:
	//
    private:
	//
};
Generic bir sınıf yapmak istediğimizden template anahtar kelimesini ve T nesnesini kullandık. Kullanıcı Vec derse int tipi T nesnesinin yerine atanacak ve T nesnesinin kullanıldığı her yer int tipindeymiş gibi olacak. public ve private kısımları boş bırakmak üzere tanımladık. Veri saklayacağımız için data ve boyut bilgisini önemli olduğu için limit adında iki değişken ekleyelim:


template <class T> class Vec {
    public:
	//
    private:
	T* data;
	T* limit;
};
Orjinal vektörlerde argümansız da obje oluşturabiliriz, boyut bilgisini vererek de obje oluşturabiliriz. Aynısını yapmak istiyoruz bu nedenle iki consturctor oluşturalım:


template <class T> class Vec {
    public:
	Vec() { create(); }
	explicit Vec(size_type n, const T& val = T()) { create(n, val); }
    private:
	T* data;
	T* limit;
};
Burada Vec() ve Vec(size_type n, const T& val = T()) şeklinde iki constructor oluşturduk. explicit anahtar kelimesini yeni görüyoruz. explicit anahtar kelimesini bir örnek üzerinden açıklayayım:


class String {
    public:
        String(int n); // allocate n bytes to the String object
        String(const char *p); // initializes object with char *p
};
Bir String sınıfı ve iki constructor oluşturduk. Şimdi bu sınıftan bir obje üretelim ve bu objeye 'x' karakterini eşitleyelim:


String mystring = 'x';
Yukarıdaki kullanımda 'x' karakteri int tipine çevrilir ve String(int) constructor'u çağırılır. Biz bunu istemiyoruz bu nedenle explicit anahtar kelimesi ile bunu önüne geçebiliriz:


class String {
    public:
        explicit String (int n); //allocate n bytes
        String(const char *p); // initialize sobject with string p
};
explicit anahtar kelimesini anladık. Şimdi Vec sınıfımıza geri dönelim ve bazı isimler tanımlayalım:


template <class T> class Vec {
    public:
	typedef T* iterator; // added
	typedef const T* const_iterator; // added
	typedef size_t size_type; // added
	typedef T value_type; // added

	Vec() { create(); }
	explicit Vec(size_type n, const T& val = T()) { create(n, val); }
    private:
	iterator data; // changed
	iterator limit; // changed
};
Artık iterator çağırdığımızda T* çalışacak, const_iterator çağırdığımızda const T* çağırılacak, size_type yazdığımızda size_t anlaşılacak, value_type yazdığımızda T çalışacak. En başta orjinal vektörlerin [i] şeklinde indeks yöntemi ile elemanlarına erişilebileceğinden ve size() methodunun olduğundan bahsetmiştim. Aynısını gerçekleştirelim:


template <class T> class Vec {
    public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;

	Vec() { create(); }
	explicit Vec(size_type n, const T& val = T()) { create(n, val); }

	size_type size() const { return limit - data; }
	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const { return data[i]; }
    private:
	iterator data;
	iterator limit;
};
Burada size() methodunu ekledik ve bu method bize limit - data değerini verecek. Yeni gördüğümüz bir özellik olan operatör tanımlamayı görüyoruz. Artık [] karakterlerini kulandığımızda ve bu karakterlerin arasında bir boyut verdiğimizde (size_type i) bize data[i] elemanını return edecek. Iterator return eden methodları yazalım:


template <class T> class Vec {
    public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;

	Vec() { create(); }
	explicit Vec(size_type n, const T& val = T()) { create(n, val); }

	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const { return data[i]; }
	size_type size() const { return limit - data; }

	iterator begin() { return data; } // added
	const_iterator begin() const { return data; } // added
	iterator end() { return limit; } // added
	const_iterator end() const { return limit; } // added
    private:
	iterator data;
	iterator limit;
};
Burada begin() ve end() methodlarını ekledik. begin() methodu data değişkenini, end() methodu limit değişkenini return edecek. Şimdi bir copy constructor oluşturalım. Fakat ilk olarak copy constructor'un ne olduğunu anlayalım. Bunun için aşağıdaki örneği inceleyelim:


double d;
d = median(vi);

string line;
vector<string> words = split(line);
Burada ilk olarak vi değişkeninin median fonksiyonun parametresine kopyaladık. Daha sonra split() fonksiyonundan dönen değeri words'e kopyaladık. Benzer şekilde, bir obje oluşturmak için de bir objeyi kopyalayabiliriz:


vector<Student_info> vs;
vector<Student_info> v2 = vs;
Burada vs'yi v2'ye kopyaladık. Burada herhangi ekstra bir işlem yapmadık çünkü copy constructor default olarak işi bizim için halletti. Fakat bazı durumlarda, özellikle kendi sınıfımızı yazıp bu sınıftan bir obje oluşturuyorsak kendi copy constructor'ımızı oluşturmak daha mantıklıdır. Yapıyı görelim:


template <class T> class Vec {
    public:
	Vec (const Vec& v); // copy constructor
};
Bu copy constructor çağırıldığında bellekten yeni bir yer ayırtmamız, yeni bir obje oluşturmamız gerekli:


template <class T> class Vec {
    public:
	Vec(const Vec& v) { create(v.begin(), v.end()); }
};
Copy constructor oluşturduk. Şimdi = operatörünü kendimiz tanımlayalım:


template <class T>
    Vec<T>& Vec<T>::operator=(const Vec& rhs){
	if (&rhs != this) {
	    uncreate();
	    create(rhs.begin(), rhs.end());
	}
        return *this;
    }
Vec sınıfından iki obje oluşturduğumuzu düşünelim, vecA ve vecB. vecA = vecB şeklinde bir komut verirsek ilk olarak vecA ile vecB'nin aynı obje olup olmadığı kontrol edilecek. Eğer farklı objeler ise vecA objesi yok edilecek ve vecB'nin begin() ve end() methodları kullanılarak yeni bir obje üretilecek. Bu yeni obje de vecA objesinin kendisi olacak. Şimdi bir destructor yazalım. Destructor, constructor'ların tersidir. Yapıcı değil yıkıcı fonksiyonlardır:


template <class T> class Vec {
    public:
	~Vec() { uncreate(); }
};
Vec sınıfından bir obje destroy edildiğinde bu fonksiyon çağırılacak. Destructor tanımlıyorsak ~ karakterini kullanmalıyız. Şimdiye kadar ki özel fonksiyonlarımızı tekrar gözden geçirelim:


T::T(); one or more constructors, perhaps with arguments
T::~T() the destructor
T::T(const T&) the copy constructor
T::operator=(const T&) the assignment operator
Şuan vektöre bir nesne eklendiğinde vektörün boyutu artmıyor. Yani 100 nesnelik bir vektör oluşturulduysa, 101. obje eklenemez. Bunu yeni bir değişken ekleyerek değiştirebiliriz:


template <class T> class Vec {
    public:
	void push_back(const T& val) {
    	    if (avail == limit) // get space if needed
	        grow();
	    unchecked_append(val) ; // append the new element
	}
    private:
	iterator data; // as before, pointer to the first element in the Vec
	iterator avail; // pointer to (one past) the last constructed element
	iterator limit; // now points to (one past) the last available element
};
Burada push_back fonksiyonu ile avail ve limit değerlerini karşılaştırdık. avail pointer'ı son eklenen nesnenin bir adım sonrasını gösteriyor. data, avail ve limit pointer'larının nereleri gösterdiğini aşağaki görselden daha iyi anlayabiliriz:

cpp-abstract

Esnek bir biçimde belleği yönetebilmek için bir kaç fonksiyon ekleyerek vec sınıfını tamamlayalım:


template <class T> class Vec {
    public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;
	
	Vec() { create(); }
	explicit Vec(size_type n, const T& t = T()) { create(n, t); }
	Vec(const Vec& v) { create(v.begin(), v.end()); }
	Vec& operator=(const Vec&);
	~Vec() { uncreate(); }
	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const { return data[i]; }
	
	void push_back(const T& t) {
	    if (avail == limit)
		grow();
		unchecked_append(t);
	}

	size_type size() const { return avail - data; }
	iterator begin() { return data; }
	const_iterator begin() const { return data; }
	iterator end() { return avail; }
	const_iterator end() const { return avail; }
    private:
	iterator data; // first element in the Vec
	iterator avail; // (one past) the last element in the Vec
	iterator limit; // (one past) the allocated memory
	allocator<T> alloc; // object to handle memory allocation
	
	void create();
	void create(size_type, const T&);
	void create(const_iterator, const_iterator);
	void uncreate();
	void grow();
	void unchecked_append(const T&);
};
Vec sınıfında adından bahsettiğimiz create, uncreate, grow, unchecked_append fonksiyonlarını oluşturalım. Bu fonksiyonları oluşturmak için kütüphanesini kullanacağız. Memory kütüphanesi bize allocator adında generic bir class sağlıyor. Bu sınıfı ve fonksiyonları inceleyelim:


template<class T> class allocator {
    public:
	T* allocate(size_t);
	void deallocate(T*, size_t);
	void construct(T*, const T&) ;
	void destroy(T*);
	...
};

template<class Out, class T> void uninitialized_fill(Out, Out, const T&);
template<class In, class Out> Out uninitialized_copy(In, In, Out);
Vec sınıfında 3 farklı create() fonksiyonu tanımladık. Bu 3 farklı fonksiyonu yazalım:


template <class T> void Vec<T>::create(){
    data = avail = limit = 0;
}

template <class T> void Vec<T>::create(size_type n, const T& val){
    data = alloc.allocate(n);
    limit = avail = data + n;
    uninitialized_fill(data, limit, val);
}

template <class T>
void Vec<T>::create(const_iterator i, const_iterator j){
    data = alloc.allocate(j - i);
    limit = avail = uninitialized_copy(i, j, data);
}
İlk fonksiyon argüman almıyor. data, avail ve limit değerlerini 0'a eşitliyor. İkinci fonksiyon bellekten n kadar yer ayırtıyor. limit ve avail değişkenleri data + n değerini alıyor. Daha sonra unitinizalized_fill() fonksiyonu çağırılıyor. Bu fonksiyon tarafından sağlanıyor ve görevi allocate() fonksiyonu tarafından bellekte ayrılan bölgeyi, verilen değer ile doldurmak. Son fonksiyonda ise bellekten allocate() fonksiyonu ile j - i kadar yer ayrılıyor. Daha sonra unitinitialized_copy() fonksiyonu çağırılıyor. Bu fonksiyon da tarafından sağlanıyor ve görevi ilk iki argümanın oluşturduğu diziyi (i ve j iteratorları), data'ya yazmak. uncreate() fonksiyonunu yazalım:


template <class T> void Vec<T>::uncreate(){
    if(data){
	iterator it = avail;
	while (it != data)
	    alloc.destroy(--it);
	alloc.deallocate(data, limit - data);
    }
    data = limit = avail = 0;
}
uncreate() fonksiyonunda ilk olarak data var mı yok mu onu kontrol ettik. Eğer data var ise, avail iteratorunu kullanarak data iteratoruna kadar geri geri gideceğiz ve her adımda verileri yok edeceğiz. Daha sonra deallocate() methodu ile bellekte ayrılmış bölgeyi boşaltacağız. Daha sonra data, limit ve avail değerlerini 0'a eşitleyeceğiz. grow() fonksiyonunu yazalım:


template <class T> void Vec<T>::grow(){
    size_type new_size = max(2 * (limit - data), ptrdiff_t(1));
    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = uninitialized_copy(data, avail, new_data);
    uncreate();

    data = new_data;
    avail = new_avail;
    limit = data + new_size;
}
grow() fonksiyonunda ilk olarak boyut değişkenini iki katına çıkarıyoruz. Daha sonra bu boyut değişkenini kullanarak bellekten yer ayırtıyoruz. Daha sonra uninitialized_copy() fonksiyonu ile eski verileri bellekten ayırttığımız yeni alana yazıp eksi verileri siliyoruz. Son olarak unchecked_append() fonksiyonunu yazalım:


template <class T> void Vec<T>::unchecked_append(const T& val){
    alloc.construct(avail++, val);
}
Bu fonksiyonda construct() methodunu kullanarak avail + 1 kısmına val değerini yazıyoruz.


Sonraki Yazı: Making Class Objects Act Like Values
Yorumlar

Henüz bir yorum bulunmuyor.