Programowanie w języku C/C++ » Artykuły

Zaawansowane programowanie cz.2

  • 2006-05-12 20:03
  • 8 komentarzy
  • 1661 odsłon
  • Oceń ten tekst jako pierwszy
Zaawansowane aspekty programowania w C++ cz. II      

Autor: Asmie (-=Nevillon=- Member)
Data: 02.II.2003
E-mail:  asmie(na)poczta.onet.pl

Spis treści:




Wstęp


        Witam w drugiej części mojego tekstu dotyczącego zaawansowanego programowania dla języka C++. Dość długo zwlekałem z napisaniem tego tekstu (eh... szkoła :) ) ale mam nadzieję, że nie przejeliście się tym za bardzo. W zeszłej części zamieściłem co nieco informacji o tym co będzie w tej części ale niestety nie udało mi sie zrobić tego tak jak zaplanowalem, bo raz, ze nie miałem tyle czasu na bawienie się, a dwa - po prostu znalazłem ciekawszy materiał. Tak jak w zeszłym tekście zaznaczam, że jest to tekst przeznaczony dla zaawansowanych i jeżeli takowy nie jesteś to się musisz trochę podszkolić :). Dobra, zaczynamy !


O klasach coś więcej


Pytacie się pewnie co można jeszcze napisać o klasach i całej reszcie ? To jest naprawdę bardzo obszerny temat, więc chciałem uzupełnic waszą wiedzę o zagadnienie konwersji jednego typu w inny. W praktyce rzecz jest w miarę prosta, ale ważna gdy piszemy bibliotekę funkcji dla kogoś innego. Zagadnienie konwersji zaczniemy od prostego przykładu: (skorzystamy tutaj ze struktury time_t reprezentującej czas)

#include <stdio.h>
#include <time.h>
 
class Data {
         int dzien, miesiac, rok;
        public:
        Data(void) {dzien = 1; miesiac = 1; rok = 2000}
        Data(time_t);
        void pokaz(void);
} ;
 
void Data::pokaz()
{
    printf("Dzien: %d, miesiac: %d, rok: %d", dzien, miesiac,rok);
}
 
Data::Data(time_t now)
{
   struct tm *tim = localtime(&now);
   dzien = tim->tm_mday;
   miesiac = tim->tm_mon + 1;
   rok = tim->tmyear;
}
 
int main(void)
{
printf("Konstruktor domyslny:\n");
Data time1;
time1.pokaz();
printf("\nKonwersja:\n");
time_t now = time(NULL);
Data time2(now);
time2.pokaz();
return 0;
}


Co tu się stalo. Otoz przekształciliśmy obiekt struktury time_t na obiekt naszej klasy. Taka metoda jest użyteczna ale pozwala nam na konwersję tylko w jednym miejscu (przy deklaracji) i na tym koniec. Załóżmy, że chcemy przekonwertowac naszą klasę na liczbę typu long, która będzie zawierała liczbę dni od początku XX wieku. Najpierw kod, a później objaśnienie:

#include <iostream.h>   // Kazdy chyba wie co to sa strumienie ??
 
class Data {
int dz, mc, rok;
public:
Data(int d, int m, int r) { dz = d; mc = m; rok = r;}
operator long();
};
 
Data::operator long()
{
static int miechy[] = {31,28,31,30,31,30,31,31,30,31,30,31};
long dni = (long) rok * 356;
dni += rok / 4;
for (register int i = 0; i < mc-1; i++)
        dni += miechy[i];
dni += dz;
return dni;
}
 
int main(void)
{
Data obiekt(4,11,49);
long minelo = obiekt;
cout << "\n Od 01.01.1900 r. minelo: ";
cout << '\n' << minelo << "dni..";
return 0;
}


Tutaj mamy przykład, który pokazuje nam w jaki sposób możemy dokonać konwersji naszego typu danych na typ long, który będzie zawierał liczbę dni. Aby przekonwertować jeden typ na inny należy użyć funkcji: nazwa_klasy::operator typ_danych. Przypomina Ci to coś może ? Tak ! Podobną rzecz robiliśmy, gdy chcieliśmy dokonać przeciążenia operatora plus (+) (pisałem o tym w pierwszej części). Równie dobrze moglibyśmy napisać taką funkcję konwertującą nasz typ Data na inny typ np.: int czy jakikolwiek dostępny. Oprócz tego jesli stworzymy np.: typ Data i jeszcze jakąś inna klasę, możemy użyć tej samej konstrukcji aby przekonwertować nasz typ danych na inny także nasz typ danych. Jest to trochę uproszczony przykład, ponieważ taki najlepiej nadaje sie do celów dydaktycznych. W każdej klasie możemy zamieścić więcej funkcji konwertujących przez co nasz typ mógłby dać sie przekonwertowac na praktycznie każdy istniejący typ danych.


Co nieco o MFC


        Większość z Was na pewno wie co to MFC. MFC (Microsoft Foundation Class) jest to zbiór klas bazowych wspierających programowanie dla systemu Windows. Klasy te są bardzo przydatne dla programistów piszących aplikacje okienkowe. Ale dla nas także mogą być w pewnien sposób przydatne. Należy tylko pamiętać, że MFC jest dostępne tylko dla Windows i pisząc program wykorzystujący MFC ograniczamy grono użytkowników. Ale w obecnej epoce, większość ludzi w domach używa tegoż systemu, więc należy się zastanowić nad wykorzystaniem tych bibliotek w swoich programach. Opisanie MFC nie jest moim celem, gdyż jest to praktycznie niemożliwe --> musiałbym napisać chyba z 2 MB tekstu. Ale chciałbym przybliżyć Wam pewne funkcje MFC, a mianowicie chodzi mi o wątki (threads). Co to są wątki to chyba każdy wie... jeżeli nie to się musi skądś dowiedzieć... (jak chce się być zaawansowanym to trzeba się uczyć ;> ).
Aby ułatwić programistom korzystanie z MFC w kompilatorze firmy M$ istnieje coś takiego, jak MFC AppWizard. Można z niego skorzystać wybierając z menu File->New i tam zakładkę Projects. Po ustaleniu głównych parametrów programu, zostanie utworzony projekt. Na początek trochę teorii. Otóż aplikacje MFC składają się z pojedynczej klasy CWinApp oraz jednej lub paru klas CWinThreads. CWinApp jest klasą reprezentujacą samą aplikację, a CWinThreads różne wątki procesu. Każda aplikacja posiada wątek główny czyli wątek, który jest uruchomiony od początku do końca programu (możemy go niejako przyrównać do funckji main()) oraz kilka lub kilkanaście wątków pobocznych, które są zarówno tworzone jak i usuwane w czasie pracy programu. Każda klasa w Windows jest pochodna od klasy CCmdTarget, która udostępnia rodzaje komunikacji. Generalnie mamy dwie możliwości tworzenia wątku. Pierwszy jest zalecany w przypadku korzystania z okien, które mają być uruchomione jako wątki. Jest to typ wątku pochodzący z CWinThread. Drugi jest tworzony, gdy funkcję chcesz uruchomić w jej własnym wątku i to jest wątek roboczy ale o nim potem.

Tworzenie obiektu CWinThread przebiega identycznie jak tworzenie wszystkich innych obiektów: określasz pochodzenie obiektu z CWinThread albo z klasy pochodzącej od CWinThread. WAŻNA UWAGA ! Po utworzeniu wątku nie WOLNO go uruchamiać - w tym celu należy wywołać metodę CreateThread() w danym obiekcie. Tworzenie wątku jest łatwe - deklarjesz klase pochodzaca z CWinThread i umieszczasz taki obiekt na stercie, potem tylko CreateThread() i sprawdzić czy zwrócona wartość to true.

