C++/Listy: Różnice pomiędzy wersjami
Usunięta treść Dodana treść
wandalizm |
|||
Linia 1:
== Lista ==
Kolejnym kontenerem udostępnianym przez STL, nieco mniej popularnym od wektorów, jest klasa <tt>list</tt> będąca listą dwukierunkową. Oto główne różnice między wektorami a listami:
{| class="wikitable"
! 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. Opis użytych tu iteratorów znajduje się w następnych rozdziałach. Oto przykład wykorzystania <tt>list</tt>:
<source lang="cpp">
#include <list>
#include <iostream>
#include <cstddef>
using namespace std;
int main()
{
list<int> lista;
int liczba;
cout << "Podaj kolejne elementy listy, podaj zero aby zakonczyc:\n";
while(cin >> liczba && liczba != 0)
lista.push_back(liczba);
size_t rozmiar = lista.size();
liczba = 0;
for( list<int>::iterator iter=lista.begin(); iter != lista.end(); ++iter )
liczba += *iter;
cout << "Srednia liczb wystepujacych w liscie wynosi " << static_cast<double>(liczba) / static_cast<double>(lista.size()) << '\n';
// usuniecie liczb ujemnych
for( list<int>::iterator iter=lista.begin(); iter != lista.end(); )
if (*iter < 0)
iter=lista.erase(iter);
else
++iter;
liczba = 0;
for( list<int>::iterator iter=lista.begin(); iter != lista.end(); ++iter )
liczba += *iter;
cout << "Srednia dodatnich liczb wynosi " << static_cast<double>(liczba) / static_cast<double>(lista.size()) << '\n';
return 0;
}
</source>
W zaprezentowanym powyżej programie, został użyty nowy zapis: '''while (cin >> liczba && liczba != 0)'''. Wywołuje on pętlę nieskończoną, 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 <tt>list</tt> (gdzie iterator to list<T>::iterator - podmiana dla czytelności).
=== Modyfikacja ===
{| class="wikitable"
! 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 ===
{| class="wikitable"
! prototyp
! opis działania
|----
| 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
|----
| 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'''(list<T> ls)
| zamienia zawartości dwóch list miejscami (wykonywane szybko, w stałym czasie)
|}
=== Dostęp ===
{| class="wikitable"
! 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
|----
| iterator '''rbegin'''()
| zwraca odwrócony iterator do pierwszego elementu
|----
| iterator '''rend'''()
| zwraca odwrócony iterator do ostatniego elementu
|}
=== Inne ===
{| class="wikitable"
! 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?<br\ ><br\ >
{{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)
<br\ >
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.<br\ >
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.<br\ >
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:
{| class="wikitable"
! 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
|}
<noinclude>{{Nawigacja|C++|
[[../Vector|Vector]]|
[[../Set|Set]]|
}}</noinclude>
| |||