`std::list` în C++

Listă dublu înlănțuită: inserare și ștergere rapidă oriunde, fără invalidarea celorlalte elemente, dar fără acces după poziție.

Sintaxă

#include <list>

std::list<T> nume;
std::list<T> nume{v1, v2, v3};

Ce face `std::list`

Într-un std::list, fiecare element este un nod separat în memorie, legat de nodul anterior și de cel următor. Inserarea sau ștergerea în orice loc (dacă ai deja un iterator acolo) este instantanee, pentru că se schimbă doar legăturile. Iteratorii și referințele la celelalte elemente rămân valide: se invalidează doar cele la elementul șters.

Prețul: nu există operator[] sau at(). Ca să ajungi la al zecelea element trebuie să treci prin primele nouă (std::next(l.begin(), 9)). Parcurgerea este și ea mai lentă decât la vector, pentru că nodurile sunt împrăștiate în memorie.

Lista are funcții membre proprii, care lucrează cu legăturile, fără să copieze elemente: sort, merge, splice, remove, unique, reverse. În practică, std::vector este de cele mai multe ori mai rapid; alege lista când ai nevoie ca iteratorii să rămână valizi sau muți des bucăți între liste.

Parametri

Parametru	Descriere
`T`	Tipul elementelor.

Ce returnează

Un obiect listă, cu push_back, push_front, pop_back, pop_front, insert, erase, front, back, size.

Exemple

Exemplul 1: Inserare în mijloc, cu iteratorii păstrați

Iteratorul ion rămâne valid după inserări și ștergeri în alte locuri ale listei.

#include <algorithm>
#include <list>
#include <print>
#include <string>

int main() {
    std::list<std::string> coada{"Ana", "Ion", "Maria"};
    auto ion = std::find(coada.begin(), coada.end(), "Ion");

    coada.push_front("Radu");
    coada.insert(ion, "Elena");     // înaintea lui Ion
    coada.pop_back();               // pleacă Maria
    std::println("{}", coada);
    std::println("Iteratorul încă arată spre: {}", *ion);
}

Rezultat

["Radu", "Ana", "Elena", "Ion"]
Iteratorul încă arată spre: Ion

Exemplul 2: Ștergere în timpul parcurgerii

#include <list>
#include <print>

int main() {
    std::list<int> numere{1, 2, 3, 4, 5, 6, 7};
    for (auto it = numere.begin(); it != numere.end(); ) {
        if (*it % 3 == 0) {
            it = numere.erase(it);
        } else {
            ++it;
        }
    }
    std::println("{} (size {})", numere, numere.size());
}