Dynamicze tablice w C
2008-05-08 15:17Czasem życie zmusza do pisania w sławetnym i na szczęście zanikającym już języku C. A tam nie ma chociażby takich luksusów jak STL z niezastąpionymi pojemnikami. O wszelkie struktury danych trzeba zatroszczyć się samemu, co obejmuje także tak podstawowe jak dynamiczne tablice.
Jak wiadomo, takie tablice należy samodzielnie alokować, zmieniać ich rozmiar (z kopiowaniem zawartości) oraz zwalniać, gdy nie są już potrzebne. Najwyraźniej więc wybitnie przydatne są tu funkcje malloc i free, prawda? Otóż nieprawda :)
O wiele wygodniej jest bowiem używać funkcji realloc:
- tab = (int*)realloc(tab, tab_size * sizeof(int));
Jej nazwa wskazuje, że jej głównym przeznaczeniem jest zmiana rozmiaru już zaalokowanego kawałka pamięci. Zazwyczaj sprowadza się to zresztą do przydzielenia nowego, skopiowania tam zawartości starej porcji i zwolnienia jej. Jednakże w dwóch szczególnych przypadkach realloc zachowuje się inaczej – zależy to od parametrów, jakie jej podamy:
- jeżeli pierwszym parametrem będzie wskaźnik pusty (
NULL), funkcja przydzieli pamięć w ilości bajtów wyrażonej drugim parametrem – czyli zachowa się jakmalloc - jeśli zaś drugim parametrem będzie zero, to funkcja spróbuje zwolnić kawałek pamięci, na który pokazuje wskaźnik będący pierwszym parametrem – czyli zachowa się jak
free
To sprawia, że możemy używać funkcji realloc w postaci wywołania podobnego jak powyżej zawsze wtedy, gdy musimy zmienić rozmiar tablicy. Można na przykład dodać do niej element w taki oto sposób:
- int* AddInt(int* tab, size_t* tab_size, int elem)
- {
- int* new_tab = (int*)realloc(tab, (*tab_size + 1) *sizeof(int));
- new_tab[(*tab_size)++] = elem;
- return new_tab;
- }
Nie musimy się martwić, czy tablica została wcześniej zaalokowana czy nie. Analogicznie wygląda usuwanie elementów z końca lub początku tablicy – wówczas nie trzeba przejmować się tym, czy z tablicy coś zostanie. Tak naprawdę opakowywanie obu tych operacji w funkcje nie jest nawet specjalnie potrzebne.
Jedynym warunkiem, aby to wszystko działało, jest odpowiednie zainicjowanie wskaźnika na tablicę oraz zmiennej przechowującej jej rozmiar – co jest aczkolwiek dość oczywiste:
- int* tab = NULL;
- size_t tab_size = 0;
I to właściwie wszystko. W sumie więc nie jest to może std::vector, ale w C nie ma co wybrzydzać :)
-
deely:
May 8th, 2008 o 15:58Pomijając fakt, że jest to strasznie nieoptymalne rozwiązanie, to faktycznie – działa. Ale w przypadku dodawania do tablicy w pętli po jednym int, czy częsta reallokacja dużej przestrzeni pamięci jest trochę bez sensu.
-
Xion:
May 8th, 2008 o 22:43Oczywiście dla większej wydajności powinno się robić tak, to robią wektory STL – czyli oprócz rozmiaru trzymać też tzw. pojemność (capacity). Pojemność jest równa liczbie elementów, na które starczy miejsca bez realokacji. Jeśli właściwy rozmiar tablicy osiągnie lub przekroczy tę pojemność, należy odpowiednio ją zwiększyć (i realokować) – zwykle dwukrotnie.
Recent posts