CUserClass *watek;
watek = new CUserClass;
 
if ( ! watek->CreateThread() )
{
        MessageBox("Błąd wątka !\n");
        Delete watek;
}


Zaznaczyć tutaj należy, że CUserClass jest dowolną klasą stworzoną przez użytkownika ale pochodzącą pośrednio lub bezpośrednio z klasy CWinThread. Reszta jest chyba zrozumiała. Każdy wątek nie jest jednak ograniczony do pracy stand-alone czyli bez kontaktu z innymi wątkami. Jak już pisałem wcześniej każda klasa w Windows dziedziczy z klasy odpowiedzialnej za komunikację... więc wątki mogą się komunikwać ze sobą. Umieszczając wskaźnik do obiektu CWinThread na stercie, można przesłać wiadomość do dowolnego innego wątku:

watek->PostThreadMessage (MOJA_STALA_WIADOMOSC, wParam, lParam);


Parametry wParam i lParam są pozostałością po 16 bitowych systemach i programach. Obecnie Windows jest systemem 32 bitowym, więc oba parametry są 32 bitowe, a nie jak wcześniej wParam był 16 bitowym. Pierwszy parametr jest stałą zdefiniowaną przez użytkownika albo przez system. Funkcja OnThreadMessage() zarządza odwzorowaniem identyfikatora wiadomości w pamięci i jest zdefiniowana w komunikacie obiektu CWinThread. Ogólnie wiadomości przed wysłaniem są jeszcze mapowane przez funckje DECLARE_MESSAGE_MAP() jednak kompilator powinien utworzyć podane funkcje oraz do tego powinien tworzyć całą reszte obsługującą mapowanie komunikatów. Zajrzyj do pomocy swojego kompilatora.

Alternatywą dla tego typu wątków są wątki robocze. Jeżeli chcesz wykonywać jakąś klase w "tle" to ten typ wątków jest najlepszym wyjściem. W celu stworzenia tego wątku trzeba użyć funkcji AfxBeginThread(). Przykładowe overloading tej funkcji to:

CWinThread * AfxBeginThread ()
(
        AFX_THREADPROC          pSomeThreadFunction,
        LPVOID                  pParameter,
        int                        nPriority = THREAD_PRIORITY_NORMAL,
        UINT                        nStackSize = 0,
        DWORD                        dwCreateFlags = 0,
        LPSECURITY_ATTRIBUTES        lpSecurityAttributes = NULL
)


Omówie teraz parametry. nPriority jest wartością integer, określającą początkowy priorytet wątku. Przykładowe wartości to: THREAD_PRIORITY_HIGHEST, THREAD_PRIORITY_BELOW_NORMAL itd. nStackSize jest typu UINT (unsigned int). Określa początkowy rozmiar stosu wątku. Jeżeli ustawisz zero, sprawisz że Windows alokuje taki sam rozmiar stosu dla każdego nowego wątku.
dwCreateFlags określa flagi użyte przy tworzeniu wątku. Wartość domyślna jest zero ale może być także wartość CREATE_SUSPEND. Po utworzeniu takiego wątku z tą flagą uruchomić go można dopiero po wywołaniu ::ResumeThread(). Ostatni parametr jest atrybutem bezpieczństwa struktury i często się go po prostu ignoruje. Teraz pora na dwa pierwsze i najważniejsze parametry. Pierwszy z nich określa funkcję, która ma być uruchomiona w ramach wątku. Drugi parametr określa strukturę, w której mają być zawarte wszystkie parametry dla funkcji. Funkcja z parametru pierwszego kontroluje wątek - jej uruchomianie uruchamia wątek - jej zamknięcie kończy pracę wątku. Funkcję dobrze jest tworzyć jako część pewnej klasy, i strukturę parametrów także ponieważ dzięki temu zyskujemy prostotę wywołania. Przykład:

class usrcls
{
public:
        static UINT  threadfunc(LPVOID params);
        ...
        ...
};


a zaimplementować tak:

UINT usrcls::threadfunc(LPVOID params)
{
        usrcls *pthis = (CClientManager *) pthispointer;
        ASSERT (pthis);
        pthis->ClassMethod();
        return 0;
}


Wywołując funkcję podajemy wtedy jako parametr this:

AfxBeginThread( usrcls::threadfunc, (LPVOID) this);


I oto praktycznie cała filozofia tworzenia wątków.



Kontener sekwenecyjny - wektor


        Co to jest kontener ? I to w dodatku sekwencyjny ... Kontener w C++ tak jak i w normalnym życiu służy do przechowywania czegoś (np.: śmieci :))), w programowaniu są to dane różnego typu. Na przykład lista  łączona, którą implementowaliśmy w zeszłej części jest przykładem kontenera sekwencyjnego. Może ona przechowywać wartości, a aby uzyskać dostęp do jakiegoś elementu należy przeszukać inne aż do czasu natrafienia na właściwy element. Tak więc kontener sekwencyjny jest czymś co przechowuje dane i daje do nich dostęp w sposób sekwencyjny. Każdy zna chyba tablice... no musi znać :) . Wektor jest kontenerem, który działa na podobnej zasadzie do tablic, jest jednak szybszy i ma większe możliwości. Przed użyciem wektora, należy go zadeklarować, tak jak każdą inną zmienną ale jest jednak jedna dość istotna różnica: podczas deklaracji należy ukonkretnić tenże wektor. Co to znaczy ? Jako programista C/C++ powinieneś znać tzw. szablony. Jeśli nie to pokażę przykładową klasę szablonową:

template<class T>
class jakas_klasa {
public:
jakas_klasa(); // konstruktor
~jakas_klasa(); //destruktor
 
void ustaw_wartosc(T& wartosc);
T& zwroc_wartosc(void);
 
private:
T wartosc;
};


Chodzi o to, że w tej klasie, możesz przechować dowolny typ zmiennej. Zmienna wartość może być typu int, float, char a nawet jakąś strukturą. Wystarczy, że przy deklaracji ukonkretnisz ten szablon, czyli podasz jaki typ zmiennej chcesz tu przechowywać. Czyli możliwe są np.: takie deklaracje:

jakas_klasa<int> schowek;
jakas_klasa<float> schowek;
jakas_klasa<fpos_t> schowek;


Ukonkretniasz szablon przez podanie nazwy klasy i typu zmiennej w nawiasach ostrych. Wracając jednak do tematu tego rozdziału czyli do kontenera wektora należy zaznaczyć iż aby go użyć należy zadeklarować odpowiedni plik nagłówkowy:

#include <vector>


Wektor deklarujemy w następujący sposób:

vector<int> wartosci_int;
vector<float> wartosci_float;


itp. Wektor posiada skończoną liczbę elementów. Powyższe deklaracje tworzą wektory puste - nie posiadające elementów.

vector<int> wartosci_int(100);


Taka deklaracja powoduje utworzenie wektora przechowującego wartości int, a wartości takich wektor moze pomieścić 100. Ok, na razie jest łatwo. Czas się zając tym zagadnieniem dokladniej :). Mimo, iż wektor posiada określoną liczbę elementów, udostępnia on metody pozwalające dodawać do niego następne elementy (rozszerzać jego wielkość). Jest to podstawowa różnica, pomiędzy wektorem a tablicami. Do zmiany wielkości wektora służą dwie funkcje:

#include <vector>
#include <iostream>
 
