Struktury danych i formaty plików

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Spis treści

  1. Wstęp
  2. Struktury danych
  3. Formaty plików
  4. Zakończenie

Wstęp

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ść:

  1. języka C++
  2. wskaźników

Artykuł obejmuje:

  1. podstawy struktur danych
  2. podstawy STL
  3. tworzenie własnych formatów plików
  4. operacje na plikach

Wstęp do STL

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:

Jeśli niewiele z tego rozumiesz, nie przejmuj się. Wszystko wyjaśni się w dalszej części.

Notacja dużego O (notacja asymptotyczna)

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):

Złożoność stała
O(1) Oznacza, że ilość operacji jest stała i nie zależy od ilości danych, na jakich operujemy.
Złożoność logarytmiczna
O(log n) Występuje wtedy, gdy zbiór jest dzielony na coraz to mniejsze części.
Złożoność liniowa
O(n) Oznacza, że ilość operacji do wykonania jest wprost proporcjonalna do ilości danych, np. kiedy trzeba przebiegnąć po wszystkich elementach zbioru.
Złożoność kwadratowa
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.

Wykresy różnych funkcji

Struktury danych

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 (wektor)

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

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.

Tablica statyczna, indeksowanie

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.

Tablica dynamiczna

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ł.

Dodawanie i usuwanie, capacity

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!

Dodawanie do wektora

// 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.

Wstawianie do wektora

// 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.

Usuwanie z wektora

// 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.

Realokacja

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:

  1. Utworzenie nowego bloku pamięci
  2. Przepisanie wszystkich elementów ze starego do nowego
  3. Usunięcie starego bloku

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;
}

Dziury

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!

Wektor STL

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:

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.

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.

Podsumowanie

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 znaków (string)

Ł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++.

Łańcuch tradycyjny

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.

Łańcuch

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:

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().

Łańcuch STL

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:

  1. Podczas przekazywania parametru nie zostanie wykonana kopia łańcucha.
  2. Nie będzie można wewnątrz funkcji zmieniać oryginalnej treści podanego łańcucha.
  3. Można podawać do funkcji stałą dosłowną, np.: MyMessage("Nastąpił straszny błąd");.

Tablica dwuwymiarowa (macierz)

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ą.

Tablica dwuwymiarowa

Statyczna tablica dwuwymiarowa

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]

Dynamiczna tablica dwuwymiarowa

Pomysł na realizację dynamicznej tablicy dwuwymiarowej polega na utworzeniu tablicy tablic. Będziemy więc musieli użyć wskaźnika do wskaźnika.

Tablica tablic

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;

Tablica dwuwymiarowa zlinearyzowana

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:

Linearyzujemy macierz

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) ];
}

Różne macierze

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.

Macierz trójkątna

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.

Macierz nieregularna

Lista łączona

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).

Lista łączona

Jak działa lista?

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.

Dodawanie do listy

Usuwanie elementów jest równie proste. Wystarczy usunąć z pamięci dany element, a wskaźnik w poprzednim ustawić na następny.

Usuwanie z listy

Podsumowując, powinieneś zapamiętać następujące wiadomości na temat listy:

Lista STL

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;
}

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.

Różne listy

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 dwukierunkowa

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).

Macierz rzadka

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).

Macierz rzadka jako lista

Talia

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.

Talia

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.

Talia STL

Ż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 [].

Zestawienie

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:

  1. Wektora należy używać, kiedy najważniejszy jest szybki dostęp do dowolnych elementów przez indeksy.
  2. Listy należy używać, kiedy najważniejsze jest szybkie wstawianie i usuwanie elementów w dowolnym miejscu.
  3. Talii należy używać, kiedy potrzebne są obydwie te cechy na raz.

Przez "najważniejsze" należy rozumieć, że dana operacja jest wykonywana bardzo często.

Stos i kolejka

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

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.

Stos

Stos w STL

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

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ą.

Kolejka

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 w STL

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;
}

Drzewo

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:

Drzewo

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:

Węzeł
to element drzewa.
Korzeń
to element na pierwszym poziomie - ten główny.
Węzeł potomny
to pod-węzeł danego węzła - tak jak podkatalog na dysku.
Liść
to węzeł nie posiadający węzłów potomnych - na rysunku zaznaczone są ciemnym kolorem.
Gałąź
to pewna ścieżka połączeń w drzewie.

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ć:

