Vetores
Editado por: Vinicius Okada, Bruno Rafael Comin Scheffel
Vetores e Arrays
Conteúdo
Array
As variáveis declaradas até agora são capazes de armazenar um único valor por vez. Sempre que atribuímos um novo valor a uma variável, o valor anterior é perdido. Isso ocorre porque cada variável está associada a uma única posição de memória, e dentro dela é possível armazenar apenas um valor do tipo especificado.
Um Array é a forma mais simples e comum de dados estruturados da linguagem C++, é um agrupamento de dados do mesmo tipo, adjacentes na memória. Trata-se simplesmente de um conjunto de variáveis de um mesmo tipo, com a vantagem de estarem todas associadas ao mesmo nome e igualmente acessíveis por um índice.
Declarando e Acessando uma Array
Em linguagem C++, a declaração de um array segue a forma tipo_dado nome_array[tamanho]; . Além disso, o acesso é feito por meio de um índice, na forma nome_array[índice] .
Vetores
Os vetores no C++ são similares aos Arrays, porém dinâmicos. Ou seja, em vez de terem um tamanho fixo, eles se expandem sozinhos para acompanhar a inserção de dados.
Para usarmos os vetores do C++ precisamos importar a biblioteca <vector>
#include <vector>
Para criarmos um vetor seguimos o padrão vector<tipo_dado> nome_vetor;
Exemplo
vector<int> v;
vector<string> v;
Pré-alocação com reserve()
Embora o crescimento dinâmico seja uma facilidade, ele tem um custo de processamento. Se soubermos previamente o número aproximado de elementos que o vetor vai possuir, podemos usar o .reserve(). para pré-alocar memória.
Isso evita múltiplas realocações internas conforme o vetor cresce, melhorando a performance.
Internamente, quando a capacidade do vetor acaba, o C++ normalmente:
- Aloca um bloco maior de memória
- Copia os elementos antigos
- Libera a memória anterior
Por isso, múltiplos push_back() podem gerar custo adicional caso não utilizemos .reserve().
Inserção/Remoção de elementos
Os métodos mais comuns para inserção e remoção em vetores são:
01. Inserção no fim
Para inserir diretamente no fim de um vetor podemos usar o .push_back(x)
int n;
cin >> n;
vector<int> v;
v.reserve(n); // Aloca espaço para N elementos de uma vez só
for(int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back(x);
}
02. Remoção no fim
Para remover o último elemento de um vetor usamos o .pop_back()
vector<int> v = {1, 2, 3, 4, 5};
v.pop_back();
// v = {1, 2, 3, 4}
03. Inserção no meio/início
Para inserir no meio ou no início de um vetor utilizamos o .insert(pos, elemento)
Para inserir no início podemos usar o .begin()
vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.begin(), 100); // .begin() aponta para '1', o insert() vai 'empurrar' os elementos para direita e encaixar o '100'
// v = {100, 1, 2, 3, 4, 5}
Como os vetores possuem memória contígua, podemos avançar posições no iterador usando +.
vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.begin() + 3, 100); // Insere '100' no índice 3
// v = {1, 2, 3, 100, 4, 5}
Em contrapartida do .begin(), existe o .end()
vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.end(), 100); // Insere o número 100 no final do vetor
// v = {1, 2, 3, 4, 5, 100}
04. Remoção no meio/início
Para remover no meio ou no início de um vetor usamos o .erase(pos)
vector<string> v = {"maca", "banana", "cereja", "damasco", "figo"};
v.erase(v.begin() + 1); // Remove o elemento na posição 1 (banana)
// v = {maca, cereja, damasco, figo}
Acesso por Índice
Para acessar qualquer elemento de um vetor, utilizamos v[i] ou v.at(i)
Exemplos:
Imprimindo o terceiro elemento do vetor
vector<int> v = {1, 2, 3, 4, 5};
cout << v[2] << endl;
Imprimindo o elemento central do vetor
vector<int> v = {1, 2, 3, 4, 5};
cout << v[v.size()/2] << endl;
Imprimindo o último elemento do vetor
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
cout << v[v.size()-1] << endl;
Ou podemos usar o .back()
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
cout << v.back() << endl;
Para acessar o primeiro podemos usar o .front()
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
cout << v.front() << endl;
Percorrendo um Vetor usando Laços de Repetição
Existem várias maneiras de percorrer um vector no C++ (detalhadas no material adicional). Aqui, vamos focar na forma mais usada para a lógica de programação, que é usando laços de repetição. Nesse caso, mostraremos usando for, mas como foi visto na aula 2, pode ser trocado por outros tipos de laços de repetição. Esse formato é útil quando precisamos do índice do elemento.
vector<tipo_de_dado> nome_do_vetor;
for (int i = 0; i < nome_do_vetor.size(); i++) {
cout << nome_do_vetor[i] << " ";
}
Exemplo
vector<int> v = {10, 20, 30, 40};
for (int i = 0; i < v.size(); i++) {
// v[i] acessa o valor na posição i
cout << v[i] << " ";
}
Conteúdo Adicional
Ordenação
Grande parte dos problemas algorítmicos envolve algum tipo de ordenação
Para ordenar vetores utilizamos o .sort() da biblioteca <algorithm>
#include <algorithm>
Ordem Crescente
Para ordenar em ordem crescente utilizamos o .begin() e o .end():
vector<int> v = {5, 1, 3, 2, 4};
sort(v.begin(), v.end());
// v = {1, 2, 3, 4, 5}
Ordem Decrescente
Para ordenar em ordem decrescente utilizamos o .rbegin() e o .rend() .
Percorrer Vetor
Usando ‘Range’
vector<int> v = {1, 2, 3, 4, 5};
for(int x : v) {
cout << x << " ";
}
// Saida 1 2 3 4 5
Esse formato é mais limpo quando só precisamos acessar os valores.
Por Referência
vector<int> v = {1, 2, 3, 4, 5};
for(int &x : v) {
x *= 2;
}
Nesse caso, x referencia diretamente os elementos do vetor, permitindo modificá-los.
Busca Binária
A biblioteca <algorithm> já tem o método binary_search(), para utilizarmos a busca binária
Exemplo de uso:
binary_search(v.begin(), v.end(), x);
Esse método retorna um valor booleano
Então para verificar se um elemento esta no vetor podemos fazer:
vector<int> v = {1, 2, 3, 4, 5};
int num = 6;
bool found = binary_search(v.begin(), v.end(), num);
if (found) {
cout << "O numero " << num << " foi encontrado no vetor." << endl;
} else {
cout << "O numero " << num << " nao foi encontrado no vetor." << endl;
}
Ou, usando ternário:
vector<int> v = {1, 2, 3, 4, 5};
int num = 7;
binary_search(v.begin(), v.end(), num) ? cout << num << " encontrado" : cout << num << " não encontrado";
Vetores de Vetores
Em muitos problemas podemos encontrar a necessidade de utilizar vetores de vetores.
O exemplo mais comum de um vetor de vetores é o da criação de uma matriz
vector<vector<int>> matriz;
matriz.push_back({1, 2, 3});
matriz.push_back({4, 5, 6});
matriz.push_back({7, 8, 9});
for (const auto& linha : matriz) {
for (const auto& elemento : linha) {
cout << elemento << " ";
}
cout << endl;
}
Criação de matriz personalizada n x m
vector<vector<int>> matriz;
int n, m;
cin >> n >> m; // Lê as dimensões da matriz
matriz.resize(n); // Redimensiona a matriz para ter n linhas
for (int i = 0; i < n; i++) {
matriz[i].resize(m); // Redimensiona cada linha para ter m colunas
for (int j = 0; j < m; j++) {
cin >> matriz[i][j]; // Lê os elementos da matriz
}
}
for (const auto& linha : matriz) {
for (const auto& elemento : linha) {
cout << elemento << " ";
}
cout << endl;
}
Tempo de Execução dos métodos
No contexto da Programação Competitiva, é muito importante entender o tempo de execução das operações executadas.
| Método / Operação | Complexidade | Explicação |
|---|---|---|
v[i] |
O(1) | Acesso direto por índice |
v.at(i) |
O(1) | Acesso direto com verificação de limites |
v.front() |
O(1) | Acesso ao primeiro elemento |
v.back() |
O(1) | Acesso ao último elemento |
v.size() |
O(1) | Retorna o tamanho atual do vetor |
v.push_back(x) |
O(1) amortizado | Inserção no final |
v.pop_back() |
O(1) | Remove o último elemento |
v.insert(pos, x) |
O(n) | Pode precisar deslocar elementos |
v.erase(pos) |
O(n) | Pode precisar deslocar elementos |
v.begin() |
O(1) | Retorna iterador do início |
v.end() |
O(1) | Retorna iterador do final |
v.rbegin() |
O(1) | Retorna iterador reverso do final |
v.rend() |
O(1) | Retorna iterador reverso do início |
v.reserve(n) |
O(n) no pior caso | Pode realocar e copiar elementos |
v.resize(n) |
O(n) | Pode inserir/remover elementos |
sort(v.begin(), v.end()) |
O(n log n) | Ordenação da STL (Standard Template Library) |
binary_search() |
O(log n) | Busca binária em vetor ordenado |
O que significa O(1) amortizado?
O método .push_back() na maioria dos casos tem custo O(1), porém quando a capacidade do vetor acaba, o C++ precisa:
Alocar um novo bloco de memória maior → Copiar todos os elementos antigos → Liberar a memória anterior
Nessa situação especifica a operação custa O(n)
Exercícios
Exercício feito em Aula:
Torneio:
Exercícios do Torneio
1172 - Substituição em Vetor I
1178 - Preenchimento de Vetor III
Slides
https://embed.figma.com/deck/OBnf2744ev4AWjGFp7HyrL?embed-host=notion&footer=false&theme=system