int main(void)
{
        vector<int> vINT1;
        vector<int> vINT2(10);
        vINT2.resize(5, 10);
        vINT1.reserve(10);
        return 0;
}


Funkcje te maja postać:

void reserve(size_type n);
void resize(size_type n, T element = T());


Funkcja reserve jest używana do pustego wektora, który nie był wcześniej inicjalizowany jakąkolwiek wielkością jak właśnie wektor vINT1. Powoduje ona zarezerwowanie n miejsc w pamięci. Natomiast funkcja resize jest używana do zmiany już zainicjalizowanego wcześniej wektora. Powoduje ona zmianę wielkości wektora do n miejsc oraz dodanie na końcu ostatniego elementu T. Nie przejmuj się dziwną deklaracją tej funkcji, druga część argumentu musi być po prostu w ten sposób zadeklarowana, gdyż służy ona pobraniu informacji o type danych dodawanych na koniec wektora.
Kontenery wektora są tak zaprojektowane aby udostępniać szybki dostęp do danych. Dzięki przeciążeniu operatora indeksowania ( [ ] ) dostęp do elementów wektora jest możliwy w ten sam sposób jak do elementów tablicy. Wtedy jednak całe sprawdzenie poprawności indeksu spoczywa na głowie programisty (czyli Twojej ;) ). Jest jednak troszke lepszy sposób dostępu do elementów wektora, a mianowice jest to funkcja at(), która w razie przekroczenia zakresu wywołuje wyjątek out_of_range, który można wychwicić w blokach try/catch. Funkcja at ma postać:

reference at(size_type n);


gdzie reference jest to:

typedef typename A::reference reference;


Mniejsza z tym, co dana definicja oznacza, gdyż w rzeczywistości nie jest to istotne, ważne jest iż sprawdza zakres i zwraca wartość z miejsca podanego jako n. Funkcja zwraca referencje wiec powinienes juz sie domyslic o co chodzi.  I mały przykładzik:

#include <iostream>
#include <vector>
using namespace std;
 
int main(void)
{
        vector<int> vInt(10);
        for (vector<int>::size_type i = 0; i < vInt.size(); ++i)
                vInt[i] = 20 + i;
 
        try 
        {
                vInt.at((vector<int>::size_type)11) = 30;  // blad zakresu
        }
        catch (out_of_range)
        {
                cout << "Blad zakresu" << endl;
        }
        try
        {
                vInt.at((vector<int>::size_type)4) = 90;  // brak bledu
        }
        catch (out_of_range)
        {
                cout << "Blad zakresu numer 2 :))" << endl;
        }
        return 0;
}


Przykład ten jest troszkę sztuczny ale to nie szkodzi. W pierwszym przypadku blok catch wyłapie wyjątek, gdyż indeks numer 11 przekracza zakres wektora. W drugim przypadku indeks 4 należy do wektora i nie nastąpi wywołanie bloku catch. Biblioteka z klasą gdzie znajduje się wektor definiuje także dla niego zestaw przeciążonych operatorów relacyjnych: =, <, >, <=, >= i !=. Korzystanie z nich jest po prostu intuicyjne i używa sie ich jak w każdym innym przypadku :) . W następnej częsci przybliżę Wam używanie interatorów i modyfikatorów na wektorze ale nie wszystko na raz. Najpierw musicie dobrze zrozumieć ogólna zasadę działania wekorów oraz szablonów funkcji, poeksperymentwać troszkę a potem dopowiem resztę o tych jakże interesujących klasach :).

                               

Algorytmy sortowania - wybór


Na pewno często podczas pisania jakiegoś programu zastanawialiście się jaki algortym sortujący bedzie najlepszy i najszybszy do pewnego rodzaju danych. Pod względem złożoności najbardziej znane algorytmy można podzielić na dwie grupy:

a) tradycyjne - złożoność O(sqr(n))  *sqr oznacza kwadrat z danej liczby
b) nowoczesne - złożoność O(n*log(n))

Testowanie algorytmów sortowania nie może sie opierać tylko i wyłącznie o kategorię czasową, ponieważ czas danego algorytmu jest wysoce uzależniony od postaci danych wejściowych. Dlatego właśnie wyróżniamy przypadek optymistyczny pracy algorytmu, w którym dane wejściowe są w formie, dla której algorytm jest najszybszy, oraz przypadek pesymistyczny, w którym dane są w formie, dla której przetworzenia algorytm potrzebuje najwięcej czasu. Najczęsciej jednak brana pod uwage jest złożoność średnia, czyli po prostu średnia między oboma przypadkami. Dotyczy to w sumie tylko porownywania pracy algorytmow, z racji tego iz czesto wiemy, jakie dane bedzie posiadal algorytm i z puli dostepnych wybieramy ten, dla ktorego te dane beda przypadkiem optymistycznym. Oczywiscie jezeli przypadek nawet pesymistyczny innego algorytmu jest szybszy niz optymistyczny naszego to nalezy wybrac szybszy (to chyba logiczne ;) ). Nie bede tutaj pokazywal ani omawial kazdego algorytmu z osobna, tylko przedstawie zalety i wady kazdego z nich oraz zrobie na koniec male zestawienie. Zacznijmy wiec:

sortowanie bąbelkowe


sortowanie babelkowe - najprostsza metoda sortowania. Polega na kolejnym przechodzeniu sekwencyjnym przez sortowana tablice i w razie czego zamienienie miejscami dwoch sasiednich elementow. Brak przestawien w calej tablicy oznacza uporzadkowanie jej. Przypadkiem pesymistycznym tego algorytmu sa dane posortowane w kolejnosci odwrotnej i cechuje sie wtedy zlozonoscia O(sqr(n)). Przypadek optymistyczny to dane posortowane w odpowiedniej kolejnosci i ma zlozonosc O(n) czyli bardzo dobra. Wada tego algorytmu jest iz po kazdej iteracji tylko jeden element jest umieszczany na wlasciwym miejscu. Jednakze ten algorytm jest bardzo prosty w implementacji wiec do prostych i srednio trudnych zadan nadaje sie doskonale.

sortowanie przez wstawianie


sortowanie przez wstawianie - metoda ta buduje posortowany ciag, pobierajac elementy ciagu wejsciowego i umieszcza je w odpowiednie miejsca tablicy. Przypadek pesymistyczny to dane posortowane w kolejnosci odwrotnej (zlozonosc O(sqr(n)) ), a przypadek optymistyczny to dane juz posortowane w zadanej kolejnosci (zlozonsc O(n)) . Wada tego algorytmu jest to iz srednia liczba porownan jest rowna zlozonosci pesymistycznej czyli O(sqr(n)) .Podobnie jak w przypadku sortowania babelkowego przy kazdej iteracji tylko jeden element jest wstawiany we wlasciwe miejsce.

sortowanie przez wybieranie


sortowanie przez wybieranie - metoda ta jest bardzo podobna do poprzedniej. Rozni sie tylko zlozonoscia optymistyczna ktora wynosi O(sqr(n)) czyli jest on wolniejszy od poprzedniego. Jako zalete mozna dodac iz liczba porownan tego algorytmu wynosi O(n). Reszta jest identyczna jak w przypadku sortowania przez wstawianie.

sortowanie szybkie


