Wskaźniki i tablice w C oraz C++
Wskaźniki (ang. pointers) są jednym z najważniejszych zagadnień do poznania podczas nauki języków C oraz C++. Wiele osób rozpoczynając naukę któregoś z tych języków (niezależnie od tego czy z własnej chęci czy z konieczności) nie może zrozumieć zasady działania wskaźników, ponieważ nie ma wystarczających informacji na temat gromadzenia danych w pamięci komputera, a to jest kluczowa wiedza potrzebna do zrozumienia "idei" wskaźników.
Gromadzenie danych w pamięci komputera
Jak zapewne każdy wie, jednostką ilości danych cyfrowych (zapisanych w formie dyskretnej systemem dwójkowym) jest bajt (ang. byte), czyli osiem bitów. A osiem bitów to dokładnie tyle ile mieści standardowa komórka pamięci w komputerach PC.
Komórki pamięci są numerowane. Numer komórki zwany jest jej adresem. Adresy zwykle podaje się w postaci szesnastkowej (heksadecymalnej - używając systemu liczbowego o podstawie 16). Charakterystyczną cechą tego zapisu jest to, że zazwyczaj przed liczbą dostawia się przedrostek 0x, a liczby odpowiadające wartościom dziesiętnym od 10 do 15 zastępuje się literami - cyframi kolejno A do F. Przykład: 0x2FFA9C (w systemie dziesiętnym 1047196).
Skoro jedna komórka pamięci jest w stanie pomieścić osiem bitów, to maksymalna wartość liczbowa, która tam może się znaleźć to 255 (1*20+1*21+1*22+1*23+1*24+1*25+1*26+1*27). Co jeśli chcemy zapisać w pamięci liczbę większą niż 255? Do tego celu wykorzystuje się kolejne komórki pamięci. Dzięki temu, bity z dołączonej komórki mają wartości 28, 29 itp.
Mała dygresja. Procesory Intela nadają wartości kolejnym bitom od prawej do lewej (tzn. patrząc od początku pamięci liczba zaczyna się najmniej znaczącym bitem (LSB - 20). Jednak istnieją procesory (na przykład niektóre procesory Motoroli) które liczą w odwrotnym kierunku. Tzn. po stronie początku pamięci znajduje się bit najbardziej znaczący (MSB).
Przyjrzyjmy się poniższemu schematowi, przedstawiającemu graficznie sposób zapisywania danych w pamięci:
Na schemacie przedstawiono dwanaście komórek pamięci o adresach od 0x0 do 0xB. W komórkach od 0x2 do 0x5 znajduje się liczba 32-bitowa (czterobajtowa). Taką wielkość ma typ int na większości systemów operacyjnych i większości kompilatorów. W czterech komórkach pamięci można zapisać liczbę od 0 do 4294967295 bez znaku lub od -2147483648 do 2147483647 (w tym wypadku jeden bit jest używany jako informacja o znaku liczby). W komórce 0x8 znajduje się liczba ośmiobitowa (na przykład typ char).
Zielona strzałka, choć już jest znacząca, na razie nas nie interesuje.
Wydaje mi się, że sposób zapisywania danych w pamięci można uznać za wystarczająco opisany. Czas przejść dalej.
Bo wszystko przekazuje się przez wartość...
Przeanalizujmy działanie działanie takiej funkcji:
void funkcja(int a) {
a += 2;
}
Przeanalizujmy taki fragment programu:
int a=8;
printf("Przed: %d\n", a);
funkcja(a);
printf("Po: %d\n", a);
Jak zapewne wszyscy się domyślają uruchomienie programu zawierającego taki kod da w wyniku:
Przed: 8 Po: 8
Dlaczego tak się dzieje? Przecież funkcja powiększyła wartość zmiennej o dwa! Powinno być dziesięć. Ale nie jest... Przekazywanie parametrów funkcjom w języku C (oraz C++) odbywa się przez wartość. Oznacza to, że nie jest przekazywana sama zmienna, ale tylko jej zawartość. A jeśli nie została przekazana sama zmienna to nie można jej zmodyfikować. W przykładzie do funkcji została przekazana wartość zmiennej a, czyli 8. W funkcji powstała zmienna lokalna (występująca tylko w obrębie tej funkcji) również o nazwie a. W rzeczywistości może się nazywać dowolnie (oczywiście zgodnie z warunkami nazywania zmiennych, tj. rozpoczynanie od litery, tylko litery i cyfry itd.). Może nawet (tak jak w tym przypadku) nazywać się tak jak istniejąca już wcześniej zmienna, ponieważ zakres istnienia tych zmiennych nie pokrywa się (jedna zmienna istnieje tylko w tej funkcji, druga zmienna istnieje wszędzie poza tą funkcją oraz ewentualnymi innymi funkcjami, chyba, że jest to zmienna globalna).
Przykładowa funkcja nie spełnia swojego zadania. Jednak jest na to sposób. Wystarczy, żeby zwracała wartość:
int funkcja(int a) {
a += 2;
return a;
}
Oraz wywołanie:
int a=8;
printf("Przed: %d\n", a);
a= funkcja(a);
printf("Po: %d\n", a);
Wynik działania tego kodu wygląda tak:
Przed: 8 Po: 10
Czyli teraz jest wszystko w porządku!
Teraz rozważmy następujący problem. Piszemy funkcję, która przyjmuje dwa parametry. Funkcja porównuje ze sobą dwie podane w parametrach wartości i modyfikuje tę większą na przykład mnożąc ją przez trzy. W przypadku gdy wartości są sobie równe do jednej z nich (nie jest ważne której) dodaje jeden, a od drugiej odejmuje jeden.
void razytrzy(int a, int b) {
if(a > b) a *= 3;
else if (b > a) b *= 3;
else { a += 1; b -= 1;}
}
Dobrze, ale jak zwrócić obie wartości? Korzystając z instrukcji return można zwrócić z funkcji tylko jedną wartość, a wtedy nie będzie wiadomo, która wartość była większa i została zmodyfikowana. Jeszcze gorsza sytuacja jest w przypadku, gdy wartości były równe. Wtedy obie wartości były modyfikowane, a zwrócona może być jedna. Ciężki orzech do zgryzienia.
W takim przypadku z pomocą przychodzą właśnie wskaźniki.
Czym jest ten wskaźnik?
Wskaźnik to zmienna (zwana zmienną wskaźnikową), która zawiera adres pierwszej komórki pamięci, w której przechowywana jest inna zmienna. Jeśli zmienna zajmuje więcej niż jedną komórkę pamięci to wskaźnik wskazuje na pierwszą z tych komórek.
Dla każdego wskaźnika określany jest jego typ. Wskaźnik typu int wskazuje na zmienną typu int. Dzięki temu, kompilator wie ile komórek w pamięci zajmuje zmienna rozpoczynająca się w komórce, na którą wskazuje wskaźnik.
Operatory związane ze wskaźnikami
Nierozłącznie ze wskaźnikami związane są dwa operatory. Są to operator wyłuskania, który jest zapisywany jako gwiazdka (*) oraz operator pobrania adresu - &.
Oba te operatory są operatorami przedrostkowymi (zapisuje się je przed zmienną) oraz jednoargumentowymi.
Operator pobrania adresu - &
Operator pobrania adresu zwraca adres (numer komórki pamięci) zmiennej, która jest jego argumentem. Przykład:
p = &x;Do zmiennej p przypisana zostaje liczba będąca adresem zmiennej x.
Operator wyłuskania - *
Operator wyłuskania pozwala na odwołanie się do zawartości komórki pamięci lub komórek pamięci rozpoczynających się od podanego jako argument adresu (zapisanego na przykład w innej zmiennej). Przykład:
*p += 7;Do zmiennej umieszczonej pod adresem p dodawane jest siedem.
Tworzenie wskaźnika
Właściwie proces tworzenia wskaźnika już opisałem w przykładach użycia operatorów wyłuskania i pobrania adresu, ale zacznijmy od początku. Przypomnijmy sobie wcześniejszy schemat:
Najpierw tworzymy jakąś zmienną (na przykład typu int).
int abc;Załóżmy, że szczęśliwym trafem, zmienna ta została przez program umieszczona w komórkach od 0x2 do 0x5. Na razie jej wartością jest poprzednia wartość tych komórek, czyli jakieś nic nieznaczące dane.
Kolejnym krokiem jest stworzenie wskaźnika na zmienną typu int.
int *p;Typ wskaźnika jest równocześnie typem zmiennej, na którą wskazuje. W deklaracji wskaźnika należy użyć gwiazdki, po to by dać do zrozumienia kompilatorowi, że jest to zmienna wskaźnikowa. Załóżmy, że zmienna p została umieszczona w komórce pamięci 0x8 (rozmiar tej zmiennej nie jest ważny).
Przypiszmy adres zmiennej abc do wskaźnika p.
p = &abc;Operacja tutaj wykonana jest graficznie pokazywana przez zieloną strzałkę ze schematu.
Podczas tworzenia zmiennej wskaźnikowej można od razu przypisać jej jakiś adres. Wykonuje się to w następujący sposób:
int *p = &abc;Podczas normalnego przypisywania adresu zmienna wskaźnikowa nie było poprzedzona operatorem wyłuskania. Tutaj również nie jest. Gwiazdka w tym przypadku nie pełni funkcji operatora ale informatora. Informuje kompilator, że tworzona zmienna jest zmienną wskaźnikową, a nie wyłuskuje adresu.
Użycie wskaźnika
Kiedy wskaźnik wskazuje już na jakąś zmienną, aby odwołać się do jej zawartości należy skorzystać z operatora wyłuskania. Dwie poniższe linie są ze sobą równoważne, ponieważ przypiszą wartość do tej samej (tych samych) komórek pamięci.
abc = 7;
*p = 7;Na początku klasyczne przypisanie: do zmiennej abc przypisuje się wartość 7. W następnej linii, do komórek pamięci zaczynających się od adresu, który jest zapisany w zmiennej p przypisuje się wartość 7. A ponieważ w tych komórkach pamięci znajduje się zmienna abc to w rezultacie zmienia się jej zawartość.
Zgodnie z przykładowym rysunkiem, zawartość zmiennej p to 0x2. Można powiedzieć, że użycie gwiazdki - operatora wyłuskania magicznie przenosi nas pod wskazany adres. Pod tym adresem dokonujemy modyfikacji zawartości komórek (tylu komórek ile wynika z wielkości zmiennej, a to określa jej typ).
Przekazywanie parametru przez wskaźnik
Powróćmy do problemu funkcji porównującej dwie wartości i, zależnie od tego która jest większa, modyfikującej je. Bez pomocy wskaźników nie dało się rozwiązać tego problemu. Ograniczała nas konieczność przekazywania argumentów przez wartość, przez co pierwotna zmienna pozostawała nietknięta.
Wskaźników ten problem dotyczy również, ale dotyczy on tylko samej zmiennej wskaźnikowej, a nie tego na co ona wskazuje. Ponieważ przekazując wskaźnik funkcji przekazujemy tylko sam adres. To funkcja już sama zatroszczy się o zmodyfikowanie zawartości komórek pod podanym adresem.
Przeanalizujmy funkcję:
void razytrzy(int *a, int *b) {
if(*a > *b) *a *= 3;
else if (*b > *a) *b *= 3;
else { *a += 1; *b -= 1;}
}W nagłówku funkcji wyraźnie zostało zaznaczone, że jej argumenty są wskaźnikami. Funkcja teraz nie modyfikuje już ani zmiennej a ani zmiennej b. Porównywanie tych zmiennych nie miałoby sensu, bo ich zawartością są adresy komórek. Modyfikowane przez funkcję są komórki pamięci wskazywane przez adresy zawarte w a i b. Argumenty przekazane przez wartość nie musiały być zmieniane (i nie zostały). Zmianie zostały poddane komórki pamięci nie przekazane funkcji bezpośrednio.
Wynika z tego, że w C nie istnieje inny sposób przekazywania argumentów jak przez wartość. Przekazywanie przez wskaźnik jest tylko sztuczką, która umożliwia obejście ograniczeń przekazywania przez wartość.
Ale samo wywołanie funkcji też musi ulec zmianie. Nie wpisujemy jako parametru samej zmiennej, ponieważ funkcja będzie się wtedy odwoływać do pamięci o adresie takim jak zawartość zmiennej (nie wskaźnika), a ta wcale nie musi należeć do tego uruchomionego programu. Takie postępowanie jest zabronione i zazwyczaj systemy operacyjne chronią pamięć poszczególnych procesów przed dostępem innych procesów. Funkcji należy podać jako parametr adres tej zmiennej. Można tego dokonać na dwa sposoby, które w rzeczywistości niczym się nie różnią.
int x=8, y=23;
int *px = &x, *py = &y;
/* można oczywiście zapisać to rozdzielając deklarację i inicjalizację wskaźników */
razytrzy(px, py); //przekazanie zawartości wskaźników
razytrzy(&x, &y); //przekazanie adresów zmiennychKiedy nie ma rzeczywistej potrzeby tworzyć wskaźnika do zmiennej, lepiej jest zmiennej przekazać jej adres. Wskaźnik do zmiennej zawiera przecież jej adres.
Tablice
Tablice są również ściśle związane ze wskaźnikami. Nazwa tablicy (sama nazwa, bez indeksu) jest wskaźnikiem do jej pierwszego elementu. Dlatego zamiast tablicy, można funkcji przekazać wskaźnik do niej.
void funkcja(int *tablica) {
;
}A wywołanie:
int tab[20];
funkcja(tab);Niestety przekazując w ten sposób, nie można stwierdzić iluelementowa jest tablica. Jeśli ta wielkość nie jest znana należy, jako dodatkowy parametr, przekazać funkcji wielkość tej tablicy.
Inkrementacja i dekrementacja wskaźnika
Sam fakt, że nazwa tablicy jest wskaźnikiem do jej pierwszego elementu nie byłby tak ważny, gdyby nie istniała możliwość inkrementacji i dekrementacji adresu we wskaźniku.
Tablica jest szeregiem zmiennych tego samego typu. Kolejne elementy tablicy są ułożone w sąsiadujących ze sobą komórkach. Załóżmy, że mamy tablicę czterech elementów typu short int (najczęściej po dwa bajty - dwie komórki pamięci).
Tablica znajduje się w komórkach o adresach od 0x1A do 0x21. Każdy element tablicy zajmuje dwie sąsiadujące ze sobą komórki pamięci (elementy zaznaczone są naprzemiennymi kolorami). W komórkach 0x22 i 0x23 istnieje już inna zmienna.
short int tablica[4];
short int a;Do elementu tablicy można odwołać się przez offset, np. tablica[2] odwołuje się do trzeciego (liczymy od zera) elementu tablicy.
Jednak przeanalizujmy ten kod:
short int tablica[4] = {1, 2, 3, 4};
printf("%d %d %d %d\n", tablica[0], tablica[1], tablica[2], tablica[3]);
printf("%d %d %d %d\n", *tablica, *(tablica+1), *(tablica+2), *(tablica+3));Wynikiem działania takiego kodu będzie:
1 2 3 4 1 2 3 4
Wyniki obu wywołań funkcji printf() są identyczne!
Analizując. Po stworzeniu tablicy i jej inicjalizacji wyświetlamy po kolei wszystkie jej elementy (można to oczywiście zrobić w pętli). Na początku przez odwołanie bezpośrednie do tablicy (przez offset). Następnie wykonujemy to samo, ale przez wskaźniki. Wskaźnik tablica odwołuje się do pierwszego elementu (o indeksie 0) tablicy. A więc wywołanie *tablica zwraca wartość, która jest w pierwszym elemencie tej tablicy. Następne wywołanie to *(tablica+1). Czyli wyłuskujemy zawartość komórek pamięci rozpoczynających się od adresu tablica+1. Zakładając, że ten przykład jest przedstawiony na powyższym schemacie, należy zauważyć, że adres pierwszego elementu to 0x1A, więc tablica+1 to 0x1B. Odwołanie się do *(tablica+1) powinno zwrócić nieprawidłowe dane. Ale nie zwraca. Ponieważ offset (w tym przypadku to +1) to nie jest liczba podająca o ile komórek pamięci od początku jest usytuowana zmienna, ale liczba wskazująca o ile segmentów zajmowanych przez konkretny typ zmiennej dalej jest usytuowana zmienna. Czyli w tym przypadku +1 przesuwa wskaźnik o dwie komórki pamięci. Offset +2 przesunie o cztery komórki pamięci. Gdyby to była tablica zmiennych typu int, zajmujących cztery bajty to każdy offset przesuwałby wskaźnik o kolejne cztery komórki.
A gdyby wskaźnik poddać operacji inkrementacji (++) lub dekrementacji (--)?
short int tablica[4] = {1, 2, 3, 4};
printf("%d %d %d %d\n", *(tablica++), *(tablica++), *(tablica++), *tablica);Ten kod niestety się nie skompiluje. Dlaczego? Dlatego, że oryginalnego wskaźnika do tablicy nie można modyfikować (ponieważ jest on cont). Po modyfikacji tablica mogłaby zostać stracona, bo jej początek byłby w miejscu, na który wskazuje ten wskaźnik.
Ale problem można rozwiązać nieco inaczej. Stwórzmy wskaźnik do tej tablicy - zmienną, która może być modyfikowana bez problemu.
short int tablica[4] = {1, 2, 3, 4};
short int *p = tablica;
int i;
for(i=0; i<=3; i++) {
printf("%d\n", *p);
p++;
}Wynikiem działania tego programu będzie:
1 2 3 4
Proste i czytelne. Wskaźnik do tablicy jest z każdym krokiem inkrementowany, więc co krok wskaźnik wskazuje na następny element tablicy. Kod ten jest równoważny temu:
short int tablica[4] = {1, 2, 3, 4};
short int *p = tablica;
int i;
for(i=0; i<=3; i++) {
printf("%d\n", *(p+i));
}Tę właściwość najlepiej wykorzystuje się w funkcjach. Jako parametr do funkcji przekazuje się nazwę tablicy. W funkcji tworzy się lokalna zmienna, którą można modyfikować i dzięki której mamy dostęp do elementów tablicy.
void funkcja(int *w) {
*w += 1;
w++;
*w += 2;
}Ta funkcja modyfikuje dwa pierwsze elementy przekazanej tablicy. Jednak podczas operowania na tablicy przy pomocy wskaźnika pojawia się pewien problem... Jaki?
Wyjście poza zakres
Każda tablica jest ograniczona. Przekazując funkcji wskaźnik do tablicy, funkcja w ogóle nie ma pojęcia jak wielka jest ta tablica. Przeanalizujmy przykład opierający się na schemacie:
Funkcja:
void funkcja(short int *p) {
int i;
for(i=0; i<=4; i++) {
printf("%d\n", *p);
p++;
}
}Kod:
short int tablica[4] = {1, 2, 3, 4};
short int a = 999;
funkcja(tablica);
Jeśli ułożenie komórek w pamięci przedstawia schemat (tablica od 0x1A do 0x21, a w 0x22 i 0x23) to wynikiem działania programu będzie:
1 2 3 4 999
Przecież tablica ma tylko cztery elementy, a liczba 999 nie jest jej częścią! Jak to się stało?
Funkcja nie zna wielkości tablicy i w tym przykładzie popełniła błąd zwany "wykroczeniem poza zakres". Liczba 999 oczywiście jest wartością zmiennej a, która, można powiedzieć, że jest "piątym elementem czteroelementowej tablicy", ponieważ jest umieszczona w pamięci bezpośrednio za nią. W tym przypadku program działa błędnie, ale nie narusza ochrony pamięci. Jednak, gdyby za tablicą był obszar pamięci nie należący do danego procesu, program z pewnością zakończyłby działanie (a właściwie to system operacyjny zakończyłby jego działanie), ponieważ próbowałby odwołać się do pamięci, do której nie ma dostępu. Jest to bardzo częsty błąd!
Przeciwdziałanie błędowi wyjścia poza zakres
Można się tego błędu pozbyć w łatwy sposób. Wystarczy przekazać funkcji wielkość tablicy.
void funkcja(short int *p, int rozmiar) {
int i;
for(i=0; i<rozmiar; i++) {
printf("%d\n", *p);
p++;
}
}Oraz wywołanie:
funkcja(tablica, 4);W ten sposób funkcja nie odwoła się do elementu spoza tablicy.
W rzeczywistości kompilator nie lokuje zmiennych w pamięci bezpośrednio obok siebie. Jest to postępowanie właśnie z powodu występowania błędu wyjścia poza zakres (często spowodowanego błędem "słupka w płocie" - zapomnieniem tego, że zaczynamy liczyć od zera, a nie od jednego). Pomiędzy sąsiadującymi zmiennymi zawsze jest kilka komórek pamięci nieprzypisanych do żadnej zmiennej. Oczywiście nie są to puste komórki, ponieważ nie istnieje coś takiego jak "pusta komórka". Mogą tam być ślady działania programu, który wcześniej wykorzystywał te komórki, a mogą to być zupełnie losowe wartości ustawione podczas włączenia zasilania w komórkach pamięci.
Dla jeszcze większego bezpieczeństwa możemy stworzyć tzw. zmienne strażników. Bezpośrednio po deklaracji tablicy deklarujemy zmienną, która nie zostanie wykorzystana, a jej jedynym celem będzie zajmowanie pamięci za tablicą. Oczywiście nigdy nie mamy pewności, że system operacyjny rozmieści te zmienne obok siebie, ale jest to dość powszechnie stosowany sposób dodatkowego zabezpieczenia.
int tablica[20];
int straznik;Oprócz kilku komórek nieużywanej pamięci, za tablicą będą jeszcze komórki zmiennej straznik. Ten obszar pamięci może być swobodnie modyfikowany i jego modyfikacja nie spowoduje "załamania" programu, co nie oznacza, że program będzie działać poprawnie.
Na zakończenie!
Nie bójmy się stosować wskaźników!