Skip to content

presentation_forward_list.md

Latest commit

 

History

History
134 lines (104 loc) · 5.71 KB

presentation_forward_list.md

File metadata and controls

134 lines (104 loc) · 5.71 KB

std::forward_list<T>

Lista jednokierunkowa

Coders School

Cechy std::forward_list<T>

  • Elementy porozrzucane po pamięci
  • Każdy element (węzeł -> ang. node) posiada wskaźnik na następny element
  • Typ <T> może być dowolny. Zarówno typ wbudowany jak int, double, jak i własny zdefiniowany przez nas typ.
  • Nie jest cache-friendly
  • Dodawanie nowego elementu jest proste. Program zaalokuje potrzebną pamięć dla węzła i przekaże poprzedniemu węzłowi (o ile istnieje) informacje o swoim położeniu.
  • Usuwanie elementu jest szybkie, program zwalnia pamięć zaalokowaną dla danego węzła oraz informuje o tym poprzedni węzeł, aby mógł zmienić swój wskaźnik.
  • Wyszukiwanie węzła (np. do usunięcia lub wstawienia za nim nowego elementu) jest już kosztowne, gdyż musimy się przeiterować kolejno przez wszystkie węzły, aż odnajdziemy poszukiwany (nawet, jeżeli dokładnie wiemy, że jest on np. 40-tym elementem listy)

Operacje na std::forward_list<T>

  • dodawanie elementu: push_front(), emplace_front(), insert_after(), emplace_after()
  • modyfikowanie/dostęp do elementu: należy samodzielnie odnaleźć element
  • pierwszy/ostatni element: front()
  • rozmiar/czy kontener jest pusty: nie mamy size(), dostępny jest tylko empty()
  • iterator początku/końca: begin(), end()
  • iterator wskazujący element przed begin(): before_begin()
  • stały iterator: cbegin(), cend(), cbefore_begin()
  • wyczyszczenie kontenera: clear()
  • posortowanie listy: sort()
  • odwrócenie listy: reverse()
  • usunięcie duplikatów: unique()
  • usunięcie elementów z listy: remove()
  • wymazanie elementów z pamięci: erase_after()
  • wymazanie elementów z pamięci używając <algorithm>: erase()
  • podmiana całego kontenera: swap()

std::forward_list<T>::insert_after() && std::forward_list<T>::before_begin()

Lista jednokierunkowa (ang. singly linked list) umożliwia nam wstawianie elementu za konkretnym węzłem. Jeżeli chcemy wstawić wartość na początku listy używając metody insert_after, musimy podać jej specjalny iterator before_begin, który wskazuje element przed pierwszym węzłem listy. W ten sposób, metoda insert_after() wstawi pożądaną przez na wartość dokładnie jako pierwszy element listy.

std::forward_list<int> list {1, 2, 3, 4, 5, 6};
list.insert_after(list.begin(), 10);
print(list);
list.insert_after(list.before_begin(), 0);
print(list);

Output:

1 10 2 3 4 5 6
0 1 10 2 3 4 5 6

std::forward_list<T>::remove()

Ponieważ lista zawiera swoją metodę remove(), nie musimy już korzystać z erase().

std::forward_list<int> list {1, 4, 2, 4, 3, 4, 5};
list.remove(4);
// {1, 2, 3, 5}

std::forward_list<T>::erase_after()

Erase_after służy do usunięcia węzłów od miejsca za elementem wskazanym przez pierwszy iterator do momentu wskazanego przez drugi iterator (bez elementu wskazywanego przez niego).

std::forward_list<int> list {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto it = list.begin();
std::advance(it, 4);
std::cout << "it: " << *it << std::endl;
auto it2 = list.begin();
std::advance(it2, 7);
std::cout << "it2: " << *it2 << std::endl;
list.erase_after(it, it2);
print(list);

Output:

it: 5
it2: 8
1 2 3 4 5 8 9 10

Zadanie 5

  • Znajdź dokumentację std::forward_list na cppreference.com
  • Skorzystaj z kodu z zadania z std::list
  • Stwórz listę jednokierunkową zawierającą elementy od 0 do 5
  • Wyświetl listę
  • Usuń 3 element z listy
  • Dodaj na początek i koniec listy wartość 10
  • Wyświetl listę
  • Dodaj na czwartej pozycji liczbę 20
  • Wyświetl listę

Q&A