sortowanie szybkie - (QuickSort) chyba najbardziej znana metoda sortowania. Dzieli ona dana tablice na dwie mniejsze podtablice i je sortuje a potem laczy ze soba. W przypadku pesymistycznym uzyskuje zlozonosc O(sqr(n)), a dzieje sie to wtedy gdy po podziale tablic na podtablice jedna z nich jest jednoelementowa a druga zawiera reszte. W przypadku optymistycznym uzyskuje zlozonosc O(n * log2n). Przypadek optymistyczny jest bardzo zblizony do sredniej zlozonosci dlatego tez ten algorytm jest najszybszy w przecietnym przypadku. Jako wady szybkiego sortowania mozna uznac bardzo zlozony kod, oraz dodatkowe obciazenie stosu.

sortowanie przez łączenie


sortowanie przez laczenie - odmiana sortowania zewnetrznego czyli danych nie mieszczacych sie w pamieci operacyjnej komputera. Polega ona na podziale pliku na kilka mniejszych, posortowanie ich oraz koncowa konkatencje. Sortowanie to nie posiada jako takich przypadkow pesymistycznych ani optymistycznych, a cechuje sie stala zlozonoscia rowna O(n * log2n). Jest to bardzo dobra wydajnosc i polecam te metode do sortowania danych zewnetrznych. Nie stosuje sie tego algorytmu do tablic poniewaz wymaga on dodatkowego narzutu pamieciowego na dwa strumienie robocze, o rozmiarze rownym rozmiarowi ciagu wejsciowego.

sortowanie metodą Shella


sortowanie metoda Shella - jest to ulepszona wersja sortowania przez wstawianie. W tej wersji mozliwe jest porownywanie elementow nie lezacych obok siebie, co znacznie przyspiesza ten algorytm. Metoda ta jest malo wrazliwa na postac danych wejsciowcyh, wiec nie potrafi wykorzystac sytuacji w ktorej na przyklad dane sa juz czesciowo posortowane. Zlozonosc optymistyczna wynosi O(n do potegi 1.25), a pesymistyczna O(n * sqr(log2n)).

sortowanie stogowe


sortowanie stogowe - przyklad sortowania drzewiastego.Dane postrzegane sa jako elementy drzewa binarnego. Element najwiekszy jest wierzcholkiem drzewa. Przypadkiem optymistycznym sa dane posortowane odwrotnie, jednakze ten typ sortowania jest bardzo malo wrazliwy na postac danych wejsciowych i cechuje sie stala zlozonoscia rowna O(n * log2n), co powoduje ze jest on jedna z nowoczesniejszych metod sortowania. Praktycznie rzecz biorac jedyna wada tego algorytmu jest jego dosc zlozona implementacja.

Jak widzicie to sa tylko podstawowe metody sortowania. Istnieje ich wiecej, a odmian wyzej wymienionych metod to juz na tuziny mozna liczyc. Przy wyborze algorytmu sortujacego kierujcie sie postacia danych wejsciowych. W przypadku danych czysto losowych polecam algorytm sortowania szybkiego, z racji tego iz radzi on sobie najlepiej z takimi danymi. Gdy na przyklad jest szansa na to iz dane beda w jakims stopniu juz posortowane to dobrym wyborem bedzie sortowanie przez wstawianie albo babelkowe. Gdy dane wejsciowe moga byc posortowane odwrotnie to od razu przychodzi na mysl sortowanie stogowe, ktore z reszta jest dobre i szybkie do wszystkich zastosowan. Praktycznie jest ono najbardziej uniwersalne ze wszystkich, poniewaz jest szybkie i odporne na rozne "dzikie" :) postacie danych wejsciowych. Pamietajmy jednak aby nie uzywac armaty do zabicia komara i w przypadku jakichs w miare prostszych programow, jak na przyklad ksiazka adresowa, mozemy spokojnie uzyc do sortowania zwyklego algorytmu sortowania babelkowego. Strata czasu nie bedzie jakas wielka i praktycznie rzecz biorac na prawde uzytkownik nie zauwazy roznicy w tym, czy uzyliscie jakiegos szybkiego czy wolniejszego algorytmu. A po co sobie dodawac roboty implementujac sortowanie stogowe, jak ten sam efekt uzyskamy w sortowaniu babelkowym kilkukrotnie mniejszym nakladem pracy. A roznice mozy byc widac na przyklad przy 10000 kontaktow na komputerze klasy 486. Wtedy uzytkownik na pewno odczuje roznice. Wazne jest to na pewno w grach, oraz systemach obslugi baz danych i innych gdzie do posortowania mamy tysiace rekordow. Jednak nawet wtedy wybor jest w sumie loteria, bo i tak nie znamy postaci danych wejsciowych, a na przyklad uzytkownik moze zaczac wpisywac dane do bazy od konca i wychodzi nam przypadek pesymistyczny dla kazdego algorytmu procz stogowego. Mimo wszystko jednak polecam dobrze zaznajomic sie z kazdym z tych algorytmow. Jakbyscie chcieli przykladowe implementacje kazdego z nich to mail-me (adres na koncu tekstu), a podesle przyklady.

                               

Uzywanie i tworzenie przestrzeni nazw


Od zawsze programisci C++ mieli problemy, ktorych zrodlem byly konfilkty nazw. Na pewno tez czesto zdarzaja Ci sie taki bledy w programie i czasem bywa to naprawde irytujace. Forum standaryzujace C++ poruszylo ten temat, jednak nie jest on (albo juz jest ?? :) ) jeszcze uwzgledniony w oficjalnej specyfikacji, tudziez warto sie z nim zapoznac. Konflikt nazw wystepuje wtedy, gdy dwie identyczne nazwy znajda sie w tym samym zasiegu w dwoch roznych modulach. Przestrzenie nazw uzywane sa do dzielenia globalnej przestrzeni nazw. Przestrzenie nazw sa podobne troche do klas i struktur. Wszystko co jest zadeklarowane w przestrzeni nazw, nalezy do niej. W jaki sposob utworzyc taka przestrzen ?? Sluzy do tego slowo kluczowe namespace:

//Plik common.h
 
namespace Moja_przestrzen {
        void Funkcja1(int x, int y);
}


W ten sposob utworzylismy wlasna przestrzen nazw zawierajaca jedna funkcje nazwana Funkcja1. W jaki sposob mozna sie teraz odniesc do tej przestrzeni. Otoz przestrzenie te sa zazwyczaj umieszczane w plikach naglowkowych, wiec po dowiazania danego pliku do projektu piszemy dyrektywe using namespace nazwa czyli w naszym przypadku:

#include "common.h"
using namespace Moja_przestrzen;


Dyrektywa using informuje iz bedziemy uzywac danych i funkcji zawartych w przestrzeni nazw nazwanej Moja_przestrzen. Nie jest to jednak jedyny sposob dostepu do danych zadeklarowanych w przestrzeniach nazw. Dostep do poszczegolnych elementow przestrzeni nazw mozna uzyskac identycznie jak w przypadku klas. Na przyklad nie uzywajac dyrektywy using mozna wywolac nasza funkcje w nastepujacy sposob:

#include "common.h"
 
Moja_przestrzen::Funkcja1(21, 20);


Bez dyrektywy using musimy podac z jakiego zakresu jest funkcja ktorej uzywamy. Jezeli nie chcemy na przyklad wlaczac do aktualnego zakresu calej przestrzeni nazw, a tylko jedna czy dwie zmienne lub funkcje a nie chce nam sie za kazdym razem podawac przestrzeni nazw, mozemy uzyc deklaracji using (UWAGA! to nie jest to samo co dyrektywa using !!). Przykladzik:

#include "common.h"
 
using Moja_przestrzen::Funkcja1;
 
Funkcja1(21,20);


