PO Kolekcje - przegląd

<<< Powrót

Kolekcje - przegląd

Wprowadzenie

Poznaliśmy już ogólny sposób posługiwania się kolekcjami i wiemy, ze pozwala on pisać bardzo ogólne programy, które odwołują się jedynie do interfejsów, a nie do ich implementacji. To niesłychanie ważna i cenna możliwość, pozwalająca pisać ogólniejsze programy, a przez to znacznie ułatwiające ich późniejsze modyfikowanie. Jeśli tylko można, to powinno się programować w kategoriach używanych interfejsów, a nie konkretnych klas.

Są jednak sytuacje, gdy koniecznie musimy wiedzieć z jaką konkretną klasą mamy do czynienia. Czasami dlatego, że spośród wielu klas implementujących jakiś interfejs koniecznie chcemy wybrać tę, która ma najlepsze specyficzne własności, na przykład szybkość działania albo zużywa najmniej pamięci. No i oczywiście zawsze wtedy, gdy już napisawszy program w kategoriach interfejsów musimy dostarczyć mu konkretne obiekty.

Dlatego w tym wykładzie przyjrzymy się różnym implementacjom kolekcji. Zbadamy jakie możliwości oferują poszczególne klasy (na przykład które są szybsze w działaniu i jaką za to płacimy cenę). Będziemy też przy tej okazji zastanawiali się nad całą konstrukcją tej części biblioteki klas. Na koniec zajmiemy się typowymi problemami związanymi z korzystaniem z kolekcji.

Przegląd klas implementujących kolekcje

Na załączonym rysunku przedstawimy hierarchię klas implementujących kolekcje w Javie.<ref name="PO_kol_liczba">Na przedstawionym diagramie nie zamieściliśmy kompletu kolekcji z Javy (jest ich o wiele więcej), wybraliśmy jedynie te najbardziej znaczące.</ref>

Po pierwsze widzimy, że klasy wszystkich kolekcji są klasami uogólnionymi. To bardzo cenne, bo oznacza, że możemy się nimi posługiwać w sposób bezpieczny ze względu na typy. Po drugie, zwraca uwagę duża liczba klas, których nazwy zaczynają się od słowa "Abstract". Mimo że większość użytkowników Javy raczej nie będzie miała okazji z nich (bezpośrednio) skorzystać, my zaczniemy nasz przegląd klas właśnie od nich, bo ilustrują ciekawe z obiektowego punktu widzenia podejście.

Klasy abstrakcyjne

Jak już wiemy klasy abstrakcyjne, to klasy które nie mają (i nie mogą mieć) obiektów. Mimo tego ograniczenia są niesłychanie użyteczne przy budowaniu hierarchii pojęć (klas). Ze względu na brak wielodziedziczenia w Javie, klasy abstrakcyjne pełnią tu jednak znacząco mniej istotną rolę, niż np. w C++. Bardzo często zamiast nich używamy w Javie interfejsów.

Oba rozwiązania (klasy abstrakcyjne i interfejsy) mają swoje zalety i wady, warto używać obu tych rozwiązań w swoich programach. Jednak na pierwszy rzut oka może dziwić, czemu hierarchia kolekcji jest trójwarstwowa:

• interfejsy,
• klasy abstrakcyjne,
• klasy konkretne.

Wbrew pozorom nie jest to ani dziwne, ani rzadkie rozwiązanie.

Pierwsza warstwa (interfejsów) jest przeznaczona przede wszystkim dla użytkowników - tu jest opisane jakich pojęć dostarcza hierarchia (bibliotek) i jak się nimi posługiwać. Jak pokazywaliśmy wcześniej, znajomość tej warstwy praktycznie wystarcza do programowania w kategoriach narzędzi i usług dostarczanych przez daną bibliotekę. Podkreślaliśmy nawet, że należy dążyć do tego, by tworzone programy nie starały się sięgać poniżej tej warstwy (poza przypadkami, gdzie tworzymy obiekty i musimy wskazać ich konkretne klasy).

