C++/Listy: Różnice pomiędzy wersjami
Usunięta treść Dodana treść
"pętla nieskończona która kończy działanie"? Dlaczego pętla nieskończona, skoro mamy wprost napisany warunek końca |
m usunięte <br\ > |
||
Linia 203:
== 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:'''
Linia 212 ⟶ 213:
* 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:
| |||