W ten sposob mozemy wlaczyc tylko poszczegolne elementy do naszej przestrzeni nazw i nie musimy za kazdym razem podawac nazwy zakresu, z ktorego dana zmienna, funkcja, klasa, struktura czy unia pochodzi. Wewnatrz przestrzeni nazw mozesz umieszczac definicje klas, typow, oraz ciala funkcji, jednak zalecane jest abys robil to poza przestrzenia. Na przyklad:

//Plik comm.h
 
namespace My_area {
        int counter;
        void move(int x, int y);
}
 
 
//Plik impl.cpp
 
void My_area::move(int x, int y)
{
 
}


Mozna oczywiscie deklarowac funkcje wewnatrz przestrzeni nazw ale wtedy powstaje ogromny burdel w deklaracjach i po pewnym czasie sam sie nie polapiesz co to w ogole jest. Do kazdej przestrzeni nazw mozna utworzyc alias. Jak sie domyslacie alias jest dodatkowa nazwa jakiejs przestrzeni nazw. Jezeli nazwa jest dluga latwiej jest stworzyc krotki alias i przez niego korzystac z danej przestrzeni. Przyklad:

namespace to_jest_dluga_nazwa_przestrzeni_nazw {
        int wartosc;
}
 
namespace SKROT = to_jest_dluga_nazwa_przestrzeni_nazw; // definicja aliasu
 
SKROT::wartosc = 22;


Oto cala idea uzywanai przestrzeni nazw. Uzywajac ich mam nadzieje ze pozbedziesz sie wiekszosci konfliktow nazw zmiennych i funkcji.


Dynamiczne rzutowanie typu obiektu


W C++ praktycznie kazde bezpieczne rzutowanie typow jest wykonywane samorzutnie, bez praktycznie zadnej interwencji programisty. Programista ma mozliwosc, za cene odstepstwa od bezpieczenstwa, rzutowac jakis obiekt na jakikolwiek inny. Do tego celu sluzy kilka operatorow C++. Pierwszy z nich to dynamic_cast. Ma on nastepujaca skladnie:

dynamic_cast <typ_wynikowy> (obiekt)


Obiekt jest dereferencja wskaznika lub referencja do przedmiotowego obiektu. Z kolei typ_wynikowy jest wskaznikiem lub referencja do typu, w roli ktorego obiekt chcemy obsadzic. Operator dynamic_cast sluzy do weryfikacji rzutowania, w oparciu o hierarchiczna zaleznosc klas, ktora jest z kolei czescia mechanizmu RTTI (Run-Time Type Information). Jesli rzutowanie jest wykonalne to wartoscia operatora dynamic_cast jest wskaznik do przedmiotowego obiektu, rezultatem z kolei rzutowania bezsensownego jest wynik 0 lub wyjatek bad_cast. I maly przykladzik, ktory moze rozjasni wam dzialanie tego operatora:

#include <typeinfo.h>
#include <iostream.h>
 
class klasa1 {
public:
        virtual void jakas_metoda() {};
};
 
class klasa2
{
        //definicja tej klasy
};
 
class klasa3 : public klasa1
{
        //definicja tej klasy
};
 
int main(void)
{
        try
        {
                klasa1 *obiekt1 = new klasa3
                klasa3& obiekt2 = dynamic_cast<klasa3&> (*obiekt1);
        }
        catch (const bad_cast&)
        {
                cout << "Blad rzutowania !!" << endl;
                return 1;
        }
}


I co tu widzimy... Wyjatek nie zostanie wygenerowany poniewaz nastepuje bezpieczna konwersja w obrebie klas polimorficznych. Zostanie ona przeprowadzona i ustawiona na referencje do odpowiedniej klasy. Ale co by sie stalo gdyby tak podstawic obiekt typu klasa2 do rzutowania z obiektem typu klasa3. Zostalby wygenerowany wyjatek, poniewaz klasy nie daloby sie przerzutowac na zupelnie odmienny typ danych. Dla przykladu:

class klasa1 {
public:
        int l;
        float b;
 
        void show_values(void);
};
 
class klasa2 {
public:
        char *my_string;
        fpos_t point;
        FILE *source;
 
        int open_file(char *filename);
};


Proba rzutowania klasa1 na klasa2 lub odwrotnie nie moze sie po prostu udac. Jakies logiczne przekonwertowanie jednej klasy w druga jest niemozliwe do zrobienia. Ogolnie rzecz biorac operator dynamic_cast jest doskonaly w przypadku rzutowania zmiennej z klasy bazowej na jakas klase pochodna. Do tego celu zostal on wlasciwie stworzony i ogranicza sie tylko do hierarchi klas. Natomiast nastepne operatory rzutowania nie sprawdzaja juz czy rzutowanie jest mozliwe oraz umozliwiaja konwersje jednych typow do drugich, jak sie mozna przekonac przy pozniejszych testach - z bardzo rozna skutecznoscia :D . Nastepnym operatorem jest static_cast. Skladnia jest identyczna jak w przypadku dynamic_cast czyli:

static_cast <typ_wynikowy> (objekt)


Operator ten uzywany jest do zdefiniowanych przez uzytkownika, standardowych lub niejawnych konwersjach typow. W przeciwienstwie do dynamic_cast calosc konwersji realizowana jest przez kompilator. W tym operatorze zarowno typ_wynikowy jak i typ obiektu musza byc znane podczas kompilacji. static_cast nie generuje zadnych wyjatkow, gdy konwersja jest niemozliwa, wiec nalezy z nim postepowac ostroznie. Gdy dany typ da sie przekonwertowac na jakis inny za pomoca metod konwersji realizowanych automatycznie przez jezyk programowania, to wykonanie static_cast da ten sam rezultat. I przyklad takiej konwersji:

char ch;
int i;
ch = static_cast <char> (i);


W tym wypadku konwersja przebiegnie bez problemow, gdyz C++ potrafi sam automatycznie skonwertowac typ int do char i vice versa. Podobnie rzecz przebiega z klasami ale jak zwykle konwersja dwoch nie zwiazanych ze soba typow da same glupoty. static_cast dobrze sie spisuje rowniez przy konwersji klas bazowych do pochodnych, dzialajac podobnie jak dynamic_cast. Trzecim operatorem jest reinterpret_cast. Skladnia:

reinterpret_cast <typ_wynikowy> (obiekt)


Jak widzimy posiada te sama skladnie co dwa pozostale. Operator ten zapewnie alternatywe dla nieprzenosnosci i niebezpieczenstw, ktore wynikaja z tradycyjnych mechanizmow rzutowania. Wykonuje on konwersje miedzy wskaznikami, ale takze pomiedzy wskaznikiem, a liczba i vice versa. W wyrazeniu typ_wynikowy moze byc wskaznikiem, referencja, typem arytmetycznym, wskaznikiem do funkcji lub wskaznikiem do elementu klasy. Operator reinterpret_cast funkcjonuje wtedy i tylko wtedy gdy istnieje niejawna konwersja z typu obiektu to typu_wynikowego. W przeciwnym wypadku kompilator od razu zglosi blad. W przypadku roznego rozmiaru obu typow moze nastapic rozszerzenie lub obciecie argumentu, totez wynik tego operatora jest nieprzewidywalny i zalezny od konkretnej implementacji. I maly przyklad:

#include <iostream.h>
 
void func(void* point)
{
        int wartosc = reinterpret_cast <int> (point);
        cout << "Wartosc zmiennej int: " << wartosc << endl;
}
 
int main(void)
{
        int wartosc1 = 15;
        float wartosc2 = 21.22;
        func(reinterpret_cast <void*> (wartosc1));
        func(reinterpret_cast <void*> (&wartosc2));
}


