std::vector, std::deque, std::list

1. Introdução

Quando você começa a programar, é tentador acreditar em um conto de fadas: “existe um contêiner único que é rápido, conveniente e sempre correto”. Na realidade, a biblioteca padrão do C++ é como um conjunto de facas de cozinha: uma corta pão perfeitamente, outra corta carne, e a terceira é praticamente um saca‑rolhas (e sim, também dá para cortar com ela, mas depois terá que explicar ao investigador). Hoje vamos comparar três contêineres sequenciais e aprender a fazer a pergunta certa: quais operações no meu cenário acontecem com mais frequência.

Falaremos sobre contêineres sequenciais — aqueles em que os elementos têm uma ordem definida (primeiro, segundo, terceiro…), mas internamente são organizados de formas diferentes. Em C++ eles incluem, por exemplo, std::vector, std::deque, std::list (há outros, mas hoje — apenas esses três). No padrão, esses contêineres aparecem como “famílias” separadas com especificações próprias.

Para não nos perdermos, vamos fixar a ideia central do dia: escolher um contêiner é escolher um compromisso. Em alguns lugares você ganha em inserções, em outros — na iteração, em outros — no acesso por índice. E grátis só existe no queijo da ratoeira, e nem mesmo para o rato.

2. std::vector: rápido, enquanto você não insere no início

std::vector normalmente se torna o “contêiner padrão” (e isso é normal). Ele é muito amigo da CPU: os elementos ficam contíguos na memória, então percorrê‑los costuma ser rápido na prática. Mas o vector tem uma fraqueza característica: quando você insere/remove elementos no começo ou no meio, ele precisa “deslocar a cauda”, como se você inserisse uma linha no topo do Excel e toda a tabela descesse.

Intuição sobre o vector

O std::vector<T> tem internamente um grande “bloco de memória” para elementos do tipo T. Dessas características nascem duas propriedades chave.

A primeira — acesso rápido por índice: v[i] normalmente funciona muito rápido, porque o “i‑ésimo elemento” pode ser calculado como “endereço inicial + i * sizeof(T)

A segunda — crescimento. Quando o vector fica cheio, às vezes é preciso alocar um novo (normalmente maior) bloco de memória e mover todos os elementos para lá. Em tópicos anteriores vocês já viram reserve() como forma de reduzir o número desses passos caros.

Uma visualização simples (muito simplificada):

flowchart LR
  A["vector: um bloco contínuo"] --> B["[0][1][2][3][4]..."]

Mini‑exemplo: índice e iteração rápida

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};

    std::cout << v[1] << '\n'; // 20
}

Este exemplo parece simples demais, mas o essencial é que o vector foi concebido como um “array dinâmico” — indexação é natural e conveniente.

Mini‑exemplo: inserção no início

#include <vector>

int main() {
    std::vector<int> v{2, 3, 4};
    v.insert(v.begin(), 1); // elementos "deslocam" para a direita
}

Não vamos nos aprofundar ainda no custo e “o que acontece com iteradores/referências” — isso fica para a próxima aula. Por ora, basta a sensação: insert perto do início em vector — operação potencialmente cara, porque é preciso “mover” elementos.

3. std::deque: operações nas duas extremidades

Se o vector é um corredor com uma porta só (é conveniente adicionar no fim), o deque é um corredor com portas na frente e atrás. O nome literalmente sugere isso: double‑ended queue. Ele é ótimo quando você quer frequentemente adicionar e remover elementos em ambas as extremidades: push_front, push_back, pop_front, pop_back.

Além disso, ao contrário de list, o deque ainda permite acesso por índice d[i]. Mas internamente ele normalmente não é um único bloco contínuo; é composto por vários blocos (simplificamos, mas essa imagem é útil).

Esquema simplificado:

flowchart LR
  A["deque: blocos"] --> B["[ ][ ][ ]"]
  A --> C["[ ][ ][ ]"]
  A --> D["[ ][ ][ ]"]

Por que usar deque se existe vector?

Porque no vector “adicionar rapidamente no início” é doloroso, e o deque foi feito exatamente para isso. Em tarefas reais é comum encontrar cenários tipo “fila de tarefas”, “buffer de mensagens”, “histórico de eventos recentes”, onde é natural operar com ambas extremidades.

Mini‑exemplo: operações em ambas extremidades

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d{2, 3};
    d.push_front(1);
    d.push_back(4);

    std::cout << d.front() << ' ' << d.back() << '\n'; // 1 4
}

