Tablice

Przykład

Tablica to zbiór komórek pamięci przeznaczonych do przechowywania pewnej
liczby danych określonego typu. Każda taka dana stanowi element tablicy.
Tablicę deklaruje się poprzez podanie typu jej elementów, następnie nazwy
tablicy i liczby elementów tablicy.

int TabInt[25] ;

Tak wygląda deklaracja tablicy 25 liczb typu int o nazwie TabInt. W momencie
napotkania takiej deklaracji kompilator rezerwuje pamięć na 25 wartości typu
int. Ponieważ każda wartość typu int zajmuje 4 bajty, to powyższa deklaracja
spowoduje zarezerwowanie 100 bajtów pamięci.

4
bajty

100 bajtów

Elementy tablicy

Do elementów tablicy dostajemy się przez nazwę tablicy i offset. Elementy
tablicy są numerowane od zera, dlatego pierwszy elementem tablicy jest
zawsze

W zadeklarowanej wcześniej tablicy TabInt pierwszym elementem jest TabInt
[0] , drugim TabInt [1] itd.

nazwa_Tablicy[0]

Przykład

Ogólnie mówiąc, Tablica [n] ma n elementów numerowanych odpowiednio

od Tablica[0] do Tablica [n-1].

Zapis za końcem tablicy

Kiedy wstawia się wartość do tablicy, to kompilator oblicza miejsce w pamięci
zarezerwowanej dla tablicy na podstawie rozmiaru pojedynczego elementu i
podanego offsetu.
Załóżmy, że ma się zapisać wartość w tablicy TabInt[5]. Kompilator pomnoży
podany offset równy 5 przez rozmiar każdego elementu, w tym wypadku 4.
Następnie przesunie się o policzoną liczbę bajtów - 20 - od początku tablicy i
zapisze tam wartość.

Błąd słupków ogrodzeniowych

Częstym błędem jest przekroczenie o jeden rozmiaru tablicy i zapis tuż za jej
końcem. Taka pomyłka jest często określana jako „

błąd słupków

ogrodzeniowych

”. Ten problem odnosi się do obliczenia, ile słupków

potrzeba na 5 metrowy płot, jeśli na każdy metr płotu ma przypadać jeden
słupek.

Większość ludzi powie: "No jak to
ile? 5!”

1

2

3

4

5

6

1 m

2 m

3 m

4 m

5 m

Prawidłowa odpowiedz
brzmi 6.

Tak w ogóle to programiści są często bardzo zdziwieni, że np. nie buduje się
budynków począwszy od piętra zerowego. Niektórzy z nich tak się
przyzwyczaili do reguł C++, że gdy chcą wjechać na piąte piętro, to naciskają
w windzie guzik z numerem 4

Inicjalizacja tablic

Prostą tablicę standardowych wartości C++ można zainicjować już w
momencie deklaracji. Po nazwie tablicy należy postawić znak przypisania
(=), a następnie w klamrach podać wartości kolejnych elementów tablicy.

Przykład

int Tablnt[5] = { 111, 222, 333, 444, 555 };

Jeżeli nie określi się w deklaracji rozmiaru tablicy, to kompilator dopasuje go
automatycznie na podstawie liczby wartości inicjalizujących.

int Tablnt[] = { 111, 222, 333, 444, 555 };

Jeżeli chce się poznać liczbę elementów tablicy to możesz ją łatwo obliczyć:

const int SizeTabInt = sizeof(TabInt) / sizeof(TabInt[0]) ;

Nie można inicjalizować tablicy większą liczbą wartości niż wynosi
dopuszczalny rozmiar tej tablicy.

int Tablnt[5] = { 111, 222, 333, 444, 555, 666 };

Jednak wolno napisać tak:

int Tablnt[5] = { 111, 222 };

Tablice obiektów