Po uruchomieniu program da dosc dziwne wyniki :). Sprobujcie :). Jezeli chodzi o zmienna typu int to jej wartosc bedzie podana dobrze, czyli 15... Natomiast w przypadku wartosci float :D... No coz.. Wynik 1245048 nie jest chyba prawidlowy... Spowodowane jest to obcieciem czesci liczby float do 4 bajtow, czyli do dlugosci typu int. Totez operator reinterpret_cast jest bezpieczny przy rzutowaniu miedzy soba typow o tej samej dlugosci, i jak widzimy jest bardzo zalezny od implementacji, poniewaz w jednej typ int moze miec 4b i typ short int moze tez miec 4b wiec konwersja sie uda, a w drugiej typ short int moze miec 2b i w przypadku liczb przekraczajacych zakres short int ale mieszczacych sie w zakresie int znowu otrzymamy glupoty.
Ostatni z operatorow jakie chcialem zaprezentowac to const_cast. Posiada on ta sama skladnie co reszta:

const_cast <typ_wynikowy> (obiekt)


ale posiada dosc ciekawe wlasciwosci, ktore sa dosc przydatne. Sam dosc czasem uzywam tego operatora i tobie rowniez to polecam, gdyz ulatwia on zycie w wielu momentach. Jezeli dany obiekt byl zadeklarowany jako const to trzy wczesniejsze operatory nie pozbawia go tego operatora. Zadaniem operatora const_cast jest pozbawienie obiektu jego atrybutow wynikajacych z modyfikatorow const lub volatile. Typ obiektu MUSI byc taki sam jak typ_wynikowy. Za pomoca tego operatora mozna zamienic wskaznik (lub referencje) do stalej na wskaznik (lub referencje) do zmiennej. Obiekt wynikowy nie posiada wtedy atrybutu stalosci, ale jest identyczny z obiektem zrodilowym. Analogicznie jest z "ulotnoscia" modyfikatora volatile. I przyklad:

#include <iostream.h>
 
class Moja_klasa {
public:
        Moja_klasa(int wart) : i(wart) {} ;
        ~Moja_klasa();
        void func(void) const;
        int i;
};
 
void Moja_klasa::func (void) const
{
        // i++;  Blad kompilacji !!
        const_cast<Moja_klasa*> (this) ->i++; 
}
 
int main(void)
{
        Moja_klasa t(10);
}


Jak widzimy bezposrednie uzycie i wewnatrz stalej funkcji spowoduje blad (przetestuj !). Ale dlaczego jest blad ?? Poniewaz funkcje zadeklarowane jako stale, nie moga dokonywac modyfikacji jej obiektu macierzystego i po to byl nam wlasnie const_cast. Aby linia z wykomentowana byla prawidlowa, konieczna bylaby deklaracja zmiennej i jako mutable tzn.

mutable int i;


I to bylby koniec odnosnie operatorow. Czyli male podsumowanko: kiedy dokonujesz konwersji typow miedzy typamie tej samej hierarchii zawsze uzywaj dynamic_cast. W innych przypadkach uzywaj dwoch pozostalych tj. static_cast i reinterpret_cast. Dopoki kompilator nie zglasza bledow uzywa static_cast, a kiedy zacznie przejdz na reinterpret_cast. Nie naduzywaj tych operatorow. Uzywaj tylko wtedy gdy jest to konieczne, poniewaz nie daja zadnej gwarancji na prawidlowy przebieg programu. W sumie jedynym bezpiecznym operatorem jest const_cast, bo kompilator wykrywa wszystkie bledy, a nie daje on zadnych nieprzewidywalnych wynikow.


Optymalizacja wydajnosci aplikacji


W tym rodziale chcialbym przedstawic kilka technik sluzacych optymalizacji pisanych programow zarowno pod wzgledem rozmiaru jak i szybkosci dzialania. Pierwsza sprawa sa funkcje inline. Do czego one sluza kazdy na pewno wie, a jak nie to niech sie skads dowie. Funkcje inline nie sa dobrym pomyslem, w przypadku jezeli definicja tej funkcji jest rozbudowana. Co oznacza slowo rozbudowana ? Coz, kazdy kompilator inaczej traktuje te funkcje i nalezy pamietac, ze dyrektywa inline ma charakter prosby, ktora kompilator moze zignorowac jesli uzna to za stosowne. A kiedy tak uzna ?? Po pierwsze gdy funkcja zawiera petle for, while oraz do. Po drugie gdy funkcja jest rekursywna, po trzecie funkcje, ktorych definicja nie jest kompilatorowi znana. Myslicie teraz jak kompilator moze nie znac ciala funkcji ? Otoz, istnieje takie cos jak funkcje wirtualne, omowie je dokladnie w nastepnej czesci i wlasnie ich definicja nie jest kompilatorowi znana. Po czwarte funkcje zbyt dlugie jak na wstawialne. To ostatnie jest najmniej sprecyzowane. Kompilator uzywa pewnego rodzaju heurystyki do okreslenia czy funkcja nadaje sie czy tez nie na wstawialna. Ogolnie rzecz biorac, nie poleca sie zbytnio uzywania funkcji inline. Zalozmy teraz ze kompilator za kazdym razem spelni prosbe programisty i tam gdzie jest inline, rzeczywiscie uczyni taka funkcje wstawialna. Jezeli taka funkcja bylaby np.: troche dluga, to wielkosc pliku bylaby bardzo duza, gdyz za kazdym razem, przy wywolaniu kompilator wstawilby cialo tej funkcji. Rozmiar programu zwiekszalby sie proporcjonalnie do ilosci wywolan tej funkcji. Jezeli chodzi nam o optymalizacje wielkosci programu to wtedy wszystko szlag trafil. Kiedy uzywac w takim razie dyrektywy inline ? Oto dwa przyklady:

- kiedy rozmiar skompilowanego kodu funkcji jest mniejszy niz rozmiar sekwencji wywylujacej. przypominam, ze na sekwencje wywolujaca sklada sie przygotowanie parametrow, umieszczenie ich na stosie, ustanowienie ramki stosu, wykonanie skoku ze sladem, odtworzenie stanu stosu oraz powrot. Jak widac to wszystko zajmuje troche czasu i kodu, tak wiec moze sie zdarzyc, ze kod funkcji bedzie mniejszy od tej sekwencji

- funkcje do ktorych jest duzo odwolan w kodzie, oczywiscie musza to byc w miare male funkcje. Uczynienie jej inline da spory przyrost szybkosci

