C++/Listy

Lista

Kolejnym kontenerem udostępnianym przez STL, nieco mniej popularnym od wektorów, jest klasa list będąca listą dwukierunkową. Oto główne różnice między wektorami a listami:

aspekt	vector	list
dostęp	przez podanie indeksu lub przez iteratory	tylko przez iteratory
dodawanie/usuwanie	jeśli nie chodzi o końcowy element - powolne	dodawanie i usuwanie elementów jest bardzo szybkie i odbywa się w stałym czasie
adresy elementów	ulegają zmianom, wskaźniki często tracą ważność (należy używać wyłącznie indeksów)	niezmienne

Kiedy więc lepszym rozwiązaniem są wektory, a kiedy listy? Jeśli nasza kolekcja raz wprowadzona nie zmienia się, lub rzadko się zmienia (np. tylko dodajemy elementy na koniec), odpowiedni do tego będzie wektor. Jeżeli często wprowadzamy zmiany w kontenerze, np. dodajemy/usuwamy elementy, listy będą tutaj szybszym rozwiązaniem. Wektor będzie bardziej odpowiedni dla operacji na pojedynczych elementach, wskazywanych numerem indeksu. W przypadku listy najlepiej jest przeprowadzać operacje po kolei, np. od pierwszego do ostatniego elementu. W przeciwieństwie do wektora, dostęp do losowego elementu listy jest kosztowną operacją.

Sposób korzystania z list jest niemal identyczny jak w przypadku wektorów. Opis użytych tu iteratorów znajduje się w następnych rozdziałach. Oto przykład wykorzystania list:

#include <list>
#include <iostream>
#include <cstddef>


int main()
{
   std::list<int> lista;
   int liczba;

   std::cout << "Podaj kolejne elementy listy, podaj zero aby zakonczyc:\n";
   while(std::cin >> liczba && liczba != 0)
      lista.push_back(liczba);

   size_t rozmiar = lista.size();
 
   liczba = 0;
   for( std::list<int>::iterator iter=lista.begin(); iter != lista.end(); iter++ )
      liczba += *iter;

   std::cout << "Srednia liczb wystepujacych w liscie wynosi " << static_cast<double>(liczba) / static_cast<double>(lista.size()) << '\n';

   // usuniecie liczb ujemnych
   for( std::list<int>::iterator iter=lista.begin(); iter != lista.end(); )
      if (*iter < 0)
         iter=lista.erase(iter);
      else
         iter++;
      

   liczba = 0;
   for( std::list<int>::iterator iter=lista.begin(); iter != lista.end(); ++iter )
      liczba += *iter;
 
   std::cout << "Srednia dodatnich liczb wynosi " << static_cast<double>(liczba) / static_cast<double>(lista.size()) << '\n';
   
   return 0;
}

W zaprezentowanym powyżej programie, został użyty nowy zapis: while (cin >> liczba && liczba != 0). Wywołuje on pętlę, która kończy działanie gdy użytkownik wpisze 0, gdy program dojdzie do końca pliku, lub gdy użytkownik wpisze coś co nie jest liczbą całkowitą.

Metody

Spis metod klasy list (gdzie iterator to std::list<T>::iterator - podmiana dla czytelności).

Modyfikacja wtyczki

prototyp	opis działania
void push_back(const T obj)	dodaje na końcu listy kopię przekazanego argumentu
void pop_back()	usuwa ostatni element z listy
void push_front(const T obj)	dodaje na początku listy kopię przekazanego argumentu
void pop_front()	usuwa pierwszy element listy
void clear()	usuwa wszystkie elementy z listy
void remove(const T& wartosc)	usuwa wszystkie elementy równe argumentowi wartosc
void remove_if(Functor func)	usuwa wszystkie elementy dla których func (bool funkcja(T arg)) zwróci true (patrz: sort)

Modyfikacja - pozostałe