Każdy obiekt, niezależnie czy jest on standardowym typem C++ czy też
został stworzony przez użytkownika, może być umieszczony w tablicy.
Kiedy deklaruje się tablicę to podaje się typ jej elementów i liczbę tych
elementów (czyli rozmiar tablicy). Kompilator, bazując na deklaracji klasy,
oblicza ile miejsca musi zarezerwować dla deklarowanej tablicy. Klasa musi
posiadać konstruktor domyślny, nie posiadający żadnych parametrów, gdyż
jest on niezbędny w momencie definiowania tablicy.
Dostęp do danych w tablicy jest dwustopniowy. Najpierw trzeba określić
numer elementu w tablicy za pomocą operatora indeksowego ( [ ] ), a
następnie za pomocą operatora kropka ( . ) odwołać się do odpowiedniej
zmiennej lub funkcji wewnętrznej obiektu.

Tablice wielowymiarowe

Nie ma żadnych przeszkód, aby tablica miała więcej niż jeden wymiar. Każdy
wymiar jest reprezentowany w deklaracji przez indeks. Tablica
dwuwymiarowa będzie miała dwa takie indeksy ( [ ] [ ] ), trójwymiarowa trzy
indeksy ( [ ] [ ] [ ] ) itd. Wymiar tablicy może być dowolny, ale w praktyce
większość tablic będzie miała nie więcej niż dwa wymiary.

Załóżmy, że mamy klasę o nazwie POLE. Deklaracja tablicy Plansza będzie
wyglądać następująco:

Przykład

POLE Plansza[8][8];

Te same dane można również reprezentować za pomocą jednowymiarowej
tablicy o 64 elementach:

POLE Plansza[64];

Jednak taka reprezentacja mniej przystaje do rzeczywistości niż tablica
dwuwymiarowa. Na początku gry król stoi na czwartym polu w pierwszej
kolumnie. Licząc od zera, ta pozycja odnosi się do:

Plansza[0][3];

oczywiście przy założeniu, ze pierwszy indeks odnosi się do wierszy, a drugi
do kolumn.

Inicjalizacja tablic wielowymiarowych

Tablice wielowymiarowe można również inicjalizować w momencie deklaracji.
Lista wartości jest przypisywana począwszy od ostatniego indeksu aż do
pierwszego.

Przykład
Jeżeli ma się tablicę: int Tab[5][3] ;
To pierwsze trzy wartości zostaną umieszczone w Tab[0], kolejne trzy w Tab[1]
itd…
Inicjalizacje tej tablicy może wyglądać np. tak:

int Tab[5][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,

14, 15 } ;

Jednak dla większej przejrzystości zapisu lepiej jest pogrupować te liczby za
pomocą klamer zgodnie z wymiarami:

int Tab[5][3] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 },
{10, 11, 12 },
{13, 14, 15 } };

Kompilator pomija wewnętrzne klamry, ale dla użytkownika stanowią one
znaczne ułatwienie w przypisaniu wartości do odpowiednich elementów.
Każda wartość musi być oddzielona przecinkiem. Wszystkie wartości muszą
być umieszczone w klamrach. Cała inicjalizacja kończy się średnikiem.

Przykład

0

0

1

1

2

2

Tab[3][2]

W momencie deklarowania tablicy informowany jest kompilator o liczbie
elementów, które będą przechowywane w tablicy. Kompilator rezerwuje
podaną liczbę miejsca niezależnie od tego czy miejsce to w całości się
wykorzysta czy też nie. Nie ma zatem problemu z deklaracją tablicy jeśli wie
się dokładanie ile elementów jest potrzebne.
Jeżeli jednak liczba elementów jest nieokreślona, to trzeba wykorzystać
bardziej złożone struktury danych.

Tablice wskaźników

Wszystkie omawiane dotychczas tablice były tworzone na stosie. Jednak stos
ma dosyć ograniczoną pojemność w stosunku do np. sterty. Można każdy
obiekt zadeklarować na stercie, a w tablicy przechowywać jedynie wskaźniki
do tych obiektów. Takie rozwiązanie w ogromnym stopniu redukuje pamięć
zajmowaną na stosie.

