Skip to content

Latest commit

 

History

History
89 lines (68 loc) · 7.08 KB

03-list.md

File metadata and controls

89 lines (68 loc) · 7.08 KB
Raw

std::list<T>

Lista dwukierunkowa

Coders School

Cechy std::list<T>

  • Nie jest cache-friendly
    • Elementy są porozrzucane po pamięci
  • Każdy element (węzeł, ang. node) posiada wskaźnik na poprzedni i 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 sąsiednim węzłom (o ile istnieją) informacje o swoim położeniu
  • Usuwanie elementu jest szybkie, program zwalnia pamięć zaalokowaną dla danego węzła oraz informuje o tym sąsiednie węzły, aby mogły zmienić swoje wskaźniki
  • 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::list<T>

Operacje Metody
dodawanie elementu push_back(), emplace_back(),
push_front(), emplace_front(),
insert(), emplace()
modyfikowanie/dostęp do elementu tylko poprzez iteratory
pierwszy/ostatni element back(), front()
rozmiar size()
odwrócony (ang. reverse) iterator rbegin(), rend()
stały iterator cbegin(), cend(), crbegin(), crend()
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()

std::list<T>::remove() && std::list<T>::erase()

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

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

erase() używamy podobnie jak dla std::vector<T>

std::list<int> list{1, 2, 3, 4, 5, 6, 7, 8};
auto it = list.begin();
std::advance(it, 3); // like on pointer ptr += 3
list.erase(list.begin(), it);
// list {4, 5, 6, 7, 8}

std::advance() służy do inkrementowania iteratorów. W naszym przypadku przesuwamy się o 3 elementy do przodu.

Zadanie

  • Znajdź dokumentację std::list na cppreference.com
  • Stwórz nowy plik i napisz funkcję main()
  • Stwórz listę zawierającą elementy od 0 do 5
  • Wyświetl listę
  • Usuń trzeci element z listy
  • Dodaj na początek i koniec listy wartość 10
  • Wyświetl listę
  • Dodaj na czwartej pozycji liczbę 20
  • Przepisz listę do std::array
  • Wyświetl std::array

Q&A