Oczywiscie aby sprawdzic rozmiar funkcji nie musisz sie trudzic aby znalezc jej rozmiar w skompilowanym kodzie :). Skompiluj modul z dyrektywa inline i bez niej i porownaj rozmiary. Jak z dyrektywa inline bedzie mniejszy lub ten sam, to bardzo dobrze trafiles. Jak bedzie wiekszy to sie nie przejmuj jezeli bedzie to roznica bajtow. Ale tez bez przesady, a zreszta co ja tu bede duzo pisal - sam wiesz co ci jest najbardziej potrzebne: szybkosc czy rozmiar programu.
Kolejna sprawa jest sprawa zmiennych. Uzywaj zawsze takiego typu zmiennej, jaki Ci jest wlasnie potrzebny. To jest logiczne, ale gdy chodzi o szybkosc programu staraj sie uzywac jak najwiecej zmiennych typu integer (int), poniewaz operacje na nich sa najszybciej wykonywane. Dobrym miejscem to umieszczenia zmiennej typu int sa wszelkiego rodzaju petle, w charakterze licznika, poniewaz w nich jest najwiecej odwolan do jakiejsc zmiennej. Dobrze jest rowniez przy bardzo wykorzystywanych zmiennych dodac w ich deklaracji slowko kluczowe register, choc podobnie jak w przypadku dyrektywy inline, ma ono status raczej prosby jak polecenia. Slowko to stara sie umiescic zmienna wewnatrz procesora, co powoduje ze uzycie jej jest niezwykle szybkie. Dobrym przykladem wykorzystania tego slowka, jest zadeklarowania jednej zmiennej licznikowej dla wszystkich petli. Wtedy w kazdej petli jest wykorzystywana ta sama zmienna o niezwyklej wprost szybkosci obliczeniowej. Dodatkowa praca wtedy dla programisty jest koniecznac zerowania takiej zmiennej przed uzyciem w kazdej nastepnej petli.
Ostatnia sprawa ktora przedstawie w tym rozdziale sa obiekty tymaczasowe. Wielu programistow czesto nie jest swiadomych istnienia takich obiektow, a jednak sa one tworzone przez kompilator. Przykladem, w ktorym danyc obiekt jest tworzony sa na przyklad podczas zwracanie danego obiektu przez funkcje, oraz przekazywanie do funkcji obiektu w charakterze parametru. Obiekty tymczasowe pozostaja niestety poza kontrola progrmisty. Wykorzystam tutaj przyklad z ksiazki C++: Ksiega Eksperta wyd. Helion:

class Integer {
public:
        Integer();
        Integer(const Integer &);
        Integer(int valueIn);
        Integer(int valueIn, int addedValue);
        Integer operator+( const Integer &lhs, const Integer &rhs);
        Integer operator=(const Integer &);
        ...
};
 
Integer value = 2;
for (int i = 0; i < 100; i++)
        value = value + 2;


Na tym przykladzie przedstawie tworzenie sie obiektow tymczasowych. Pierwszych taki obiekt obeserwujemy juz w linii:

Integer value = 2;


Dlaczego ?? Wyglada to jak zwykla konstrukcja obiektu Integer i przypisanie mu wartosci 2... Jednak argumentem operatora = jest typ Integer, liczba 2 musi zostac skonwertowana wlasnie do takiego typu, przy uzyciu konstruktora Integer ( int valueIn); . A wiec zlapalismy nasz pierwszy roboczy obiekt tymczasowy. Jak sie go pozbyc ? Wystarcza ta linijke kodu zamienic na :

Integer value(2);


I w ten oto sposob, kompilator nie ma powodu aby utworzyc jakikolwiek obiekty tymczasowy, wiec wykonuje ta instrukcje, a my oszczedzamy troche czasu i pamieci dla naszej aplikacji. Druga interesujaca nas linia jest linia wewnatrz petli:

value = value + 2;


Operator + wymaga aby oba argumenty byly typu Integer, natomiast po jego prawej stronie znajdzie wartosc calkowita. I znow musi utworzyc, ale tym razem juz nie jeden, a dwa obiekty tymczasowe. Jeden bedzie pochodzil od liczby 2, gdyz musi ona stac sie obiektem klasy Integer, a drugi bedzie wynikiem dodawania, a na koniec dopiero, wartosc tego obiektu zostanie przypisana wlasciwej zmiennej value. Tak wiec przepiszmy ten kawalek kodu wykorzystujac obiekty tymczasowe:

Integer *temp = new temp(2);
value = temp;
delete temp;
 
for (int i = 0; i < 100; i++)
{
        Integer *temp1 = new temp1;
        Integer *temp2 = new temp2;
        temp1 = Integer(2);
        temp2 = value + temp1;
        value = temp2;
        delete temp1;
        delete temp2;                                
}


Jak widzimy na tym przykladzie w jaki sposob , moze zostac przez kompilator, rozwinieta zwykla i pozornie krotka petla. Teraz tylko wystarczy pomyslec ile czasu nam doda 100 krotne tworzenie i kasowanie dwoch obiektowo raz taki nadklad pracy. A w jaki sposob mozna to choc troche zoptymalizowac ?? Przyklad:

Integer value(2);   // nie utworzy sie obiekt
Integer valueadded(2);
for (int i = 0; i < 100; i++)
        value = value + valueadded;


W ten sposob pozbedziemy sie WSZYSTKICH obiektow tymczasowych z tego kawalka kodu.


Przechowywanie danych we wlasnych bazach danych


Coz.. tak jak w naglowku dzialu sprobuje przedstawic prosty sposob stworzenia szybkiej i skalarnej bazy danych. Wiele razy piszac program zastanawiales sie, w jaki sposob przechowac duza ilosc danych na dysku. Uzycie istniejacego systemu bazodanowego jest dosc wygodnym rozwiazaniem, jednak jezeli potrzebujemy dosc nietypowych rozwiazan, piszac na przyklad program przechowujacy pewne dane, a potem pobierajacy je w jakis "dziwny" sposob, mozna pokusic sie o stworzenie wlasnego systemu bazodanowego. Nie pokaze tutaj dokladnie calej implementacji takiego systemu, poniewaz zajmowaloby to zbyt duzo miejsca, a poza tym nie mialoby to zadnego celu dydaktycznego. Ten rozdzial jest calkowicie moim autorskim pomyslem wiec moga w nim wystapic bledy, totez w razie ich znalezienia (zarowno w przykladowym kodzie) prosze o kontakt.
Zacznijmy od ustalenia podstawowych regul takiego systemu. Zalozmy ze potrzebujemy bazy danych aby przechowywac dane w roznego rodzaju tabelach. Sprobujmy zatem napisac na poczatek system, ktory wyglada podobnie jak istniejace systemy i nie posiada na razie zadnych specyficznych funkcji. Musimy zaczac od interfejsu danej bazy danych. Jako ze uzywamy C++ interfejs opieral sie bedzie na klasach. I tak zaczynamy od podstawowej klasy jaka bedzie ogolny obiekt reprezentujacy baze danych. Przykladowy interfejs bazy danych:

//Autor: Asmie 2002
 
class CDatabase {
private:
        FILE *base;
public:
        CDatabase();
        CDatabase(char *FileName, char *Password, int mode, int share_mode, int cursor_type, int curosr_mode, char *RecordSource);
        ~CDatabase();
 
        char *FileName;
        char *Password;
        int mode;
        int cursor_type;
        int cursor_mode;
        int share_mode;
        char *RecordSource;
 
        CRecordset *Recordset;
        CError *Errors;
 
        void Refresh(void);
        void NewDatabase(void);
        void Clean(void);
        void EncryptDatabase(char *Password);
        void Validate(void);
};


Ok. Mamy tutaj przykladowa implementacje klasy CDatabase, ktora jest szkieletem bazy danych. W czesci danych prywatnych mamy tylko wskaznik do pliku. Podczas otwierania polaczenia z baza danych ustalany jest na dany plik na dysku. Pewnie sie zastanawiasz w jaki sposob otworzyc jakas baze danych skoro nie ma nigdzie funkcji do otwierania. Aby otworzyc dana baze danych nalezy podac nazwe pliku z nia w polu FileName, haslo jesli jest wymagane w polu Password, potem tryb otworzenia w polu mode. Przykladowe tryby otwarcia:

#define MODE_READ_ONLY 0x1
#define MODE_READ_WRITE 0x2


I w ten sposob mozemy okreslic tryb w jakim baza ma zostac otworzona. Nie tlumacze ich juz :). Dalej nalezy podac typ kursora, w polu cursor_type. Bynajmniej nie chodzi tu o wskaznik myszy ale o wskaznik polozenia w bazie danych. Przykladowe typy kursora:

