O Array que Cresce Sozinho — std::vector a Fundo

Fechamos a Fase 3 dominando o projeto de tipos. Agora abrimos a Fase 4, e ela talvez seja a que mais muda o seu dia a dia como programador. A Standard Template Library — a STL — é o arsenal de estruturas de dados e algoritmos que vem pronto no C++, testado por milhões de programas e afiado por décadas. Tudo aquilo que em C você implementava à mão — arrays dinâmicos, listas, tabelas hash, ordenação — já existe aqui, correto e eficiente. Começamos pela estrutura que você usará mais que qualquer outra, a ponto de ser sua escolha padrão para "preciso guardar uma sequência de coisas": o std::vector. É o array que cresce sozinho, gerencia a própria memória e aposenta de vez o par malloc/realloc/free que você fazia à mão. Hoje vamos a fundo em como ele funciona.

O que o vector resolve

Em C, um array tem tamanho fixo. Quando você não sabe quantos elementos virão, o ritual é conhecido e perigoso: malloc de um bloco inicial, contar os elementos, e quando encher, realloc para o dobro, copiar, torcer para não errar o tamanho e nunca esquecer o free. O std::vector faz tudo isso por dentro, corretamente:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;         // começa vazio; nenhum tamanho fixado

    v.push_back(10);            // adiciona ao fim — o vector cresce sozinho
    v.push_back(20);
    v.push_back(30);

    std::cout << "tamanho: " << v.size() << '\n';   // 3
    std::cout << "primeiro: " << v[0] << '\n';       // 10 — indexação como em C
    std::cout << "último: " << v.back() << '\n';     // 30

    // Percorrer com range-based for (mais sobre ele adiante nesta fase):
    for (int x : v)
        std::cout << x << ' ';   // 10 20 30
    std::cout << '\n';

    return 0;   // o vector libera sua memória automaticamente — RAII
}

std::vector<int> significa "um vetor de int" — os <> são a primeira aparição dos templates, que só estudaremos a fundo na Fase 5; por ora, leia como "vetor de tal tipo". O push_back acrescenta ao fim, size() responde o tamanho em tempo constante, [i] indexa como um array de C, e no fim do escopo a memória é liberada sozinha. Nenhum malloc, nenhum free, nenhum vazamento possível.

O modelo de crescimento: tamanho versus capacidade

Para usar vector bem, você precisa entender uma distinção que ele mantém: size (quantos elementos existem) e capacity (para quantos há espaço reservado). Quando push_back enche a capacidade, o vector aloca um bloco maior (tipicamente o dobro), copia ou move os elementos para lá, e libera o antigo. Isso é o realloc manual do C, automatizado:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    std::cout << "size / capacity ao crescer:\n";
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        std::cout << "size=" << v.size() << " capacity=" << v.capacity() << '\n';
    }
    return 0;
}

Você verá a capacidade saltar em potências (1, 2, 4, 8, 16...) enquanto o tamanho cresce de um em um. Cada salto é uma realocação — custo que, diluído por muitas inserções, dá um custo médio constante por push_back, mas que envolve copiar/mover todos os elementos. Se você sabe de antemão quantos elementos virão, pode evitar essas realocações reservando espaço com reserve:

#include <vector>
int main() {
    std::vector<int> v;
    v.reserve(1000);   // reserva espaço para 1000 já de cara: zero realocações depois
    for (int i = 0; i < 1000; ++i)
        v.push_back(i);   // nenhuma realocação ocorre — capacity já era suficiente
    return 0;
}

reserve é uma otimização honesta e barata: quando você conhece (ou estima) o tamanho final, ela elimina o custo repetido de realocar. É um dos poucos "truques de desempenho" que valem a pena aprender cedo.

Acesso seguro versus rápido, e a armadilha da referência pendente

Como em std::string (artigo O Fim do char — Textos de Verdade com std::string*), há duas formas de indexar: v[i], que não checa limites (rápido, comportamento indefinido se você errar), e v.at(i), que lança uma exceção se i estiver fora (seguro, com custo da checagem). Use [] no caminho quente onde o índice já está garantido, e .at() quando a validação vale a pena.

Há uma armadilha específica do vector que preciso plantar com destaque, porque pega muita gente: guardar um ponteiro ou referência a um elemento e depois fazer o vector crescer. Se o push_back causar uma realocação, todos os elementos mudam de lugar na memória, e sua referência antiga vira uma referência pendente — o dangling de sempre:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    int& ref = v[0];        // referência ao primeiro elemento
    v.push_back(4);         // PODE realocar! Se realocar, 'ref' fica pendente.
    // std::cout << ref;    // PERIGO: ref pode apontar para memória liberada
    std::cout << v[0] << '\n';   // acesso seguro: sempre use o índice após crescer
    return 0;
}