Dla kogo zatem jest druga warstwa? Dla twórców biblioteki - zarówno jej wersji pierwotnej jak i dla tych, którzy ją rozbudowują. Dlatego jest to dla nas tak ważna - wszak nie tylko po to tak dokładnie omawiamy tę bibliotekę, by poznać szczegóły jej używania, ale przede wszystkim po to, by nauczyć się konstruować własne biblioteki i hierarchie pojęć.

Interfejsy są znakomite do opisywania tego, jak posługiwać się pojęciami (klasami) dostarczanymi przez biblioteki (właściwie jedyne co można im zarzucić, to fakt, że nie pozwalają opisywać konstruktorów). Często jednak przy tworzeniu hierarchii klas okazuje się, że jesteśmy w stanie opisać na bardzo wysokim poziomie abstrakcji implementację niektórych z operacji udostępnianych przez bibliotekę. Bardzo dobrym przykładem takiej sytuacji jest metoda addAll z poprzedniego wykładu. Oczywiście nie miałoby sensu w każdej klasie implementującej interfejs Collection zapisywać tę implementację na nowo. Nie można tego również zrobić w warstwie interfejsów. Pozostaje zatem dodanie warstwy klas abstrakcyjnych, w której zawarta zostanie ta część implementacji, która nie zależy od konkretnych rozwiązań przyjętych w klasach konkretnych.

W hierarchii kolekcji te klasy pełnią jeszcze dodatkową funkcję. Gdybyśmy chcieli dodać własną kolekcję (nie jest to wprawdzie bardzo częsta sytuacja ze względu na bogactwo klas już istniejących), to nie musimy w tym celu pisać wiele metod - wystarczy aby nowa klasa dziedziczyła po odpowiedniej klasie abstrakcyjnej. Na przykład żeby stworzyć nową realizację sekwencji elementów za pomocą listy wystarczy stworzyć klasę dziedziczącą po klasie AbstractSequentialList i zaimplementować zaledwie dwie metody: listIterator i size. Z kolei dostarczenie odpowiedniego iteratora (dla listy której nie będziemy modyfikować) wymaga zaimplementowania w nim jedynie metod hasNext, next, hasPrevious, previous, nextIndex i previousIndex.

Obecność trzeciej warstwy jest oczywista. Zwróćmy jednak uwagę na to, że dzięki wprowadzeniu pierwszej i drugiej warstwy warstwa implementacji jest bardzo ustrukturalizowana, a dzięki drugiej warstwie jej implementacja jest znacznie uproszczona - definiując nowe klasy definiujemy tylko te ich cechy, które są różne w stosunku do pozostałych klas.

Przyjrzyjmy się jeszcze bliżej klasom abstrakcyjnym wymienionym na naszym diagramie kolekcji.

AbstractCollection<E>

Już na tak wysokim poziomie abstrakcji jest sporo metod, które można zaimplementować. To bardzo istotne i pouczające - budujmy własne hierarchie klas tak, by wyodrębniać te operacje, którymi istotnie się różnią przedstawione w naszej hierarchii pojęcia, a resztę funkcjonalności budujmy w kategoriach tych pojęć.

Pamiętajmy też o tym, ze podanie implementacji w klasie abstrakcyjnej nie oznacza, że wszystkie podklasy są skazane na tę właśnie implementację. Metody możemy swobodnie przedefiniowywać w podklasach, a dzięki polimorfizmowi mamy pewność, że zawsze zostanie wywołana właściwa wersja metody.

Niektóre z zaimplementowanych tu metod są bardzo proste, jak na przykład isEmpty:

 public boolean isEmpty() {
   return size() == 0;
 }