prototyp	opis działania
void merge(std::list<T> ls)	dostawia zawartość ls do obecnej listy i całość sortuje rosnąco
void merge(std::list<T> ls, Functor func)	dostawia zawartość ls do obecnej listy i całość sortuje przy użyciu func (patrz: funkcja sort poniżej)
void splice(iterator pos, std::list<T>& ls)	wstawia zawartość listy ls przed elementem wskazywanym przez pos (ls staje się pusta)
void splice(iterator pos, std::list<T>& ls, iterator i)	usuwa element wskazywany przez i w liście ls i wstawia go przed elementem pos w obecnej liście
void splice(iterator pos, std::list<T>& ls, iterator poczatek, iterator koniec)	usuwa elementy z przedziału <poczatek;koniec> i wstawia przed elementem pos w obecnej liście
void unique()	usuwa wszystkie następujące po sobie elementy o równych wartościach poza pierwszym spośród nich
void unique(Functor func)	usuwa wszystkie następujące po sobie elementy, dla których func zwróci true (bool funkcja(T arg1, T arg2) poza pierwszym spośród nich
void assign(size_t n, const T obj)	czyści listę i wypełnia ją n kopiami argumentu obj
iterator assign(iterator poczatek, iterator koniec)	czyści listę i wypełnia ją elementami z przedziału <poczatek;koniec>
iterator insert(iterator pos, T obj)	wstawia element obj przed wskazywaną przez iterator pos pozycją i zwraca iterator do dostawionego elementu (stały czas wykonania)
void insert(iterator pos, size_t n, const T obj)	wstawia n kopii argumentu obj przed pozycją wskazywaną przez iterator pos
void insert(iterator pos, iterator poczatek, iterator koniec)	wstawia przed pozycją wskazywaną przez iterator pos elementy między iteratorami początek i koniec (włącznie)
iterator erase(iterator pos)	usuwa element wskazywany przez pos i zwraca iterator do następnego elementu
iterator erase(iterator poczatek, iterator koniec)	usuwa elementy z przedziału <poczatek;koniec> i zwraca iterator do elementu za nimi
void reverse()	odwraca kolejność wszystkich elementów (wykonywane w stałym czasie)
void sort()	sortuje elementy listy
void sort(Functor func)	sortuje elementy listy przy użyciu przekazanej funkcji (bool funkcja(T arg1, T arg2)), może to być wskaźnik na funkcję lub obiekt ze zdefiniowanym operatorem(); zwracana wartość tejże funkcji ma określać czy arg1 < arg2
void swap(std::list<T> ls)	zamienia zawartości dwóch list miejscami (wykonywane szybko, w stałym czasie)

Dostęp

prototyp	opis działania
T& front()	zwraca referencję do pierwszego elementu listy
T& back()	zwraca referencję do ostatniego elementu listy
iterator begin()	zwraca iterator do pierwszego elementu listy (często mylone z front())
iterator end()	zwraca iterator ustawiony za ostatnim elementem listy (określa tym samym element "niepoprawny", nieistniejący w liście)
iterator rbegin()	zwraca odwrócony (reverse) iterator, wskazuje ostatni element i służy do iterowania w odwrotnym kierunku (od ostatniego do pierwszego elementu)
iterator rend()	zwraca odwrócony iterator (podobnie jak end wskazuje element za listą, rend wskazuje teoretyczny element "przed" listą)

Inne

prototyp	opis działania
size_t size()	zwraca obecną ilość elementów listy (działa w czasie liniowym)
size_t max_size()	zwraca ilość elementów, którą maksymalnie może pomieścić lista
bool empty()	zwraca true jeśli lista nie przechowuje żadnych zmiennych
void resize(size_t n, T obj)	zmienia rozmiar listy do n; jeśli jest większy od obecnego, dodawane są nowe elementy będące kopiami obj
void resize(size_t n)	zmienia rozmiar listy do n; jeśli jest większy od obecnego, dodawane są nowe elementy o przypadkowych wartościach

Listy jednokierunkowe

Listy jednokierunkowe są odmianą list dwukierunkowych i nazwane jako slist. Główna różnica między nimi a zwykłymi listami leży w ogólnym mechanizmie działania. Każdy element zwykłych list posiada wskaźniki na poprzedni i następny element w liście, podczas gdy w kontenerze slist każdy element posiada wskaźnik jedynie na kolejny element w liście, skąd też wzięły się ich nazwy. Jakie wynikają z tego różnice dla korzystającego z nich programisty?

Zalety list jednokierunkowych:

• są szybsze w działaniu
• zużywają znacznie mniej pamięci (zwłaszcza, gdy przechowujemy sporo małych elementów, wtedy różnice są bardzo duże)

Wady list jednokierunkowych:

• iteratory mogą przesuwać się jedynie do przodu
• brak odwrotnych iteratorów i funkcji z nimi powiązanych
• funkcje insert, erase oraz splice działają bez porównania wolniej (opis problemu poniżej)

Funkcje insert i splice działają wolniej, gdyż wstawiają elementy przed pozycją wskazywaną przez podany w argumencie iterator. Element, na który wskazuje iterator "nie zna" pozycji poprzedniego elementu, więc aby dostawić element przed nim algorytm listy jednokierunkowej musi przeszukać listę od początku w celu znalezienia poprzedniego elementu.

Funkcja erase z kolei działa wolniej, gdyż po usunięciu danego elementu wskaźnik tego stojącego przed wykasowanym elementem, musi wskazywać na element stojący za usuniętym elementem.

Stąd też postanowiono poszerzyć arsenał list jednokierunkowych względem list dwukierunkowych o nowe metody, które mogą zastąpić owe powolne funkcje, gdyż mają podobne działanie a wykonują się znacznie szybciej. Oto lista nowych metod:

prototyp	opis działania
void splice_after(iterator pos, std::list<T>& ls)	wstawia zawartość listy ls za elementem wskazywanym przez pos (ls staje się pusta)
void splice_after(iterator pos, iterator poczatek, iterator koniec)	usuwa elementy z przedziału (poczatek;koniec+1> i wstawia za elementem pos w obecnej liście
iterator insert_after(iterator pos)	dostawia nowy element za pos
iterator insert_after(iterator pos, T obj)	wstawia element obj za wskazywaną przez iterator pos pozycją i zwraca iterator do dostawionego elementu (stały czas wykonania), przy czym pos != end()
void insert_after(iterator pos, size_t n, const T obj)	wstawia n kopii argumentu obj za pozycją wskazywaną przez iterator pos, przy czym pos != end()
void insert_after(iterator pos, InputIterator poczatek, InputIterator koniec)	wstawia za pozycją wskazywaną przez iterator pos elementy z przedziału <poczatek;koniec>, przy czym pos != end()
void insert_after(iterator pos, T* poczatek, T* koniec)	wstawia za pozycją wskazywaną przez iterator pos elementy z przedziału <poczatek;koniec>, przy czym pos != end()
iterator erase_after(iterator pos)	usuwa następny element za pos i zwraca iterator do następnego elementu (stały czas wykonania)
iterator erase_after(iterator poczatek, iterator koniec)	usuwa elementy z przedziału (poczatek;koniec> i zwraca iterator do elementu za nimi