Wskaźniki a tablice

Doświadczeni programiści wiedzą, że w wielu sytuacjach nazwy tablic można traktować jak wskaźniki, a zmienne wskaźnikowe - jak nazwy tablic. Nie ma w tym nic dziwnego - w języku C++ nazwę tablicy implementuje się bowiem jako wskaźnik do jej pierwszego elementu. W praktyce oznacza to, że do danych, wskazywanych przez zmienną wskaźnikową, możemy sięgać tak, jak do tablicy, czyli poprzez operator indeksowania ("[ ]"). I na odwrót - przy pomocy zmiennej wskaźnikowej możemy bez trudu sięgać do dowolnych elementów tablicy. Zmienną wskaźnikową możemy też inkrementować (czyli "zwiększać o jeden element"), co odpowiada przesunięciu wskaźnika do kolejnego elementu tablicy. Oczywiście w każdym przypadku obowiązek zagwarantowania, że wskaźnik rzeczywiście wskazuje na jakiś element tablicy, spoczywa na programiście.

Typowym przykładem tablicy jest łańcuch znaków. W bibliotece standardowej znajduje się funkcja strlen, która oblicza długość napisów zakończonych bajtem zerowym. Spróbujmy napisać własną implementację tej funkcji. Nazwiemy ją StrLen. 
int StrLen (char const str [] )
{
    int i;
    for (i = 0; str [i] != '\0'; ++i)
        continue;
    return i;
}

Jak widać, aby znaleźć długość łańcucha znaków, przeglądamy kolejne elementy tablicy str w poszukiwaniu kończącego ją bajta zerowego, a po znalezieniu go zwracamy odpowiadający mu indeks jako wartość funkcji. Prawda, że to dość oczywisty algorytm?

Zwróćmy jeszcze uwagę na to, że w treści pętli zamiast instrukcji pustej (czyli samotnego średnika) umieściliśmy instrukcję continue. Taka konstrukcja pętli jest czytelniejsza, a przez to bardziej odporna na błędy.

Oto definicja funkcji main, w której testujemy funkcję StrLen, przekazując jej tablicę znaków aString: 
int main ()
{
    char aString [] = "dlugi napis";
    int len = StrLen (aString);
    std::cout << "Dlugosc napisu " << aString << " wynosi " << len << std::endl;
}

A oto bardziej tradycyjna, "zoptymalizowana" wersja funkcji StrLen: 
int StrLen (char const * pStr)
{
    char const * p = pStr;
    while (*p++);
    return p - pStr - 1;
}

W tej implementacji najpierw inicjujemy zmienną wskaźnikową1 p adresem pierwszego elementu tablicy2. Pętla while wygląda natomiast dość tajemniczo. W jednym wyrażeniu:

  1. operatorem * wyłuskujemy wartość znaku, wskazywanego przez wskaźnik p;
  2. sprawdzamy, czy wyrażenie logiczne odpowiadające wartości tego znaku jest prawdziwe;
  3. przy pomocy operatora ++ dokonujemy tzw. opóźnionego powiększenia jednostkowego (ang. post-incrementation) wartości wskaźnika p.
Pętla wykonywana jest tak długo, jak długo znak, który uzyskujemy poprzez wyłuskanie wartości ze wskaźnika p, jest różny od bajta zerowego (innymi słowy: pętlę wykonujemy tak długo, jak długo prawdziwe jest wyrażenie *p != 0)3. Operator opóźnionego powiększenia jednostkowego (++) powoduje przesunięcie wskaźnika p do kolejnego elementu tablicy4. Jednak ta modyfikacja wartości zmiennej p nastąpi dopiero po użyciu jej oryginalnej wartości w wyrażeniu5 (w celu określenia fałszywości bądź prawdziwości warunku kontynuowania pętli).