Przykład

Tablica Dynastia przechowuje nie obiekty klasy KOT, a
wskaźniki do obiektów na stercie.

W pętli na stercie jest tworzone 500
obiektów KOT. Ponieważ tablica jest
przystosowana do przechowywania
wskaźników, dlatego nie są wstawiane
do niej obiekty, a wskaźniki do nich.
W tym przykładzie tablica i wskaźniki w
niej zawarte są przechowywane na
stosie. Jednak wszystkie 500 KOTów
znajduje się na stercie.

Istnieje możliwość umieszczenia całej tablicy na stercie. Wykorzystuje się do
tego new i operator indeksu. Otrzymujemy w ten sposób wskaźnik do obszaru
na stercie przechowującego tablicę.

Deklarowanie tablicy na stercie

Przykład

KOT *Dynastia = new KOT[500];

W ten sposób Dynastia staje się wskaźnikiem na pierwszy element pięciuset
elementowej tablicy obiektów klasy KOT. Innymi słowy, Dynastia jest adresem
elementu Dynastia[0].
Zaletą takiego rozwiązania jest możliwość wykorzystania arytmetyki
wskaźników do zarządzania elementami tablicy Rodzina. Można np. napisać
tak:

KOT *Dynastia = new KOT[500];
KOT *pKot = Dynastia; // pKot wskazuje na Dynastia[0]
pKot->UstawWiek(10);

// niech Dynastia[0] ma

10 lat
pKot++;

// przejdź na Dynastia[1]

pKot->UstawWiek(20);

// niech Dynastia[1] ma

20 lat

Wskaźniki Dynastia i pKot wskazują na początek tablicy. Za pomocą pKot
wywołujemy metodę UstawWiek(). Następnie inkrementujemy wskaźnik tak,
aby wskazywał na następny element tablicy i ponownie wywołujemy metodę
UstawWiek ().

Wskaźnik do tablicy, a tablica wskaźników

Rozpatrzmy trzy różne deklaracje:

KOT Dynastia1[500]; KOT *Dynastia2[500]; KOT* Dynastia3 =

new KOT[500];

Dynastia1 to tablica

500 obiektów klasy

KOT

Dynastia2 to tablica

500 wskaźników do

obiektów klasy KOT

Dynastia3 to wskaźnik

do tablicy 500

obiektów klasy KOT.

Różnice między tymi trzema deklaracjami powoduję skrajnie różne metody
ich obsługi. Można powiedzieć, że Dynastia3 jest wariantem Dynasti1 i są one
całkowicie różne od tablicy Dynastia2.
Widać, jak wskaźniki odnoszą się do tablic. W trzecim przypadku, Dynastia3
jest wskaźnikiem do tablicy. Oznacza to, że adres zawarty we wskaźniku
Dynastia3 jest adresem pierwszego elementu tablicy. Podobnie jest w
przypadku tablicy Dynastia1.

Nazwy wskaźników i tablic

W C++ nazwa tablicy jest jednocześnie nazwą stałego wskaźnika na pierwszy
element tej tablicy. W deklaracji:

KOT Dynastia[50];

Dynastia jest wskaźnikiem do & Dynastia[0], czyli adresem pierwszego
elementu w tablicy Dynastia.
Nazwa tablicy może być wykorzystywana jako stały wskaźnik i na odwrót.
Oznacza to, że np.

Kompilator odpowiada za właściwą obsługę arytmetyki przy dodawaniu,
inkrementacji lub dekrementacji wskaźników. Adres będący wynikiem
dodawania Dynastia+4 nie jest adresem czwartego bajtu począwszy od
początku tablicy, lecz adresem 4 elementu tablicy.
Jeżeli każdy element ma 4 bajty to Dynastia+4 oznacza przesunięcie o 16
bajtów względem początku tablicy. Jeżeli obiekt klasy KOT zajmowałby 20
bajtów (np. 4 zmienne typu int i 2 zmienne typu short) to Dynastia+4
oznaczałoby przesunięcie o 80 bajtów.

