C++/Listy

Z Wikibooks, biblioteki wolnych podręczników.

[edytuj] Listy dwukierunkowe

Kolejnym kontenerem udostępnianym przez STL, nieco mniej popularnym od wektorów, są listy. Oto najwyraźniejsze 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ść	niezmienne

Kiedy więc lepszym rozwiązaniem są wektory, a kiedy listy? Jeśli operujemy na pojedynczych elementach kontenera, lepszym rozwiązaniem są wektory, gdyż podajemy po prostu indeks do interesującego nas elementu. Gdy nasze algorytmy za każdym razem przetwarzają cały kontener od początku do końca, bez cienia wątpliwości lepszym rozwiązaniem są listy. Jeżeli zdarza się, że dodajemy/usuwamy elementy umieszczone gdzieś w środku kontenera, tutaj bez wątpienia powinniśmy wybrać listy.
Sposób korzystania z list jest niemal identyczny jak w przypadku wektorów. Oto przykład wykorzystania:

#include <list>
// ...
list<int> lista;
int liczba;

printf("podaj liste liczb (0 przerywa sekwencje):\n");
while(true)
{
  scanf("%d", &liczba);
  if(liczba == 0)
    break;
  lista.push_back(liczba);
}

int rozmiar = lista.size();

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

printf("srednia tych liczb wynosi %0.2f\n", (double)liczba / (double)lista.size());

liczba = 0;

for(list<int>::iterator iter=lista.begin(); iter != lista.end();)
  if(*iter > 0)
  {
    liczba += *iter;
    lista.erase(iter++);
  }
  else iter++;

printf("srednia dodatnich liczb wynosi %0.2f\n", (double)liczba / (double)(rozmiar - lista.size()));

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

prototyp	opis działania
void swap(list<T> ls)	zamienia zawartości dwóch list miejscami (wykonywane szybko, w stałym czasie)
void merge(list<T> ls)	dostawia zawartość ls do obecnej listy i całość sortuje rosnąco
void merge(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, list<T>& ls)	wstawia zawartość listy ls przed elementem wskazywanym przez pos (ls staje się pusta)
void splice(iterator pos, 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, list<T>& ls, iterator poczatek, iterator koniec)	usuwa elementy z przedziału <poczatek;koniec> i wstawia przed elementem pos w obecnej liście
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
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)
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
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
iterator rbegin()	zwraca odwrócony iterator do pierwszego elementu
iterator rend()	zwraca odwrócony iterator do ostatniego elementu

[edytuj] 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?

Uwaga! Listy jednokierunkowe znajdują się w pliku nagłówkowym ext/slist zaś definicja samych list jednokierunkowych w przypadku kompilatora gcc znajduje się w przestrzeni nazw __gnu_cxx. Nie zapomnij o odwoływaniu się do tej przestrzeni, gdyż kompilator nie będzie "widzieć" tej definicji!

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, 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