Módulo 02
Estruturas Sequenciais
Vetores e Memória Contígua
O vetor é uma das estruturas mais importantes da computação. Seus elementos são armazenados em posições consecutivas da memória, o que permite calcular diretamente o endereço de qualquer posição a partir de um índice. Essa simplicidade torna o acesso extremamente eficiente, mas também cria custos importantes em operações como inserção e remoção no meio da estrutura.
A estrutura sequencial clássica
O Que é um Vetor?
Um vetor é uma coleção ordenada de elementos, normalmente do mesmo tipo, armazenados em uma sequência contígua de memória. Cada elemento possui uma posição lógica chamada índice. Em C e C++, os índices normalmente começam em 0.
Contiguidade
Os elementos ficam lado a lado na memória, formando um único bloco.
Índices
Cada posição é identificada logicamente por 0, 1, 2, 3...
Acesso Direto
O endereço de uma posição pode ser calculado sem percorrer as anteriores.
Mesmo Tipo
Como cada elemento ocupa o mesmo tamanho, o cálculo do endereço é simples.
Modelo mental: pense no vetor como uma fileira numerada de gavetas do mesmo tamanho.
Saber o número da gaveta permite calcular diretamente onde ela está.
Vetor é uma estrutura sequencial
Seus elementos possuem uma ordem lógica definida. O elemento de índice 3 vem depois do índice 2 e antes do índice 4. Essa ordem lógica coincide com a disposição física contígua da memória.
Por que os índices começam em zero?
O índice pode ser interpretado como deslocamento a partir do primeiro elemento. O índice 0 representa deslocamento zero; o índice 1, um elemento; o índice 2, dois elementos, e assim por diante.
Vetor e Array são a mesma coisa?
No sentido conceitual, vetor costuma significar array unidimensional. Em C++, porém, std::vector é um contêiner dinâmico que preserva contiguidade, enquanto um array tradicional tem tamanho fixo.
Por que acessar vetor é tão rápido?
Índice, Endereço e Acesso Direto
Como todos os elementos possuem o mesmo tamanho e ficam lado a lado, o endereço de qualquer posição pode ser calculado por uma fórmula simples. Não é necessário visitar os elementos anteriores.
Para um vetor cujo primeiro elemento começa no endereço
base,
o endereço do elemento de índice i é:
endereço = base + i × tamanho_do_elemento.
Clique em uma posição do vetor ou utilize os botões para calcular seu endereço.
Você também pode clicar diretamente em qualquer célula do vetor.
Acesso é barato; deslocar elementos não
Operações em um Vetor
A organização contígua explica tanto a principal vantagem quanto uma das principais limitações do vetor. Ler uma posição é extremamente eficiente, mas inserir ou remover elementos no início ou no meio pode exigir deslocar vários elementos.
Observe principalmente o contador de elementos deslocados. Acesso por índice não desloca nada; inserções e remoções no meio precisam preservar a ordem.
Azul: acesso diretoAmarelo: deslocamento/verificaçãoVerde: resultado
Escolha uma operação para visualizar seu custo.
Acesso por índice
Acessar v[i] é O(1). O endereço é calculado diretamente; não importa se estamos acessando o primeiro ou o milionésimo elemento.
Inserção no meio
Para inserir em uma posição ocupada, os elementos seguintes precisam ser deslocados para abrir espaço. No pior caso, inserir no início desloca n elementos: O(n).
Remoção no meio
Após remover um elemento, normalmente deslocamos os posteriores para preencher o espaço vazio. Também é O(n) no pior caso.
Busca
Em um vetor não ordenado, buscar por valor pode exigir percorrer todas as posições: O(n). Se estiver ordenado, busca binária pode chegar a O(log n).
O vetor dinâmico do C++
Como o std::vector Cresce?
std::vector mantém os elementos contíguos, mas consegue crescer durante a execução.
Para isso ele separa size, quantidade utilizada, de capacity,
quantidade que cabe no bloco atualmente reservado.
Quando
size == capacity e um novo elemento é inserido, o vetor solicita um
novo bloco contíguo maior, move ou copia os elementos e libera a região anterior.
O fator exato de crescimento depende da implementação.
Bloco atualcapacity = 4
O vetor possui size = 3 e capacity = 4. Ainda existe uma posição reservada disponível.
Resumo de desempenho
Complexidade das Principais Operações
| Operação | Complexidade | Por quê? |
|---|---|---|
Acessar v[i] | O(1) | O endereço é calculado diretamente. |
Alterar v[i] | O(1) | Mesmo princípio do acesso por índice. |
| Buscar valor não ordenado | O(n) | Pode ser necessário percorrer todos os elementos. |
| Inserir no início/meio | O(n) | É necessário deslocar elementos para abrir espaço. |
| Remover do início/meio | O(n) | Elementos posteriores precisam preencher o espaço. |
push_back() em std::vector | O(1) amortizado | A maioria usa capacidade já reservada; realocações ocasionais custam O(n). |
pop_back() | O(1) | Remove o último elemento sem deslocar os anteriores. |
Por que O(1) amortizado? Uma realocação isolada pode custar O(n),
mas ela não acontece em todo
push_back(). O custo é distribuído ao longo
de várias inserções.
Aplicação prática
Vetores em C++17
Em C++ existem arrays de tamanho fixo e o contêiner std::vector.
Quando precisamos de uma sequência contígua cujo tamanho pode variar,
std::vector é uma das opções mais importantes da biblioteca padrão.
std::vector — criação, acesso e inserção
#include <iostream>
#include <vector>
int main() {
std::vector<int> numeros = {10, 20, 30};
numeros.push_back(40);
std::cout << numeros[0] << '\n';
std::cout << numeros[2] << '\n';
return 0;
}Percorrendo um vetor
std::vector<int> v = {10, 20, 30, 40, 50};
for (std::size_t i = 0; i < v.size(); ++i) {
std::cout << "v[" << i << "] = "
<< v[i] << '\n';
}size e capacity
std::vector<int> v;
for (int i = 1; i <= 10; ++i) {
v.push_back(i);
std::cout
<< "size = " << v.size()
<< " | capacity = " << v.capacity()
<< '\n';
}size() e capacity()
size() informa quantos elementos existem logicamente. capacity() informa quantos cabem no bloco reservado antes de uma nova realocação.
[] vs at()
at() verifica limites e lança exceção para índice inválido. [] não oferece essa verificação.
reserve()
Quando temos uma estimativa da quantidade de elementos, reserve() permite solicitar capacidade antecipadamente e reduzir realocações.
Modelo mental
O Que Você Precisa Guardar
Resumo: o vetor troca flexibilidade de inserção no meio por excelente acesso aleatório,
boa localidade de memória e uma representação simples. Por isso é uma das estruturas mais utilizadas.