A regra de bolso: não guarde referências, ponteiros ou iteradores para elementos de um vector que você vai modificar em tamanho. Se precisar, acesse por índice, que continua válido. Essa invalidação é o preço da contiguidade — que, em compensação, dá ao vector sua maior virtude.

Por que o vector é o container padrão

Termino com o argumento de projeto. O std::vector guarda seus elementos em memória contígua, exatamente como um array de C. Isso importa enormemente para o desempenho real: processadores modernos leem memória em blocos (linhas de cache), e dados contíguos são percorridos com altíssima eficiência. Muitas estruturas "mais sofisticadas" (como listas ligadas) espalham os dados pela memória e, na prática, são mais lentas para a maioria dos usos, apesar de terem melhor complexidade teórica para inserção no meio. Por isso a orientação, que pode surpreender quem vem da teoria: comece sempre com std::vector, e só troque por outra estrutura se você medir um problema concreto que ela resolva. É a estrutura de dados padrão do C++ por mérito.

O vector é o container padrão por uma razão concreta: memória contígua aproveita o cache do processador, e isso costuma vencer estruturas teoricamente mais eficientes em tamanhos reais de dados. O par tamanho e capacidade explica quase todo comportamento surpreendente — crescer é caro porque realoca e move tudo, mas o custo amortizado continua baixo. Daí vem também a armadilha que aparece cedo: qualquer realocação invalida ponteiros, referências e iteradores obtidos antes dela, e o código quebra longe do push_back que causou o problema.

Fontes e leituras recomendadas

• cppreference.com/w/cpp/container/vector: a referência completa de std::vector, com todos os métodos, garantias de complexidade e regras de invalidação de iteradores.
• Bjarne Stroustrup, A Tour of C++ (3ª ed.), capítulo sobre containers: a colocação do vector como container padrão pelo criador da linguagem.
• Scott Meyers, Effective STL (2001), Itens 13 e 14 (uso de vector, reserve e capacidade): conselhos práticos clássicos, ainda válidos.
• ISO C++ Core Guidelines, regras SL.con.2 ("Prefer std::vector by default unless you have a reason to use a different container") e SL.con.1: a diretriz oficial de "vector primeiro".
• cppreference.com/w/cpp/container/vector/reserve: os detalhes de reserve e capacity, essenciais para o modelo de crescimento.

Exercícios

Exercício 1

Crie um std::vector<std::string> com alguns nomes lidos do usuário (pare quando ler "fim"), depois imprima todos e o total. Use push_back e size.

#include <iostream>
#include <vector>
#include <string>
int main() {
    std::vector<std::string> nomes;
    std::string entrada;
    std::cout << "Digite nomes (fim para parar):\n";
    while (std::cin >> entrada && entrada != "fim")
        nomes.push_back(entrada);
    std::cout << "Total: " << nomes.size() << '\n';
    for (const auto& n : nomes) std::cout << "- " << n << '\n';
    return 0;
}

Exercício 2

Escreva uma função double media(const std::vector<double>& v) que devolva a média dos elementos (ou 0 se vazio). Explique por que o parâmetro é const std::vector<double>&.

#include <vector>
double media(const std::vector<double>& v) {
    if (v.empty()) return 0.0;         // evita divisão por zero
    double soma = 0.0;
    for (double x : v) soma += x;
    return soma / v.size();
}

Exercício 3

Rode o exemplo de size/capacity desta aula e descreva o padrão de crescimento da capacidade. Depois modifique o programa para chamar reserve(16) antes do laço e explique o que muda na saída.

Exercício 4

O código abaixo tem um bug de invalidação. Explique o que pode dar errado e corrija-o para acessar o valor com segurança.

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {10, 20, 30};
    int& primeiro = v[0];
    for (int i = 0; i < 100; ++i) v.push_back(i);
    std::cout << primeiro << '\n';   // seguro?
    return 0;
}

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {10, 20, 30};
    for (int i = 0; i < 100; ++i) v.push_back(i);
    std::cout << v[0] << '\n';   // índice 0 é sempre válido após o crescimento
    return 0;
}

Exercício 5

Um colega insiste em usar uma lista ligada (std::list) "porque inserir no meio é O(1)" para uma coleção que ele percorre inteira milhares de vezes e raramente modifica no meio. Argumente, com base no que foi visto aqui, por que std::vector provavelmente seria mais rápido na prática, e diga que evidência resolveria a discussão.