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:

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.

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:

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:

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.

Problemas para praticar:

Problema 1 - Frequência na Aula

Problema 2 - Número Proibido

Problema 3 - Redundancy

Problema 4 - Lista de Chamada