#define CURSOR_DYNAMIC 0x3   //kursor dynamiczny
#define CURSOR_STATIC 0x4    //kursor statyczny


Roznic pomiedzy tymi kursorami tez nie bede tlumaczyl bo to nie lezy mojej gestii, ale jezeli nie znasz roznicy to mozesz ja znalezc na przyklad w pierwszych rozdzialach ksiazki Visual Basic: Programowanie Baz Danych :). Mimo ze jest to ksiazka do Visual Basic, pierwsze rozdzialy doskonale omawiaja zagadnienie baz danych. Kolejnym polem jest tryb kursora, czyli kierunki w jakich mozna przechodzic po tabeli. Do wyboru mamy:

#define CURSOR_FORWARD 0x5
#define CURSOR_BACKWARD 0x6
#define CURSOR_BOTH 0x7
#define CURSOR_SEEK 0x8


Trzy pierwsze chyba nie wymagaja wyjasnien. Jest to po prostu sekwencyjne przejscie przez tabele. Natomiast nastepny pozwala na dostep swobodny do rekodow tabeli, czyli mozliwosc, ze tak powiem skakanie po rekordach. Potem nalezy podac juz tylko nazwe tabeli w polu RecordSource i wywolac funkcje Refresh(). Druga klasa interfejsu konieczna do poprawnego dzialania systemu jest klasa CRecordset. I oto przykladowa implementacja:

CRecordset {
private:
        char *record;
        char* _read_record();
        FILE *base;
        char *types;
        char **name_of_cols;
        unsigned int cols;
        unsigned long rows;
        unsigned long current_row;
        fpos_t BOT;
        fpos_t EOT;
        fpos_t current;
        CError *err;
        int curosor_type;
 
public:
        CRecordset(FILE *wp, int cursor_type, fpos_t BOT, CError *err);
        ~CRecordset();
 
        BOOL iserror;
 
        BOOL EOT(void);
        BOOL BOT(Void):
 
        void MoveNext(void);
        void MovePrev(void);
        void MoveFirst(void);
        void MoveLast(void);
 
        void Seek(unsigned long num);
        void Seek(unsigned int poz, unsigned long offset);
 
        void AddNew(void);
        void Edit(void);
        void Delete(void);
        void Update(void);
 
        void Field(unsigned int index, void *buff) const;
        void Filed(char *name_of_field, void *buff) const;
 
        unsigned long GetRows(void) const;
        unsigned int GetCols(void) const;
        unsigned long GetCurrentRow(void) const;
 
};


Coz.. ten kawalek kody wymaga wiecej wyjasnien :). W czesci danych prywatnych tej klasy mamy zmienna typu wskaznik do char o nazwie record. Reprezentuje ona aktualny rekord tabeli. Posiada caly ten rekord jako jeden ciag znakow, ktory potem bedzie dzielony przez funkcje Field. Pozniej jest funkcja, ktora na podstawie zmiennej polozenia current spisuje rekord do pola record. Potem mamy wskaznik do pliku z baza, a potem zmienna typu wskaznik do char definiujaca typy poszczegolnych kolumn. Nalezy sobie przyjac ze na przyklad: s to string, i to integer itd. Nastepna zmianna okresla nazwy kolumn. Potem dwie nastepne okreslaja liczbe kolumn i wierszy tej tabeli. Kolejna identyfikuje numer aktualnego wiersza. Potem trzyb polozenia plikowe: poczatek tabeli, koniec tabeli i obecne polozenia w tabeli. I potem wskaznik do obiektu errors klasy CDatabase, gdzie beda umieszczane opisy bledow. Nastepnie przechodzimy do danych publicznych funkcji i na sam poczatek konstruktor i destruktor. Pozniej zmienna okreslajaca czy wystapil blad. Nastepnie funkcja sprawdzajaca osiagniecie konca i poczatku tabeli. Nastepnie 4 funkcje do poruszania sie sekwencyjnego po tabeli. Pozniej funkcja do dostepu dowolnego, oraz jej przeciazenie. Nalezy pamietac, ze jakie funkcje moga zostac uzyte zalezy od wyboru kursora, totez na przyklad przy wybraniu CURSOR_BACKWARD nie bedzie mozliwe uzycie ani funkcji Seek, ani funkcji MoveNext, a jesli uzyjesz funkcji MoveFirst, nie bedzie mozna sie wrocic inaczej niz przez funkcje MoveLast i ponowne sekwencyjne przejscie od konca przez tabele. Reszta funkcji jest chyba jasnych. W nastepnej czesci pokaze przykladowy szkielet pliku z baza danych oraz popracujemy nad tym dalej.

Zakonczenie


Koniec czesci drugiej...  i mam nadzieje ze ktos te druga czesc w ogole przeczytal :P. Nastepnych czesci szukajcie gdzies po sieci i koniecznie zajrzyjcie na:

http://nevillon.pac.pl

a znajdziecie cos ciekawego ! :)

Czesc pierwsza dostepna pod adresami... jak wyjdzie trzecia mam nadzieje ze tez tam bedzie :P

http://nevillon.pac.pl  ---> dzial NvCoders
http://www.programowanie.of.pl

I to by bylo na tyle !

Literatura:
Jesse Liberty "C++ - ksiega eksperta" wyd. Helion
Adam K. Majczak "Praktyczne programowanie w C++"

I jak zwykle pozdrowienia :) :
Neo, Furiza, MISIEK_RDK, lukasz, raaddii, dla ludzi z #dabrowagornicza i #nevillon
i dla calego Nevillonu

Kontakt:

asmie(na)poczta.onet.pl
GG: 1868980

8 komentarzy

Marooned 2006-05-12 20:01

doda ktoś PL znaki? [green]

pralat_adi 2006-02-13 21:48

co do sortowania Quicksort radzilbym wprowadzic poprawke, gdyz po wstepnym pozamienianiu niektorych liczb dzieli tablice na 2 czesci( w 1. powstalej tablicy nie ma zadnego wiekszego elementu niz w 2.), a pozniej powtarza te czynnosc az otrzymamy posortowana, podzielana tablice na tyle czesci ile bylo liczb

pralat_adi 2006-02-13 21:46

co do sortowania Quicksort radzilbym wprowadzic poprawke, gdyz po wstepnym pozamienianiu niektorych liczb dzieli tablice na 2 czesci( w 1. powstalej tablicy nie ma zadnego wiekszego elementu niz w 2.), a pozniej powtarza te czynnosc az otrzymamy posortowana, podzielana tablice na tyle czesci ile bylo liczb

asmie 2003-04-21 15:53

Pierwsza czesc tez jest tutaj tylko czemu autor inny :) Otoz czesc pierwsza jest juz tu dlugo, zanim bylo logowanie itp. i po zmianie enginu, po prostu zostaly wrzucone stare texty na konto admina i tyle :)

Marooned 2003-04-17 08:39

Przecież na końcu napisał:

Część pierwsza dostępna pod adresami:
http://nevillon.pac.pl ---> dzial NvCoders
http://www.programowanie.of.pl

tam już nie dotrwaliście? ;)

AndRew 2003-04-15 23:57

chyba tu : (tylko autor nie ten sam ;) --> <url>http://www.4programmers.net/view.php?id=77</url>

Hex 2003-04-14 14:03

Nio wlasnie, gdzie jest??? ;P

Dryobates 2003-04-13 18:44

A gdzie jest część pierwsza?