====== List ====== //Autor: Kacper Szkudlarek//\\ List to rodzaj kontenera, który przechowuje dane w liniowej sekwencji. Kontener jest zaimplementowany na zasadzie listy dwukierunkowej, każdy element zawiera wskaźnik na obiekt następny i poprzedni. \\ \\ **Zalety korzystania z kontenera list:** * Wstawianie i usuwanie elementów z kontenera w stałym czasie. * Przenoszenie elementu, bądź grupy elementów w ramach jednego kontenera lub pomiędzy kontenerami odbywa się w stałym czasie. * Przechodzenie po elementach w porządku prostym i odwróconym w czasie liniowym. \\ Implementacja listy w bibliotece standardowej to szablon z dwoma parametrami. template < class T, class Allocator = allocator > class list; gdzie T to typ elementu jaki będziemy przechowywać, a Allocator definiuje sposob przydzielania pamięci dla nowych elementów. Domyślnie jest on już jest on już zdefiniowany. \\ \\ Przykładowy program pokazujący działanie kontenera list: {{:opis_kontenera:list.cpp|list.cpp}} ===== Metody ===== List udostępnia następujące metody którymi możemy manipulować jego zawartością.\\ |[[list#Konstruktory]]|Tworzą liste i inicjalizują przekazanymi danymi.| |[[list#operator=]]|Kopiuje zawartość konera| **Iteratory** |[[list#begin]]| Zwraca iterator na peirwszy element| |[[list#end]]| Zwraca iterator na ostatni element| |[[list#rbegin]]| Zwraca reverse_iterator na odwrócony początek| |[[list#rend]]| Zwraca reverse_iterator na odwrócony koniec| **Pojemność** |[[list#empty]]| Sprawdza czy lista zawiera jakieś elementy| |[[list#size]]|Zwraca rozmiar kontenera| |[[list#max_size]]|Zwraca maksymalny możliwy rozmiar kontenera| |[[list#resize]]|Zmienia rozmiar kontenera| **Dostęp do elementów** |[[list#front]]|Dostęp do pierwszego elementu listy| |[[list#back]]|Dostęp do ostatniego elementu listy| **Modifiers** |[[list#assign]]|Przydziela nową zawartość do kontenera| |[[list#push_front]]|Wstawia element na początku| |[[list#pop_front]]|Usuwa pierwszy element| |[[list#push_back]]|Dodaje element na końcu| |[[list#pop_back]]|Usuwa ostatni element| |[[list#insert]]|Wstawia elementy| |[[list#erase]]|Usuwa elementy| |[[list#swap]]|Zamienia zawartość listy| |[[list#clear]]|Usuwa wszystkie elementy z listy| **Operacje na liście** |[[list#splice]]|Przenosi elementy pomiędzy listami| |[[list#remove]]|Usuwa elementy o określonej wartości| |[[list#remove_if]]|Usuwa elementy spełniające warunek| |[[list#unique]]|Usuwa powtarzające się wartości| |[[list#merge]]|Łączy posortowane listy| |[[list#sort]]|Sortuje listę| |[[list#reverse]]|Odwraca kolejność elementów| === Konstruktory === * explicit list ( const Allocator& = Allocator() ); Konstruktor domyślny, tworzy pustą listę * explicit list ( size_type n, const T& value = T(), const Allocator& = Allocator() ); Tworzy listę zawierającą ''n'' elementów o wartości ''value'' * template < class InputIterator > list ( InputIterator first, InputIterator last, const Allocator& = Allocator() ); Tworzy listę zawierającą elementy z przedziały wskazywanego przez iteratory * list ( const list& x ); Konstruktor kopiujący === operator= === list& operator= ( const list& x ); Przypisuje kontenerowi kopię kontenera podanego jako argument x. Całą pierwotna zawartość kontenera jest kasowana. === begin === iterator begin(); const_iterator begin() const; Funkcja zwraca iterator do pierwszego elementu listy.\\ === end === iterator end(); const_iterator end() const; Funkcja zwraca iterator wskazujący za ostatni element Listy, co ułatwia iterację.\\ === rbegin === reverse_iterator rbegin(); const_reverse_iterator rbegin() const; Funkcja zwraca odwrotny iterator wskazujący na koniec listy.\\ === rend === reverse_iterator rend(); const_reverse_iterator rend() const; Funkcja zwraca odwrotny iterator wskazujący na początek listy. === empty === bool empty() const; Funkcja zwraca wartość logiczną ''true'' jeśli lista jest pusty, ''false'' w przeciwnym przypadku. === size === size_type size() const; Funkcja zwraca liczbę elementów znajdujących się w kontenerz.\\ === max_size === size_type max_size () const; Funkcja zwraca potencjalną maksymalną liczbę elementów jakie mogą znajdować się w Kontenerze. Wielkość ta zależna jest od systemu i implemnetacji.\\ Podobne: [[vector#capacity]], [[vector#max_size]] === resize === void resize ( size_type sz, T c = T() ); Funkcja zmienia rozmiar listy do rozmiaru ''sz''. \\ Jeśli wartość ''sz'' jest większa od aktualnego rozmiaru, to nowe elementy będą miały wartość ''c''. W przeciwnym wypadku wielkość kontenera jest redukowana, a nadmiarowe elementy usuwane. === front === reference front ( ); const_reference front ( ) const; Funkcja zwraca referencje do pierwszego elementu w liście. === back === reference back ( ); const_reference back ( ) const; Funkcja zwraca referencje do ostatniego elementu w liście. === assign === void assign( size_type num, const TYPE& val ); void assign( input_iterator start, input_iterator end ); Metoda ''assign()'' wstawia do listy: * ''num'' elementów o wartości ''val'', * elementy z wskazywane przez''start'' oraz ''end''. === push_front === void push_front ( const T& x ); Funkcja dodaje element o wartości ''x'' na początek listy. === pop_front === void pop_front(); Funkcja usuwa pierwszy element z listy. === push_back === void push_back ( const T& x ); Funkcja dodaje element o wartości ''x'' na koniec listy. === pop_back === void pop_back(); Funkcja usuwa ostatni element z listy. === insert === * iterator insert ( iterator position, const T& x ); Wstawia element ''x'' na pozycje wskazywaną przez iterator ''position''. * void insert ( iterator position, size_type n, const T& x ); Wstawia ''n'' elementów ''x'' zaczynając od pozycji ''position''. * template void insert ( iterator position, InputIterator first, InputIterator last ); Wstawia zaczynając od pozycji ''position'' wskazanej przez iterator elementy ograniczone iteratorami ''first'' i ''last''. === erase === * iterator erase ( iterator position ); Usuwa element wskazywany prze iterator ''position''. * iterator erase ( iterator first, iterator last ); Usuwa elementy wskazywane przez iteratory ''first'' i ''last'' Funkcja zwraca iterator do pierwszego nie usuniętego elementu. === swap === void swap ( list& lst ); Funkcja zamienia zawartość listy z której był wywołany z zawartością listy podanej jako parametr ''lst''.\\ === clear === void clear(); Funkcja usuwa wszystkie elementy listy. === splice === * void splice ( iterator position, list& x ); Przenosi elementy z listy ''x'', wstawiając je od pozycji wskazywanej przez iterator ''position''. * void splice ( iterator position, list& x, iterator i ); Przenosi elementy z listy ''x'', zaczynając od pozycji ''i'', wstawiając je od pozycji wskazywanej przez iterator ''position''. * void splice ( iterator position, list& x, iterator first, iterator last ); Przenosi elementy z listy ''x'', zawarte pomiędzy iteratorami ''first'' i ''last'', wstawiając je od pozycji wskazywanej przez iterator ''position''. === remove === void remove ( const T& value ); Funkcja usuwa elementy o wartości ''value''. Wywoływane są destruktory tych elementów, zmniejszana jest wartość ''size''. === remove_if === template void remove_if ( Predicate pred ); Usuwa elementy spełniające warunek ''pred''. Warunek może być zaimplementowany jako dowolny typ wyrażenia pobeirającego jako argument element typu listy i zwracający wartość ''bool''. === unique === * void unique ( ); Usuwa wszystkie poza pierwszym równe elementy występujące w ciągu. * template void unique ( BinaryPredicate binary_pred ); Usuwa wszystkie poza pierwszym równe elementy występujące w ciągu, równość określona jest przez warunek ''binary_pred'', pobierający dwa elementy z listy i zwracający odpowiednią wartość logiczną. === merge === * void merge ( list& x ); Łączy dwie posortowane listy w jedną **posortowaną** listę. * template void merge ( list& x, Compare comp ); Łączy dwie posortowane listy w jedną **posortowaną** listę, przy łączeniu używa warunku ''comp'' dla ustalenie kolejności elementów, która pobiera dwa elementy i zwraca odpowiednią wartość logiczna. === sort === * void sort ( ); Funkcja sortuje listę, porównując dwa sąsiadujące ze sobą elementy. * template void sort ( Compare comp ); Funkcja sortuje listę, porównując dwa sąsiadujące ze sobą elementy, do porównanie używana jest funkcja ''comp'' pobierająca dwa elementy i zwracająca odpowiednią wartość logiczną. === reverse === void reverse(); Funkcja odwraca kolejność elementów w liście.