Drzewa binarne
każdy węzeł może mieć maksymalnie 2 węzły potomne.
Drzewa czwórkowe
każdy węzeł może mieć maksymalnie 4 węzły potomne.

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.

Zbiory i wielozbiory STL

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:

  1. Elementów nie można modyfikować - żeby to zrobić trzeba usunąć stary, a potem dodać nowy.
  2. Elementy muszą być takiego typu, żeby kontener mógł je porównywać (czyli stwierdzić, czy jeden jest większy od drugiego), co jest potrzebne podczas sortowania - np. liczby, znaki albo typy własne, w których specjalnie postaramy się o możliwość ich porównywania.
  3. Elementy nie mogą się powtarzać - nie może być kilku takich samych.

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;
}

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.

Mapy i multimapy STL

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.

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.

Wektor
jest dobry, kiedy najważniejszy jest szybki, swobodny dostęp do dowolnych elementów przez indeksowanie.
Lista
jest dobra, kiedy najważniejsze jest szybkie wstawianie i usuwanie elementów w dowolnym miejscu.
Mapa
jest dobra, kiedy najważniejsze jest szybkie znajdowanie elementów.

Graf

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

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:

Skierowane
Połączenia między elementami są w postaci strzałek od jednego do drugiego - czyli tylko w jedną stronę (jak ten na rysunku). Wtedy mogłyby być dwa osobne połączenia między tymi samymi dwoma elementami skierowane w przeciwne strony.
Nieskierowane
Połączenia nie mają kierunku - dwa elementy są połączone albo nie są.

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.

Formaty plików

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.

Wstęp do plików

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.

Budowa pliku

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:

  1. Będzie tylko jeden plik w takim formacie, ukryty gdzieś i wykorzystywany wewnętrznie przez program, np. plik przechowujący konfigurację (ustawienia) programu.
  2. Format, w którym program będzie przechowywał swoje dokumenty, które użytkownik będzie mógł nazywać, zapisywać i odczytywać, kopiować i przenosić (np. format dokumentów twojego edytora tekstu albo zapisane gry - "save" - w twojej grze).

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:

Budowa pliku

Nagłówek to dane na początku pliku, które niosą informacje:

  1. O formacie, w jakim plik jest zapisany. Użytkownik identyfikuje format pliku po jego rozszerzeniu, ale program nie powinien na nim polegać i zawsze sprawdzać nagłówek. Identyfikator formatu to zazwyczaj kilka znaków, np. GIF89a w plikach graficznych GIF, Rar! w archiwach RAR czy MZ w programach EXE. Od tych znaków rozpoczyna się plik.
  2. O wersji formatu. Być może kiedyś będziesz chciał rozszerzyć swój format pliku o nowe rzeczy i wtedy twój nowy program będzie musiał poprawnie zidentyfikować, czy plik zapisany jest w starej, czy w nowej wersji twojego formatu (tak jak dokumenty Microsoft Word). Stary program nie powinien akceptować plików w nowej wersji, a nowy powinien obsługiwać obydwie (oczywiście preferując nową).
  3. Ogólne informacje o zapisanych danych, np. rozmiar obrazka w pliku graficznym (dalej następują kolory kolejnych punktów obrazu).

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:

  1. Przed odczytaniem każdego następnego elementu sprawdzać, czy kursor odczytujący nie znajduje się na końcu pliku.
  2. W nagłówku pliku zapisywać z góry, ile plik liczy elementów.
  3. Na końcu zapisywać dodatkowy element specjalnego typu, który będzie oznaczał koniec.

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.

Inna budowa pliku (1)

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.

Inna budowa pliku (2)

Obsługa plików w Windows API

Obsługę plików można pisać na wiele sposobów, m.in.:

  1. Za pomocą funkcji C - fopen(), fclose(), fwrite(), fread(). Te funkcje są przestarzałe, zaleca się wariant 2.
  2. Za pomocą strumieni C++ - klas ofstream i ifstream. Ten sposób jest przenośny między różnymi systemami.
  3. Za pomocą funkcji Windows API - 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:

  1. Nazwa pliku razem z pełną ścieżką bezwzględną, np. C:\Moje dokumenty\Savy\Save1.gam.
  2. Sama nazwa pliku, tak jak w kodzie powyżej, albo nazwa razem ze ścieżką względną, np. ..\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:

  1. Sprawdzenie, czy udało się otworzyć plik (funkcja CreateFile() zwróciła poprawny uchwyt do pliku, a nie wartość równą INVALID_HANDLE_VALUE).
  2. Sprawdzenie, czy udało się zapisać do pliku (funkcja WriteFile() zwróciła wartość różną od zera).
  3. Sprawdzenie, czy udało się zapisać tyle bajtów, ile chcieliśmy zapisać (zmienna 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ć:

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.

Pliki binarne

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 :)