Não há mágica aqui — o papel chave do deque é atuar de forma nativa com duas extremidades.

Observação importante

O deque não precisa ser um “vector melhorado”. É um compromisso diferente. Em geral ele abre mão de parte da “continuidade perfeita na memória” em prol da conveniência das operações nas duas extremidades. Vamos discutir o impacto da organização de memória na velocidade na aula final, mas desde já vale lembrar: deque costuma ser “sobre conveniência das extremidades”, e vector — “sobre densidade de dados”.

4. std::list: nós e trabalho por posições

std::list é uma lista duplamente encadeada. Imagine um colar de contas: cada elemento é uma conta (nó), e cada conta tem um link para a anterior e para a próxima. Ao contrário de vector e deque, os elementos da lista não precisam ficar contíguos na memória. Isso é chamado de contêiner baseado em nós (node‑based): cada nó normalmente é alocado separadamente.

Esquema ilustrativo:

flowchart LR
  A["[10]"] <--> B["[20]"] <--> C["[30]"]

Em que o list difere do vector e do deque

A principal diferença “psicológica” é: list não é sobre índices, é sobre posições.

O std::list não tem operator[]. E não porque os autores da STL “esqueceram de adicionar”, mas porque a ideia de “pegar o i‑ésimo elemento rapidamente” não combina bem com lista: para alcançar o i‑ésimo você precisa percorrer i links.

Por outro lado, o list tem um ponto forte: inserção/remoção em uma posição conhecida (quando você já tem um iterador) normalmente não requer deslocar todos os outros elementos. Reforçando: hoje mantemos isso em nível intuitivo — “não movemos a cauda” é a ideia.

Mini‑exemplo: inserção via iterador

#include <list>
#include <iostream>

int main() {
    std::list<int> lst{10, 30};

    auto it = lst.begin();
    ++it;                 // posição em 30
    lst.insert(it, 20);   // inserimos 20 antes de 30

    for (int x : lst) {
        std::cout << x << ' ';
    }
    std::cout << '\n';    // 10 20 30
}

O iterador aqui é um “marcador de posição”. A lista é especialmente boa quando você frequentemente opera “dentro” da sequência, e para você é mais importante inserir/remover rapidamente por posição do que indexar rapidamente.

Armadilha de pensar em inserção O(1)

Um iniciante frequentemente ouve: “na list a inserção é O(1)” e conclui: “logo, list é sempre melhor para inserções”. Mas isso é meia‑verdade. A inserção pode ser rápida se você já conhece o local (tem um iterador). Já “encontrar o local” é outra parte do custo, que muitas vezes exige um percurso linear.

Hoje vamos apenas lembrar a fórmula:

“encontrar a posição” + “inserir na posição” = duas tarefas distintas.

O list acelera a segunda parte, mas não necessariamente a primeira.

5. Como escolher um contêiner: comparação e mini‑cenários

Tabela comparativa

Quando você for escolher um contêiner da próxima vez, é útil ter um pequeno “mapa da área” à vista. Vamos torná‑lo o mais prático possível: não uma tabela do padrão, mas um cheat sheet para o desenvolvedor que uma vez tentou fazer uma fila com vector e depois ficou olhando para o teto por um bom tempo.

std::vector

std::deque

std::list

push_back / pop_back

push_front / pop_front

Essa tabela não é “matemática eterna”, é uma aproximação prática. Mas ajuda muito a não escolher um contêiner “no feeling”. E sim, a biblioteca padrão claramente distingue deque, list, vector como contêineres separados com especificações e famílias de operações próprias.

Mini‑cenários do TaskKeeper

Até este ponto do curso, desenvolvemos de forma condicional uma aplicação de console chamada TaskKeeper: armazenamos tarefas, imprimimos listas, filtramos, ordenamos, buscamos por condições. Na prática, para a maioria dessas tarefas std::vector<Task> é uma excelente escolha, e você não precisa complicar sua vida só porque “existem outros contêineres em C++”.

Mas há situações em que outro contêiner faz mais sentido. Vejamos três mini‑cenários. Nosso objetivo aqui não é reescrever a aplicação, mas aprender a reconhecer as situações.

Para os exemplos, introduzimos um modelo simples de tarefa:

#include <string>

struct Task {
    int id{};
    std::string title;
};