Dynastia+4

Dynastia[4]

Przykład

Każdy element KOT jak i sama
tablica Dynastia jest tworzona na
stercie. Zauważ, że tym razem nie
wstawiamy do tablicy wskaźnika,
lecz sam obiekt. Nie jest to tablica
wskaźników, lecz obiektów klasy
KOT.

Usuwanie tablicy ze sterty

pKot jest w każdej iteracji wykorzystywany do stworzenia kolejnego obiektu.

Byłby to wielki problem, gdyby nie fakt, że skasowanie wskaźnika Dynastia
(za pomocą delete) zwolni całą pamięć zarezerwowaną dla tablicy. Kompilator
potrafi usunąć każdy obiekt z tablicy i zwolnić zajmowaną pamięć.

Czy nie pojawia się tutaj niebezpieczeństwo utraty wskaźników do
obiektów w tablicy?

Jeżeli tworzy się obiekt za pomocą
new to zawsze musisz go usunąć za
pomocą delete. Podobnie, gdy tworzy
się tablicę z wykorzystaniem

new

< klasa >

[

rozmiar

]

to kasujesz ją potem za pomocą

delete [ ]

Nawiasy

są

informacją

dla

kompilatora, że skasowaniu ma ulec
cała tablica.

Jeżeli pominie się nawiasy, to usunięty zostałby tylko pierwszy element
tablicy. Można to sprawdzić.

Gratulacje! Właśnie ubyło Nam pamięci!

Tablice znaków (char)

Łańcuch to ciąg znaków. Dotychczas wykorzystywaliśmy tylko stałe łańcuchy.
Jednym z nich był:

W C++ łańcuch jest reprezentowany przez tablicę znaków zakończoną
wartością zero. Możesz zadeklarować łańcuch tak jak każdą tablicę. Np.:

cout « "Hello world!\n"

Ostatni znak '\0' stanowi znacznik końca tekstu. Taki sposób podawania
tekstu, znak po znaku, jest bardzo niewygodny. C++ pozwala na wpisywanie
tekstów do łańcuchów w skróconej formie:

char Czesc[]={'H','e','l','l','o',’’,'W','o','r','l','d','\0' };

Jednak stosując ten zapis trzeba pamiętać o dwóch rzeczach:

char Czesc[] = "Hello World";

1. Zamiast klamer i apostrofów wykorzystuje się znaki cudzysłowu na

początku i na

końcu tekstu.

2. Nie dodaje się pustego znaku (null) końca tekstu. Kompilator dodaje go
automatycznie.

W sumie łańcuch Hello World zajmuje 12 bajtów - 11 bajtów na tekst i 1 bajt
na znak końca (null). Dopuszczalne jest tworzenie niezainicjalizowanych
tablic znakowych. Tak jak w przypadku innych tablic ważne jest, aby nie
wstawiać do nich więcej niż wynosi ich rozmiar.

Przykład

Napotkaliśmy na dwa problemy. Pierwszy polega na tym, że jeśli użytkownik
poda tekst dłuższy niż 79 znaków, to cin będzie pisać poza buforem. Drugi
jest widoczny na wydruku. Jeżeli użytkownik wpisze w tekście spację, to cin
potraktuje ten znak jako koniec tekstu i przestanie zapisywać do bufora.

Żeby rozwiązać powstałe problemy, musimy wykorzystać specjalną metodę
dostępną w cin, a mianowicie get().

cin.get() pobiera trzy parametry:
1. Bufor do wypełniania.
2. Maksymalną liczbę znaków do wczytania.
3. Znak kończący wpisywania.
Domyślnym znakiem kończącym wpisywanie jest znak końca linii.

Przykład

Nie jest niezbędne podanie znaku kończącego, gdyż określona jest wartość
domyślna tego parametru - znak końca linii.

