Explorando a STL - Aula 1 - Vector

Escrito por Thiago Mota e Anita Almeida

A estrutura $vector$ faz parte do conjunto de estruturas da Standard Template Library e representa um vetor dinâmico, ou seja, um vetor que não precisa ter um tamanho fixo pré-definido como visto anteriormente na aula de Vetores.

Declaração

A biblioteca <vector> é necessária para utilizar a estrutura $vector$ . Além disso, também vemos que, diferentemente de um vetor, o tipo da estrutura é colocada entre <tipo>, ou seja, declaramos usando o seguinte comando: vector<tipo> nome.

	#include <vector> // Biblioteca que contém a estrutura vector
	using namespace std;

	int main()
	{
	vector<int> v1; // Declaração de um vector do tipo 'int'
	vector<double> v2; // Declaração de um vector do tipo 'double'
	return 0;
	}

view raw vector_codigo1.cpp hosted with

by GitHub

Inserção de elementos

O primeiro comando do $vector$ e um dos mais importantes é o push_back(), que insere um elemento ao final do vetor. Por exemplo, se os elementos do vetor forem $\{1, 3, 5, 7\}$ e usarmos o comando push_back(2), o vetor após a mudança será $\{1, 3, 5, 7, 2\}$ .

A complexidade do comando push_back() é $O(1)$ .

	#include <vector> // Biblioteca que contém a estrutura vector
	using namespace std;

	int main()
	{
	vector<int> v; // Declaração de um vector do tipo int inicialmente vazio

	v.push_back(1); // Insiro o elemento 1 no final do vetor
	v.push_back(3); // Insiro o elemento 3 no final do vetor
	v.push_back(5); // Insiro o elemento 5 no final do vetor
	v.push_back(7); // Insiro o elemento 7 no final do vetor

	// O vetor final é {1, 3, 5, 7}
	return 0;
	}

view raw vector_codigo2.cpp hosted with

by GitHub

Acesso a um elemento

Assim como um vetor normal, para acessarmos o $i$ -ésimo elemento do $vector$ , podemos utilizar a sintaxe $v[i]$ . Além disso, como o vetor é dinâmico, podemos utilizar o comando $size()$ para acessar o número de elementos no vetor.

Nota: O comando $size()$ retorna um tipo diferente de $int$ . Assim, para realizar comparações entre $int$ e $v.size()$ é recomendado utilizar $(int)v.size()$ para o computador transformar o $v.size()$ em inteiro.

	#include <vector> // Biblioteca que contém a estrutura vector
	using namespace std;

	int main()
	{
	vector<int> v; // Declaração de um vector do tipo int inicialmente vazio

	v.push_back(1); // Insiro o elemento 1 no final do vetor
	v.push_back(3); // Insiro o elemento 3 no final do vetor
	v.push_back(5); // Insiro o elemento 5 no final do vetor
	v.push_back(7); // Insiro o elemento 7 no final do vetor
	// v = {1, 3, 5, 7}

	for(int i=0; i<(int)v.size(); i++) // Percorre o vetor da posição 0 até a última posição (v.size()-1)
	{
	printf("%d ", v[i]); // Imprimo o i-ésimo elemento do vetor
	}
	printf("\n");
	// Saída:
	// 1 3 5 7

	return 0;
	}

view raw vector_codigo3.cpp hosted with

by GitHub

Outros comandos

Abaixo, citaremos brevemente outros comandos úteis do $vector$ :

pop_back(): Remove o último elemento do $vector$ .

Complexidade: $O(1)$ .

	// v = {1, 2, 3, 4, 5}
	v.pop_back(); // Remove o último elemento do vetor
	// v = {1, 2, 3, 4}

view raw vector_codigo4.cpp hosted with

by GitHub

erase(): Remove o(s) elemento(s) de uma determinada posição ou intervalo do $vector$ .

Complexidade: $O(n)$ .

	// v = {1, 9, 5, 3, 7}
	v.erase(v.begin()+3); // Apaga o elemento da posição v.begin()+3 = 0+3 = 3, ou seja, apaga o elemento v[3] = 3
	// v = {1, 9, 5, 7}

	// v = {1, 9, 5, 7}
	v.erase(v.begin()+1,v.begin()+3); // Apaga os elementos do intervalo da posição 1 à 2, ou seja, apaga o 9 e o 5
	// v = {1, 7}

view raw vector_codigo7.cpp hosted with

by GitHub

clear(): Remove todos os elementos do $vector$ .

Complexidade: $O(n)$ .

	// v = {1, 9, 5, 3, 7}
	v.clear(); // Remove todos os elementos do vetor
	// v = {}

view raw vector_codigo.8cpp hosted with

by GitHub

resize(n): Troca o tamanho do vetor para $n$ e pode ou não inserir um determinado número nas novas posições.

Complexidade: $O(n)$ .

	// v = {1, 2, 3, 4, 5}
	v.resize(8); // Muda o tamanho do vector v para 8
	// v = {1, 2, 3, 4, 5, 0, 0, 0}

	// v = {1, 2, 3, 4, 5, 0, 0, 0}
	v.resize(12,-1); // Muda o tamanho do vector v para 12 e nas posições novas/vazias insere o número -1
	// v = {1, 2, 3, 4, 5, 0, 0, 0, -1, -1, -1, -1}

view raw vector_codigo5.cpp hosted with

by GitHub

Para ordenar um vector utilizando o sort, podemos fazer o seguinte código:

Complexidade: $O(n \log_{} n)$ .

	#include <vector> // Biblioteca que contém a estrutura vector
	#include <algorithm> // Biblioteca do sort
	using namespace std;

	int main()
	{
	vector<int> v; // Declaração de um vector do tipo int

	v.push_back(3); // Insiro o elemento 3 no final do vetor
	v.push_back(1); // Insiro o elemento 1 no final do vetor
	v.push_back(7); // Insiro o elemento 7 no final do vetor
	v.push_back(5); // Insiro o elemento 5 no final do vetor

	// v = {3, 1, 7, 5}
	sort(v.begin(), v.end());
	// v = {1, 3, 5, 7}
	return 0;
	}

view raw vector_codigo6.cpp hosted with

by GitHub

Nota: Os outros comandos do vector podem ser encontrados nos links de referência a seguir:

Problemas para praticar:

Problema 1 - Fila

Problema 2 - Escada Rolante

Problema 3 - Zero para Cancelar

Problema 4 - Lista de Chamada