PO Kolekcje

<<< Powrót

Kolekcje

Wprowadzenie

Rzadko kiedy zdarzają się tak proste programy, którym do działania wystarcza kilka zmiennych zadeklarowanych w programie. Zwykle programy muszą operować na większej liczbie wartości. Wiemy już, że możemy w tym celu użyć tablic. Często jest to wystarczające rozwiązanie, ale ma ono pewne ograniczenia. Tablice mają stały rozmiar, a często przy pisaniu programów występują sytuacje, gdy liczba przechowywanych wartości zmienia się w trakcie działania programu. Co więcej bardzo często chcemy narzucić pewną strukturę przechowywanym wartościom (na przykład chcemy, by były posortowane, albo chcemy utrzymywać powiązanie między dwoma zestawami wartości). Ponieważ takie sytuacje zdarzają się bardzo często, praktycznie wszystkie współczesne języki programowania obiektowego dostarczają zestaw kolekcji - klas służących do przechowywania obiektów.

Ponieważ kolekcje mają być uniwersalne, to znaczy maja służyć do przechowywania obiektów różnych typów, w naturalny sposób do ich tworzenia wykorzystuje się omówione przez nas wcześniej typy uogólnione. Można nawet zaryzykować stwierdzenie, że kolekcje są głównym powodem, dla którego wprowadza się do języków programowania typy uogólnione.

Inną ciekawą dla nas cechą kolekcji jest ich organizacja. Wszystkie kolekcje służą do przechowywania obiektów. Skoro tak to są zestawem podobnych do siebie klas. A zatem naturalnie i wygodnie będzie przedstawić je w postaci hierarchii. Dzięki temu nauczenie się posługiwania się kolekcjami jest dużo prostsze. Nie musimy dla każdej kolekcji od nowa uczyć się jej interfejsu - języka jakim mamy się z nią porozumiewać. Jeśli raz nauczymy się ogólnego interfejsu kolekcji, to przy kolejnych członkach tej hierarchii będziemy musieli uczyć się jedynie specyficznych dla danej kolekcji pojęć i operacji. Co więcej, mając hierarchię kolekcji możemy tworzyć bardzo abstrakcyjne programy, które działają z (nieokreślona z góry) kolekcją zadaną jako parametr i w zależności od tego jaką kolekcję otrzymają inaczej się zachowują. Klasycznym przykładem jest tu problem obchodzenia grafu: jeśli program obchodzący graf dostanie jako parametr stos, to dokona obejścia grafu wgłąb, jeśli natomiast jako parametr otrzyma kolejkę, to obejdzie graf wszerz.

Kolejnym powodem dla którego tak dokładnie przyjrzymy się kolekcjom jest sposób dostępu do zawartych w nich danych. Oczywiście sam fakt przechowywania wartości nie wystarcza, ważne jest by można było wygodnie na nich operować. W tym celu w podejściu obiektowym stosuje się szereg standardowych technik, z których najczęściej spotykaną jest zastosowanie wzorca Iterator.

Nasze rozważania o kolekcjach zakończymy rozważeniem pewnych niebezpieczeństw związanych z ich stosowaniem. Przede wszystkim zastanowimy się co właściwie chcemy przechowywać w kolekcjach (oryginały czy ich kopie) oraz przyjrzymy się pewnym anomaliom pojawiającym się wtedy, gdy korzystając z niektórych kolekcji zapomnimy o przedefiniowaniu operacji ``equals lub hash.

Kolekcje w Javie

Zacznijmy od sprecyzowania pojęcia kolekcji. Przez kolekcję będziemy rozumieli obiekty służące do przechowywania (innych) obiektów i udostępniające mechanizmy pozwalające na wstawianie, przeglądanie i pobieranie składowanych w nich obiektów. Dodatkowo będziemy też oczekiwać, że kolekcja jest w stanie pomieścić w zasadzie dowolną (to znaczy ograniczoną tylko pojemnością pamięci komputera) liczbę obiektów, choć nie musi to oznaczać, że każda kolekcja ma mieć zmienny rozmiar (być może rozmiar będziemy musieli zadać od razu przy tworzeniu kolekcji). To dodatkowe żądanie oznacza, że np. obiektów klasy Para (z wykładu o typach uogólnionych), nie chcemy traktować jako kolekcji. Dla uproszczenia nazwą kolekcja będziemy również określać klasy obiektów będących kolekcjami i interfejsy definiujące właściwe dla kolekcji zachowania implementowane przez te obiekty.

