ED Não Linear

Subpáginas

Subsecções de ED Não Linear

Capítulo 10

Map

O map é uma estrutura interessante pois permite “mapear” chaves à valores, e dado uma chave encontrar o seu valor rapidamente (complexidade depende da implementação). Por exemplo, podemos fazer um map com strings de chave e int de valor, sendo possível recuperar o valor inteiro associado a aquela string rapidamente.

Deve-se ter cuidado com o uso de map pois ele é implementado em c++ como um set de pairs, isto é, vai ter complexidade O(log n) para inserir e modificar dados.

Informação

Existe também o unordered_map, que é uma estrutura que usa hash. No pior caso é linear, mas em média tem complexidade constante. O seu funcionamento é similar ao do map, com a diferença de que seus elementos não estão ordenados.

Métodos

  • insert({key, element}) - Insere uma chave e um valor no map
  • erase() - Remove uma key ou um iterator
  • find(element) - Retorna um iterator da posição do element
  • count - Retorna a quantidade de elementos de uma chave específica
  • size - Retorna o tamanho do map
  • clear - Limpa todo o conteúdo do Map
  • begin - Retorna um iterator para o início do map
  • end - Retorna um iterator para o final do map

Inicialização

#include <bits/stdc++.h>
using namespace std;

int main(){
    // map chave, valor de inteiros

    map<int, int> m; // Inicialização de map vazio
    
    map<int, int> m = {{2, 3}, {4, 6}}; // Inicialização de map com valor 

    m[7] = 3
    m[7] ++; // 4
}

Iteração

#include <bits/stdc++.h>
using namespace std;

int main(){
    // iterando por métodos iterator

    map<int, int> m = {{2, 3}, {4, 6}};


    // Printa a chave e o valor em cada linha
    for(auto it = m.begin(); it != m.end(); it++){
        cout<< it.first <<" "<< it.second<< endl;
    }

    // tambem pode ser escrito como:
    for(auto it: m){
        cout<< it.first << " "<< it.second<< endl;
    }
}

Saída

2 3
4 6

Apagando elemento

#include <bits/stdc++.h>
using namespace std;

int main(){
    // iterando por métodos iterator
    map<int, int> m = {{2, 3}, {4, 6}}
    
    m.erase(m.find(2));
    m.erase(4);
}
Informação

Da primeira maneira, ele apaga em tempo constante, pois está passando um iterator. Da segunda maneira, ele apaga em log(N), pois ele faz uma busca no elemento.

Verificar um elemento

#include <bits/stdc++.h>
using namespace std;

int main(){
    // iterando por métodos iterator
    map<int, int> m = {{2, 3}, {4, 6}}

    if( m.count(2) > 0 ){ // existe uma chave {2}
        cout<< "Elemento existe";
    }else{
        cout<< "Elemento não existe";
    }
}

Saída

Elemento existe
Capítulo 11

Set

A estrutura set é bem parecida com o que conhecemos de conjuntos da matemática; não existem elementos repetidos e a ordem não importa.

A implementação do set, porém, é feita com uma árvore binária de busca, sendo assim permitido inserir, remover e acessar um elemento em O(log n).

A vantagem do set em relação ao vector é que, caso queira inserir um elemento em um vector ordenado e preservar a ordenação, você terá que procurar o lugar que ele deve ser inserido, fazer a inserção e modificar a posição dos elementos à direita dele. Modificar todas as posições à direita tem uma complexidade ruim O(n), então este algoritmo será mais eficiente com o set.

Além da vantagem de eficiência, essas operações com set são feitas com alguns simples métodos!

Métodos

  • insert(element) - Insere um elemento no Set
  • erase() - Remove uma key ou um iterator
  • find(element) - Retorna um iterator da posição do element
  • count - Retorna a quantidade de elementos de uma chave específica
  • size - Retorna o tamanho do set
  • clear - Limpa todo o conteúdo do set
  • begin - Retorna um iterator para o início do set
  • end - Retorna um iterator para o final do set
  • lower_bound(element) - Retorna um iterator para o primeiro valor >= element
  • upper_bound(element) - Retorna um iterator para o primeiro valor > element

Exemplo 1


#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    s.insert(3); // insere elemento no set
    cout << s.size() << endl; // tamanho do set

    // para verificar se um elemento está contido no set ou nao podemos utilizar
    // o metodo find; caso nao esteja presente ele retornará o iterator para
    // o fim do set

    if(s.find(2) == s.end()) {
        cout << "O numero 2 nao esta no set" << endl;
    }
    else {
        cout << "O numero 2 esta no set" << endl;
    }

    if(s.find(3) == s.end()) {
        cout << "O numero 3 nao esta no set" << endl;
    }
    else {
        cout << "O numero 3 esta no set" << endl;
    }
    
    s.erase(3); // apaga elemento 3 do set
    
    if(s.find(3) == s.end()) {
        cout << "O numero 3 nao esta no set" << endl;
    }
    else {
        cout << "O numero 3 esta no set" << endl;
    }

    return 0;
}

Outro método extremamente útil é o lower_bound (e o upper_bound). O lower_bound recebe um inteiro x como argumento e retorna o menor inteiro maior ou igual a x. Caso não exista, ele retorna um iterator para o fim do set (set.end()).

Exemplo 2

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    s.insert(3); // insere elemento no set
    s.insert(4);
    s.insert(5);
    s.insert(7);

    auto iterator1 = s.lower_bound(6);
    // se iterator eh igual a s.end() entao nao existe
    if(iterator1 != s.end()) {
        int numero = *iterator1;
        cout << "menor inteiro maior ou igual a 6 eh " << numero << endl;
    }
    else {
        cout << "nao existe inteiro numero maior ou igual a 6" << endl;
    }

    auto iterator2 = s.lower_bound(9);
    // se iterator eh igual a s.end() entao nao existe
    if(iterator2 != s.end()) {
        int numero = *iterator2;
        cout << "menor inteiro maior ou igual a 9 eh " << numero << endl;
    }
    else {
        cout << "nao existe inteiro numero maior ou igual a 9" << endl;
    }

    return 0;
}
Informação

Na verdade, você pode utilizar o lower_bound para qualquer tipo que implemente a operação “<”, como por exemplo o pair<int, int>.