Abstrakcyjne typy danych

Abstrakcyjne typy danych, pliki nagłówkowe, funkcje składowe "normalne" i wklejane (inline), asercje.

Nadszedł czas, by zaprojektować poważniejsze klasy, dzięki którym można będzie wykonać jakąś użyteczną pracę. Rozpocznijmy od czegoś prostego - abstrakcyjnego typu danych reprezentującego stos liczb całkowitych. Stos jest w pełni określony poprzez swój interfejs. Od każdego stosu wymaga się, by można było na nim wykonywać dwie podstawowe operacje: wkładać nań lub zdejmować zeń obiekty (w naszym przypadku - liczby całkowite typu int). Podstawową cechą stosu jest to, iż jest rodzajem kolejki LIFO (ang. Last-In-First-Out, czyli "kto wszedł ostatni wyjdzie jako pierwszy"). Na stos możemy wkładać obiekty w dowolnej kolejności, lecz wyjmować je z niego możemy tylko w dokładnie odwrotnej kolejności.

W naszej pierwszej implementacji stosu posłużymy się tablicą liczb całkowitych. Chcielibyśmy możliwie jak najpełniej oddzielić interfejs od implementacji. Pełna realizacja tego zadania jest możliwa w kilku językach programowania, lecz niestety język C++ do nich nie należy (w każdym bądź razie wymagałoby to sporego zachodu). Powody tego stanu rzeczy są głównie natury technologicznej - aby można było w pełni oddzielić interfejs od implementacji, kompilator musiałby mieć dostęp do informacji o wszystkich plikach tworzących dany projekt.

W języku C++ możemy co najwyżej umieścić szczegóły implementacji niektórych funkcji w osobnym pliku. Jednak plik, zawierający opis interfejsu, musi zawierać pełną definicję klasy, a więc i jawną informację o wszystkich składowych, służących do przechowywania informacji o stanie obiektów danej klasy. Definicje interfejsów tradycyjnie umieszcza się w plikach z rozszerzeniem .h, które zwie się plikami nagłówkowymi (ang. header files). Oto interfejs naszego stosu, czyli zawartość pliku stack.h:
Tu można pobrać pliki źródłowe projektu Stack
Download!
Źródła 
const int maxStack = 16;

class IStack
{
public:
    IStack () :_top (0) {}
    void Push (int i);
    int  Pop ();
private:
    int _arr [maxStack];
    int _top;
};

Konstruktor klasy IStack inicjuje zerem składową _top, która jest licznikiem ilości liczb, aktualnie znajdujących się na stosie. Składowa _top służy jednocześnie jako indeks do tablicy _arr, identyfikujący jej pierwszy wolny element. Tak, w języku C++ elementy tablicy n-elementowej numeruje się od zera do n-1. W naszym przypadku rozmiar tablicy _arr wynosi 16 - fakt ten wynika z definicji stałej maxStack: 
const int maxStack = 16;

Użyty tu modyfikator const informuje kompilator, że wartość zmiennej maxStack nigdy nie ulegnie zmianie. Dlatego kompilator może zastąpić każde wystąpienie symbolu maxStack jego rzeczywistą wartością (czyli 16). I dokładnie w ten właśnie sposób kompilator postąpi!

Z kolei instrukcja 
int _arr [maxStack];

definiuje składową _arr jako tablicę maxStack liczb całkowitych. W języku C++ rozmiar tablicy musi być stały (tj. znany podczas kompilacji). Jeżeli tablica w punkcie swojej definicji jest jednocześnie jawnie inicjowana, nie musimy podawać jej rozmiaru (przykład zastosowania tej cechy tablic widzieliśmy już podczas omawiania tablic znaków i literałów napisowych).

Zwróćmy uwagę na to, że w powyższej definicji klasy Istack znajdują się deklaracje funkcji składowych Push i Pop, lecz nie ma tam ich definicji. Różnica pomiędzy deklaracją funkcji a jej definicją polega na tym, że definicja zawiera instrukcje, tworzące treść funkcji, czyli jej implementację (i kończy się średnikiem). Deklaracja funkcji nie zawiera natomiast żadnych inforamcji o tym, jak funkcja działa, lecz jedynie określa interfejs funkcji, czyli ilość i typy jej argumentów oraz typ jej wartości. Gdzież więc podziewa się implementacja metod Push i Pop? Odpowiedź brzmi: w oddzielnym pliku stack.cpp, zawierającym implementację klasy Istack.

W pierwszym wierszu pliku implementacyjnego znajduje się dyrektywa include, która powoduje dołączenie zdefiniowanego przed chwilą pliku nagłówkowego stack.h. Następnie do naszego pliku dołączamy kolejny, standardowy plik nagłówkowy cassert. Zawiera on definicję niezwykle ważnej funkcji assert. Nie będę tu szczegółowo omawiał implementacji tej funkcji, Czytelnik powinien jednak zapamiętać, że definiując symbol preprocesora NDEBUG można ją zupełnie wyłączyć - tak, jakby jej w ogóle nie było w programie!. Jeśli jednak nie zdefiniujemy symbolu NDEBUG, funkcja assert będzie sprawdzać, czy wartością logiczną jej argumentu jest true, czyli czy jego wartość jest różna od zera. Innymi słowy funkcja assert służy do weryfikacji prawdziwości wyrażenia, przekazanego w jej argumencie. Symbol NDEBUG definiujemy dopiero wtedy, gdy nasz program został już poddany wszechstronnemu testowaniu i uważamy, iż nie zawiera błędów. Definiując w tej sytuacji symbol NDEBUG w jednym posunięciu pozbywamy się wszystkich asercji, co powinno istotnie poprawić prędkość wykonywania się programu1. Co się stanie w sytuacji, gdy wyrażenie, przekazane jako argument asercji, nie jest prawdziwe (lub, co na jedno wychodzi, różne od zera)? W tym niefortunnym przypadku asercja wyświetli na ekranie komunikat zawierający nazwę pliku źródłowego, numer wiersza i warunek, który nie był spełniony. Asercje są narzędziem odpluskwiania programów. Gdy na ekranie pojawia się komunikat, którego źródłem jest asercja, oznacza to, że w programie znajduje się błąd.

