Introdução

Nesta série sobre contêineres da STL do C++, vamos explorar em detalhes o contêiner vector, um dos mais versáteis e amplamente utilizados na programação moderna. Este artigo abordará os conceitos fundamentais, operações comuns e técnicas avançadas para trabalhar eficientemente com vetores em C++.

I. Definição Básica e Declaração

1. Definição Central

O std::vector é um contêiner sequencial que implementa uma matriz dinâmica com armazenamento contíguo na memória. Como classe modelo (template), ele pode armazenar qualquer tipo de dado, desde tipos primitivos como int e double até objetos complexos ou outros vetores. Sua combinação de acesso rápido aos elementos e gerenciamento automático de memória o torna uma das estruturas mais utilizadas no desenvolvimento cotidiano.

2. Principais Características

• Armazenamento Contínuo: Permite acesso aleatório eficiente aos elementos através de índices, assim como arrays nativos.
• Redimensionamento Dinâmico: Automaticamente aloca mais espaço quando necessário, geralmente seguindo uma política de crescimento exponencial.
• Operações Eficientes no Final: Inserção e remoção no final do vetor são operações de tempo constante (O(1)), enquanto operações no meio ou início têm complexidade linear (O(n)).
• Compatibilidade com Algoritmos STL: Integra-se perfeitamente com os algoritmos da biblioteca padrão do C++.

3. Propósito de Design

O vector foi projetado para superar as limitações dos arrays nativos do C:

• Tamanho Estático: Arrays nativos requerem tamanho fixo em tempo de compilação, enquanto o vector ajusta seu tamanho dinamicamente conforme necessário.
• Gerenciamento de Memória: Elimina a necessidade de alocação manual de memória (malloc/new) e liberação (free/delete), reduzindo riscos de vazamento de memória.
• Funcionalidade Enriquecida: Fornece métodos prontos para inserção, remoção, busca e outras operações comuns, eliminando a necessidade de implementações manuais propensas a erros.

4. Exemplo de Código

#include <iostream>
#include <vector>