Rysunek 2. Zmienna wskaźnikowa p początkowo przechowuje informację o położeniu pierwszego znaku łańcucha "Hi!", znajdującego się np. pod adresem 0xe04 (adresy zwyczajowo zapisuje się w notacji szesnastkowej). Kolejne wywołania operatora ++ przemieszczają p poprzez kolejne znaki napisu aż do momentu przetworzenia bajta zerowego.

 

Operator powiększenia jednostkowego występuje w dwóch odmianach, "opóźnionej" i "przyspieszonej". Obie zapisuje się tak samo: jako dwa połączone znaki "plus". Jednak w przeciwieństwie do poznanego już operatora opóźnionego, operator przyspieszony umieszcza się przed zmienną (np. ++p). Jego "przyspieszenie" polega na tym, że zwiększa on wartość zmiennej, na którą działa, przed użyciem jej wartości w wyrażeniu.

Operatory powiększania jednostkowego (działające na zmienną i)
i++ powiększenie opóźnione
++i powiększenie przyspieszone
Operatory pomniejszania jednostkowego (działające na zmienną i)
i-- pomniejszanie opóźnione
--i pomniejszanie przyspieszone

Aby wskaźnikowej wersji funkcji StrLen nadać ducha języka C pozwoliłem sobie pominąć w pustej instrukcji pętli for instrukcję continue. Starym wyjadaczom języka C taki samotny średnik wydaje się zupełnie wystarczającym sygnałem stosowania instrukcji pustej.