strcpy () i strncpy ()

C++ odziedziczyło po zwykłym C wszystkie biblioteki odpowiedzialne za
zarządzanie łańcuchami znaków. Wśród wielu ciekawych funkcji znajdują się
dwie, służące do kopiowania jednego łańcucha znaków do drugiego: strcpy()i
strncpy().

strcpy() kopiuje całą zawartość jednego łańcucha znaków do podanego
bufora.

Jeżeli tablica źródłowa będzie dłuższa niż docelowa, to funkcja strcpy() będzie
wypełniać pamięć poza końcem tablicy docelowej.

Żeby uniknąć tego niebezpieczeństwa, standardowa biblioteka zawiera
również funkcję strncpy(). Ten wariant pozwala dodatkowo na określenie
maksymalnej liczby znaków do skopiowania. Kopiowanie trwa aż do
napotkania znaku końca tekstu lub gdy zostanie przekroczona podana
maksymalna liczba znaków.

Klasy obsługujące łańcuchy

Większość kompilatorów C++ zawiera duży zbiór klas służących do
manipulacji danymi. Taką klasą jest np. klasa String.
C++ odziedziczyło po C konwencję kończenia tekstu pustym znakiem (null) i
biblioteki zawierające takie funkcje jak strcpy(). Jednak wszystkie te funkcje
nie są wbudowane w obiektowo zorientowaną strukturę języka. Klasa String
oferuje odrębny zbiór danych i funkcji służących do specjalistycznego
manipulowania danymi. Pozwala ona na ukrycie danych przez użytkownikiem.
Jeżeli wasz kompilator nie zawiera takiej klasy (a nawet jeżeli zawiera), to
można napisać własną klasę String.
W minimalnej wersji, klasa String musi zapewnić proste ograniczenia tablic
znakowych. Jak wszystkie tablice, również tablice znakowe są statyczne. Wy
definiujecie ich rozmiar. Tablica zajmuje podaną przez was ilość pamięci
nawet jeśli jej nie wykorzystujecie w całości. Pisanie poza końcem tablicy jest
niedozwolone.
Sprawna klasa String zawsze rezerwuje tyle pamięci ile potrzeba. Jeżeli
zarezerwowanie pamięci nie jest możliwe, to klasa powinna obsługiwać taką
sytuację.

Tablice półdynamiczne i dynamiczne

Jak wspominałem wcześniej można również alokować pamięć na więcej niż
jeden obiekt dowolnego typu. Składnia wtedy jest następująca :

Fundamentalne znaczenie ma fakt, że wyrażenie WYMIAR może być
dowolnym wyrażeniem o dodatniej wartości całkowitej. Wymiar ten może
zatem być wczytany lub w jakiś sposób, wyliczony w trakcie działania
programu - nie musi być znany już w czasie kompilacji (a właściwie
ładowania), tak jak miało to miejsce dla zwykłych tablic.

int *Tab = new int [ WYMIAR ];

Dlatego cały ten proces nazywamy dynamicznym przydziałem pamięci, a
tablice tak utworzone tablicami dynamicznymi.

Można też alokować w ten sposób pamięć na tablice wielowymiarowe, ale są
one wtedy tylko ,,półdynamiczne''. Oznacza to tyle, że tylko jeden, a
mianowicie pierwszy, wymiar może nie być stałą wyliczalną podczas
ładowania programu. Rozpatrzmy przykład

Zauważmy typ zmiennej Tab: jest to wskaźnik do trzyelementowej tablicy
int'ow. Zatem obiektem wskazywanym jest tu nie ,,coś'' typu int, ale cała
tablica int'ów, w tym przypadku o wymiarze 3. Zatem Tab[0] jest taką
tablicą i ma wobec tego rozmiar 12 bajtów (3×4). Odpowiada ona
pierwszemu wierszowi tablicy. Zatem Tab[1] też jest taką tablicą,
odpowiadającą drugiemu wierszowi, i powinno leżeć w pamięci komputera o
12 bajtów dalej. Że tak jest rzeczywiście przekonuje nas wydruk tego
programu (0030191c – 00301910 = c w układzie szesnastkowym, czyli 12 w
układzie dziesiętnym).

