C++ list e deque

O std::vector é ótimo para pôr e tirar itens no fim. Mas e se você precisa pôr gente no começo da fila, ou no meio? Para isso a STL tem mais dois containers de sequência: a std::list (inserir e remover no meio sem empurrar ninguém) e o std::deque (crescer pelas duas pontas). Esta aula mostra como cada um funciona, o que eles não sabem fazer, quanto custa cada operação, e por que, mesmo assim, o conselho continua sendo: comece pelo vector.

Todos os programas desta aula foram compilados com o g++ 15.2 na máquina fictícia da Ana, na pasta ~/cpp/ld, com g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa. É bom conhecer std::vector e Iteradores.

A ideia: a fileira de cadeiras, o trem e a fila de duas portas

• O vector é uma fileira de cadeiras parafusadas no chão. Achar a cadeira 7 é instantâneo (é só contar). Mas para pôr alguém na cadeira 1, todo mundo da cadeira 1 em diante tem que se levantar e andar uma cadeira para a direita.
• A list é um trem: cada vagão sabe qual é o da frente e o de trás. Para pôr um vagão no meio, você desengata dois vagões e engata o novo entre eles. Ninguém mais se mexe. Mas para chegar no vagão 7, tem que andar do primeiro até ele, vagão por vagão.
• O deque (lê-se "déc", de double-ended queue, "fila de duas pontas") é uma fila com duas portas: dá para entrar e sair pela frente e por trás, rápido. Por dentro, são vários blocos de cadeiras; dá para achar a cadeira 7 contando, quase tão rápido quanto no vector.

1. std::list: inserir no meio

#include <algorithm>
#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> fila{"Ana", "Bruno", "Davi"};

    fila.push_back("Eva");
    fila.push_front("Zeca");

    auto pos = std::find(fila.begin(), fila.end(), "Davi");
    fila.insert(pos, "Carla");

    fila.remove("Bruno");

    for (const auto& nome : fila) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
    std::cout << "Primeiro: " << fila.front() << ", último: " << fila.back() << '\n';
}

#include <list>

O cabeçalho da std::list.

push_back / push_front

Engata um vagão no fim / no começo. Na list, as duas são baratas.

std::find(…, "Davi")

Procura o Davi andando vagão por vagão e devolve um iterador para ele (aula Iteradores).

fila.insert(pos, "Carla")

Engata a Carla antes do vagão apontado por pos. Nenhum outro item se move.

fila.remove("Bruno")

Desengata todos os vagões com o valor "Bruno". É um método só da list.

front() / back()

O primeiro e o último item.

$ g++ -std=c++23 -Wall -Wextra fila-list.cpp -o fila-list
$ ./fila-list
Zeca Ana Carla Davi Eva
Primeiro: Zeca, último: Eva

Uma vantagem da list que o vector não tem: inserir ou apagar um item não invalida os iteradores dos outros itens. O pos que apontava o Davi continua apontando o Davi depois do insert, porque o Davi não saiu do lugar. Só o iterador do item apagado deixa de valer.

#include <algorithm>
#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> fila{"Ana", "Bruno", "Davi"};

    // ponha a Carla antes do Davi aqui

    for (const auto& nome : fila) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
}

#include <algorithm>
#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> fila{"Ana", "Bruno", "Davi"};

    auto pos = std::find(fila.begin(), fila.end(), "Davi");
    fila.insert(pos, "Carla");

    for (const auto& nome : fila) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
}

2. A list não tem []

No vector, notas[1] pega o segundo item na hora. Na list, isso não existe:

#include <iostream>
#include <list>

int main() {
    std::list<int> notas{7, 9, 4};
    std::cout << notas[1] << '\n';
}

$ g++ -std=c++23 -Wall -Wextra colchetes.cpp -o colchetes
colchetes.cpp: In function ‘int main()’:
colchetes.cpp:6:23: error: no match for ‘operator[]’ (operand types are ‘std::__cxx11::list<int>’ and ‘int’)
    6 |     std::cout << notas[1] << '\n';
      |                       ^

"Não há operator[] (o colchete) para uma list<int> e um int." No editor do guia, o Clang diz type 'std::list<int>' does not provide a subscript operator ("o tipo não oferece operador de índice"). Não é esquecimento: é de propósito. Chegar no vagão 1000 exige andar 1000 vagões, e os criadores da STL não quiseram esconder esse custo atrás de um [] que parece instantâneo.

Se você precisa mesmo do item número tal, ande com o iterador, usando std::next (cabeçalho <iterator>), e deixe o custo à vista:

#include <iostream>
#include <iterator>
#include <list>

