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<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ą.

Iteratory

Pojemność

Dostęp do elementów

Modifiers

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,
• elementy z wskazywane przezstart 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.