Piękno rozwiązań obiektowych wykorzystujących dziedziczenie polega nie tylko na tym, że jesteśmy w stanie wydefiniować pojęcie bycia pustą kolekcją, nie mając jeszcze żadnej konkretnej kolekcji, tak jak to zrobiono w powyższym przykładzie (zaczerpniętym zresztą z oryginalnej implementacji klasy AbstractCollection), ale też na tym, że gdy w jakiejś kolekcji okaże się, że policzenie liczby jej elementów jest kosztowną operacją, a my uznamy, że użytkownicy tej kolekcji stosunkowo często będą badać jej pustość, to wystarczy, że w tej kolekcji na przykład dodamy atrybut pusta, będziemy go stosownie modyfikować przy operacjach wstawiania i usuwania i przekazywać jako wynik operacji isEmpty. Dziedziczenie w połączeniu z polimorfizmem daje wielką elastyczność, pozwala proponowac gotowe rozwiązania, ale nie zmusza do ich stosowania.

Oczywiście w klasie AbstractCollection znajdziemy też ciekawsze metody, na przykład contains:

 public boolean contains(Object o) {
   Iterator<E> e = iterator();
   if (o==null) {
     while (e.hasNext())
       if (e.next()==null)
         return true;
   } else {
     while (e.hasNext())
       if (o.equals(e.next()))
         return true;
   }
   return false;
 }

Zwróćmy uwagę na zastosowanie iteratora, dzięki niemu możemy opisać przejście całej kolekcji, mino że nie znamy jej implementacji. Drugim ciekawym elementem w tej implementacji jest traktowanie wartości null. Biblioteka kolekcji Javy nie jest do końca jednorodna, jeśli chodzi o traktowanie tej wartości. Czasem ta wartość jest traktowana jako pełnoprawna i dozwolona, czasem z kolei jest używana do sygnalizowania (jako wartość wyniku metod) różnych nietypowych sytuacji. W niektórych językach obiektowych wartość null jest też obiektem, co znacznie ułatwia jej jednorodne traktowanie. W Javie null' oznacza pustą referencję, więc nie można od tej wartości wywoływać żadnych metod. W szczególności metody equals i to jest powód, dla którego w powyższej metodzie są dwie wersje wyszukiwania, jedna specjalnie dla wartości null.

Oczywiście można by zapytać, po co w ogóle wstawiać do kolekcji wartość null, wszak kolekcje mają służyć do przechowywania obiektów, a nie informacji o ich braku. Jednak jest kilka powodów, dla których dobrze jest móc czasami umieścić w kolekcji tę wartość. Po pierwsze często wstawia się do kolekcji nie konkretne, dopiero co utworzone obiekty, lecz obiekty wyliczane przez inne metody. Często te metody jako wynik potrafią przekazać wartość null. We fragmencie programu takim jak poniżej:

 ...
 p = inny_obiekt.metoda();
 kolekcja.add(p);

trudno jest stwierdzić, czy nie następuje wstawienie do kolekcji pustej referencji. Można oczywiście dodać tu sprawdzenie za pomocą instrukcji warunkowej, ale wymaganie, żeby przy każdym wstawianiu do kolekcji dokonywać takich sprawdzeń byłoby bardzo kłopotliwe i przez wiele programów nie byłoby zachowywane. Ponadto czasami wygodne jest wstawianie do kolekcji specjalnych znaczników (na przykład w algorytmie przechodzenia grafu wszerz ze zliczaniem minimalnej odległości odwiedzanych wierzchołków od wierzchołka startowego wygodnie jest zaznaczać koniec jednej warstwy odwiedzonych wierzchołków) a wartość null jest w tej roli bardzo poręczna.

Na zakończenie rozważań na temat wartości null w kolekcjach warto zauważyć, że problemy z tą wartością dotyczą nie tylko kolekcji, i że podejmowane są próby przeniesienia części sprawdzeń tego, czy referencja w danym miejscu programu nie jest pusta na poziom sprawdzania zgodności typów (na przykład przez wprowadzanie dwu wersji typu referencyjnego, zwykłej i takiej, która nie obejmuje wartości null). Ten bardzo ciekawy temat wykracza jednak poza ramy naszego wykładu.

AbstractList<E>

Kolejna abstrakcyjna klasa AbstractList (podklasa klasy AbstractCollection) jest prawie kompletną implementacją interfejsu List<E>. Omówimy kilka ciekawych zagadnień związanych z jej implementacją.