int main() {
    std::list<int> notas{7, 9, 4, 10};
    auto it = std::next(notas.begin(), 2);
    std::cout << *it << '\n';

    notas.sort();
    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra posicao.cpp -o posicao
$ ./posicao
4                        « std::next andou 2 vagões a partir do primeiro
4 7 9 10                 « notas.sort(): o método de ordenar da própria list

Se você usa std::next com números o tempo todo, é sinal de que escolheu o container errado: use um vector.

3. std::sort não serve para list

Por que o exemplo acima usou notas.sort() e não std::sort, como na aula O que é a STL? Porque o std::sort precisa pular direto para o meio da faixa (ele faz contas como fim - começo), e os iteradores da list só sabem andar um passo de cada vez. Veja o que acontece:

#include <algorithm>
#include <list>

int main() {
    std::list<int> notas{7, 3, 9};
    std::sort(notas.begin(), notas.end());
}

$ g++ -std=c++23 -Wall -Wextra ordenar.cpp -o ordenar
In file included from /usr/include/c++/15/algorithm:63,
                 from ordenar.cpp:1:
/usr/include/c++/15/bits/stl_algo.h: In instantiation of ‘constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = _List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’:
/usr/include/c++/15/bits/stl_algo.h:4841:18:   required from ‘constexpr void std::sort(_RAIter, _RAIter) [with _RAIter = _List_iterator<int>]’
 4841 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ordenar.cpp:6:14:   required from here
    6 |     std::sort(notas.begin(), notas.end());
      |     ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/15/bits/stl_algo.h:1907:50: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘std::_List_iterator<int>’)
 1907 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~
/usr/include/c++/15/bits/stl_algo.h:1907:50: note: there are 2 candidates
In file included from /usr/include/c++/15/bits/stl_algobase.h:67,
                 from /usr/include/c++/15/algorithm:62:
/usr/include/c++/15/bits/stl_iterator.h:620:5: note: candidate 1: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)’
  620 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/15/bits/stl_iterator.h:620:5: note: template argument deduction/substitution failed:
/usr/include/c++/15/bits/stl_algo.h:1907:50: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::reverse_iterator<_IteratorL>’
 1907 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~
/usr/include/c++/15/bits/stl_iterator.h:1785:5: note: candidate 2: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’
 1785 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/15/bits/stl_iterator.h:1785:5: note: template argument deduction/substitution failed:
/usr/include/c++/15/bits/stl_algo.h:1907:50: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::move_iterator<_IteratorL>’
 1907 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~

Vinte e nove linhas. Use a técnica da aula Templates de Função:

1. A linha required from here: ordenar.cpp:6:14, a chamada do std::sort. É ali que está o problema.
2. O primeiro error:: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘std::_List_iterator<int>’). Tradução: "não sei fazer - entre dois iteradores de list". O sort tentou calcular __last - __first (quantos itens há entre o fim e o começo), e iterador de list não faz essa conta.
3. O resto (candidate 1, candidate 2, reverse_iterator, move_iterator) são as outras funções - que o compilador tentou. Pode ignorar.

O conserto: notas.sort();. A list tem o próprio sort, que reengata os vagões na ordem certa, sem pular. Ela também tem reverse(), unique() (tira repetidos vizinhos) e remove(valor).

4. std::deque: a fila de duas pontas

A Ana atende numa lojinha. Clientes chegam no fim da fila, mas quem tem prioridade (idosos, gestantes) entra na frente. E o atendimento sempre tira da frente.

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> atendimento{"Bruno", "Carla"};

    atendimento.push_back("Davi");
    atendimento.push_front("Dona Lúcia");

    std::cout << "Primeira: " << atendimento.front() << '\n';
    std::cout << "Terceiro: " << atendimento[2] << '\n';

    atendimento.pop_front();
    atendimento.pop_back();

    for (const auto& nome : atendimento) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
}

#include <deque>

O cabeçalho do std::deque.

push_back("Davi")

Entra no fim, como no vector.

push_front("Dona Lúcia")

Entra na frente, sem empurrar os outros. É a razão de existir do deque.

atendimento[2]

O deque tem []: {"Dona Lúcia", "Bruno", "Carla", "Davi"}, posição 2 = Carla.

pop_front() / pop_back()

Tira o primeiro / o último. Repare que não devolvem nada: leia com front() antes, se precisar do valor.

$ g++ -std=c++23 -Wall -Wextra deque.cpp -o deque
$ ./deque
Primeira: Dona Lúcia
Terceiro: Carla
Bruno Carla

E o vector? Ele simplesmente não tem push_front:

$ g++ -std=c++23 -Wall -Wextra vector-frente.cpp -o vector-frente     « notas.push_front(5);
vector-frente.cpp: In function ‘int main()’:
vector-frente.cpp:5:11: error: ‘class std::vector<int>’ has no member named ‘push_front’
    5 |     notas.push_front(5);
      |           ^~~~~~~~~~

