När ska man använda 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.

#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);

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.

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.

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.

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.