Zazwyczaj trudno jest przewidzieć, gdzie w programie znajdują się błędy - pojawiają się jednak one w różnych nieoczekiwanych miejscach bez żadnej widocznej przyczyny. Jednak w naszym programie z reguły istnieją miejsca, w których takie błędy można wychwycić. Są to miejsca, w których czynimy pewne założenia. Zakładanie w programie spełnienia pewnych warunków jest zupełnie poprawne - dzięki nim programy stają się prostsze i szybsze. Jednak powinniśmy dokładnie sprawdzać, przynajmniej w fazie tworzenia i testowania oprogramowania, że w żadnym miejscu nie naruszamy tych założeń.

Jesteśmy gotowi, by przyjrzeć się implementacjom metod Push i Pop: 
#include "stack.h"
#include <cassert>
#include <iostream>
using std::cout;
using std::endl;

//by pozbyć się asercji zdefiniuj symbol NDEBUG (np. usuń komentarz z następnego wiersza)
//#define NDEBUG 1 

void IStack::Push (int i)
{
    assert (_top < maxStack);
    _arr [_top] = i;
    ++_top;
}

int IStack::Pop ()
{
    assert (_top > 0);
    --_top;
    return _arr [_top];
}

Jak widzimy, jeżeli funkcje składową definiujemy poza definicją klasy, musimy nazwę tej funkcji poprzedzić operatorem przestrzeni nazw :: oraz nazwą klasy. Jednak taki sposób definicji metod pociąga za sobą pewne ważne konsekwencje dla sposobu ich kompilacji. Wszystkie funkcje składowe, które dotychczas definiowaliśmy, były funkcjami wklejanymi (inline). Domyślnie kompilator traktuje wszystkie funkcje, których definicje podano w definicji klasy, jako funkcje wklejane. Co to znaczy w praktyce? Otóż kompilator, napotkawszy na wywołanie funkcji wklejanej, w miejscu jej użycia nie wygeneruje instrukcji skoku do funkcji, lecz spróbuje wygenerować jej treść ("wkleić jej treść"). Rozpatrzmy znany już przykład metody GetValue klasy Input. Ponieważ metodę tę zdefiniowano w definicji klasy, jest ona przykładem funkcji wklejanej. Dlatego jej wywołanie 
cout << input.GetValue ();
jest, z punktu widzenia wygenerowanego kodu wynikowego, równoważne instrukcji 
cout << input._num;

Z drugiej strony, jeżeli definicję funkcji składowej umieścimy poza definicja klasy, jak w przypadku metody Pop, automatycznie zostanie ona potraktowana jak "zwykła" funkcja, a nie funkcja wklejana.

Kiedy powinniśmy posługiwać się metodami wklejanymi, a kiedy zwykłymi? Podstawowym kryterium jest stopień złożoności metody. Jeżeli metoda zawiera tylko jedną instrukcję, zazwyczaj opłaca się zadeklarować ją jako funkcję wklejaną - uzyskany w ten sposób program powinien działać szybciej i zajmować mniej miejsca w pamięci komputera. Jeżeli metoda wykonuje jakieś bardziej skomplikowane czynności i jest wywoływana w wielu różnych miejscach, rozsądniej jest zadeklarować ją jako funkcje "zwyczajną".

Funkcje wklejane mają absolutnie podstawowe znaczenie dla pisania efektywnych programów w C++. Bez tej techniki przekonanie kogokolwiek do posługiwania się metodami typu GetValue lub SetValue byłoby praktycznie niemożliwe - wszyscy woleliby umieścić składową _num w interfejsie publicznym i odwoływaliby się do niej bezpośrednio (jednak istnieje grupa programistów, których nawet możliwość definiowania metod jako funkcji wklejanych nie przekonuje do stosowania takich funkcji). Brak jakiegokolwiek kosztu związanego z ukrywaniem danych jest źródłem ogromnej siły języka C++. Konieczność okazjonalnego wpisywania kilku dodatkowych wierszy kodu jest ceną, którą za wygodę i korzyści, związane z możliwością ukrywania danych, każdy doświadczony programista z przyjemnością gotów jest zapłacić.

Działanie stosu demonstrujemy w funkcji main. 
void main ()
{
    IStack stack;
    stack.Push (1);
    stack.Push (2);
    cout << "Popped " << stack.Pop() << endl;
    cout << "Popped " << stack.Pop() << endl;
}

1 Ignorowanie konieczności wyłączania w produkcie finalnym asercji oraz włączania w kompilatorze opcji optymalizacyjnych jest jednym z głównych źródeł fałszywej opinii o powolności programów, napisanych w języku C++. Inne tego typu przypadki wiążą się zazwyczaj z niewłaściwym wykorzystywaniem (czyli niezrozumieniem) różnych właściwości języka.