Zacznijmy od bardzo prostej metody add (jak zwykle korzystamy z oryginalnej treści metod udostępnianej przez producenta):

 public boolean add(E e) {
   add(size(), e);
   return true;
 }

Zwróćmy uwagę na to, że kolejne pojęcia są definiowane - o ile to tylko możliwe - w kategoriach innych pojęć (w tym przypadku jest tak, że metodę dodającą element na zadanej pozycji ma zdefiniować użytkownik, o ile chce by kolekcja pozwalała na dodawanie nowych elementów). Ta definicja jedynie precyzuje, że wstawianie do listy oznacza wstawianie na koniec. Jeśli z jakiś powodów zmienimy implementację listy, to tej metody zmieniać nie będziemy musieli, będziemy więc mieć nie tylko mniej pracy, ale także mniej okazji do popełnienia błędów.

Przy okazji, implementacja wstawiania na zadanej pozycji w tej klasie wygląda następująco:

 public void add(int index, E element) {
   throw new UnsupportedOperationException();
 }

Zatem użytkownik tej klasy, który chce mieć kolekcję bez operacji wstawiania nie musi tej operacji implementować. To rozwiązanie ma niestety też i wady. Jeśli użytkownik tej klasy jednak gdzieś w programie przez pomyłkę wywoła operacje wstawienia, to błąd ten nie zostanie wykryty przez kompilator i dopiero podczas działania programu będzie wygenerowany wyjątek.

Ciekawą cechą tej klasy jest również to, że implementuje ona własny iterator (a dokładniej dwa iteratory, jeden zwykły (Iterator) i drugi listowy (ListIterator). To typowe rozwiązanie, każda kolekcja implementuje specyficzny dla siebie iterator w postaci zagnieżdżonej klasy.

Zwróćmy tez uwagę na przykład ciekawego wykorzystania interfejsów - jako interfejsów znacznikowych - w metodzie sublist:

 public List<E> subList(int fromIndex, int toIndex) {
   return (this instanceof RandomAccess ?
           new RandomAccessSubList<E>(this, fromIndex, toIndex) :
           new SubList<E>(this, fromIndex, toIndex));
 }

RandomAccess jest pustym interfejsem (nie zawiera żadnej deklaracji). Zgodnie z dokumentacją interfejsu List<E> te jego implementacje, które oferują szybki (czyli praktycznie w czasie stałym) dostęp do elementów kolekcji mogą wskazać, że realizują interfejs RandomAccess, co pozwala potem twórcom algorytmów listowych wybierać realizację lepiej dostosowaną do struktury danych. Tu mamy akurat przykład operacji dającej podlistę listy istniejącej. Nie wnikając w szczegóły zastosowanych tu klas RandomAccessSubList<E> i SubList<E> możemy zauważyć, że typ tworzonej (pod)listy zależy od własności listy, na której działamy. Metody tworzące nowe obiekty typu zależnego od pewnych warunków pozwalają na tworzenie bardzo wygodnych i elastycznych rozwiązań, bo zauważmy, że użytkownik tej metody sam nie musi podawać, jaka podlista ma być stworzona, decyzję podejmuje metoda subList w sposób niewidoczny dla użytkownika.<ref>Podkreślmy też w tym miejscu, że użycie instanceof w programach obiektowych powinno być zawsze starannie przemyślane. Zwykle zamiast kodu stosującego tę operację można stworzyć dużo krótszy i czytelniejszy zapis korzystając z polimorfizmu.</ref> Zauważmy też, że mamy tu kolejny przykład sytuacji prowadzącej do polimorfizmu - użytkownik tej metody nie wie jaka będzie konkretna klasa jej wyniku, ale wie, że będzie to klasa realizująca interfejs List<E> co w zupełności wystarcza do operowania na tym wyniku.

Implementacje pozostałych klas abstrakcyjnych nie są w tej chwili dla nas istotne, więc ich omówienie pomijamy.

Przypisy

<references/>