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:
Implementacja listy w bibliotece standardowej to szablon z dwoma parametrami.
template < class T, class Allocator = allocator<T> > 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: list.cpp
List udostępnia następujące metody którymi możemy manipulować jego zawartością.
Konstruktory | Tworzą liste i inicjalizują przekazanymi danymi. |
operator= | Kopiuje zawartość konera |
Iteratory
begin | Zwraca iterator na peirwszy element |
end | Zwraca iterator na ostatni element |
rbegin | Zwraca reverse_iterator na odwrócony początek |
rend | Zwraca reverse_iterator na odwrócony koniec |
Pojemność
empty | Sprawdza czy lista zawiera jakieś elementy |
size | Zwraca rozmiar kontenera |
max_size | Zwraca maksymalny możliwy rozmiar kontenera |
resize | Zmienia rozmiar kontenera |
Dostęp do elementów
Modifiers
assign | Przydziela nową zawartość do kontenera |
push_front | Wstawia element na początku |
pop_front | Usuwa pierwszy element |
push_back | Dodaje element na końcu |
pop_back | Usuwa ostatni element |
insert | Wstawia elementy |
erase | Usuwa elementy |
swap | Zamienia zawartość listy |
clear | Usuwa wszystkie elementy z listy |
Operacje na liście
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<T,Allocator>& x );
Konstruktor kopiujący
list<T,Allocator>& operator= ( const list<T,Allocator>& x );
Przypisuje kontenerowi kopię kontenera podanego jako argument x. Całą pierwotna zawartość kontenera jest kasowana.
iterator begin(); const_iterator begin() const;
Funkcja zwraca iterator do pierwszego elementu listy.
iterator end(); const_iterator end() const;
Funkcja zwraca iterator wskazujący za ostatni element Listy, co ułatwia iterację.
reverse_iterator rbegin(); const_reverse_iterator rbegin() const;
Funkcja zwraca odwrotny iterator wskazujący na koniec listy.
reverse_iterator rend(); const_reverse_iterator rend() const;
Funkcja zwraca odwrotny iterator wskazujący na początek listy.
bool empty() const;
Funkcja zwraca wartość logiczną true
jeśli lista jest pusty, false
w przeciwnym przypadku.
size_type size() const;
Funkcja zwraca liczbę elementów znajdujących się w kontenerz.
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: capacity, max_size
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.
reference front ( ); const_reference front ( ) const;
Funkcja zwraca referencje do pierwszego elementu w liście.
reference back ( ); const_reference back ( ) const;
Funkcja zwraca referencje do ostatniego elementu w liście.
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
,start
oraz end
.void push_front ( const T& x );
Funkcja dodaje element o wartości x
na początek listy.
void pop_front();
Funkcja usuwa pierwszy element z listy.
void push_back ( const T& x );
Funkcja dodaje element o wartości x
na koniec listy.
void pop_back();
Funkcja usuwa ostatni element z listy.
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 <class InputIterator> void insert ( iterator position, InputIterator first, InputIterator last );
Wstawia zaczynając od pozycji position
wskazanej przez iterator elementy ograniczone iteratorami first
i last
.
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.
void swap ( list<T,Allocator>& lst );
Funkcja zamienia zawartość listy z której był wywołany z zawartością listy podanej jako parametr lst
.
void clear();
Funkcja usuwa wszystkie elementy listy.
void splice ( iterator position, list<T,Allocator>& x );
Przenosi elementy z listy x
, wstawiając je od pozycji wskazywanej przez iterator position
.
void splice ( iterator position, list<T,Allocator>& 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<T,Allocator>& 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
.
void remove ( const T& value );
Funkcja usuwa elementy o wartości value
. Wywoływane są destruktory tych elementów, zmniejszana jest wartość size
.
template <class Predicate> 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
.
void unique ( );
Usuwa wszystkie poza pierwszym równe elementy występujące w ciągu.
template <class BinaryPredicate> 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ą.
void merge ( list<T,Allocator>& x );
Łączy dwie posortowane listy w jedną posortowaną listę.
template <class Compare> void merge ( list<T,Allocator>& 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.
void sort ( );
Funkcja sortuje listę, porównując dwa sąsiadujące ze sobą elementy.
template <class Compare> 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ą.
void reverse();
Funkcja odwraca kolejność elementów w liście.