Explorando a STL - Aula 5 - Set

Escrito por Sofhia de Souza e Anita Ramos Almeida

Set (ou conjunto) é uma estrutura de dados da STL, na biblioteca <set>, que guarda elementos distintos de maneira ordenada. Ele tem como membros funções como insert(), erase() e find(), que possuem complexidade $O(log \; n)$, onde $n$ é o tamanho do conjunto. É uma estrutura muito útil, uma vez que, já implementada no C++, é muito simples de ser utilizada e torna alguns algoritmos muito mais eficientes.

Antes de falarmos sobre esta estrutura, recomendamos a leitura da aula de Ponteiros, pois o seu entendimento será de grande ajuda no decorrer desta aula. Agora, vamos à aula de set:

Declaração

Para declararmos um set, usamos uma estrutura muito parecida com a do vector:

	#include <set> // Biblioteca do set
	using namespace std;
	int main()
	{
	set<int> t; // Declaração de um set que armazena valores inteiros
	}

view raw set_codigo1.cpp hosted with by GitHub

Inserção de elementos

Para inserimos um elemento dentro do set, utilizamos a função insert(), como no exemplo abaixo. Essa função insere o elemento de forma ordenada e possui complexidade é $O(log \; n)$. É importante lembrar que cada elemento é inserido no máximo uma vez no set, que não permite a existência de elementos repetidos.

	#include <set> // Biblioteca do set
	using namespace std;
	int main()
	{
	set<int> t; // Declaração de um set de int
	t.insert(5); // Adiciona o elemento 5 no set
	t.insert(12); // Adiciona o elemento 12 no set
	// t = {5, 12}
	t.insert(3); //Adiciona o elemento 3 no set
	// t = {3, 5, 12} (set sempre é ordenado)
	t.insert(5); // Não adiciona o elemento 5 no set porque ele já está presente
	// t = {3, 5, 12}
	}

view raw set_codigo2.cpp hosted with by GitHub

Remoção de elementos

Para remover um elemento do set, basta utilizarmos a função erase(). Essa função também possui complexidade $O(log \; n)$. Segue abaixo um exemplo da função:

	#include <set> // Biblioteca do set
	using namespace std;
	int main()
	{
	set<int> t; // Declaração de um set de int
	t.insert(5); // Adiciona o elemento 5 no set
	t.insert(12); // Adiciona o elemento 12 no set
	t.insert(3); // Adiciona o elemento 3 no set
	// t = {3, 5, 12}
	t.erase(5); //remove o elemento 5 do set
	// t = {3, 12}
	}

view raw set_codigo3.cpp hosted with by GitHub

Busca de elementos

A função find() verifica se um elemento está inserido no set, retornando um ponteiro que aponta para esse elemento. Caso ele não esteja no conjunto, o ponteiro aponta para o fim do set (definido pela função end()). Como as outras funções, também possui complexidade $O(log \; n)$. Segue abaixo um exemplo:

	#include <iostream> // Bibiloteca iostream necessária para funcionar
	#include <set> // Biblioteca do set
	using namespace std;
	int main()
	{
	set<int> t; // Declaração de um set de int
	t.insert(5); // Adiciona o elemento 5 no set
	t.insert(12); // Adiciona o elemento 12 no set
	t.insert(3); // Adiciona o elemento 3 no set
	// t = {3, 5, 12}
	if(t.find(5) != t.end()) // Verifico se o 5 está no meu set
	{
	printf("5\n"); // Se estiver, imprimo o valor
	}
	}

view raw set_codigo4.cpp hosted with by GitHub

Outras funções

A lista abaixo possui outras funções muito utilizadas:

begin(): retorna um ponteiro que aponta para o inicio do set, em $O(1)$.
end(): retorna um ponteiro que aponta para o fim do set, em $O(1)$.
empty(): retorna um valor booleano, que indica se o set está ou não vazio, em $O(1)$.
size(): retorna quantidade de elementos do set, em $O(1)$.
clear(): remove todos os elementos do set, em $O(n)$.
lower_bound($x$): retorna um ponteiro que aponta para o primeiro valor que não vem antes que $x$, em $O(log \; n)$.
upper_bound($x$): retorna um ponteiro que aponta para o primeiro valor que vem depois de $x$, em $O(log \; n)$.

Para acessar a lista completa de funções do set, clique aqui e veja a sua página na referência do C++.

Percorrer o set

O set consegue fazer as operações que vimos anteriormente em tempo $O(log \; n)$ porque ele guarda seu elementos de maneira ordenada (de forma crescente, por padrão). Entretanto, os elementos não estão localizados lado a lado como em um vetor. Eles são posicionados de maneira bem mais complexa, utilizando a estrutura de dados Red-Black Tree.

Poranto, o set utiliza um iterator, que pode ser definido como um objeto que recebe um ponteiro e percorre os elementos do set de maneira crescente. Assim, se temos um iterador de nome it e executarmos o comando "it++;", ele passará a apontar para o próximo elemento do set, em ordem crescente. Para percorrer todo o set, basta usarmos um for e um iterador que começará apontando para o primeiro elemento do conjunto (ou seja, o ponteiro begin()) e, enquanto ele não apontar para o fim do set (o ponteiro end()), iremos para o próximo elemento.

Escreveremos o comando "set<int>::iterator it;", para criar este tipo de iterador. Segue abaixo um código que exemplifica isso, que insere os valores de 10 a 1 no set, depois o percorre e imprime todos os elementos presentes no conjunto.

	#include <iostream> // Bibiloteca iostream necessária para funcionar
	#include <set> // Biblioteca do set
	using namespace std;
	int main()
	{
	set<int> t; // Declaração de um set de int
	for(int i=10; i>=1; i--) // Percorre os números de 10 a 1
	{
	t.insert(i); // Adiciono o elemento i
	}
	set<int>::iterator it; // Declaração de um iterator para o set
	for(it=t.begin(); it!=t.end(); it++) // Percorre o set inteiro
	{
	printf("%d ", *it); // Imprimo cada elemento do set (sempre ordenado)
	}
	// Saída
	// 1 2 3 4 5 6 7 8 9 10
	}

view raw set_codigo5.cpp hosted with by GitHub

Problemas para praticar:

Problema 1 - Frequência na Aula

Problema 2 - Número Proibido

Problema 3 - Redundancy

Problema 4 - Lista de Chamada