Skip to content

Latest commit

 

History

History
138 lines (106 loc) · 9.79 KB

04-forward-list.md

File metadata and controls

138 lines (106 loc) · 9.79 KB

std::forward_list<T>

Lista jednokierunkowa

Coders School

Cechy std::forward_list<T>

  • Nie jest cache-friendly
    • Elementy są 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.
  • 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>

Operacje Metody
dodawanie elementu push_front(), emplace_front(),
insert_after(), emplace_after()
modyfikowanie/dostęp do elementu tylko poprzez iteratory
pierwszy/ostatni element front(), brak back()
rozmiar brak size()
iterator wskazujący element przed begin() before_begin()
odwrócony (ang. reverse) iterator brak rbegin() i rend()
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()

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

Lista jednokierunkowa 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 nas 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

  • 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