int main() {
    // Criar um vetor de inteiros com tamanho dinâmico
    std::vector<int> dados;
    
    // Inserir elementos no final (automático redimensionamento)
    dados.push_back(10);
    dados.push_back(20);
    dados.push_back(30);
    
    // Acessar elementos como em um array
    for (size_t i = 0; i < dados.size(); ++i) {
        std::cout << dados[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

II. Construtores

1. Definição Central

Os construtores do vector fornecem diferentes maneiras de inicializar um objeto vector, permitindo escolher o método mais adequado para cada cenário de uso, semelhante a diferentes opções de configuração ao adquirir um armazenamento.

2. Principais Tipos de Construtores

• Construtor Padrão: Cria um vetor vazio, ideal quando o tamanho exato dos dados é desconhecido no momento da criação.
• Construtor de Preenchimento: Inicializa o vetor com um número especificado de elementos, todos com o mesmo valor, útil quando a quantidade e valor inicial são conhecidos.
• Construtor de Cópia: Cria uma nova cópia profunda de um vetor existente, garantindo que modificações no novo vetor não afetem o original.
• Construtor por Intervalo de Iteradores: Permite criar um vetor a partir de elementos de outro contêiner ou array, oferecindo máxima flexibilidade na inicialização.

3. Propósito de Design

A variedade de construtores visa simplificar o processo de inicialização, permitindo que os desenvolvedores criem vetores com o estado desejado em uma única operação, reduzindo código repetitivo e minimizando erros durante atribuições manuais.

4. Exemplo de Código

#include <iostream>
#include <vector>

int main() {
    // 1. Construtor padrão (mais comum)
    std::vector<int> vazio;
    std::cout << "Tamanho do vetor vazio: " << vazio.size() << std::endl;

    // 2. Construtor de preenchimento: 7 elementos com valor 5
    std::vector<double> preenchido(7, 5.0);
    std::cout << "Elementos do vetor preenchido: ";
    for (auto valor : preenchido) {
        std::cout << valor << " ";
    }
    std::cout << std::endl;

    // 3. Construtor de cópia
    std::vector<int> copia(preenchido.begin(), preenchido.begin() + 3);
    std::cout << "Tamanho da cópia: " << copia.size() << std::endl;

    // 4. Construtor por intervalo de iteradores
    int arr[] = {10, 20, 30, 40, 50};
    std::vector<int> do_array(arr, arr + sizeof(arr)/sizeof(arr[0]));
    std::cout << "Vetor do array: ";
    for (auto elemento : do_array) {
        std::cout << elemento << " ";
    }

    return 0;
}

III. Capacidade e Espaço

1. Definição Central

Dois conceitos fundamentais compreendem o gerenciamento de espaço em vetores:

• size: Número de elementos atualmente armazenados no vetor (ocupados).
• capacity: Espaço total alocado para o vetor (ocupados + disponíveis).
• reserve(n): Aloca espaço para pelo menos n elementos, sem alterar o tamanho atual.
• resize(n, val): Altera o número de elementos para n, preenchendo novos elementos com val se necessário.

2. Principais Regras

Mecanismo de Redimensionamento

• Gatilho: O redimensionamento automático ocorre quando a inserção de um novo elemento faria size() igual a capacity().
• Fator de Crescimento: O padrão C++ não especifica um fator exato, implementações comuns usam 1.5x (versão PJ) ou 2x (versão SGI).
• Processo: Aloca novo bloco de memória maior → copia elementos existentes → libera memória antiga.
• Otimização: Usar reserve() com tamanho estimado evita múltiplos redimensionamentos, melhorando o desempenho.

Diferenças entre reserve() e resize()

Método	Altera size?	Altera capacity?	Inicializa novos elementos?	Caso de Uso Principal
reserve(n)	Não	Aumenta se necessário	Não	Reservar espaço para melhor desempenho
resize(n, val)	Sim	Aumenta se necessário	Sim (com val)	Modificar número de elementos

3. Propósito de Design

A separação entre size e capacity visa otimizar o desempenho evitando realocações frequentes. Ao reservar espaço extra, o vetor reduz a necessidade de realocar memória e copiar elementos sempre que novos elementos são adicionados.

4. Exemplo de Código

// Exemplo 1: Demonstração do mecanismo de redimensionamento
#include <iostream>
#include <vector>

int main() {
    std::vector<int> colecao;
    size_t capacidade_antiga = colecao.capacity();
    std::cout << "Processo de redimensionamento do vetor:" << std::endl;

    // Descomente a linha abaixo para reservar espaço inicialmente
    // colecao.reserve(100);

    for (int i = 0; i < 100; ++i) {
        colecao.push_back(i);
        if (capacidade_antiga != colecao.capacity()) {
            capacidade_antiga = colecao.capacity();
            std::cout << "Nova capacidade: " << capacidade_antiga << std::endl;
        }
    }
    return 0;
}

// Exemplo 2: Comparação entre reserve e resize
#include <iostream>
#include <vector>

int main() {
    std::vector<int> reserva, redimensiona;
    reserva.reserve(10);
    redimensiona.resize(10, 7);

    std::cout << "Vetor com reserve: size=" << reserva.size() 
              << ", capacity=" << reserva.capacity() << std::endl;
    std::cout << "Vetor com resize: size=" << redimensiona.size() 
              << ", capacity=" << redimensiona.capacity() << std::endl;
    std::cout << "Elementos do vetor redimensionado: ";
    for (auto valor : redimensiona) {
        std::cout << valor << " ";
    }
    return 0;
}

IV. Inserção, Remoção, Busca e Modificação

1. Definição Central

As operações de modificação fornecem métodos para manipular elementos do vetor de forma segura e eficiente, abstraindo a complexidade do gerenciamento de memória e movimentamento de elementos.

2. Principais Operações

Operação	Funcionalidade Principal	Complexidade	Ponto de Atenção
push_back(valor)	Insere elemento no final	O(1) (exceto redimensionamento)	Mais eficiente para innserções
pop_back()	Remove último elemento	O(1)	Verificar se o vetor não está vazio
insert(pos, valor)	Insere antes da posição pos	O(n)	Pode invalidar iteradores
erase(pos)	Remove elemento na posição pos	O(n)	Invalida iteradores; use o valor retornado
operator[]	Acesso por índice	O(1)	Verificar limites do índice
swap(v2)	Troca conteúdos com outro vetor	O(1)	Troca apenas ponteiros internos
clear()	Remove todos os elementos	O(n)	Não libera memória alocada
empty()	Verifica se o vetor está vazio	O(1)	Mais idiomático que size() == 0

Nota: find não é membro do vector, mas um algoritmo da STL. Requer inclusão de <algorithm>.

3. Propósito de Design

O encapsulamento de operações comuns em métodos bem definidos permite que os desenvolvedores trabalhem em um nível de abstração mais alto, focando na lógica de aplicação em vez de detalhes de implementação de baixo nível.

4. Exemplo de Código

#include <iostream>
#include <vector>
#include <algorithm> // Necessário para find

int main() {
    std::vector<int> numeros;
    
    // 1. Inserção no final
    numeros.push_back(5);
    numeros.push_back(10);
    numeros.push_back(15);
    numeros.push_back(20);
    std::cout << "Após inserções: ";
    for (auto num : numeros) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 2. Remoção do final
    numeros.pop_back();
    std::cout << "Após remoção: ";
    for (auto num : numeros) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 3. Busca e inserção em posição específica
    auto posicao = std::find(numeros.begin(), numeros.end(), 10);
    if (posicao != numeros.end()) {
        numeros.insert(posicao, 100); // Insere 100 antes de 10
    }
    std::cout << "Após inserção em posição específica: ";
    for (auto num : numeros) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 4. Remoção de elemento específico
    posicao = std::find(numeros.begin(), numeros.end(), 100);
    if (posicao != numeros.end()) {
        numeros.erase(posicao); // Remove 100
    }
    std::cout << "Após remoção específica: ";
    for (auto num : numeros) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 5. Limpeza
    numeros.clear();
    std::cout << "Após limpeza: size=" << numeros.size() 
              << ", capacity=" << numeros.capacity() << std::endl;

    return 0;
}

V. Iteração e Iteradores

1. Definição Central

A iteração é o processo de acessar cada elemento do vetor sequencialmente. O vector oferece três métodos principais de iteração, cada um com vantagens específicas para diferentes cenários.

2. Métodos de Iteração

• Iteração por Índice: Similar à iteração em arrays nativos, acessando elementos por posição.

1. Vantagens: Simples e intuitivo, suporta acesso aleatório e modificação direta, fácil depuração.
2. Desvantagens: Limitada a contêineres com armazenamento contínuo, risco de acesso fora dos limites.
3. Cenário: Quando se conhece o contêiner e é necessário acesso por índice.

• Iteração por Faixa (C++11+): Notação compacta para percorrer todos elementos.

1. Vantagens: Código mais conciso, sem necessidade de gerenciar índices, proteção contra acesso fora dos limites.
2. Desvantagens: Não fornece índice do elemento atual, apenas acesso sequencial.
3. Cenário: Quando é necessário percorrer todos elementos sem necessidade de índice.
4. Detalhe: Para modificar elementos, usar auto& (referência) em vez de auto.

• Iteradores: Método genérico compatível com todos contêineres STL.

1. Vantagens: Máxima portabilidade entre contêineres, compatibilidade com algoritmos STL.
2. Desvantagens: Sintaxe mais complexa para iniciantes.
3. Cenário: Uso com algoritmos STL, iteração com inserção/remoção, código genérico.

3. Propósito de Design

A oferta de múltiplos métodos de iteração visa equilibrar simplicidade para iniciantes (acesso por índice) com poder e generalidade (iteradores), mantendo a compatibilidade com os algoritmos da STL que operam independentemente da estrutura do contêiner.

4. Exemplo de Código

#include <iostream>
#include <vector>

int main() {
    std::vector<int> valores = {1, 2, 3, 4, 5};

    // 1. Iteração por índice (modificando elementos)
    std::cout << "Iteração por índice: ";
    for (size_t i = 0; i < valores.size(); ++i) {
        valores[i] *= 2; // Multiplica cada elemento por 2
        std::cout << valores[i] << " ";
    }
    std::cout << std::endl;

    // 2. Iteração por faixa (apenas leitura)
    std::cout << "Iteração por faixa: ";
    for (auto valor : valores) {
        std::cout << valor << " ";
    }
    std::cout << std::endl;

    // 3. Iteração por iteradores
    std::cout << "Iteração por iteradores: ";
    std::vector<int>::iterator it = valores.begin();
    while (it != valores.end()) {
        std::cout << *it << " ";
        ++it;
    }
    std::cout << std::endl;

    return 0;
}

5. Invalidação de Iteradores

Os iteradores do vector são essencialmente ponteiros para elementos na memória. Quando a estrutura interna do vector muda (redimensionamento, remoção de elementos), esses ponteiros podem se tornar inválidos.

Principais Causas de Invalidez

• Invalidação por Redimensionamento

1. Cenários: Qualquer operação que altere a capacidade do vector (resize, reserve, insert, push_back, assign).
2. Causa: O redimensionamento aloca novo bloco de memória, copia elementos e libera o bloco antigo.
3. Solução: Após operações de redimensionamento, iteradores devem ser reatribuídos usando begin()/end().

• Invalidação por Remoção

1. Cenários: Operação erase em uma posição específica.
2. Causa: Após remoção, elementos subsequentes são movidos para posições anteriores, invalidando iteradores para posições afetadas.
3. Solução: erase retorna um iterador válido para o elemento seguinte ao removido; este valor deve ser usado para atualização.

Regras Gerais de Evitação de Problemas

1. Após qualquer operação que modifique a estrutura do vector (inserção, remoção, redimensionamento), evite usar iteradores antigos.
2. Não confie em comportamentos não especificados; mesmo que o código compile e execute, resultados podem ser incorretos.
3. O problema de invalidação de iteradores não é exclusivo do vector; contêineres como string também são afetados por operações similraes.

Exemplo de Problemas Comuns

// Problema 1: Invalidez por redimensionamento
#include <iostream>
#include <vector>

int main() {
    std::vector<int> dados = {1, 2, 3, 4, 5};
    auto iterador = dados.begin(); // Iterador para o espaço antigo

    dados.reserve(100); // Redimensionamento ocorre, iterador se torna inválido

    // Uso do iterador inválido causa comportamento indefinido
    while(iterador != dados.end()) {
        std::cout << *iterador << " ";
        ++iterador;
    }
    return 0;
}

// Problema 2: Invalidez por remoção
#include <iostream>
#include <vector>

int main() {
    std::vector<int> valores = {1, 2, 3, 4, 5, 6};
    auto it = valores.begin();
    
    while (it != valores.end()) {
        if (*it % 2 == 0) {
            valores.erase(it); // Iterador se torna inválido após remoção
        }
        ++it; // Comportamento indefinido
    }
    
    // Correção: usar o valor retornado por erase
    /*
    while (it != valores.end()) {
        if (*it % 2 == 0) {
            it = valores.erase(it); // Atualiza o iterador
        } else {
            ++it; // Apenas avança se não houve remoção
        }
    }
    */
    
    for (auto valor : valores) {
        std::cout << valor << " ";
    }
    return 0;
}

VI. Técnicas Avançadas e Vetores Bidimensionais

1. Definição Central

Esta seção aborda tópicos avançados de uso do vector, incluindo armadilhas comuns, técnicas de gerenciamento de memória e implementação de estruturas bidimensionais dinâmicas usando vetores aninhados.

2. Principais Conceitos

Armadilha de Cópia Rasa (Shallow Copy)

• memcpy realiza cópia binária rasa de memória, copiando apenas ponteiros, não os recursos apontados.
• Para tipos primitivos (int, char, etc.), memcpy funciona corretamente.
• Para tipos gerenciados de recursos (string, classes customizadas), cópia rasa resulta em múltiplos objetos apontando para o mesmo recurso, causando liberação dupla e falha do programa.

Conclusão: Para tipos customizados, sempre use cópia por atribuição ou construtor de cópia, nunca memcpy.

Técnicas de Liberação de Memória

• clear() remove elementos mas não libera memória alocada (capacity permanece inalterado).

Métodos para liberação completa de memória:

1. Troca com vetor temporário: std::vector<int>().swap(v); troca conteúdo com vetor vazio, liberando memória ao destruir o objeto temporário.

2. shrink_to_fit() (C++11): Reduz capacity para igual size, liberando memória excedente.

Vetores Bidimensionais

• Vetores bidimensionais são essencialmente vetores de vetores (std::vector<std::vector<T>>).
• Cada linha é um vetor independente, podendo ter tamanhos diferentes, formando verdadeiras matrizes dinâmicas.
• Acesso aos elementos é feito com notação de matriz: matriz[i][j].

3. Propósito de Design

A estrutura de vetor aninhado permite implementar matrizes verdadeiramente dinâmicas, superando a limitação de matrizes nativas que exigem número de colunas fixo em tempo de compilação. Essa flexibilidade é particularmente útil para estruturas irregulares como triângulos de Pascal.

4. Exemplo de Código

// Exemplo 1: Implementação de triângulo de Pascal com vetor bidimensional
#include <iostream>
#include <vector>

std::vector<std::vector<int>> gerarTriangulo(int linhas) {
    // Criar vetor bidimensional com 'linhas' linhas
    std::vector<std::vector<int>> triangulo(linhas);
    
    for (int i = 0; i < linhas; ++i) {
        // Linha i tem i+1 elementos, todos inicializados como 1
        triangulo[i].resize(i + 1, 1);
    }
    
    // Preencher elementos internos
    for (int i = 2; i < linhas; ++i) {
        for (int j = 1; j < i; ++j) {
            triangulo[i][j] = triangulo[i-1][j] + triangulo[i-1][j-1];
        }
    }
    
    return triangulo;
}

int main() {
    auto triangulo = gerarTriangulo(5);
    
    for (const auto& linha : triangulo) {
        for (auto valor : linha) {
            std::cout << valor << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

// Exemplo 2: Técnicas de liberação de memória
#include <iostream>
#include <vector>

int main() {
    std::vector<int> dados;
    dados.reserve(100); // Reserva espaço para 100 elementos
    dados.push_back(1);
    dados.push_back(2);
    
    std::cout << "Estado inicial: size=" << dados.size() 
              << ", capacity=" << dados.capacity() << std::endl;
    
    dados.clear();
    std::cout << "Após clear(): size=" << dados.size() 
              << ", capacity=" << dados.capacity() << std::endl;
    
    dados.shrink_to_fit();
    std::cout << "Após shrink_to_fit(): size=" << dados.size() 
              << ", capacity=" << dados.capacity() << std::endl;
    
    return 0;
}