Własny format

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

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

Zabezpieczenia

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.

Wolny dostęp

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.

Pliki tekstowe

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:

  1. Standard kodowania znaków (np. jedna ze stron kodowych z polskimi literami, jak Windows-1250 czy ISO-8859-2 albo Unikod UFT-8 czy UTF-16)
  2. Standard zapisywania końca linii (np. znak LF, jak w Linuksie czy para CR i LF, jak w Windows)

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:

Format INI

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ś

Format XML

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>

Obsługa plików tekstowych

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:

Pliki binarne skompresowane
mają sens wtedy, kiedy:
  • dane dobrze się kompresują (np. obraz, muzyka)
  • danych jest bardzo dużo
  • dane muszą zajmować jak najmniej (np. mają być przesyłane przez Internet)
Pliki binarne
mają sens prawie zawsze, kiedy nie ma żadnych przeciwwskazań, szczególnie jeśli:
  • danych jest względnie dużo
  • ważna jest szybkość ich zapisywania i odczytywania
Pliki tekstowe
mają sens wtedy, gdy:
  • danych jest mało
  • rozmiar danych oraz szybkość zapisywania i odczytywania nie jest sprawą krytyczną
  • plik powinien być czytelny oraz możliwy do modyfikacji przez użytkownika poza wykorzystującym go programem

Zakończenie

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.

Co dalej?

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.

Źródła

Strony WWW

MSDN Library
Skarbnica wiedzy na tematy wszelakie, w szczególności Windows API, ale także C++ i STL. Najważniejsze to nauczyć się odnajdywać w niej informacje.
Standard Template Library Programmer's Guide
Jedno z wielu dostępnych w Sieci źródeł informacji na temat STL.
World Wide Web Consortium
Organizacja, która opracowała m.in. format XML i inne z nim związane.
The Programmer's File Format Collection
Zbiór dokumentów z opisami bardzo wielu różnych formatów plików.
zlib Home Site
Darmowa, uniwersalna biblioteka C++ do kompresji danych. Przydatna do tworzenia własnych, skompresowanych formatów plików.
Cyfrowe przetwarzanie tekstu
Mój artykuł na temat tekstu, m.in. tekstowych formatów plików i pisania parserów.

Książki

Algorytmy w C++
Autor: Robert Sedgewick
Stron: 634
Wydawnictwo: Grupa Wydawnicza ReadMe
Bardzo dobra i obszerna, ale też niełatwa książka o algorytmach i strukturach danych.
Algorytmy w C++ .Grafy
Autor: Robert Sedgewick
Stron: 472
Wydawnictwo: Grupa Wydawnicza ReadMe
Drugi tom powyższej książki. W całości traktuje o grafach.
Algorytmy i struktury danych z przykładami w Delphi
Autor: Rod Stephens
Stron: 380
Wydawnictwo: Helion
Bardzo fajna książka. Przykłady w Delphi.
Algorytmy, struktury danych i techniki programowania. Wydanie II
Autor: Piotr Wróblewski
Stron: 348
Wydawnictwo: Helion
Kolejna książka, która opisuje interesujący nas temat. Niestety trochę wybiórczo i ogólnikowo. Autor postanowił zawrzeć na tej niewielkiej ilości stron także informacje o metodach numerycznych, sztucznej inteligencji, kompresji danych itp.
Algorytmy + struktury danych = programy
Autor: Wirth Niklaus
Stron: 384
Wydawnictwo: Wydawnictwa Naukowo-Techniczne
Klasyczna pozycja na temat algorytmów i struktur danych. Niestety bardzo teoretyzująca. Przykłady są w pseudokodzie stylizowanym na język Pascal (którego Wirth jest twórcą).
C++. Biblioteka standardowa. Podręcznik programisty
Autor: Nicolai M. Josuttis
Stron: 728
Wydawnictwo: Helion
Szczegółowa i wyczerpująca książka na temat biblioteki standardowej C++. Można w niej znaleźć dokładny opis kontenerów i algorytmów STL. Wymagana doskonała znajomość języka C++.
Adam Sawicki
2004-05-14
[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2019