"A classe std::vector<int> não tem membro chamado push_front." De novo, de propósito: no vector, pôr na frente obriga a empurrar todos. Se você precisar mesmo, existe notas.insert(notas.begin(), 5), que funciona, mas deixa o custo à vista. A próxima seção mede esse custo.

5. Quanto custa cada operação

Programadores descrevem o custo de uma operação pelo que acontece quando o container fica grande. Os dois casos que importam aqui:

• Constante: leva sempre mais ou menos o mesmo tempo, com 10 itens ou com 1 milhão. Escreve-se O(1).
• Linear: o tempo cresce junto com o número de itens; com o dobro de itens, o dobro do trabalho. Escreve-se O(n).

Uma medição pequena

A Ana mediu duas situações com std::chrono (o relógio do C++, aula Tempo e Datas). Primeiro, pôr 20 000 números no começo de cada container:

#include <chrono>
#include <deque>
#include <iostream>
#include <list>
#include <vector>

int main() {
    const int N = 20000;
    using relogio = std::chrono::steady_clock;

    auto t0 = relogio::now();
    std::vector<int> v;
    for (int i = 0; i < N; ++i) {
        v.insert(v.begin(), i);
    }
    auto t1 = relogio::now();

    std::deque<int> d;
    for (int i = 0; i < N; ++i) {
        d.push_front(i);
    }
    auto t2 = relogio::now();

    std::list<int> l;
    for (int i = 0; i < N; ++i) {
        l.push_front(i);
    }
    auto t3 = relogio::now();

    using ms = std::chrono::duration<double, std::milli>;
    std::cout << "vector (insert no começo): " << ms(t1 - t0).count() << " ms\n";
    std::cout << "deque  (push_front):       " << ms(t2 - t1).count() << " ms\n";
    std::cout << "list   (push_front):       " << ms(t3 - t2).count() << " ms\n";
}

$ g++ -std=c++23 -Wall -Wextra frente.cpp -o frente
$ ./frente
vector (insert no começo): 36.2485 ms
deque  (push_front):       0.283619 ms
list   (push_front):       2.85643 ms

Pôr na frente: o vector perdeu feio (cada inserção empurra todos os anteriores). O deque ganhou até da list, porque a list pede memória nova para cada vagão. Agora a situação mais comum de todas: percorrer um milhão de itens, somando:

$ ./fim-ler              « 1 milhão de push_back em cada um, depois um for somando
somar 1 milhão no vector: 3.03591 ms
somar 1 milhão no deque:  12.182 ms
somar 1 milhão na list:   18.2945 ms
1499998500000

Para percorrer, o vector foi umas 6 vezes mais rápido que a list, embora a tabela diga "linear" para os três. É o efeito da memória colada: o processador lê blocos vizinhos de uma vez, e os vagões da list estão espalhados pela memória.

6. Qual usar

Na prática, a list é rara: a maioria dos programas que "precisariam" dela fica mais rápida com um vector, mesmo empurrando itens. Use a list quando tiver medido e visto a diferença, ou quando a garantia de "iteradores não se invalidam" for essencial. Existe também a std::forward_list (cabeçalho <forward_list>), um trem que só anda para a frente e gasta menos memória; é ainda mais rara.

Quando dá errado

Referência rápida

Exercícios

Missão final: a fila da lojinha

Atendendo: Dona Lúcia
Atendendo: Bruno
Resta: Carla

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> fila{"Bruno", "Carla"};

    // ponha a Dona Lúcia na frente

    // atenda duas pessoas

    // mostre quem resta
}

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> fila{"Bruno", "Carla"};

    fila.push_front("Dona Lúcia");

    for (int i = 0; i < 2; ++i) {
        std::cout << "Atendendo: " << fila.front() << '\n';
        fila.pop_front();
    }

    std::cout << "Resta: " << fila.front() << '\n';
}

Resumo

• std::list é um trem de vagões: inserir e apagar no meio é barato e não invalida os outros iteradores, mas não há [] e percorrer é lento. Tem .sort() próprio (o std::sort não aceita list).
• std::deque é uma fila de duas pontas: push_front/pop_front e push_back/pop_back baratos, e [] funciona.
• O vector não tem push_front; insert(begin(), x) existe, mas empurra todos.
• Constante = O(1), não depende do tamanho; linear = O(n), cresce com o tamanho. Na prática, a memória colada faz o vector ganhar ao percorrer.
• Comece pelo vector. Troque por deque quando precisar da frente; por list, raramente, e depois de medir.
• Próximo passo: guardar valores por nome, em std::map.