Michał Czardybon

Wstęp

STL (Standard Template Library) jest biblioteką dla języka C++ dostarczającą funkcjonalności wspólnej dla niemal wszystkich nietrywialnych programów - w tym przede wszystkim klas uniwersalnych kontenerów (list, drzew binarnych). Od 1998 roku jest ona częścią standardu języka C++. Wcześniej powstało wiele analogicznych bibliotek, właściwie każda firma programistyczna miała swoją własną - przykłady można znaleźć w bibliotekach MFC, wxWindows czy w Borland C++ Builderze. Ty sam zapewne w swoich projektach programistycznych nie raz implementowałeś listy, sterty itp. Dobrze więc stało się, że raz na zawsze rozwiązano ten problem i teraz wszyscy mogą używać tej samej, uniwersalnej bibliteki.

W tym krótkim wprowadzeniu opisuję ogólne koncepcje, potrzebne do rozpoczęcia pracy z biblioteką STL. Więcej informacji, w tym pełną dokumentację, można znaleźć na stronie http://www.sgi.com/tech/stl (lektura obowiązkowa). Warto także zajrzeć do bardziej opisowego opracowania autorstwa: Alexander Stepanov, Meng Lee (wygoogluj).

Krótko o wzorcach

W celu zrozumienia działania biblioteki STL trzeba wcześniej zrozumieć czym są wzorce. Jeśli jednak chcesz szybko zacząć zabawę z STL'em, wystarczy krótkie przedstawienie. Otóż wzorce klas są elementem języka C++ służącymi do opisywania operacji typu copy-paste, czyli tam, gdzie potrzebujesz takiego samego kodu jak ten, który już napisałeś, z tę jedną różnicą, że wszędzie zamiast intów chcesz mieć double. Ta funkcjonalność jest bardzo potrzebna w celu utworzenia klas kontenerów, które działałyby dla różnych typów obiektów zawieranych - np. możesz chcieć mieć listę intów, a w innym miejscu programu listę wskaźników na jakieśtam obiekty.

Używa się tego (w dużym skrócie) w ten sposób, że przed definicją klasy dołącza się deklarację:

   template <class T>

a następnie w miejsce typów, które mają być dowolne, wpisuje się T. Tak zdefiniowany wzorzec używa się podając po nazwie klasy, nazwę typu ujętą w nawiasy ostre (<, >).

Przykład:

   template <class T>
   class Array
   {
   public:
      ...
      T& getItem(int k) { return data[k]; }
   private:
      T* data;
   };
   
   Array<int>my_array_of_int;

Iteratory

Aby nie było zbyt prosto, potrzebujemy jeszcze jednej nowej koncepcji w języku programowania. Jest nią pojęcie iteratora. Iterator jest uogólnieniem wskaźnika (tj. każdy wskaźnik jest iteratorem). Aby zrozumieć dlaczego uogólnienie jest potrzebne, rozważmy przykład tablicy i listy. Zmienna typu tablicowego (w języku C) jest równoważna wskaźnikowi na jej pierwszy element. Dostęp do kolejnych elementów tej tablicy możemy uzyskać za pomocą indeksowania, ale także, co jest zazwyczaj bardziej efektywne, za pomocą inkrementowania wskaźnika. I tak można na przykład zdefiniować funkcję strcpy (kopiowanie stringów w języku C) następująco:

   void strcpy(char* p, char* q)
   {
      while (*q != 0) *p++ = *q++;
   }

Operacji takiej nie można jednak wykonać dla innych typów kontenerów - np. dla listy. Nie można oczywiście tylko wtedy, gdy nie mamy iteratorów, bo iteratory zostały wymyślone właśnie po to, aby było to możliwe. A dlaczego to właściwie jest potrzebne? No nie tylko dla większej wydajności. Przede wszystkim po to, aby można było uogólnić operacje na kontenerach takie, jak na przykład wspomniane kopiowanie, na kontenery dowolnych typów - można wtedy kopiować w dokładnie ten sam sposów tablicę do listy i drzewo binarne do tablicy haszującej! Oczywiście kopiowanie jest tylko przykładem. Za pomocą iteratorów można łatwo wyrazić bardziej skomplikowane operacje takie, jak wyszukiwanie elementu czy sortowanie.

Podsumowując:

Iteratory są po to aby można było używać różnych kontenerów w ten sam sposób.

W bibliotece STL iteratory są klasami wewnętrznymi klas kontenerów, a same kontenery posiadają metody zwracające iteratory - np. metody begin() oraz end() zwracające początek i koniec sekwencji elementów zawieranych. Jak już wspomniałem, iteratorem posługujemy się tak, jak zwykłym wskaźnikiem w przypadku tablicy - czyli aby przejść do następnego elementu korzystamy z operatora “++”, a w celu dostania się do zawartości operatora “*”.

Typowa pętla wypisująca wszystkie elementy kontenera (tutaj tablica liczb) wygląda następująco:

   vector<int>::iterator i;
   for (i = v.begin(); i != v.end(); i++)
   {
      printf(“%d “, (*i));
   }

Jest jeszcze jedna sprawa, o której powinienem wspomnieć - istnieją różne iteratory. Najważniejsze są: Forward Iterator (np. dla listy jednokierunkowej, może przesuwać się tylko w jednym kierunku), Bidirectional Iterator (dla listy dwukierunkowej, może się cofać - operator “--”) i Random Access Iterator (dla tablicy, ale nie dla listy, może się poruszać o dowoną liczbę elementów). Nie wszystkie algorytmy da się wykonać na wszystkich typach iteratorów - np. sortowanie może być wykonane tylko dla iteratorów o dostępie swobodnym.

Kontenery

Biblioteka STL dostarcza następujące kontenery:

• vector - tablica, która może dynamicznie się rozszerzać

• list - lista dwukierunkowa

• set - kontener o logarytmicznym czasie wstawiania i wyszukiwania

• map - tak jak set, ale składa się z par klucz-wartość

• multiset - tak jak set, ale może zawierać zduplikowane elementy

• multimap - tak jak map, ale może zawierać zduplikowane elementy

• priority_queue - kolejka priorytetowa, zwraca element największy w czasie logarytmicznym

Algorytmy

Korzystając z abstrakcji iteratora na powyżych kontenerach lub ogólniej na danych wyznaczonych zakresem iteratorów można wykonywać algorytmy, tak zwane uogólnione. Na przykład:

• sort - wiadomo, sortowanie

• find - znajduje (lub przynajmniej się stara) wskazany element

• copy - kopiowanie elementów wyznaczonych zakresem iteratorów

• unique - wyrzuca zduplikowane elementy

• random_shuffle - wymieszanie elementów (zmiana kolejności na losową)

Co dalej?

W tym krótkim wprowadzeniu przedstawiłem jedynie motywację i ogólne koncepcję potrzebne do rozpoczęcia nauki biblioteki STL. Uznałem, że nie ma sensu kopiować tutaj opisu metod i tym podobnych rzeczy, które można znaleźć w dokumentacji. Ściągnij więc teraz sobie dokumentację ze strony Silicon Graphics i zobacz jak używa się poszczególnych klas. Powodzenia!