Programming, graphics, games, media, C++, Windows, Internet and more...
Uczy się programowania. Poznaje język i różne biblioteki. Ma dużo pomysłów i nawet sporo potrafi napisać. Ma tylko jeden problem - jak przechowywać obiekty? Do wszystkiego używa pojedynczych zmiennych, zwykłych statycznych tablic albo różnych najdziwniejszych sposobów. Tak wygląda sylwetka niejednego początkującego programisty. Podczas mojej praktyki zawsze spotykałem się z takimi osobami. Pamiętam, jak jedna z nich postawiła nawet w Delphi na okienku pole listy (taką normalną kontrolkę Windows) i uczyniła ją niewidzialną używając jej tylko do przechowywania wewnętrznych danych w swoim programie. Oczywiście w postaci łańcuchów tekstowych, bo tylko takie lista mogła przechowywać.
Przychodzi podczas nauki programowania taka chwila, że niezbędne jest poznanie dziedziny, której nazwa to struktury danych. Trzeba nauczyć się, jak pisać własną kolekcję obiektów danego rodzaju (np. linijek tekstu w twoim edytorze czy potworków w twojej grze), jak przechowywać ją w pamięci, jak operować na niej i jak przechowywać ją na dysku (serializować).
Dostępnych jest wiele książek, które w tytule mają "algorytmy" i "struktury danych". Jednak ich poziom może odstraszać powodując mylną opinię, jakoby ta dziedzina była bardzo trudna. W niniejszym artykule postaram się przystępnie opisać jedynie najważniejsze i najużyteczniejsze struktury danych koncentrując się na nich od strony praktycznej, ponieważ wierzę, że algorytmy są tylko dodatkiem do nich.
Do zrozumienia artykułu wymagana jest znajomość:
Artykuł obejmuje:
Zanim przejdziemy do omawiania pierwszych struktur danych, chciałbym napisać ogólnie o STL, którego będziemy później używali.
Biblioteka standardowa C++ to zbiór funkcji i innych elementów napisanych w C++, które wchodzą w skład standardu. Oznacza to, są sprawdzone, dobre, szybkie, a także przenośne. Można ich używać na dowolnej platformie (np. Windows, Linux), bo biblioteka standardowa jest dołączana do kompilatorów C++.
STL (ang. Standard Template Library) to najważniejsza część biblioteki standardowej. Zawiera zbiór użytecznych szablonów klas, zwłaszcza uniwersalnych struktur danych. Warto ich używać, bo nie ma sensu pisać wszystkiego samemu i wyważać otwartych drzwi. Lepiej skupić się na pisaniu właściwego programu.Oto przykład kodu używającego biblioteki standardowej:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v;
v.push_back(10);
std::cout << v[0] << std::endl;
return 0;
}
Można tu zauważyć kilka rzeczy:
H.std. W praktyce oznacza to, że zawsze trzeba go poprzedzać
przedrostkiem std::.<>.Jeśli niewiele z tego rozumiesz, nie przejmuj się. Wszystko wyjaśni się w dalszej części.
Każdą rzecz można zrobić na różne sposoby. Nas szczególnie będą interesowały algorytmy operujące na strukturach danych, np. sortujące pewne elementy czy wyszukujące w zbiorze dany element. Jedne sposoby są gorsze, inne lepsze. Dlatego wymyślono pewien sposób ich oceniania.
Ilość operacji potrzebnych do wykonania naszego zadania jest zależna od
ilości danych, na jakich ma operować. Jeśli liczbę elementów oznaczymy
przez n, możemy powiedzieć, że złożoność algorytmu jest jakąś
funkcją f(n). Ponieważ taka funkcja może być bardzo skomplikowana,
warto wprowadzić pewne ogólne oznaczenie
klasy złożoności. Właśnie do tego służy notacja dużego O.
Oto niektóre najpopularniejsze klasy złożoności ułożone w kolejności od najlepszych (wymagających najmniej operacji) do najgorszych (wymagających najwięcej operacji):
O(1) Oznacza, że ilość operacji jest stała i nie zależy od ilości danych,
na jakich operujemy.O(log n) Występuje wtedy, gdy zbiór jest dzielony
na coraz to mniejsze części.O(n) Oznacza, że ilość operacji do wykonania jest wprost proporcjonalna
do ilości danych, np. kiedy trzeba przebiegnąć po wszystkich elementach
zbioru.O(n2) Oznacza, że ze wzrostem ilości elementów
ilość potrzebnych operacji wzrasta bardzo szybko, np. kiedy trzeba
przebiegnąć po wszystkich elementach, a dla każdego z nich jeszcze raz
przebiegać po wszystkich.
Rozpoczynamy omawianie najważniejszych struktur danych. Dzięki nim będziesz mógł w swoich programach przechowywać w pamięci kolekcje obiektów dowolnego rodzaju. Dzięki dobraniu struktury odpowiedniej do konkretnych potrzeb operacje na niej będą proste i wydajne (szybkie). Pokażę sposoby pisania własnych struktur danych, jak również używania tych wbudowanych w STL.
Tablica jednowymiarowa to zbiór umieszczonych kolejno po sobie w pamięci elementów tego samego rodzaju i tej samej wielkości (np. liter). Spójrz na poniższy rysunek. Nie przejmuj się ilością różnych szczegółów na nim - będziemy do niego wracali i po kolei omawiali te szczegóły.
Wektor to inna nazwa tablicy jednowymiarowej. To prawda,
że wektor znany z lekcji matematyki to taka strzałka na wykresie. Jednak
w zapisie liczbowym wektor wygląda tak: [3, 7]. Jak widać, jest to
ciąg kilku (tutaj - dwóch) elementów jakiegoś rodzaju (tutaj - liczb),
a więc wszystko się zgadza.
Najprostszą implementacją wektora jest zwykła, statyczna tablica. Jeśli znasz choć trochę język C++, nie powinieneś mieć problemów ze zrozumieniem takiego kodu:
// stały rozmiar tablicy const int SIZE = 16; // tablica char tab[SIZE]; // wypełnienie jej kolejnym literami for (int i = 0; i < SIZE; i++) tab[i] = 'A' + i; // wypisanie środkowego elementu std::cout << tab[SIZE/2] << std::endl;
Rozmiar tablicy warto zawsze przechowywać pod jakąś nazwą - w stałej, a nie wpisywać za każdym razem liczbę. Dzięki temu wystarczy go zmienić tylko w jednym miejscu.
Tablica przechowuje znaki (typ char), ale równie dobrze mogą to
być obiekty dowolnego typu - liczbowego, wskaźnikowego czy nawet
zdefiniowanego przez ciebie typu strukturalnego albo klasy, wskaźniki
na klasę itd.
Indeks to liczba zapisywana w nawiasie kwadratowym [],
dzięki której odwołujemy się do danego elementu tablicy. Elementy są
ponumerowane po kolei od 0 do SIZE-1. W takim też zakresie
zmienia się w pętli wypełniającej zmienna i. Indeksy kolejnych
elementów są napisane nad elementami na rysunku powyżej.
Dlaczego indeksuje się od 0, a nie od 1? Ponieważ taki sposób jest najbardziej naturalny. Żeby dostać się do któregoś elementu, komputer bierze miejsce w pamięci, gdzie znajduje się tablica i dodaje do niego indeks pomnożony przez rozmiar pojedynczego elementu:
pozycja = pozycja_tablicy + (indeks * rozmiar_elementu)
Kiedy pierwszy element ma indeks 0, wynikiem będzie:
pozycja = pozycja_tablicy + (0 * rozmiar_elementu) = pozycja_tablicy
Tak więc pierwszy element zaczyna się od miejsca, gdzie zaczyna się sama zmienna tablicowa, a każdy następny jest o rozmiar elementu dalej - wszystko się zgadza!
W powyższym przykładzie ostatnia instrukcja wypisuje element o indeksie
SIZE/2 = 16/2 = 8, czyli element dziewiąty. Dziewiątą literą jest
I.
Zwykła, statyczna tablica musi mieć rozmiar znany już podczas kompilacji, czyli podany w postaci liczby lub stałej. Nie może to być zmienna, dlatego nie można np. poprosić użytkownika o podanie rozmiaru tablicy i utworzyć tablicy o takim rozmiarze. To wymaga użycia tablicy dynamicznej opartej na wskaźnikach:
// zmienna na rozmiar int size; // użytkownik podaje rozmiar std::cin >> size; // UTWORZENIE TABLICY char *tab = new char[size]; // wypełnienie jej kolejnym literami for (int i = 0; i < size; i++) tab[i] = 'A' + i; // wypisanie ostatniego elementu std::cout << tab[size-1] << std::endl; // USUNIĘCIE TABLICY delete [] tab;
Jak widać, jej używanie nie różni się od używania zwykłej tablicy statycznej z wyjątkiem tego, że trzeba ją przed użyciem utworzyć, a po użyciu usunąć. Szczegóły tych czynności należą już do dziedziny zwanej wskaźnikami i nie będę ich tutaj opisywał.
Dotychczas tablica zawsze miała pewien rozmiar (liczbę elementów) niezmienny podczas swojego istnienia. Nietrudno się domyślić, że potrzeba czasem dodać do istniejącej tablicy jakiś element albo jakiś z niej usunąć. Zastanówmy się, jak możnaby to napisać...
Pomysł polega na tym, aby nie zawsze używane były wszystkie elementy tablicy, a jedynie pewna ilość początkowych. Taki prawdziwy rozmiar tablicy (ilość zarezerwowanych elementów, a zarazem maksymalną ilość elementów, czyli maksymalny rozmiar) nazywamy pojemnością (ang. capacity). Oprócz niej, trzeba będzie zapamiętać także aktualny rozmiar, czyli ile początkowych elementów jest wykorzystywane. Na rysunku powyżej pojemność tablicy wynosi 9 elementów, natomiast używanych jest tylko 6. Elementy używane są zaznaczone na zielono, a nieużywane na szaro.
// pojemność tablicy const int CAPACITY = 16; // aktualny rozmiar (na początku pusta) int size = 0; // tablica char tab[CAPACITY];
Jeśli rozumiesz ten pomysł, możemy przejść do obmyślania samego
dodawania i usuwania elementów. Najprościej wyobrazić sobie dodawanie
elementu na końcu tablicy. Wystarczy wpisać go na swoje miejsce. Tak się
składa, że jego indeks przechowuje zmienna size z aktualnym
rozmiarem tablicy, bo dotychczasowe elementy miały indeksy od 0
do size-1. Potem trzeba zwiększyć tą zmienną o jeden. Nie można też
zapomnieć o sprawdzeniu, czy przypadkiem nie próbujemy przekroczyć
maksymalnego rozmiaru tablicy!
// Funkcja dodaje podany element na końcu tablicy
// Jeśli nie można dodać, zwraca false
bool Add(char element)
{
// jeśli tablica jest pełna
if (size == CAPACITY) return false;
else {
// wpisanie nowego elementu na swoje miejsce
tab[size] = element;
// zwiększenie rozmiaru
size++;
return true;
}
}
Kolejność elementów w kolekcji nie zawsze ma znaczenie, ale w niektórych zastosowaniach ma. Czasami trzeba wstawić element gdzieś w środku wektora. Żeby to zrobić, trzeba będzie przesunąć wszystkie dalsze elementy o jedną pozycję w prawo, by zrobić miejsce dla nowego.
// Funkcja wstawia podany element w podane miejsce
// Jeśli nie można wstawić, zwraca false
bool Insert(char element, int index)
{
// jeśli tablica jest pełna
if (size == CAPACITY) return false;
else {
// jeśli indeks jest prawidłowy
if (index >= 0 && index <= size) {
// przepisanie dalszych elementów o jedno miejsce w prawo
// od ostatniego do tego w podanym miejscu
for (int i = size-1; i >= index; i--)
tab[i+1] = tab[i];
// wstawienie podanego elementu
tab[index] = element;
// zwiększenie rozmiaru
size++;
return true;
}
else return false;
}
}
Najgorszym przypadkiem jest wstawianie na początek. Trzeba wtedy
przepisać wszystkie elementy. Można też zauważyć, że dodawanie na koniec
jest szczególnym przypadkiem wstawiania, w którym niczego nie trzeba
przepisywać. Średnio jednak ilość operacji potrzebnych do wstawienia
elementu wewnątrz wektora jest wprost proporcjonalna do jego rozmiaru,
a więc wstawianie do wektora ma złożoność rzędu O(n).
Podobnie będzie z usuwaniem. Trzeba przestawić wszystkie dalsze elementy o jedno miejsce wcześniej.
// Funkcja usuwa element z podanego miejsca
// Jeśli nie można usunąć, zwraca false
bool Delete(int index)
{
// jeśli indeks jest prawidłowy
if (index >= 0 && index < size) {
// przepisanie dalszych elementów o jedno miejsce w lewo
// od następnego do ostatniego
for (int i = index+1; i < size; i++)
tab[i-1] = tab[i];
// zmniejszenie rozmiaru
size--;
return true;
}
else return false;
}
Usunięcie polega na tym, że podczas przepisywania elementów o jedno miejsce wcześniej element usuwany zostaje zamazany następnym.
Do powyższego wektora nie można było dodać więcej, niż 16 elementów. Co zrobić, żeby był pojemniejszy? Nie ma sensu alokować całych megabajtów pamięci na zapas, a szukanie kompromisowej, stałej pojemności (capacity) zwykle nie jest dobrym rozwiązaniem. Dobrze byłoby, gdyby wektor potrafił sam zwiększyć swój rozmiar w razie potrzeby. Tylko jak to zrobić?
Realokacja to ponowne przydzielenie pamięci, zazwyczaj o większym (albo mniejszym) rozmiarze od poprzedniej. Składa się z takich etapów:
W ten sposób możemy napisać wektor, który sam będzie się zwiększał wedle potrzeb! Tylko że nie ma sensu realokować pamięci i przepisywać całej tablicy podczas dodania albo usunięcia każdego elementu. Trzeba to robić tylko co jakiś czas - np. kiedy aktualnie przydzielona pamięć jest już pełna, a my chcemy dodać kolejny elementy.
Jak pamiętamy, taką możliwość przechowywania pamięci na zapas daje nam
idea pojemności (capacity). Można wtedy przydzielić pamięć o kilka elementów
większą od dotychczasowej albo np. 2 razy większą. Warto też realokować
wektor zmniejszając go, kiedy zawiera bardzo mało elementów w stosunku do
ilości tych "rezerwowych". W takiej sytuacji zmiana w stosunku
do poprzedniego przykładu polega na tym, że także capacity stanie się
zmienną, a nie stałą.
// o ile elementów zwiększać lub zmniejszać podczas realokacji
const int DELTA = 10;
// pojemność tablicy
int capacity = 0;
// aktualny rozmiar
int size = 0;
// tablica
char *tab = 0;
// Funkcja wstawia podany element w podane miejsce
// Jeśli nie można wstawić, zwraca false
bool Insert(char element, int index)
{
// jeśli indeks jest prawidłowy
if (index >= 0 && index <= size) {
// jeśli tablica jest pełna - realokacja
if (size == capacity) {
// nowe capacity
capacity += DELTA;
// 1. Utworzenie nowej
char *newTab = new char[capacity];
// 2. Przepisanie ze starej do nowej
for (int i = 0; i < size; i++)
newTab[i] = tab[i];
// 3. Usunięcie starej
if (tab) delete [] tab;
tab = newTab;
}
// przepisanie dalszych elementów o jedno miejsce w prawo
// od ostatniego do tego w podanym miejscu
for (int i = size-1; i >= index; i--)
tab[i+1] = tab[i];
// wstawienie podanego elementu
tab[index] = element;
// zwiększenie rozmiaru
size++;
return true;
}
else return false;
}
// Funkcja dodaje podany element na końcu tablicy
// Dodawanie to tylko szczególny przypadek wstawiania!
bool Add(char element)
{
return Insert(element, size);
}
// Funkcja usuwa element z podanego miejsca
// Jeśli nie można usunąć, zwraca false
bool Delete(int index)
{
// jeśli indeks jest prawidłowy
if (index >= 0 && index < size) {
// przepisanie dalszych elementów o jedno miejsce w lewo
// od następnego do ostatniego
for (int i = index+1; i < size; i++)
tab[i-1] = tab[i];
// zmniejszenie rozmiaru
size--;
// jeśli tablica jest za duża - realokacja
if (size > DELTA && size < capacity-DELTA) {
// nowe capacity
capacity -= DELTA;
// 1. Utworzenie nowej
char *newTab = new char[capacity];
// 2. Przepisanie ze starej do nowej
for (int i = 0; i < size; i++)
newTab[i] = tab[i];
// 3. Usunięcie starej
delete [] tab;
tab = newTab;
}
return true;
}
else return false;
}
W konkretnych zastosowaniach występują różne potrzeby i należy wymyślić stosowne do tego algorytmy i struktury danych. Kiedy tylko można, lepiej jest dodawać elementy na końcu wektora - nie trzeba wtedy rozsuwać wszystkich następnych (chyba, że następuje realokacja - wówczas trzeba przepisać cały wektor). Rozpatrzmy teraz przypadek, kiedy kolejność elementów nie ma znaczenia, a nam zależy, by przyspieszyć usuwanie z wektora.
Pomysł polega na tym, żeby nie usuwać elementów w taki sposób, jak to napisałem wyżej - z przesuwaniem wszystkich następnych elementów. Czasami wystarczy wpisanie do danej komórki tablicy jakiejś specjalnej wartości, która oznacza, że to miejsce jest puste. Jeśli elementami wektora są liczby całkowite, ale zawsze dodatnie, za wartość pustą można przyjąć np. -1.
Teraz już wiesz, dlaczego na rysunkach w tym podrozdziale nie we wszystkich elementach jest litera. To są właśnie te "dziury" - ostatnia rzecz, którą w nich ukryłem. Takie dziury można potem wykorzystywać, by przyspieszyć wstawianie elementów - nie trzeba przesuwać wszystkich. Jeśli zaś kolejność nie ma znaczenia, można wstawiać w pierwszej napotkanej dziurze!
Napisałem, jak utworzyć własny wektor, bo są to wiadomości podstawowe i przydatne. Czasami warto taki napisać. STL oferuje nam jednak gotową implementację wektora, którą można wykorzystywać w swoich programach w C++. Sposób jego użycia najlepiej zilustruje przykład:
#include <iostream>
#include <vector>
int main()
{
// deklaruję wektor
std::vector<char> v;
// dodaję 10 pierwszych liter
for (int i = 0; i < 10; i++)
v.push_back('A' + i);
// czy wektor jest pusty?
if ( v.empty() )
std::cout << "Wektor jest pusty!" << std::endl;
// wypisuję ostatni element
std::cout << v[ v.size()-1 ] << std::endl;
return 0;
}
Powyższy przykład wpiszę literę J, a po dodaniu 10 elementów
wektor oczywiście nie jest pusty.
Wektor STL jest bardzo dobry, szybki i sam się realokuje. Jest
wygodny w użyciu i posiada wiele użytecznych funkcji składowych. Oto
krótkie omówienie wektora STL:
#include <vector> - taki nagłówek trzeba włączyć, aby
skorzystać z wektora STL.std::vector<char> - tak deklaruje się wektor. Cały ten
łańcuch to typ deklarowanej zmiennej v. W nawiasach kątowych pisze
się typ elementów wektora.push_back() dodaje podany element na końcu
wektora.empty() zwraca true, jeśli wektor jest pusty
(nie zawiera żadnych elementów) i false, jeśli nie jest pusty
(zawiera przynajmniej jeden element).size() zwraca rozmiar wektora, czyli aktualną liczbę
elementów.v[indeks].
Trzeba tylko uważać, by indeks zawsze był w zakresie od 0 do
v.size()-1 - wektor sam tego nie sprawdza!Kolejne elementy wektora, jak również każdego innego kontenera STL można też przechodzić z użyciem tzw. iteratorów:
// wypisuje wszystkie elementy std::vector<char>::iterator it; for (it = v.begin(); it != v.end(); ++it) std::cout << *it << ' ';
std::vector<char>::iterator jest nazwą typu, która oznacza
iterator dla wektora znaków takiego, jak w poprzednim przykładzie.
Deklarujemy zmienną it tego typu i używamy jej w pętli.
Iterator zachowuje się podobnie do wskaźnika. Jest to taki jakby
specjalny wskaźnik do pokazywania na elementy kontenera STL.
begin() zwraca iterator pokazujący na pierwszy element
wektora. Taką wartością inicjujemy go w pętli.end() zwraca iterator pusty - niepokazujący na żaden
z elementów, a oznaczający błąd. Mówi się też czasem, że pokazuje na
element następny za ostatnim. Właśnie z tą wartością porównujemy nasz
iterator by dowiedzieć się, czy nie przekroczył już końca wektora.++it przesuwa iterator tak, że pokazuje na następny element.
Użyłem preinkrementacji, a nie postinkrementacji, bo w przypadku
iteratorów ta pierwsza może działać szybciej.* tak, jakby iterator był zwykłym wskaźnikiem.Oczywiście za pomocą nawiasów kwadratowych [] użytych na wektorze
oraz gwiazdki * użytej na iteratorze można nie tylko odczytywać,
ale także zapisywać (zmieniać) istniejące już elementy wektora.
Wektor to jednowymiarowa tablica umieszczonych kolejno po sobie elementów jakiegoś typu. Jego największą zaletą jest to, że do elementów można natychmiast odwoływać się podając ich indeksy. Może nie zwracaliśmy na to szczególnej uwagi uznając tą cechę za coś oczywistego, ale jak przekonamy się w następnych podrozdziałach, wcale nie musi tak być.
Wektory mają też to do siebie, że są proste w implementacji. Jednak
wstawianie i usuwanie elementów jest powolne i ma złożoność klasy
O(n). Na koniec rozdziału o taliach będzie okazja, by więcej
powiedzieć o szybkości działania wektora i porównać go z innymi
strukturami danych.
Łańcuch (ang. string) to tablica znaków traktowana jako pewien tekst. Łańcuchy mają szczególne znaczenie, ponieważ przechowuje się w nich wszelkie napisy pokazywane użytkownikowi i polecenia odbierane od użytkownika. Są dwa podstawowe sposoby używania łańcuchów w C++.
Tradycyjny łańcuch to zwyczajna, statyczna lub dynamiczna tablica znaków. Przyjęło się, że jego zakończenie oznacza znak o kodzie 0. Dzięki temu nie trzeba osobno pamiętać jego długości. Oczywiście chodzi o faktyczną ilość znaków napisu, a ilość zarezerwowanych elementów tablicy może być większa. Takie podejście powoduje też dodatkowe ogranicznie, że w treści łańcucha nie mogą się znajdować znaki o kodzie 0.
To jest najbardziej naturalny i najoszczędniejszy, ale nie najszybszy ani
nie najwygodniejszy sposób implementacji łańcuchów. Jednak właśnie tego typu
łańcuchami są w C++ wszystkie napisy objęte w cudzysłowy, np.
"Jakiś tekst". Tego typu łańcuchów oczekują również funkcje
Windows API. Rozpatrzmy przykład:
#include <iostream>
#include <windows.h>
int main()
{
// tworzę łańcuch
char *s = new char[256];
// wpisuję tekst
strcpy(s, "Ala");
// dopisuję tekst
strcat(s, " ma kota");
// wypisuję na ekran
std::cout << s << std::endl;
// wypisuję długość
std::cout << strlen(s) << std::endl;
// wypisuję pierwszy znak
std::cout << s[0] << std::endl;
// pobieram od użytkownika
std::cin >> s;
// porównuję
if ( strcmp(s, "spadaj") == 0 ) return 0;
else MessageBox(0, s, "Wpisałeś:", MB_OK);
// usuwam łańcuch
delete [] s;
return 0;
}
Oto krótki komentarz do powyższego kodu:
char.strcpy() kopiuje łańcuch podany w drugim parametrze
(jak widać, może to być stała dosłowna) do łańcucha podanego w pierwszym
parametrze. Po tym wywołaniu s zawiera znaki: Ala oraz
kończące zero.strcat() dołącza na koniec łańcucha podanego
w pierwszym parametrze łańcuch podany w drugim. Po tym wywołaniu s
zawiera znaki: Ala ma kota oraz zero kończące cały ten ciąg.strlen().strcmp() zwraca 0, jeśli podane dwa łańcuchy są
identyczne i wartość różną od zera, jeśli są różne.MessageBox() pobiera dwa parametry
łańcuchowe. Jako tytuł okna z komunikatem podana została stała dosłowna
"Wpisałeś:", a jako treść komunikatu zmienna s.Jak widać, w przeciwieństwie do wszelkich języków skryptowych (jak PHP, TCL, LUA, Python itd.) w C++ łańcuchy znaków nie są typem wbudowanym, ale tablicą. Nie można tak po prostu stosować na nich, jak to się robi na liczbach, przypisania, porównania itp. Służą do tego specjalne funkcje.
Bardzo częstym błędem jest porównywanie łańcuchów w taki sposób:
if (s == "spadaj") return 0; // BŁĄD !
Kompilator nie sygnalizuje problemów, ale kod nie działa prawidłowo.
Problem polega na tym, że w rzeczywistości porównujemy wskaźniki typu
char* - adres łańcucha s z adresem, pod którym umieszczona
jest w pamięci podana stała dosłowna "spadaj". Dlatego nawet,
jeśli obydwie tablice zawierają te same elementy, wynik porównania będzie
fałszywy - bo są to dwie różne tablice. Porównywać trzeba zawartość tych
tablic (kolejne znaki) i służy do tego opisana wyżej funkcja
strcmp().
Biblioteka standardowa C++ przychodzi nam z pomocą oferując alternatywną, wygodniejszą implementację łańcuchów. Oto ten sam przykład napisany z jej użyciem:
#include <iostream>
#include <string>
#include <windows.h>
int main()
{
// deklaruję łańcuch
std::string s;
// wpisuję tekst
s = "Ala";
// dopisuję tekst
s += " ma kota";
// wypisuję na ekran
std::cout << s << std::endl;
// wypisuję długość
std::cout << s.size() << std::endl;
// wypisuję pierwszy znak
std::cout << s[0] << std::endl;
// pobieram od użytkownika
std::cin >> s;
// porównuję
if (s == "spadaj") return 0;
else MessageBox(0, s.c_str(), "Wpisałeś:", MB_OK);
return 0;
}
Łańcuch STL najlepiej będzie omówić porównując go z łańcuchami tradycyjnymi.
| Cecha | Tradycyjny | STL |
|---|---|---|
| Nagłówek | (brak) | #include <string> |
| Typ | char* |
std::string |
| Pamięć | Trzeba samemu alokować | Sam się realokuje |
| Ograniczenia | Nie może zawierać znaku 0 | Może zawierać dowolne znaki |
| Przypisanie | Funkcja strcpy() |
Operator przypisania = |
| Konkatenacja (łączenie) | Funkcja strcat() |
Operator zwiększania += lub dodawania + |
| Długość | Funkcja strlen() |
Funkcja s.size() |
| Odwołanie do znaku | Operator s[indeks] |
Operator s[indeks] |
| Porównanie | Funkcja strcmp() |
Operator porównania == lub != |
| Kompatybilność z funkcjami Windows API | (jest) | Funkcja s.c_str() zwraca łańcuch STL "przerobiony"
na tradycyjny (nie trzeba go zwalniać!) |
Często trzeba przekazywać łańcuchy jako parametry do funkcji. Żeby uniknąć przy tym ich kopiowania, warto zawsze robić to w taki sposób:
void MyMessage(const std::string &msg)
{
MessageBox(0, msg.c_str(), "Komunikat", MB_OK);
}
Konstrukcja const std::string &msg oznacza przekazywanie
parametru przez referencję do stałej. Dzięki temu zagwarantowane jest,
że:
MyMessage("Nastąpił straszny błąd");.Tablica dwuwymiarowa to taka tablica, do której elementów odwołujemy się za pomocą dwóch indeksów. Można ją sobie wyobrazić jako obszar pokryty kwadratami albo jako wektor wektorów. Macierz ma szerokość i wysokość. To, który indeks potraktujemy jako numer kolumny, a który jako numer wiersza, to kwestia umowna. Dlatego w tym artykule często jest to pomieszane. Istnieje kilka sposobów, na jakie można napisać tablicę dwuwymiarową.
Najprościej jest zadeklarować tablicę statyczną. Ma ona wszystkie te ograniczenia, co statyczna tablica jednowymiarowa (wektor).
// szerokość i wysokość
const int WIDTH = 3;
const int HEIGHT = 2;
// tablica
char tab[WIDTH][HEIGHT];
// wypełnienie tablicy różnymi znakami
int x, y;
for (y = 0; y < HEIGHT; y++) {
for (x = 0; x < WIDTH; x++) {
tab[x][y] = 'A' + x + y;
}
}
Możnaby zastanawiać się, w jakiej kolejności elementy takiej tablicy umieszczone są w - jednowymiarowej przecież - pamięci? Otóż zasada jest taka, że najszybciej zmienia się ostatni indeks. Kolejnymi elementami tej tablicy są więc:
tab[0][0] tab[0][1] tab[1][0] tab[1][1] tab[2][0] tab[2][1]
Pomysł na realizację dynamicznej tablicy dwuwymiarowej polega na utworzeniu tablicy tablic. Będziemy więc musieli użyć wskaźnika do wskaźnika.
Przyjrzyj się powyższemu rysunkowi oraz poniższemu kodowi i postaraj się je zrozumieć.
// zmienne do pętli
int x, y;
// szerokość i wysokość
int width = 3;
int height = 2;
// UTWORZENIE TABLICY
// - tej żółtej
char **tab = new char*[width];
// - tych zielonych
for (x = 0; x < width; x++) {
tab[x] = new char[height];
}
// wypełnienie tablicy różnymi znakami
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
tab[x][y] = 'A' + x + y;
}
}
// USUNIĘCIE TABLICY
// - tych zielonych
for (x = 0; x < width; x++) {
delete [] tab[x];
}
// - tej żółtej
delete [] tab;
Drugim możliwym sposobem na napisanie dynamicznej tablicy dwuwymiarowej
(i moim ulubionym) jest jej zlinearyzowanie, czyli przedstawienie w postaci
jednowymiarowej tablicy o długości równej szerokość*wysokość.
Żeby to zrobić, potrzebny nam będzie wzór zamieniający indeksy tablicy
dwuwymiarowej x i y na indeks tablicy jednowymiarowej
i. Spójrzmy najpierw na poniższy rysunek:
Wyobraź sobie, że ta macierz jest rozłożona do jednowymiarowej tak, że
po kolei następują po sobie kolejne wiersze. Chcemy dostać się do komórki
zawierającej znak gwiazdki * o indeksie [3][2].
Policzywszy ciemniejsze pola wiemy, że musimy w tym celu przejść 16 komórek
- naszym poszukiwanym indeksem jednowymiarowym jest 15.
Żeby go otrzymać, trzeba przejść przez tyle szerokości tablicy, ile wynosi numer wiersza (2) i dodać do tego numer kolumny (3). Oto gotowy wzór (warto go zapamiętać!):
i = y * width + x
W naszym przypadku mamy: 2*6+3 = 12+3 = 15. Po raz kolejny
okazuje się, że indeksowanie od zera przynosi doskonałe efekty! Najwyższy
czas na implementację:
// szerokość i wysokość
int width, height;
// tablica
char *tab;
// Funkcja tworzy tablicę o podanych wymiarach
void Create(int a_width, int a_height)
{
width = a_width;
height = a_height;
tab = new char[width*height];
}
// Funkcja usuwa tablicę
void Destroy()
{
delete [] tab;
}
// Funkcja zamienia indeksy x,y na indeks jednowymiarowy i
inline xy2i(int x, int y)
{
return (y * width + x);
}
// Funkcja zapisuje znak do podanej komórki
inline void Set(int x, int y, char c)
{
tab[ xy2i(x, y) ] = c;
}
// Funkcja odczytuje i zwraca znak z podanej komórki
inline char Get(int x, int y)
{
return tab[ xy2i(x, y) ];
}
Macierz kwadratowa to macierz, która ma taką samą szerokość, jak wysokość.
Macierz trójkątna to taka macierz, która ma istotne wartości tylko po jednej stronie przekątnej. Przykładem może być tabela odległości między miastami. Jeśli odległość z Częstochowy do Siedlec wynosi 320 km, to nie ma sensu zapisywać odległości z Siedlec do Częstochowy.
Gdyby do przechowywania macierzy trójkątnej używać standardowej prostokątnej tablicy dwuwymiarowej, połowa pamięci marnowałaby się. To niedopuszczalne. Można ją zrealizować lepiej albo w postaci zlinearyzowanej (trzeba wtedy wymyślić odpowiedni wzór do indeksowania), albo w postaci tablicy tablic, z których każda z tych tablic ma inną długość.
Macierz nieregularna to taka, w której każdy wiersz ma inną liczbę kolumn (albo odwrotnie). Ją także można bardzo dobrze napisać używając tablicy przechowującej wskaźniki do tablic o różnej długości.
Lista to druga po wektorze najważniejsza struktura danych i w pewnym sensie jego przeciwieństwo. Jej idea jest zupełnie inna, niż omawianych dotychczas tablic.
Lista łączona jest zbudowana tak: mamy wskaźnik do pierwszego elementu, a każdy element oprócz swojej wartości przechowuje wskaźnik do następnego elementu. Ostatni element ma wskaźnik do następnego ustawiony na 0 (adres pusty).
Nie będziemy pisali własnej listy. Omówimy tylko ogólnie zasadę jej działania. W kodzie lista byłaby zapewne zdefiniowana w taki sposób:
struct Element
{
char value;
Element *next;
}
// to jest nasza lista
Element *first;
Mając wskaźnik do pierwszego elementu i odczytując wskaźniki
do kolejnych można przejść wszystkie elementy list. Gorzej, jeśli potrzebne
byłoby dostać się do konkretnego elementu, np. piątego. W przeciwieństwie
do wektorów, tutaj trzeba przejść przez wszystkie poprzednie (pierwszy,
drugi, trzeci, czwarty) odczytując wskaźniki do następnych. Indeksowanie
listy ma więc złożoność liniową - rzędu O(n).
Ale lista ma też zalety. Bardzo proste jest wstawianie nowego elementu w konkretne miejsce. Wystarczy odpowiednio powiązać wskaźniki z poprzednim i następnym. Nie trzeba przepisywać żadnych elementów, jak to było w wektorze. Osobnymi blokami pamięci rezerwowanymi dla pojedynczych elementów zarządza sam system.
Usuwanie elementów jest równie proste. Wystarczy usunąć z pamięci dany element, a wskaźnik w poprzednim ustawić na następny.
Podsumowując, powinieneś zapamiętać następujące wiadomości na temat listy:
Implementacji tak ważnej struktury danych nie mogło oczywiście zabraknąć pośród gotowych do wykorzystania, standardowych kontenerów STL. Zobaczmy, jak wygląda jej wykorzystanie:
#include <iostream>
#include <list>
int main()
{
// deklaracja listy
std::list<char> l;
// dodanie elementu na koniec
l.push_back('A');
// wstawienie elementu na początek
l.insert(l.begin(), 'B');
// usunięcie wszystkich elementów 'A'
std::list<char>::iterator it;
for (it = l.begin(); it != l.end(); ++it) {
if ( *it == 'A' ) {
it = l.erase(it);
}
}
return 0;
}
#include <list> - taki nagłówek trzeba włączyć, aby
skorzystać z listy STL.std::list<char> - tak deklaruje się listę. Cały ten łańcuch
to typ deklarowanej zmiennej l. W nawiasach kątowych pisze się typ
elementów listy. Wskaźnik na następny element STL realizuje sobie
sam.push_back() dodaje podany element na końcu listy.insert() wstawia podany element w miejscu określonym
przez podany iterator. Funkcja begin() zwraca iterator
do pierwszego elementu.erase() usuwa element, na który wskazuje podany
iterator i zwraca iterator do następnego elementu (tamten już nie byłby
poprawny i nie wolno byłoby go używać!).Jak widać, używanie listy STL jest bardzo podobne do używania wektora STL. W szczególności warto zwrócić uwagę na użycie iteratorów - lista nie oferuje innego rodzaju dostępu do elementów. Iteratory były szerzej opisane przy okazji opisu wektora.
Lista dwukierunkowa to taka lista, w której przechowujemy wskaźnik na pierwszy i ostatni element, a każdy element przechowuje wskaźnik na poprzedni i następny. Taką listę można przechodzić w obydwie strony. Lista STL jest tak naprawdę listą dwukierunkową.
Lista z wartownikiem to taka lista, do której dołączamy poszukiwany element. Dzięki temu podczas przeszukiwania nie musimy sprawdzać dwóch warunków - czy element odnaleziono i czy osiągnięto koniec listy - tylko ten pierwszy. Potem wystarczy sprawdzić: jeśli odnaleziony element to wartownik, to znaczy, że we właściwej kolekcji szukanego elementu nie było.
Lista cykliczna to taka lista, w której ostatni element nie pokazuje na adres pusty (0), tylko na pierwszy i tak powstaje zamknięty obieg.
Lista wielowątkowa to lista, której elementy mają po kilka wskaźników na następny element. Każdy z nich tworzy osobną listę i dzięki temu te same elementy mogą być w różnych listach umieszczone w różnej kolejności, np. posortowane wg różnych kryteriów.
Macierz rzadka to taka macierz, w której tylko nieliczne elementy posiadają jakąś znaczącą wartość (np. różną od 0).
Wspominam o niej dopiero teraz, bo jej najoszczędniejszą implementacją jest właśnie lista (na poniższym przykładzie widać, że sama kolekcja wierszy (ta żółta) też jest macierzą rzadką i została zrealizowana w postaci listy).
Lista była jakby przeciwieństwem wektora, a podobno wszelkie skrajności są niedobre. Dlatego czas na omówienie struktury danych, która w pewnym sensie łączy wektor i listę, a w pewnym sensie jest czymś pośrednim.
Talia (ang. deque) to, najprościej mówiąc, lista wektorów. Nie pojedynczy wektor, tylko ich lista i nie lista pojedynczych elementów, tylko całych wektorów.
Można sobie wyobrazić przechodzenie kolejnych elementów takiej struktury. Rozpatruje się kolejne elementy wektora, a na końcu skacze się po wskaźniku do następnego.
Także bezpośrednie indeksowanie któregoś elementu nie jest tak czasochłonne, jak w przypadku listy (choć nie tak szybkie, jak w przypadku wektora). Trzeba skakać po kolejnych wektorach, ale tych skoków będzie wielokrotnie mniej, niż pojedynczych elementów.
Dodawanie nie wymaga przesuwania wszystkich elementów. Wystarczy przesunąć elementy danego wektora, a jeśli się nie mieszczą - przealokować go lub wstawić do listy nowy wektor. Analogicznie można sobie wyobrazić usuwanie.
Charakterystyczne dla talii jest również to, że dodawanie i usuwanie elementów na jej początku jest równie szybkie, co na końcu. Dlatego nazywana bywa też kolejką o dwóch końcach.
Żeby używać talii STL, trzeba włączyć taki nagłówek: #include
<deque>. Stosowny typ nazywa się natomiast deque, np.
std::deque<char> MyDeque;.
To w zasadzie wszystko, co trzeba wiedzieć o talii STL. Używa się jej
dokładnie tak samo, jak listy czy wektora - łącznie z wykorzystaniem
iteratorów, funkcjami składowymi, a także możliwością
indeksowania za pomocą operatora nawiasów kwadratowych [].
| Cecha | Wektor | Talia | Lista |
|---|---|---|---|
| Nagłówek | #include <vector> |
#include <deque> |
#include <list> |
| Typ | std::vector<> |
std::deque<> |
std::list<> |
| Przechodzenie po kolei (iterowanie) | + Szybkie |
+ Szybkie |
+ Szybkie |
| Dostęp swobodny (indeksowanie) | + Szybkie |
* Średnie |
- Wolne |
| Wstawianie i usuwanie na końcu | + Szybkie |
+ Szybkie |
+ Szybkie |
| Wstawianie i usuwanie na początku | - Wolne |
+ Szybkie |
+ Szybkie |
| Wstawianie i usuwanie w środku | - Wolne |
* Średnie |
+ Szybkie |
Podsumowując:
Przez "najważniejsze" należy rozumieć, że dana operacja jest wykonywana bardzo często.
Nie zawsze potrzebna jest pełna funkcjonalność kontenera. Niekiedy wystarczy ograniczyć się do niektórych operacji, szczególnie jeśli chodzi o miejsce dodawania i usuwania elementów. Stos i kolejka to właśnie nazwy takich ograniczeń, a nie nowe struktury danych.
Stos (ang. stack), inaczej kolejka LIFO (ang. last in first out - ostatni wejdzie pierwszy wyjdzie) to taka struktura danych, w której mamy dostęp tylko do pojedynczego elementu na jednym końcu zwanym wierzchołkiem stosu (ang. top).
Stos można sobie wyobrazić jako stos brudnych talerzy po obiedzie. Talerze odkłada się na wierzchu, a potem do zmywania zdejmuje się je z wierzchu w odwrotnej kolejności. Nie wyjmujemy talerzy gdzieś z środka, bo cały stos by się zawalił, a talerze by się potłukły.
STL oferuje otoczkę na wybrany kontener (adaptator) realizującą stos. Domyślnie używana jest w tym celu talia. Stos jest tak prosty, że poniższy przykład prezentuje wszystkie jego funkcje składowe:
#include <iostream>
#include <stack>
int main()
{
// deklaruję stos
std::stack<char> s;
// odkładam element
s.push('A');
// wypisuję liczbę elementów
std::cout << s.size() << std::endl;
// wypisuję element z wierzchu
std::cout << s.top() << std::endl;
// usuwam element z wierzchu
s.pop();
// sprawdzam, czy stos jest pusty
if ( s.empty() )
std::cout << "Stos jest pusty" << std::endl;
return 0;
}
Push i pop to zwyczajowo przyjęte nazwy dla czynności odkładania
elementu na stos i zdejmowania elementu ze stosu. Czasami uznaje się,
że odczytanie elementu ze szczytu stosu i jego usunięcie to jedna i
nierozłączna czynność. Na szczęście STL daje większą swobodę zapewniając
osobno dostęp do elementu z wierzchu bez jego usuwania
(funkcja top()) oraz usuwanie elementu z wierzchu bez jego
odczytywania (funkcja pop()).
Kolejka (ang. queue), inaczej kolejka FIFO (ang. first in first out - pierwszy wejdzie pierwszy wyjdzie) to taka struktura danych, w której elementy można dodawać tylko z jednej strony, a usuwać tylko z drugiej.
Można sobie ją wyobrazić jako kolejkę ludzi przy kasie w supermarkecie. Jeden koniec kolejki, nazywany koniec (ang. back) to jedyne miejsce, do którego nowi klienci mogą dochodzić. Drugi, nazywany początek (ang. front) to jedyne miejsce, z którego klienci mogą odchodzić z zakupami. Nie można wepchnąć się w środek kolejki, bo ludzie się zdenerwują.
Mimo zbieżności angielskich nazw kolejka (ang. queue) nie ma niczego wspólnego z talią (ang. deque). Talia to, obok wektora i listy, jedna z podstawowych struktur danych a kolejka to, obok stosu, jeden z rodzajów ograniczeń, jakie często nakłada się na struktury.
Kolejka STL jest podobna do stosu. Jedyną różnicą jest to, że elementy
dodawane są na końcu, a usuwane na początku. Mamy dostęp zarówno
do pierwszego, jak i do ostatniego. Poniższy przykład wypisuje litery
B i A.
#include <iostream>
#include <queue>
int main()
{
// deklaruję kolejkę
std::queue<char> q;
// dodaję elementy na końcu
q.push('A');
q.push('B');
// wypisuję element z końca
std::cout << q.back() << std::endl;
// wypisuję element z początku
std::cout << q.front() << std::endl;
// usuwam element z początku
q.pop();
return 0;
}
Na wektorze, liście i talii zakończyliśmy poznawanie sekwencyjnych struktur danych - czyli takich, w których elementy są umieszczone kolejno jeden za drugim. Można wyobrazić sobie inny układ elementów, np. hierarchię. Właśnie taką budowę mają drzewa.
Drzewo (ang. tree) to hierarchiczna struktura danych, w której każdy element może mieć swoje podelementy. Można go porównać do:
Drzewa to bardzo obszerny i niełatwy temat. Nie będę go omawiał dokładnie, ale warto znać pewne podstawy. Oto najważniejsze związane z nimi pojęcia:
Zastanówmy się teraz przez chwilę, jak możnaby napisać drzewo? Z pewnością byłoby to coś podobnego do listy łączonej z tym, że każdy element musiałby przechowywać listę (a może wektor?) wskaźników na swoje węzły potomne. Ale gdyby maksymalna liczba węzłów potomnych była ograniczona, wtedy możnaby zamiast tego użyć po prostu kilku pól wskazujących na te węzły potomne lub na adres pusty.
struct Element
{
char value;
Element *sub1;
Element *sub2;
}
// to jest nasze drzewo
Element *root;
Można też wymyślić sposób na zlinearyzowanie drzewa, czyli przechowywanie go w zwykłej jednowymiarowej tablicy.
Drzewa bywają różne - stosownie do potrzeb. Często nakłada się na nie specjalne wymagania i ograniczenia, np. w sprawie pewnego posortowania (ułożenia węzłów w pewnym porządku). Natomiast według maksymalnej ilości węzłów potomnych możemy wyróżnić:
Przejdźmy teraz to metod przechodzenia drzewa. Drzewa są tak trudne, że nawet ten proces bywa przedmiotem obszernych opisów. Najważniejsze jest to, że nie wystarczy już przechodzić w pętli kolejnych elementów (iteracyjnie). Pierwszym nasuwającym się sposobem przechodzenia drzewa jest wyjście od korzenia i dla każdego węzła przeglądanie wszystkich jego pod-węzłów (rekurencyjnie). Są też różne inne sposoby.
Z drzewami związana jest pewna bardzo ważna właściwość. Wyobraźmy sobie dla przykładu drzewo binarne tak posortowane, że węzeł potomny z lewej strony każdego węzła i wszystkie jego węzły potomne mają wartość mniejszą od niego, a węzeł potomny każdego węzła z prawej strony i wszystkie jego podwęzły mają wartość większą od niego. Szukając konkretnej wartości w takim drzewie wymieramy stale drogę w prawo lub w lewo, a tym samym ograniczamy ilość potencjalnych możliwości o około połowę. Taki algorytm ma złożoność logarytmiczną, a więc bardzo dobrą! Do przeszukania ok. 1000 elementów wystarcza 10 kroków.
Dlatego drzewa są bardzo dobrym rozwiązaniem skomplikowanych problemów. Niestety, nie są proste w implementacji. STL nie dostarcza też żadnych uogólnionych mechanizmów do pisania drzew. Istnieje jednak kilka kontenerów STL o bardzo ciekawych właściwościach, których wewnętrzna budowa oparta jest na drzewach. Zajmijmy się nimi.
Zbiór STL to kontener, który przechowuje swoje elementy w posortowanym drzewie. Dzięki temu zapewnia bardzo szybkie wyszukiwanie. Wiążą się z tym jednak trzy ograniczenia:
Oto przykład użycia zbioru i jego zwięzłe omówienie:
#include <iostream>
#include <set>
int main()
{
// deklaruję zbiór
std::set<char> s;
// dodaję elementy
s.insert('A');
s.insert('B');
// znajduję literkę A
std::set<char>::iterator it = s.find('A');
// jeśli się znalazła
if ( it != s.end() )
// usuwam ją
s.erase(it);
// wypisuję wszystkie elementy
for (it = s.begin(); it != s.end(); ++it)
std::cout << *it << std::endl;
return 0;
}
#include <set> - taki nagłówek trzeba włączyć, aby
skorzystać ze zbioru STL.std::set<char> - tak deklaruje się zbiór. Cały ten ciąg to
typ deklarowanej zmiennej s. W nawiasach kątowych pisze się typ
elementów zbioru.insert() dodaje element do zbioru. Pamiętamy, że
kolejność nie jest zachowana - zbiór sortuje sobie te
elementy.std::set<char>::iterator - takiego typu są iteratory
pokazujące na elementy zbiorów.find() szuka elementu o podanej wartości i zwraca
iterator wskazujący na niego. Jeśli element się nie znajdzie, zwraca
iterator pusty - równy wartości zwracanej przez funkcję
end().erase() usuwa ze zbioru element, na który pokazuje
podany iterator.Istnieje także drugi typ - std::multiset<char>. Wymaga
włączenia tego samego nagłówka, a od zwykłego zbioru różni się tym, że
wartości mogą się w nim powtarzać - ta sama wartość może być w zbiorze
kilka razy.
Problem polega na tym, że najczęściej chcielibyśmy przechowywać w zbiorze elementy jakiegoś bardziej złożonego typu, których on nie będzie potrafił bezpośrednio porównywać (stwierdzać, że jeden jest większy od drugiego), a przez to sortować. Zwykle jest tak, że element posiada szereg pól, z których jeden powinien stanowić kryterium sortowania i wyszukiwania. Tutaj z pomocą przychodzi kolejny kontener STL - mapa.
Mapa jest bardzo podobna do zbioru, ale przechowuje kolekcję elementów - tzw. par, z których każda posiada klucz i wartość. Elementy sortuje sobie według klucza i według niego pozwala szybko je wyszukiwać. Rozważmy przykład bazy danych dla firmy, w której mają być przechowywane informacje o klientach w postaci par: jakiś numer identyfikacyjny (liczba) -> opis (łańcuch).
#include <iostream>
#include <string>
#include <map>
int main()
{
// deklaruję mapę
std::map<int, std::string> m;
// dodaję elementy
m.insert( std::make_pair(7, "Jan Kowalski - bardzo solidny klient") );
m.insert( std::make_pair(666, "Maciej Nowak - Klient bardzo niesolidny") );
// znajduję osobę o numerze 7
std::map<int, std::string>::iterator it = m.find(7);
// jeśli się znalazła
if ( it != m.end() ) {
// wypisuję jej opis
std::pair<int, std::string> p = *it;
std::cout << p.second << std::endl;
}
return 0;
}
Cała trudność w nauczeniu się używania mapy polega na zrozumieniu, jak należy używać par STL.
#include <map> - taki nagłówek trzeba włączyć, żeby
skorzystać z mapy STL.std::map<int, std::string> - takiego typu jest
zadeklarowana w przykładzie mapa m. Jak widać, w nawiasie kątowym
podaje się dwa typy - typ klucza i typ wartości. Elementami mapy będą
nierozłącznie związane pary - w tym przypadku pary liczba - łańcuch.insert() wstawia do mapy parę. Żeby ją utworzyć,
używamy funkcji make_pair(), która pobiera dwie niezależne
wartości i zwraca parę, która je zawiera zestawione razem.find() wymaga tylko podania klucza, a zwraca
iterator pokazujący na odnaleziony element (czyli na parę). Jeśli
element się nie znajdzie, zwrócony zostaje błędny iterator - równy
wartości zwracanej przez funkcję end().std::pair<int, std::string> - takiego typu jest tak
naprawdę każda para w naszym przykładzie, czyli element naszej mapy.
Deklarujemy osobną zmienną tego typu i przepisujemy do niej parę,
na którą pokazuje otrzymany iterator.second i jest łańcuchem.
Pierwszy składnik pary, który w mapie pełni rolę klucza, znajduje się
w polu o nazwie first i w tym przykładzie jest liczbą.W normalnej mapie nie może istnieć kilka elementów o takim samym kluczu.
Analogicznie, jak to było ze zbiorami, mapa posiada także specjalną
odmianę pozwalającą na to. Wymaga ona włączenia tego samego nagłówka,
a odpowiedni typ nazywa się multimap<>.
Teraz, po omówieniu map, chciałbym jeszcze raz przypomnieć i podsumować, która struktura do czego się nadaje.
Drzewo wyglądało na dość swobodną organizację danych, jednak nie do końca. Połączenia między elementami nie mogły tworzyć cykli. Grafy to struktury pozbawione jakichkolwiek ograniczeń. Jednocześnie są to struktury najtrudniejsze i dlatego napiszę o nich najmniej.
Graf to zbiór elementów i dowolnych połączeń między nimi. Oprócz tego, że elementy mają pewne wartości (np. litery), samym połączeniom także przypisuje się często pewne liczby - tzw. wagi. Graf może być wyobrażeniem jakiejś sieci, np. komputerowej albo kanalizacyjnej. Jeszcze lepiej można go porównać do mapy, na której są zaznaczone miasta i drogi między nimi. Wyróżniamy dwa rodzaje grafów:
W jaki sposób można przechowywać grafy? Jedną z możliwości jest tzw. macierz wag:
| A B C D E ---+-------------------- A | - 9 10 3 * B | * - * * * C | * 1 - 4 * D | * * * - 7 E | * * 5 * -
Jest to tablica dwuwymiarowa, w której na przecięciu kolumn i wierszy
znajdują się wagi połączeń od elementu, któremu odpowiada dany wiersz
do elementu, któremu odpowiada dana kolumna (albo odwrotnie). Na przekątnej
tej tablicy są myślniki -, ponieważ zwykle nie rozpatruje się
połączenia elementu z samym sobą. Brak połączenia danych elementów w danym
kierunku oznaczone zostało gwiazdką *. Gdyby graf był nieskierowany,
wystarczyłaby macierz trójkątna - jedna strona przekątnej byłaby lustrzanym
odbiciem drugiej, bo w grafie nieskierowanym połączenia są po prostu między
dwoma elementami, a nie od jednego do drugiego.
Algorytmy przechodzenia grafów i robienia innych operacji na nich są tematem całych grubych książek. Niektóre z tych algorytmów mają bardzo dużą złożoność (są bardzo wolne) i nie nadają się do stosowania w dużych grafach. Dlatego nierzadko trzeba zadowolić się szybszym algorytmem, który nie znajduje idealnego rozwiązania, a tylko bliskie idealnemu.
Jednym z najbardziej znanych problemów dotyczących grafów jest tzw. problem komiwojażera. Bohater ma odwiedzić podane miasta (w dowolnej kolejności) i musi wybrać najkrótszą drogę, po której będzie podróżował. Wagi połączeń mogą oznaczać odległości.
Zakończyliśmy omawianie najważniejszych struktur danych. Dzięki ich znajomości wiesz już, jak można przechowywać w pamięci dane - kolekcję jakiś elementów. Jednak większość programów potrzebuje też zachowywać niektóre z nich w plikach na dysku. Właśnie o tym traktuje druga część tego artykułu.
Omawiając struktury danych oczekiwałem, że znasz pewne podstawy, np. wskaźniki. Obsługę plików postaram się wyjaśnić od samego początku. Będzie trochę mniej przykładów, a trochę więcej abstrakcyjnych opisów, ale mam nadzieję, że będą one zrozumiałe.
Jeśli twój program ma przechowywać jakieś dane na dysku, prawdopodobnie musisz opracować do tego własny, nowy format pliku. To nic strasznego - format może być bardzo prosty, a znajomość pewnych wspólnych podstaw daje pewność, że wszystko będzie działało poprawnie.
Format pliku to sposób, w jaki dane są zapisywane w pliku - jakiego rodzaju informacje, w jakiej formie i w jakiej kolejności się w nim znajdują. Formaty plików można podzielić na takie dwie kategorie:
Można wymyślić sobie nazwę dla swojego formatu i swoje rozszerzenie pliku. Powinieneś też solidnie opisać ten format w jakimś pliku tekstowym. Kiedyś zapomnisz, jak go zorganizowałeś, a wtedy domyślanie się tego z kodu, który zapisuje i odczytuje takie pliki nie będzie przyjemne. Ogólna budowa prawie każdego pliku wygląda tak:
Nagłówek to dane na początku pliku, które niosą informacje:
GIF89a w plikach graficznych GIF, Rar!
w archiwach RAR czy MZ w programach EXE. Od tych znaków rozpoczyna
się plik.Używanie nagłówka jest bardzo ważne, bo użytkownik może łatwo zmienić rozszerzenie pliku. Gdyby program sugerował się tylko rozszerzeniem, mógłby spróbować odczytywać dane z pliku zapisanego zupełnie w innym formacie, np. program graficzny próbowałby zinterpretować dokument tekstowy jako obrazek.
Dalej po nagłówku następują kolejne elementy (rekordy), np. punkty obrazu, linijki tekstu itp. Odpowiadają one kolejnym elementom przechowywanej w pamięci struktury danych (jak wektor czy lista). Ich kolejność może mieć lub nie mieć znaczenia, a ich długość może być taka sama lub różna. Pośród informacji zapisywanych w każdym elemencie często można spotkać:
Po czym program odczytując plik może poznać, że odczytał już wszystkie elementy? Są 3 ogólne sposoby na zaplanowanie tego:
Można też wyobrazić sobie inne, bardziej skomplikowane modele budowy pliku. Na rysunku poniżej pokazany jest plik, w którym po nagłówku znajduje się kolekcja elementów pewnego rodzaju, a po niej druga kolekcja elementów innego rodzaju.
Struktura informacji w pliku może też być hierarchiczna - element przechowuje kolekcję swoich podelementów, te przechowują swoje podelementy itd... Tak można zapisywać na dysku drzewo.
Obsługę plików można pisać na wiele sposobów, m.in.:
fopen(), fclose(),
fwrite(), fread(). Te funkcje są przestarzałe, zaleca się
wariant 2.ofstream i
ifstream. Ten sposób jest przenośny między różnymi systemami.CreateFile(),
CloseHandle(), WriteFile(), ReadFile(). Ten wariant
gwarantuje pełną obsługę plików dokładnie w taki sposób, jaki oferuje
system Windows. Właśnie ten wariant wybieramy.Żeby zaprezentować ogólny sposób obchodzenia się z plikami jeszcze bez wdawania się w projektowanie jakiegoś sensownego formatu, pokażę teraz przykład operacji na dwuznakowym pliku. Na początek funkcja do zapisywania.
bool MyWrite()
{
bool ok;
HANDLE file = CreateFile("Plik.dat", FILE_WRITE_DATA, 0, 0,
CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, 0);
ok = (file != INVALID_HANDLE_VALUE);
if (ok) {
DWORD x;
ok = ( WriteFile(file, "AB", 2, &x, 0) != 0 );
if (ok)
ok = ( x == 2 );
CloseHandle(file);
}
return ok;
}
Funkcja ma zwracać true, jeśli operacja zapisania pliku się
powiedzie i false, jeśli coś pójdzie nie tak. Do przechowywania
aktualnego stanu procesu używamy zmiennej logicznej ok. To jest
konieczne, bo nie wystarczy po prostu w miejscu wystąpienia błędu wyjść
instrukcją return false; - trzeba zamknąć plik, jeśli został już
otwarty!
Użyte funkcje pochodzą z nagłówka #include <windows.h> i
pobierają bardzo dużo parametrów. Jednak nie ma się czego bać - wielu
z nich nie będziemy omawiali i pozostaną ustawione na 0 albo na inną
wartość, jaka jest widoczna w kodzie.
Funkcja CreateFile(), wbrew swojej nazwie, potrafi oprócz
tworzenia nowych także otwierać istniejące pliki. Musimy omówić dość
dokładnie kilka parametrów, które przyjmuje.
Pierwszy parametr to łańcuch - nazwa pliku do otwarcia. Może występować
w dwóch wariantach:
C:\Moje dokumenty\Savy\Save1.gam...\Saves\Autosave.gam.W tym drugim przypadku plik jest poszukiwany w lokalizacji podanej
względem katalogu bieżącego. Katalog bieżący to katalog, mówiąc ogólnie,
z którego zostaje uruchomiony program. Wcale nie musi to być katalog
z plikiem EXE twojego programu. Dlatego otwierając położone razem z nim
pliki zawsze trzeba podawać pełną, bezwzględną ścieżkę do pliku. Katalog
swojego pliku EXE można wyciągnąć z łańcucha zwracanego przez funkcję
GetModuleFileName().
Drugim parametrem CreateFile() jest żądany sposób dostępu
do pliku. Stała FILE_WRITE_DATA oznacza, że chcemy zapisywać. Pliki
można otwierać do zapisu, do odczytu albo do obydwu tych operacji
jednocześnie.
Parametr trzeci odpowiada za sposób, w jaki chcemy zablokować plik ograniczając dostęp do niego innym programom na czas, kiedy my mamy go otwartego. Nie należy pomijać tego tematu - trzeba zawsze odpowiednio dobrać sposób blokowania. 0 oznacza, że nie pozwalamy w tym czasie innym programom na żadne operacje na tym pliku. Nie chcemy przecież, by ktoś czytał nie do końca jeszcze zapisany plik, a tym bardziej, żeby do niego zapisywał razem z nami.
Wreszcie parametr piąty to dyspozycje dla systemu jak ma się zachować,
jeśli plik jeszcze nie istnieje oraz jeśli już istnieje. Jest kilka
możliwości. Do tego zastosowania najlepsza jest flaga CREATE_ALWAYS
która oznacza, że jeśli plik nie istnieje, zostanie utworzony a jeśli
istnieje, zostanie opróżniony (czyli stanie się pusty).
Funkcja CreateFile() zwraca uchwyt typu HANDLE
do otwartego pliku lub wartość równą INVALID_HANDLE_VALUE, jeśli
nie uda się go otworzyć. Otwarty plik trzeba koniecznie zamknąć za pomocą
funkcji CloseHandle().
Do zapisywania danych służy funkcja WriteFile(). Jako pierwszy
parametr przyjmuje uchwyt otwartego pliku. Jako drugi - wskaźnik do
obszaru pamięci, w którym znajdują się dane do zapisania. Może to być adres
zmiennej dowolnego typu, wektora albo (tak jak na przykładzie) łańcuchowa
stała dosłowna, która jest wektorem znaków.
Trzeci parametr to ilość bajtów, jakie mają zostać zapisane. Można tam
wpisać bezpośrednio liczbę. Jeśli zapisuje się pojedynczą zmienną, można
podać wartość wyrażenia sizeof(zmienna) albo
sizeof(typ_tej_zmiennej), które zwraca rozmiar zmiennej
w bajtach. Jeśli do zapisania podajesz
wskaźnik do wektora, nie można zapomnieć o pomnożeniu ilości jego elementów
przez rozmiar pojedynczego elementu.
Parametr czwarty jest parametrem wyjściowym. Jest to adres do zmiennej
typu DWORD, do której funkcja wstawi ilość bajtów, jakie udało się
zapisać. W tym miejscu chciałbym bardzo mocno podkreślić, że podczas
operacji na plikach niezwykle ważna jest kontrola błędów. Błędy mogą się
zdarzyć praktycznie zawsze i na każdym etapie. W pokazanym przykładzie
można odnaleźć 3 miejsca, w których są sprawdzane błędy:
CreateFile()
zwróciła poprawny uchwyt do pliku, a nie wartość równą
INVALID_HANDLE_VALUE).WriteFile() zwróciła wartość różną od zera).x ma taką samą wartość, jak podana w trzecim
parametrze funkcji WriteFile()).Mimo niepowodzenia jakiejś operacji otwarty plik trzeba koniecznie zamknąć.
Zobaczmy teraz przykład funkcji do odczytywania z pliku:
bool MyRead(char *c)
{
bool ok;
HANDLE file = CreateFile("Plik.dat", FILE_READ_DATA, FILE_SHARE_READ, 0,
OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
ok = (file != INVALID_HANDLE_VALUE);
if (ok) {
ok = ( SetFilePointer(file, 1, 0, FILE_BEGIN) != INVALID_SET_FILE_POINTER );
if (ok) {
DWORD x;
ok = ( ReadFile(file, c, sizeof(char), &x, 0) != 0 );
if (ok)
ok = ( x == sizeof(char) );
}
CloseHandle(file);
}
return ok;
}
Funkcja ma za zadanie odczytać drugi znak i zwrócić go przez podany
wskaźnik. Wartością zwracaną przez funkcje jest true, jeśli
odczytanie się udało i false, jeśli wystąpił jakiś błąd. Funkcja jest
trochę podobna do poprzedniej, więc omówię tylko różnice.
Jako sposób otwarcia przekazujemy do funkcji CreateFile() stałą
FILE_READ_DATA - co oznacza, że chcemy odczytywać treść pliku.
Podanie w trzecim parametrze stałej FILE_SHARE_READ zezwala innym
programom na jednoczesne czytanie z tego samego pliku - nie mamy przecież
nic przeciwko temu. Plik zostaje jedynie zablokowany przed zapisem.
Stała OPEN_EXISTING w parametrze piątym nakazuje, by plik został
otwarty bez utraty jego treści jeśli istnieje, a jeśli nie istnieje, żeby
otwarcie się nie powiodło.
W otwartym pliku jest coś, co można sobie wyobrazić jako kursor. Bywa też zwany pozycją lub wskaźnikiem. Jest to miejsce, w którym aktualnie jesteśmy, z którego odczytujemy lub do którego zapisujemy. Podczas odczytywania i zapisywania ten kursor automatycznie się przesuwa, ale można go też samemu przestawiać.
Dzięki temu zamiast odczytywać obydwa znaki, skaczemy w pliku od razu do
interesującego nas znaku drugiego. Służy do tego funkcja
SetFilePointer(). Jako pierwszy parametr przyjmuje ona uchwyt do
otwartego pliku, a jako drugi pozycję w pliku. Znaczenie tej pozycji
określa stała podana w parametrze ostatnim. Może to być:
FILE_BEGIN - oznacza, że podana została pozycja względem
początku pliku (czyli bezwzględny numer bajta w pliku).FILE_CURRENT - oznacza, że podana została pozycja względem
aktualnej (czyli o ile bajtów przesunąć kursor do przodu albo do tyłu).FILE_END - oznacza, że podana została pozycja względem końca
pliku.Do odczytywania danych z pliku służy funkcja ReadFile(). Jest
bardzo podobna do omówionej wcześniej funkcji zapisującej. Jako pierwszy
parametr przyjmuje uchwyt do otwartego pliku. Jako drugi wskaźnik na
miejsce w pamięci, w którym ma umieścić odczytane dane. Tym razem nie może
to być stała łańcuchowa ani żaden wskaźnik do stałej. Parametr trzeci
to ilość bajtów do odczytania, a czwarty to wskaźnik do zmiennej typu
DWORD, w której funkcja umieści liczbę bajtów, jaką udało się
odczytać. Trzeba ją koniecznie sprawdzić, czy się zgadza.
Plik binarny to plik, w którym dane zapisywane są tak samo jak
w pamięci. Np. jeśli w pamięci liczba jest przechowywana w zmiennej typu
int, która zajmuje 4 bajty, to takie same 4 bajty zostaną zapisane
do pliku. Po podglądnięciu plik binarny wygląda na bardziej lub mniej
chaotyczny zbiór różnych znaczków:
Numer Znaki szesnastkowo Znaki 00000460 966A B76A BF2B 9AC8 D0C2 4D9A DC4E A366 .j.j.+....M..N.f 00000470 3766 7857 1DDD 0290 8C80 4DCD BDDD DBC1 7fxW......M..... 00000480 FFAD B7B2 49B8 AF3E DF66 7666 1E73 5CB4 ....I..>.fvf.s\. 00000490 6B94 CB96 28E6 0457 4EDA E51F 7CAD 797A k...(..WN...|.yz 000004A0 634C 2085 CC0B 878E 9AA9 CC8A FCB4 BF85 cL ............. 000004B0 6356 B166 CB8F B63A 6602 90EB 69E4 A8AD cV.f...:f...i...
Jednak wbrew pozorom to jest najszybszy, najoszczędniejszy i najbardziej naturalny dla komputera sposób zapisywania danych na dysku. Jego wadą natomiast jest nieczytelność i trudność (jeśli nie niemożliwość) ręcznego edytowania takich plików przez użytkownika. Do edytowania i odczytywania plików binarnych trzeba używać programów, które obsługują dany format albo być niezłym hakerem :)
Zaprojektujemy teraz własny binarny format pliku i napiszemy kod do jego obsługi. Wyobraźmy sobie, że do napisania jest gra. Skupiamy się na kolekcji gatunków potworów, z jakimi gracz może walczyć. Każdy z potworów ma swoją nazwę i siłę. Do przechowywania tej kolekcji można użyć takiej struktury danych:
struct Potwor {
std::string nazwa;
int sila;
};
typedef std::list<Potwor*> PotworList;
PotworList potwory;
Pora na zaprojektowanie formatu pliku. Trzeba go dokładnie opisać. Przykładowo, systematyczny opis może wyglądać w taki sposób:
Rozszerzenie pliku: PTW
Budowa pliku: Nagłówek, Element, Element, ..., Element
Nagłówek: Identyfikator formatu, Ilość potworów
Identyfikator formatu: łańcuch "PTW" [3 znaki]
Ilość potworów: liczba typu size_t [4B]
Element: Nazwa, Siła
Nazwa: Długość nazwy, Znak, Znak, ..., Znak
Długość nazwy: liczba typu BYTE [1B]
Znak: pojedynczy znak [1B]
Siła: liczba typu int [4B]
Mając taki opis można spróbować zaimplementować funkcje do jego obsługi. Poniższy kod jest najdłuższym przykładem w tym artykule i łączy wszystko, czego się dotychczas nauczyliśmy - struktury danych i operacje na plikach. Opisu do niego nie będzie, bo nie ma tu niczego nowego, ale w jego zrozumieniu pomogą komentarze. Na początek zapisywanie:
// Obudowuje funkcję WriteFile() i zwraca false,
// jeśli wystąpi jakiś błąd
bool WriteCos(HANDLE file, const void *data, DWORD size)
{
DWORD x;
// jeśli funkcja WriteFile zwróci 0
if ( WriteFile(file, data, size, &x, 0) == 0 ) return false;
// lub jeśli nie uda się zapisać wszystkich bajtów
if ( x != size ) return false;
// OK
return true;
}
// Zapisuje do podanego pliku nagłówek
bool WriteNaglowek(HANDLE file)
{
// Identyfikator formatu
if (! WriteCos(file, "PTW", 3) ) return false;
// Ilość potworów
size_t ilosc = potwory.size();
if (! WriteCos(file, &ilosc, sizeof(ilosc)) ) return false;
// OK
return true;
}
// Zapisuje od podanego pliku podanego potwora z pamięci
bool WriteElement(HANDLE file, Potwor* potwor)
{
// Długość nazwy
BYTE dlugosc = static_cast<BYTE>( potwor->nazwa.size() );
if (! WriteCos(file, &dlugosc, sizeof(dlugosc)) ) return false;
// Znaki nazwy
if (! WriteCos(file, potwor->nazwa.c_str(), dlugosc) ) return false;
// Siła
if (! WriteCos(file, &potwor->sila, sizeof(potwor->sila)) ) return false;
// OK
return true;
}
// Funkcja główna - zapisuje plik
bool WritePotwory()
{
bool ok;
// otwarcie pliku do zapisu
HANDLE file = CreateFile("Potwory.ptw", FILE_WRITE_DATA, 0, 0,
CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, 0);
ok = (file != INVALID_HANDLE_VALUE);
if (ok) {
// zapisanie nagłówka
ok = WriteNaglowek(file);
if (ok) {
PotworList::iterator it;
// dla każdego potwora...
for (it = potwory.begin(); it != potwory.end(); ++it) {
// zapisanie go jako element pliku
if (! WriteElement(file, *it) ) {
ok = false;
break;
}
}
}
// zamknięcie pliku
CloseHandle(file);
}
return ok;
}
Teraz odczytywanie:
// Obudowuje funkcję ReadFile() i zwraca false,
// jeśli wystąpi jakiś błąd
bool ReadCos(HANDLE file, void* data, DWORD size)
{
DWORD x;
// jeśli funkcja ReadFile zwróci 0
if ( ReadFile(file, data, size, &x, 0) == 0 ) return false;
// lub jeśli nie uda się odczytać wszystkich bajtów
if ( x != size ) return false;
// OK
return true;
}
// Odczytuje nagłówek z podanego pliku i sprawdza go,
// a także zwraca przez parametr ilość potworów
bool ReadNaglowek(HANDLE file, size_t *ilosc)
{
// Identyfikator formatu
char id[4] = " ";
if (! ReadCos(file, id, 3) ) return false;
if ( strcmp(id, "PTW") != 0 ) return false;
// Ilość potworów
if (! ReadCos(file, ilosc, sizeof(*ilosc)) ) return false;
// OK
return true;
}
// Odczytuje potwora z podanego pliku do podanego miejsca w pamięci
bool ReadElement(HANDLE file, Potwor* potwor)
{
// Długość nazwy
BYTE dlugosc;
if (! ReadCos(file, &dlugosc, sizeof(dlugosc)) ) return false;
// Znaki nazwy
char *nazwa = new char[dlugosc];
if (! ReadCos(file, nazwa, dlugosc) ) {
delete [] nazwa;
return false;
}
potwor->nazwa.append(nazwa, dlugosc);
delete [] nazwa;
// Siła
if (! ReadCos(file, &potwor->sila, sizeof(potwor->sila)) ) return false;
// OK
return true;
}
// Funkcja główna - odczytuje plik
bool ReadPotwory()
{
bool ok;
// otwarcie pliku do odczytu
HANDLE file = CreateFile("Potwory.ptw", FILE_READ_DATA, FILE_SHARE_READ, 0,
OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
ok = (file != INVALID_HANDLE_VALUE);
if (ok) {
size_t ilosc;
// odczytanie nagłówka
ok = ReadNaglowek(file, &ilosc);
if (ok) {
Potwor *p;
// dla każdego potwora...
for (size_t i = 0; i < ilosc; i++) {
p = new Potwor;
// odczytanie go jako element pliku
if (! ReadElement(file, p) ) {
delete p;
ok = false;
break;
}
potwory.push_back(p);
}
}
// zamknięcie pliku
CloseHandle(file);
}
return ok;
}
Kompresja to takie zapisywanie danych, żeby zajęły mniej miejsca. Wprawdzie sam format binarny jest oszczędny i dobry, ale czasami (kiedy danych jest bardzo dużo) warto zastosować kompresję, żeby jeszcze bardziej zmniejszyć ich rozmiar. Metody kompresji można podzielić na bezstratne i stratne.
Kompresja bezstratna to zapisywanie danych w postaci skompresowanej tak, żeby po zdekompresowaniu można było odtworzyć wszystkie oryginalne dane. Metody kompresji bezstratnej wykorzystują pewne regularności w strukturze kompresowanych danych. Kompresja bezstratna wykorzystywana jest w uniwersalnych formatach archiwów, jak RAR czy ZIP, a także w niektórych formatach graficznych, jak PNG.
Najprostszą implementacją kompresji bezstratnej byłoby takie zapisywanie pliku, żeby w miejscu wielu powtarzających się bajtów czy dłuższych sekwencji zapisywać je tylko jeden raz razem z ilością powtórzeń. To jednak nie daje najlepszych rezultatów. Dlatego warto skorzystać z gotowych bibliotek do kompresji danych, jak np. ZLIB.
Kompresja stratna to takie zapisywanie danych w postaci skompresowanej, by w minimalnym rozmiarze dało się zapisać wszystkie najważniejsze dane. Pewne szczegóły ulegają utraceniu. Kompresja stratna jest wydajniejsza, ale nadaje się tylko do danych niektórego rodzaju, jak obraz czy dźwięk. Metody kompresji stratnej są oparte na skomplikowanych wzorach matematycznych oraz na niedoskonałości ludzkich zmysłów i wymagają wiedzy o tym, jakie dane są kompresowane.
Kompresji stratnej używają formaty plików takie, jak JPG czy MP3. Ich stratność polega na tym, że np. w przypadku MP3 nie są zapisywane dźwięki, których i tak byśmy nie usłyszeli, a w przypadku JPG na obrazie widoczne są takie charakterystyczne zakłócenia.
Za wymyślanie własnych metod kompresji stratnej nie ma się co brać chyba, że się jest profesorem matematyki albo innym takim specjalistą. Najlepiej korzystać z gotowych formatów i bibliotek do ich obsługi.
| Cecha | Kompresja bezstratna | Kompresja stratna |
|---|---|---|
| Skuteczność | - Gorsza |
+ Lepsza |
| Uniwersalność | + dowolne dane |
- tylko określone dane |
| Wierność | + wszystkie dane zostają zachowane |
- niektóre szczegóły ulegają utraceniu |
Czasami zachodzi potrzeba zabezpieczania plików przed podglądaniem albo niekontrolowaną modyfikacją. W tym celu można stosować metody takie, jak szyfrowanie czy sumy kontrolne. Nie zawsze to jest potrzebne, bo każdy plik binarny jest w pewien sposób nieczytelny i trudny w modyfikacji. Wszystko zależy od zastosowań.
Szyfrowanie to takie zapisywanie danych, żeby nie dało się ich
odczytać bez znajomości metody szyfrowania i hasła. Najprostsze algorytmy
szyfrujące zapisują np. każdy znak powiększony o pewną liczbę (zamiast A
jest B, zamiast P jest Q, a zamiast Z jest A) albo używają prostych
operacji, jak XOR (operator ^ w C++).
To wystarcza, żeby dane nie były zapisane bezpośrednio i widoczne na
pierwszy rzut oka, ale takie metody są łatwe do złamania. Skuteczne
algorytmy szyfrujące są oparte na skomplikowanych wzorach
matematycznych.
Suma kontrolna to pewna wartość zapisywana w pliku i powiązana z jego danymi. Żeby sprawdzić, czy dane nie zostały zmodyfikowane, trzeba ponownie policzyć z nich sumę kontrolną i porównać z tą zapisaną. Sumy kontrolne można liczyć na wiele sposobów. Najprostszym jest sumowanie kolejnych bajtów ignorując przekroczenia zakresu albo operacja XOR. Są też bardziej zaawansowane, jak CRC.
We wszystkich przedstawionych przykładach plik był w całości i od nowa zapisywany albo w całości odczytywany. Nie zawsze musi tak być. Duże pliki, jak np. obrazy płyt CD-ROM czy bazy danych, nie nadają się do wczytywania w całości do pamięci. Trzeba korzystać z nich w inny sposób. Podstawowe różnice w obsługiwaniu takich plików względem sposobu poznanego wyżej to:
Można sobie wyobrazić zaprojektowanie formatu pliku archiwum, który mógłby zawierać wewnątrz spakowaną całą strukturę katalogów i plików razem z ich zawartością. Takie formaty nazywa się wirtualnymi systemami plików (ang. Virtual File System - VFS) i są szeroko wykorzystywane w grach. Większość dużych gier składa się tylko z kilku ogromnych plików, a w nich wpakowane są wszystkie obrazki, dźwięki i inne potrzebne dane.
Aby dostać się do konkretnego pliku w takim archiwum, trzeba ustawić kursor od razu w odpowiednim miejscu. To jest podstawowa różnica między omawianym wcześniej sekwencyjnym odczytywaniem lub zapisywaniem kolejno wszystkich danych z pliku a swobodnym dostępem do jego zawartości. Gdzieś na początku takiego archiwum może być np. spis wszystkich wpakowanych plików i miejsce w archiwum, od którego zaczyna się treść każdego z nich.
Plik tekstowy to plik, w którym zapisane są znaki i który jest czytelny dla użytkownika. Do podglądania i edytowania plików tekstowych wystarcza jakikolwiek prosty edytor tekstu niesformatowanego, np. systemowy Notatnik.
Decydując się na zapisywanie danych w pliku tekstowym tracisz na wydajności, a taki plik jest większy. Np. każdą liczbę musisz zapisać w postaci łańcucha z kolejnymi cyframi. Używając formatu tekstowego musisz zdecydować się na sposób jego zapisywania:
Nas interesuje oczywiście nie tyle zapisywanie zwykłego tekstu, ile przechowywanie w plikach tekstowych pewnych ustrukturalizowanych danych. Do tego celu trzeba opracować pewien tekstowy format pliku (język opisu) albo skorzystać z jednego z powszechnie używanych.
Najprostszym sposobem przechowywania danych w pliku tekstowym, jaki można sobie wyobrazić, jest zapisywanie kolejnych informacji - łańcuchów czy liczb - w kolejnych linijkach jedna po drugą. Taki format nie jest jednak zbyt czytelny dla użytkownika (nie wiadomo, co dana informacja oznacza), a to jest zazwyczaj w plikach tekstowych istotne. Oto dwa najszerzej stosowne formaty tekstowe:
INI to prosty, używany od dawna format tekstowy wykorzystywany
głównie do przechowywania konfiguracji programów. Ma budowę płaską -
składa się z sekcji [Nazwa], a w każdej z nich może być ciąg par w postaci
klucz=wartość. Przykładowy plik w tym formacie wygląda tak:
; Konfiguracja mojego programu [Main] WindowWidth=640 WindowHeight=480 [Recent] 1=D:\Temp\Mój dokument.coś 2=C:\Moje dokumenty\Pilne.coś 3=A:\Nic.coś
XML (Extensible Markup Language) to format opracowany jako standard przez konsorcjum W3C. Jest coraz częściej wykorzystywany, głównie w zastosowaniach internetowych. Wygląda podobnie do języka HTML, ale w odróżnieniu od niego nie służy do opisywania stron WWW, tylko jest uniwersalnym formatem do przechowywania danych.
XML posiada budowę hierarchiczną, tzn. każdy element może zawierać swoje
podelementy, te mogą zawierać następne itd. Elementy obejmuje się w nawiasy
kątowe <>. Przykładowy dokument wygląda tak:
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <potwory> <potwór siła="10">Szkielet</potwór> <potwór siła="20">Zombi</potwór> </potwory>
Parser to moduł, który zajmuje się analizą tekstu według składni języka (formatu), w którym jest zapisany. Zapisywanie i (szczególnie!) odczytywanie danych z pliku tekstowego wymaga dużo bardziej skomplikowanych algorytmów, niż w przypadku plików binarnych. W tym celu można napisać własny parser lub użyć jednego z gotowych parserów istniejących formatów tekstowych.
Temat plików tekstowych potraktowałem bardzo ogólnie, ponieważ nie chcę kopiować części innego mojego artykułu. Zainteresowanych odsyłam do niego (patrz źródła na końcu tego dokumentu). Opisałem tam dokładnie temat plików tekstowych oraz pisania własnych parserów. Tymczasem tutaj przejdźmy już do podsumowania całego rozdziału:
| Cecha | Pliki binarne skompresowane | Pliki binarne | Pliki tekstowe |
|---|---|---|---|
| Rozmiar | + Mały |
* Średni |
- Duży |
| Szybkość | * Średnia |
+ Duża |
- Mała |
| Zapisywanie i odczytywanie | * Średnie |
+ Łatwe |
- Trudne |
| Czytelność | - Mała |
* Średnia |
+ Duża |
Podsumowując:
O napisaniu takiego artykułu myślałem już od dawna. Podjąłem w nim temat, który jest bardzo ważny dla początkujących, a równocześnie mało ciekawy, by zaawansowanym chciało się o nim pisać. Zauważyłem jednak, że bardzo wielu początkującym programistom pasjonatom brakuje wiedzy z właśnie tej, jakże ważnej dziedziny i często nie wiedzą, w jaki sposób można przechowywać w pamięci i zapisywać na dysku kolekcje obiektów. O randze tego tematu niech świadczy fakt, że na studiach informatycznych "Algorytmy i struktury danych" to osobny przedmiot.
Artykuł starałem się napisać prostym językiem, opisując jedynie podstawowe zagadnienia i skupiając się na zastosowaniach praktycznych. Zrobiłem dużo rysunków, a wszystkie zamieszczone fragmenty kodu uruchomiłem dając pewność, że są poprawne. Czy udało mi się osiągnąć zamierzony cel? To zależy od tego, ile skorzystałeś z lektury tego artykułu...
Na podziękowania zasługuje przede wszystkim Spax, który bezpośrednio zainspirował mnie do napisania tego tekstu, a także Xion, z którym pomagamy sobie wzajemnie w pisaniu naszych tekstów oraz AyuFan, gemGreg i wszyscy fajni ludzie z Warsztatu.
Nie chciałem, żeby ten artykuł miał charakter przeglądu i mam nadzieję, że znalazłeś w nim kilka konkretnych, użytecznych informacji. Jednak poruszony tutaj temat jest równocześnie tematem niejednej kilkusetstronnicowej książki. Dlatego z konieczności opisałem tutaj jedynie podstawowe, najprostsze i najważniejsze struktury danych oraz informacje o plikach. Chciałbym teraz zachęcić do dalszych poszukiwań...
Po pierwsze, zachęcam do dalszego zgłębiania tematu struktur danych. W zaawansowanych zastosowaniach przydatna bywa szeroka wiedza na temat tych trudniejszych struktur, jak drzewa i grafy.
Po drugie, nie mogę nienapisać niczego na temat algorytmów, które są nierozłącznie związane ze strukturami danych. Algorytmika to trudna dziedzina, ale pozwala ona optymalnie rozwiązywać problemy i zarządzać danymi (np. sortować, wyszukiwać), a to jest bardzo ważne.
Zachęcam też do dokładniejszego poznania biblioteki standarowej, szczególnie kontenerów i algorytmów STL. Opisałem tutaj tylko niektóre właściwości kontenerów, a o gotowych do wykorzystania algorytmach zaszytych w bibliotece nie wspomniałem ani słowem.
Wreszcie zachęcam do zapoznania się z niektórymi spośród wymienionych niżej źródeł. Szczególnie podkreślam, że nie należy bać się oryginalnych dokumentacji. Na samych artykułach, kursach i "tutorialach" daleko się nie zajdzie.