Uwaga notacyjna: hierarchia interfejsów i klas kolekcji w Javie jest bardzo rozbudowana, przy czym ani dla interfejsów ani dla klas nie jest drzewem (w obu przypadkach jest lasem). W związku z tym, mimo tego że w pakiecie java.util występuje interfejs Collection nie wszystkie omawiane przez nas kolekcje go implementują czy dziedziczą. Tym nie mniej poręczniej będzie nam używać w dalszej części wykładu terminu kolekcja w szerszym znaczeniu (w odniesieniu do obiektów, klas i interfejsów służących do przechowywania grup obiektów), a nie tylko do podinterfejsów oraz klas i obiektów implementujących interfejs Collection).

Java dostarcza bardzo bogaty zestaw kolekcji, zawierający interfejsy, klasy abstrakcyjne i oczywiście klasy konkretne. Część z tych kolekcji służy specjalnym zastosowaniom (np. przy tworzeniu aplikacji webowych), część została stworzona z myślą o rozwiązaniu specyficznych problemów (np. związanych z synchronizowaniem dostępu do kolekcji przy programowaniu współbieżnym). W naszych rozważaniach nie będziemy ich brać pod uwagę i skupimy się jedynie na najbardziej ogólnych kolekcjach i ich zastosowaniu.

Kolekcje w Javie zostały umieszczone w pakiecie java.util, zatem na początku programów korzystających z kolekcji zazwyczaj umieszczamy deklarację umożliwiająca dostęp do całego pakietu:

 import java.util.*;

Przegląd kolekcji

Nasz przegląd kolekcji zaczniemy od przyjrzenia się najważniejszym pojęciom wprowadzonym przez ich twórców. Oto (uproszczona) hierarchia interfejsów kolekcji w Javie.

Po pierwsze zwróćmy uwagę, że jest ona lasem złożonym z dwóch drzew. Większe z nich ma jako korzeń interfejs Comparable<T>. Ten interfejs jest bardzo skromny - składa się tylko z jednej metody:

 public interface Iterable<T>{
   Iterator<T> iterator();
 }

Klasy implementujące ten interfejs zobowiązują się do dostarczenia narzędzia pozwalającego na przeglądanie ich zawartości - iteratora. Jakkolwiek taki mechanizm jest bardzo użyteczny (i będziemy często po niego sięgać), nie stanowi on o byciu (lub nie) kolekcją i dlatego na razie odłożymy jego dokładniejsze omówienie. Więcej na temat klasy Iterator<T> powiemy w dalszej części tego wykładu.

Sama nazwa kolejnego interfejsu - Collection - świadczy o jego kluczowym znaczeniu w hierarchii kolekcji. W rzeczy samej jest to interfejs "typowej" kolekcji. Przypatrzmy się zatem mu dokładniej.

 public interface Collection<E>
        extends Iterable<E>{
 // ...
 }

Podstawową informacją o kolekcji jest to, czy w ogóle zawiera ona jakieś elementy. Tę informację możemy dostać za pomocą interfejsu Collection aż na dwa sposoby

 boolean isEmpty();
 int size();

Oczywiście druga metoda jest bardziej ogólna (ale i niebezpieczna), gdyż podaje liczbę elementów kolekcji. Jeśli nie wiesz czemu druga wersja jest niebezpieczna, to zajrzyj do dokumentacji tej metody (wskazówka: kolekcje mogą być potencjalnie dowolnie duże).

Jeśli okaże się, że kolekcja jest pusta, to pewnie będziemy chcieli coś do niej wstawić

 boolean add(E e);
 boolean addAll(Collection<? extends E> c);

Pierwsza z metod wstawia pojedynczy element do kolekcji. Zwróćmy uwagę, że realizacja tej operacji będzie bardzo się różniła w zależności od kolekcji do której wstawiamy element, na przykład dla zbioru może się okazać, że po wykonaniu operacji add liczba elementów kolekcji się nie zmieniła. To czego oczekujemy od kolekcji implementującej ten interfejs to zapewnienie, że wskazany element zostanie dodany do kolekcji, w sposób zgodny z rodzajem tej kolekcji (np. na odpowiednie miejsce w zadanym porządku, jeśli to będzie kolekcja posortowana). Użytkownik tego interfejsu nie może niczego więcej zakładać o realizacji (np. zwiększenia rozmiaru kolekcji). Druga operacja wstawia do jednej kolekcji (tej dla której wywołano addAll) wszystkie elementy drugiej kolekcji (parametru c). Warto zwrócić uwagę na to, że choć na pierwszy rzut oka druga metoda wydaje się bardziej ogólna i można by za jej pomocą zastąpić użycia pierwszej<ref name="PO_kol_tworzenie_kolekcji">Jest możliwe utworzenie kolekcji jednoelementowej za pomoca tablic bez użycia operacji add.</ref>, to zwykle postępuje się odwrotnie i drugą z nich implementuje za pomocą pierwszej, gdyż można to zrobić w sposób bardzo ogólny.

Przypisy

<references/>