Cenário A: “lista de tarefas” — na maioria das vezes vector

Se você tipicamente faz “mostrar todas as tarefas”, “ordenar”, “percorrer em loop e imprimir”, “buscar por condição”, então vector costuma ser a opção mais simples e rápida. Nesse caso você valoriza compactação e conveniência para algoritmos.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> ids{101, 102, 103};
    for (int id : ids) {
        std::cout << id << ' ';
    }
    std::cout << '\n'; // 101 102 103
}

Ponto chave: iteração linear em vector é o “cenário nativo”. Na maioria das vezes é isso que você fará.

Cenário B: “fila de eventos” — pede deque

Imagine que adicionamos ao TaskKeeper o processamento de eventos da interface: o usuário digita comandos, e queremos manter uma “fila de comandos a executar” onde às vezes acrescentamos um comando urgente “na frente da fila”. Isso se parece com trabalhar com ambas extremidades.

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

int main() {
    std::deque<std::string> q;
    q.push_back("load");
    q.push_front("help"); // mostrar help com urgência

    std::cout << q.front() << '\n'; // help
}

A ideia é simples: o deque é conveniente quando “a frente também importa”, e não apenas a cauda.

Cenário C: “tarefas ativas e realocações” — list pode ajudar

Suponha que temos uma fila de “tarefas ativas” e frequentemente movemos uma tarefa do meio para outro lugar (por exemplo, para o fim, porque a tarefa ficou bloqueada). Se já tivermos um iterador para a tarefa desejada, a lista pode ser conveniente por trabalhar diretamente por posições.

#include <list>
#include <iostream>

int main() {
    std::list<int> active{1, 2, 3};

    auto it = active.begin();
    ++it;                 // aponta para 2
    active.erase(it);     // removemos 2

    std::cout << active.front() << '\n'; // 1
}

Note que ainda não discutimos “o que acontece com iteradores” e “quais garantias cada contêiner dá”. Isso fica para a próxima aula. Aqui o importante é o modelo: a lista é um contêiner onde é natural pensar em iteradores‑posições, não em índices.

6. Erros típicos

Erro nº1: escolher std::list porque “a inserção é O(1)
É uma armadilha comum: soa científico, parece convincente, mas depois descobre‑se que você ainda precisa procurar linearmente o local certo, só que agora a iteração ficou menos amigável para a memória. É mais correto dividir a tarefa em duas partes: primeiro entender como você encontra a posição, e só então pensar em como inserir.

Erro nº2: tentar acessar std::list por índice como se fosse um array.
Às vezes a mão escreve lst[i] porque “quero o terceiro elemento”. O list não tem operator[], e isso é um aviso honesto da STL: o contêiner não foi feito para “terceiro elemento em O(1)vector ou deque faz mais sentido.

Erro nº3: achar que std::deque é “o mesmo que vector, só melhor”.
O deque realmente suporta indexação e adição no fim, mas seu papel principal é operações eficientes nas duas extremidades. Se seu cenário é “muita leitura sequencial, raras modificações”, o vector costuma ser mais simples e previsível. Use deque quando você precisa de push_front/pop_front.

Erro nº4: tentar otimizar o contêiner “por precaução”, sem perfil de operações.
É tentador escolher o “contêiner mais certo” desde o início, mas a escolha depende do que você faz com mais frequência: iteração, inserções, acesso por índice, trabalho com extremidades. Então a ordem saudável é: listar operações típicas, escolher o contêiner para essas operações, e só então pensar nos detalhes.

Erro nº5: misturar modelos mentais: armazenar como em um vector, mas trabalhar como se fosse uma lista.
Por exemplo, fazer muitas inserções no início de um vector em um loop e se surpreender com a lentidão. Contêineres “educam”: se você trabalhar contra sua natureza, eles começam a punir — silenciosamente, sem avisos, apenas ficando mais lentos.

1

Tarefa

C++ SELF, nível 59, lição 1

Bloqueado

Índices do armazém

Índices do armazém

Abrir

1

Tarefa

C++ SELF, nível 59, lição 1

Bloqueado

Painel do deque

Painel do deque

Abrir

1

Tarefa

C++ SELF, nível 59, lição 1

Bloqueado

Últimas mensagens do chat

Últimas mensagens do chat

Abrir

1

Tarefa

C++ SELF, nível 59, lição 1

Bloqueado

Cursor de linhas

Cursor de linhas

Abrir