# När ska man använda STL list

15 juli 2025 | https://www.ribomation.se/blog/2025/nar-ska-man-anvanda-stl-list/

Om du har ett applikationsproblem rörande en container med många insättningar och/eller uttag i mitten på containern (dvs inte i någon av ändarna), så är `std::list` det givna valet. Till skillnad för övriga block-baserade sekvens-containrar så har list en konstant insert/extract time, dvs O(1), oberoende av antalet element.

Eftersom det är en länkad struktur, så går det inte att hoppa direkt till ett element utan man får iterera sig fram. Ett annat sätt att formulera detta på är att list erbjuder en bidirectional iterator, medan vector och deque erbjuder en random-access iterator.

```cpp
#include <list>
#include <iterator>
//...
auto lst = std::list<int>{1,2,3,4,5,6,7,8,9,10};
std::println("init:   {}", lst);

auto iter = lst.begin();
std::advance(iter, 4);
std::println("advance: {}", *iter);

lst.insert(iter, 42);
lst.insert(iter, 43);
lst.insert(iter, 44);
std::println("insert: {} ({})", lst, *iter);

iter = lst.erase(iter);
iter = lst.erase(iter);
iter = lst.erase(iter);
std::println("erase:  {} ({})", lst, *iter);

for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it % 2 == 1) it = lst.erase(it);
    else ++it;
}
std::println("even:   {}", lst);
```

```shell
init:   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
advance: 5
insert: [1, 2, 3, 4, 42, 43, 44, 5, 6, 7, 8, 9, 10] (5)
erase:  [1, 2, 3, 4, 42, 43, 44, 8, 9, 10] (8)
even:   [2, 4, 42, 44, 8, 10]
```

Internt är den realiserad som en dubbel-länkad cirkulär lista med huvud (_circular doubly linked list with a sentinel_). Varje nod har två pekare, den ena pekar på nästa nod (`next`) och den andra på föregående nod (`prev`). Här är en skiss över hur det ser ut med tre element.

  ![Internals of std::list<T>](/blog/2025/nar-ska-man-anvanda-stl-list/std-list-1300w.png "Internals of std::list<T>")

Huvudelement innehåller ingen data, utan när listan är tom, så är det bara den som finns kvar. Det innebär att next och prev pekar tillbaka på head noden.

  ![Internals of std::list<T>](/blog/2025/nar-ska-man-anvanda-stl-list/std-list-empty-1300w.png "Internals of std::list<T>")

Detta är en kolossalt effektiv representation av en lista där insert utförs med fyra assignments och erase med två, oberoende var i listan man pekar.

```cpp
void insert(iterator pos, ElementType data) {
    auto node       = new Node<ElementType>{data};
    node->prev      = pos;
    node->next      = pos->next;
    pos->next->prev = node;
    pos->next       = node;
}

void erase(iterator pos) {
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    delete pos;
}
```

Det finns ytterligare en länkad list-typ i biblioteket, som heter `std::forward_list`. Denna är en enkel-länkad lista, vilket betyder att varje nod bara har en next pekare. Detta gör att man bara kan göra insert/erase i början av listan, om det ska vara effektivt. Min personliga uppfattning är att det är synnerligen få fall där man verkligen har nytta av denna. Ett sådant är som så kallad bucket list vid implementation av en hash-table.

Men jag nämner denna så att min genomgång av sekvens-containrar i C++ STL nu är komplett. Dvs jag har i en liten serie av artiklar beskrivit std::vector, std::array, std::deque och nu std::list samt omnämnt std::forward\_list.