C++/Listy: Różnice pomiędzy wersjami

Usunięta treść Dodana treść
Linia 1:
== Metody ==
Spis metod klasy <tt>list</tt> (gdzie iterator to list<T>::iterator - podmiana dla czytelności).
 
== 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>