W końcu ilość odczytanych elementów tablicy obliczamy jako różnicę dwóch wskaźników pomniejszona jeszcze o jedną jednostkę. To odjęcie "jedynki" bierze się stąd, że bajta zerowego nie traktujemy jako składnika napisu (podczas ostatniego testowania wyrażenia *p++ odczytujemy wartość bajta zerowego, po czym zwiększamy p o jednostkę. Prawdę mówiąc w tego typu testach zawsze za pierwszym razem robię błąd. Muszę więc tracić czas na testowanie poprawności warunku pętli, edycję, kompilację i uruchamianie programu. Jeżeli jednak Czytelnik miał (ma?) problemy ze zrozumieniem implementacji wskaźnikowej, może uważać się za... szczęściarza! A ja nie będę musiał więcej przekonywać Cię, że takiego kodu nie powinno się pisać.

Pozwól, drogi Czytelniku, że po zaprezentowaniu dwóch rozwiązań tego samego problemu zadam Ci teraz pytanie: czy pisząc w przyszłości własny kod funkcji typu StrLen będziesz używać prostszego i bardziej czytelnego stylu tablicowego? Jeżeli odpowiedź brzmi tak, możesz przejść bezpośrednio do lektury następnego paragrafu. Jeżeli jednak nie jesteś jeszcze przekonany do wyższości zapisu tablicowego nad wskaźnikowym, możesz zaznajomić się z bardziej techniczną argumentacją opartą na analizie kodu asemblerowego.

 

Kącik agitatora

Sztuka programowania znajduje się w niezwykłym stanie. Informatyka rozwija się tak szybko, że osoby, które nauczyły się programować w okresie niemowlęctwa języka C, wciąż są bardzo aktywne zawodowo. W wielu innych dziedzinach nauki postęp niejednokrotnie dokonywał się poprzez naturalną wymianę pokoleń6. Jednak rewolucja informatyczna dokonała się za życia jednej generacji. Faktem jest, że wielu programistów zarobiło już tyle pieniędzy, że teraz stać ich na to, by zaangażować się w darmową pracę na na rzecz różnych projektów niekomercyjnych. Jednak wielu innych wciąż posługuje się zestawem starych (np. kilkuletnich) sztuczek, których nauczyli się, programując komputery klasy XT mające 64KB pamięci operacyjnej.

Młodzi programiści uczą się sztuki programowania z kilku klasycznych pozycji, np. podręcznika B. Kernighana i D. Ritchie’go Język C. Proszę mnie dobrze zrozumieć - uważam, że jest to wspaniała książka. Ma jednak jedną wadę - uczy technik programowania, których już od dawna się nie używa.

Z kolei w dziedzinie algorytmów i struktur danych największym poważaniem cieszy się klasyczna seria książek Donalda Knutha "The Art of Computer Programming". Jest to piękny, dogłębnie przemyślany (i niestety niedokończony, przyp. tłum.) zestaw podręczników akademickich. Jednak widziałem już oparte na zawartych w niej ideach implementacje algorytmu quicksort, które wyglądały jak prawdziwe potworki rodem z epoki, gdy nie słyszano nawet o programowaniu proceduralnym.

Jeżeli Czytelnik posługuje się kompilatorem, który nie potrafi zoptymalizować łatwego w pielęgnacji, czytelnego dla człowieka kodu, jeżeli w związku z tym to Czytelnik musi wykonywać część pracy kompilatora, jest to widomy znak, iż nadszedł czas, by kupić nowy kompilator! Pracodawców nie stać już na kupowanie ludzi zamiast kompilatorów. Miej litość dla siebie samego i dla swoich współpracowników, którzy muszą czytać napisane przez Ciebie programy.

 

Podstawowa reguła

Nie zastępuj wskaźnikami operatora [ ]

Uwagi tłumacza

1 Instrukcja char const * p; definiuje zmienną p jako wskaźnik do stałej typu char. Modyfikator const równie dobrze moglibyśmy umieścić przed nazwą typu wskazywanego obiektu (pisząc const char * p;). Taki wskaźnik służy wyłącznie do odczytywania wartości wskazywanych przez siebie obiektów (np. elementów tablic). Można także zdefiniować stały wskaźnik -- w tym celu słowem kluczowym const modyfikujemy nazwę wskaźnika (np. char * const p;). Taki wskaźnik zawsze wskazuje ten sam obiekt, jednak może służyć zarówno do jego odczytywania jak i modyfikacji. Oczywiście łącząc obie te metody można zdefiniować stały wskaźnik do stałej (char const * const p;).

2Zwróćmy uwagę na to, że wskaźnikowa wersja funkcji StrLen pobiera jako swój argument nie nazwę tablicy, lecz zmienną wskaźnikową. Jak już jednak wiemy, nazwa tablicy jest równoważna adresowi jej pierwszego elementu, więc obie deklaracje argumentów funkcji StrLen są sobie równoważne. Dlatego można mówić, że instrukcja char const * p = pStr; inicjuje zmienną p adresem pierwszego elementu tablicy. Jednak na podstawie wskaźnikowej deklaracji funkcji StrLen nie możemy przewidzieć, czy jako jej argument przekazuje się nazwę tablicy, czy też może wskaźnik do pojedynczego znaku. Już choćby z tego powodu deklarację int StrLen (char const str [] ) należy uznać za lepszą od int StrLen (char const * pStr).

3We wskaźnikowej implementacji funkcji StrLen wykorzystaliśmy znany nam już fakt, że jeżeli warunku kontynuowania pętli nie zapiszemy w postaci wyrażenia logicznego (np. while (i != 0)), lecz jako wyrażenie arytmetyczne (np. for (int i = 10; i; i--)), to pętla będzie wykonywana tak długo, jak długo wartość tego wyrażenia jest różna od zera.

4Jeżeli p jest wskaźnikiem do elementu pewnej tablicy, to po wykonaniu instrukcji p++; zmienna p będzie wskazywać na kolejny element tej tablicy niezależnie od tego, jaki jest rzeczywisty rozmiar jej elementów.

5Dlatego przyrostkowy operator ++ nazwaliśmy operatorem "opóźnionego powiększenia jednostkowego".

6Jak wieść gminna niesie, niektóre rewolucyjne koncepcje fizyki, np. teoria kwantowa, zdobyły powszechne uznanie wskutek wymarcia swoich oponentów.