Alokujemy tu pamięć na tablicę nSize × 3, gdzie
nSize nie jest znane z góry gdyż jest
wczytywane z klawiatury w trakcie wykonania.
Natomiast drugi wymiar musi być stałą, ogólnie -
wszystkie prócz pierwszego.

Tworzymy zmienną wskaźnikową typu int* i wpisujemy tam adres początku

całej tablicy Tab (o operatorze reinterpret_cast będziemy jeszcze mówić,

na razie powiedzmy tylko, że jest on tu konieczny ze względu na kontrolę

typów: typem Tab nie jest bowiem int*). Traktując następnie PTab jak

jednowymiarową tablicę liczb całkowitych drukujemy kolejne wartości

elementów tablicy.

Przydział pamięci może się nie powieść, na przykład jeśli zażądaliśmy
zarezerwowania zbyt dużej jej ilości. Teoretycznie operator new zwraca
wtedy wskaźnik pusty (należy to zawsze sprawdzać!). W C++ w takich
sytuacjach generowany jest wyjątek typu bad_alloc (z nagłówka new) który
możemy przechwycić i obsłużyć zapobiegając załamaniu programu.

W nieskończonej pętli alokujemy i natychmiast zwalniamy za pomocą
operatora delete coraz większy obszar pamięci. W pewnym momencie
żądamy tej pamięci za dużo; wysyłany jest wyjątek który przechwytujemy,
drukujemy komunikat, i kończymy program.

Przykład

Wydruk nie znaczy, że
komputer

ma

rzeczywiście

1400MB

pamięci - wliczony tu jest
bowiem również obszar
wymiany

(ang. swap),

który zajmuje ok. 1GB

Czasem

zachodzi

potrzeba

dynamicznego

tworzenia

tablic

wielowymiarowych, na przykład dwuwymiarowych, ale takich w których
wszystkie wymiary są określane dynamicznie w trakcie wykonania programu.

Załóżmy, że chcemy zaalokować miejsce na tablicę liczb typu double o
wymiarach 2×3. Chcielibyśmy odnosić się do tej tablicy za pomocą normalnej
składni z użyciem indeksów w nawiasach kwadratowych. Na przykład m[1]
[2] powinno oznaczać element z ,,wiersza'' numer 1 i ,,kolumny'' numer 2
tablicy (macierzy) m.

Wiemy, że jest to skrócony zapis wyrażenia ' *(m[1] + 2)'. Zatem m[1] musi
byś wskaźnikiem typu double*. A zatem m jest tablicą wskaźników, której
kolejne elementy wskazują na początki kolejnych wierszy.

Co oznacza m[1][2]?

To z kolei ' *(m + 1)'; skoro wartością tego wyrażenia ma być wskaźnik typu
double*, to samo m musi być wskaźnikiem do wskaźnika, a więc mieć typ
double**.

A co to jest m[1]?

Przykład

Najpierw tworzymy zmienną macierz2d
typu double** i wpisujemy tam adres
zaalokowanej tablicy wskaźników typu
double*.

Ilość

tych

wskaźników

odpowiada ilości wierszy w macierzy.
Następnie tworzymy właściwą tablicę
liczb. Ich ilość to iloczyn wymiarów. Adres
zawarty w pDumm to adres początku tej
tablicy.

W pętli wypełniamy tablicę wskaźników
do kolejnych elementów wpisujemy
adresy początków wierszy tablicy liczb.
Są one od siebie odległe o tyle
wielokrotności długości jednej liczby typu
double ile wynosi ilość kolumn, czyli jak
długi jest jeden wiersz.

Do funkcji wywołującej zwracamy
zmienną macierz2d, która może być
używana zgodnie ze składnią
macierzową.