Lista 06 · map e set¶

Como resolver

Copie o bloco de código de cada exercício, cole no seu compilador online, preencha a parte marcada como ESCREVA SUA SOLUCAO AQUI e rode. A saída mostra quais testes passaram.

ex01¶

Escreva conta_caracteres, que recebe um texto e devolve um std::map<char, int> com a contagem de cada caractere que aparece.

conta_caracteres("aab")  // -> { {'a', 2}, {'b', 1} }

// ex01 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <string>
#include <map>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX01_H
#define EX01_H

// Retorna um map com a contagem de cada caractere de texto.
std::map<char, int> conta_caracteres(const std::string& texto);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::map<char, int> conta_caracteres(const std::string& texto) {
    // TODO: percorra texto, usando contagem[c]++ para cada caractere c.
    std::map<char, int> contagem;
    return contagem;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::map<char, int> esperado1 = {{'a', 2}, {'b', 1}};
    assert(conta_caracteres("aab") == esperado1);

    std::map<char, int> esperado2 = {};
    assert(conta_caracteres("") == esperado2);

    std::map<char, int> esperado3 = {{'x', 3}};
    assert(conta_caracteres("xxx") == esperado3);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex02¶

Escreva remove_duplicados, que recebe um std::vector<int> e devolve um std::vector<int> sem duplicatas, em ordem crescente. Use um std::set<int> como passo intermediário (ele já remove duplicatas e mantém ordem sozinho).

remove_duplicados({3, 1, 2, 3, 1})  // -> {1, 2, 3}

// ex02 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>
#include <set>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX02_H
#define EX02_H

// Retorna os valores de v sem duplicatas, em ordem crescente.
std::vector<int> remove_duplicados(const std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::vector<int> remove_duplicados(const std::vector<int>& v) {
    // TODO: insira todos os elementos de v num std::set<int> (remove duplicatas
    // e ordena sozinho), depois monte um vector a partir do set.
    return {};
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::vector<int> esperado1 = {1, 2, 3};
    assert(remove_duplicados({3, 1, 2, 3, 1}) == esperado1);

    std::vector<int> esperado2 = {};
    assert(remove_duplicados({}) == esperado2);

    std::vector<int> esperado3 = {5};
    assert(remove_duplicados({5, 5, 5}) == esperado3);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex03¶

Escreva existe_chave, que recebe um std::map<std::string, int> e uma chave, e devolve true se a chave existir — sem usar operator[] (isso criaria a chave se ela não existisse!). Use .count() ou .find().

std::map<std::string, int> m = {{"a", 1}, {"b", 2}};
existe_chave(m, "a")  // -> true
existe_chave(m, "z")  // -> false

// ex03 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <string>
#include <map>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX03_H
#define EX03_H

// Retorna true se "chave" existir em m, sem usar operator[].
bool existe_chave(const std::map<std::string, int>& m, const std::string& chave);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool existe_chave(const std::map<std::string, int>& m, const std::string& chave) {
    // TODO: use m.count(chave) ou m.find(chave) != m.end().
    return false;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::map<std::string, int> m = {{"a", 1}, {"b", 2}};
    assert(existe_chave(m, "a"));
    assert(!(existe_chave(m, "z")));

    std::map<std::string, int> vazio = {};
    assert(!(existe_chave(vazio, "a")));

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex04¶

Escreva interseccao, que recebe dois std::set<int> e devolve um novo std::set<int> só com os valores que aparecem nos dois conjuntos.

interseccao({1, 2, 3}, {2, 3, 4})  // -> {2, 3}
interseccao({1, 2}, {3, 4})        // -> {}

// ex04 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <set>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX04_H
#define EX04_H

// Retorna um set com os valores que aparecem em a e em b ao mesmo tempo.
std::set<int> interseccao(const std::set<int>& a, const std::set<int>& b);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::set<int> interseccao(const std::set<int>& a, const std::set<int>& b) {
    // TODO: percorra a; para cada elemento, se ele tambem estiver em b
    // (use b.count(elemento)), insira no resultado.
    std::set<int> resultado;
    return resultado;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::set<int> esperado1 = {2, 3};
    assert(interseccao({1, 2, 3}, {2, 3, 4}) == esperado1);

    std::set<int> esperado2 = {};
    assert(interseccao({1, 2}, {3, 4}) == esperado2);

    std::set<int> esperado3 = {1, 2};
    assert(interseccao({1, 2}, {1, 2}) == esperado3);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex05¶

Escreva chave_maior_valor, que recebe um std::map<std::string, int> não vazio e devolve a chave associada ao maior valor.

std::map<std::string, int> m = {{"a", 3}, {"b", 9}, {"c", 1}};
chave_maior_valor(m)  // -> "b"

// ex05 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <string>
#include <map>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX05_H
#define EX05_H

// Retorna a chave associada ao maior valor em m (assume que m nao esta vazio).
std::string chave_maior_valor(const std::map<std::string, int>& m);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::string chave_maior_valor(const std::map<std::string, int>& m) {
    // TODO: percorra m com "for (const auto& [chave, valor] : m)" guardando
    // a chave do maior valor visto ate agora.
    return "";
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::map<std::string, int> m1 = {{"a", 3}, {"b", 9}, {"c", 1}};
    assert(chave_maior_valor(m1) == std::string("b"));

    std::map<std::string, int> m2 = {{"x", 5}};
    assert(chave_maior_valor(m2) == std::string("x"));

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex06¶

Escreva palavras_unicas, que recebe um texto e devolve quantas palavras diferentes ele tem (ignorando repetições). Use std::istringstream para separar as palavras e um std::set<std::string> para contar só as diferentes.

palavras_unicas("o rato roeu a roupa do rei de roma")  // -> 9
palavras_unicas("oi oi oi")                             // -> 1

// ex06 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <string>
#include <set>
#include <sstream>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX06_H
#define EX06_H

// Retorna quantas palavras diferentes existem em texto.
int palavras_unicas(const std::string& texto);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int palavras_unicas(const std::string& texto) {
    // TODO: use std::istringstream para separar as palavras (stream >> palavra
    // num while), insira cada uma num std::set<std::string>, e retorne o
    // tamanho do set no final.
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(palavras_unicas("o rato roeu a roupa do rei de roma") == 9);
    assert(palavras_unicas("oi oi oi") == 1);
    assert(palavras_unicas("") == 0);
    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex07¶

Escreva atualiza_estoque, que recebe um std::map<std::string, int>& (o estoque da loja, produto → quantidade) e um std::vector<std::string> com os produtos vendidos. Para cada venda, diminua 1 da quantidade daquele produto.

Se um produto vendido não estiver no estoque, ele deve entrar no map com valor 0 (a loja vendeu algo que não estava cadastrado — o registro precisa aparecer para o problema ser visível).

std::map<std::string, int> estoque = {{"cabo", 5}, {"fonte", 2}};
atualiza_estoque(estoque, {"cabo", "cabo", "led"});
// estoque: cabo -> 3, fonte -> 2, led -> 0

// ex07 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <map>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX07_H
#define EX07_H

// Diminui 1 da quantidade de cada produto vendido. Produtos vendidos que nao
// estavam no estoque sao inseridos com quantidade 0.
void atualiza_estoque(std::map<std::string, int>& estoque,
                      const std::vector<std::string>& vendidos);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void atualiza_estoque(std::map<std::string, int>& estoque,
                      const std::vector<std::string>& vendidos) {
    // TODO: para cada produto vendido, verifique com .count() se ele ja existe
    // no estoque. Se existir, subtraia 1 da quantidade; se nao, insira com 0.
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::map<std::string, int> estoque = {{"cabo", 5}, {"fonte", 2}};
    atualiza_estoque(estoque, {"cabo", "cabo", "led"});
    assert(estoque["cabo"] == 3);
    assert(estoque["fonte"] == 2);
    assert(estoque.count("led") == 1);
    assert(estoque["led"] == 0);

    // Vender de novo um produto que entrou com 0 deixa a quantidade negativa:
    // e o sinal de que a loja vendeu o que nao tinha.
    atualiza_estoque(estoque, {"led"});
    assert(estoque["led"] == -1);

    std::map<std::string, int> intacto = {{"cabo", 5}};
    atualiza_estoque(intacto, {});
    assert(intacto["cabo"] == 5);
    assert(intacto.size() == 1);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex08¶

Escreva diferenca, que recebe dois std::set<int> e devolve um novo std::set<int> com os valores que estão no primeiro conjunto e não estão no segundo (a diferença de conjuntos a \ b).

No exercício ex04 você fez a interseção; a diferença é o mesmo padrão com a condição invertida.

diferenca({1, 2, 3}, {2, 4})   // -> {1, 3}
diferenca({1, 2}, {1, 2})      // -> {}

// ex08 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <set>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX08_H
#define EX08_H

// Retorna os elementos que estao em a mas nao estao em b.
std::set<int> diferenca(const std::set<int>& a, const std::set<int>& b);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::set<int> diferenca(const std::set<int>& a, const std::set<int>& b) {
    // TODO: percorra a e insira no resultado cada valor que b.count(valor) == 0.
    return {};
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::set<int> r1 = diferenca({1, 2, 3}, {2, 4});
    assert(r1.size() == 2);
    assert(r1.count(1) == 1);
    assert(r1.count(3) == 1);
    assert(r1.count(2) == 0);

    assert(diferenca({1, 2}, {1, 2}).empty());
    assert(diferenca({}, {1, 2}).empty());

    std::set<int> r2 = diferenca({1, 2}, {});
    assert(r2.size() == 2);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex09¶

Escreva conta_comuns, que devolve quantos valores distintos aparecem nos dois vectors ao mesmo tempo.

A regra do exercício: sem set e sem map, só laço e comparação. Depois de resolver, compare com o ex04 desta mesma lista, que faz a interseção usando std::set: aqui você precisa cuidar da duplicata na mão ({1, 1, 2} contra {1, 2} dá 2, e não 3), enquanto o set cuidaria disso sozinho.

É esse contraste que mostra o que o container associativo está resolvendo.

conta_comuns({1, 2, 3}, {2, 3, 4})   // -> 2
conta_comuns({1, 1, 2}, {1, 2})      // -> 2   (o 1 conta uma vez so)

// ex09 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX09_H
#define EX09_H

// Retorna quantos valores DISTINTOS aparecem nos dois vectors.
// Escreva sem usar set nem map: so laco e comparacao.
int conta_comuns(const std::vector<int>& a, const std::vector<int>& b);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int conta_comuns(const std::vector<int>& a, const std::vector<int>& b) {
    // TODO: para cada valor de a, verifique se ele aparece em b.
    // Cuidado: se o mesmo valor se repetir em a, ele nao pode ser contado
    // duas vezes -- confira antes se ele ja apareceu em a mais cedo.
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(conta_comuns({1, 2, 3}, {2, 3, 4}) == 2);
    assert(conta_comuns({1, 2}, {3, 4}) == 0);
    assert(conta_comuns({1, 2}, {1, 2}) == 2);

    // valor repetido em a conta uma vez so
    assert(conta_comuns({1, 1, 2}, {1, 2}) == 2);
    assert(conta_comuns({5, 5, 5}, {5}) == 1);

    assert(conta_comuns({}, {1}) == 0);
    assert(conta_comuns({1}, {}) == 0);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex10¶

Escreva chaves_com_valor_zero, que recebe um std::map<std::string, int> (um estoque) e devolve um std::vector<std::string> com as chaves cujo valor é 0, em ordem crescente de chave.

Você não precisa ordenar nada: a própria iteração do map já entrega as chaves em ordem.

std::map<std::string, int> estoque = {{"parafuso", 0}, {"prego", 5}, {"arruela", 0}};
chaves_com_valor_zero(estoque)  // -> {"arruela", "parafuso"}

// ex10 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <map>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX10_H
#define EX10_H

// Retorna as chaves de "estoque" cujo valor e 0, em ordem crescente de chave.
std::vector<std::string> chaves_com_valor_zero(const std::map<std::string, int>& estoque);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::vector<std::string> chaves_com_valor_zero(const std::map<std::string, int>& estoque) {
    // TODO: percorra estoque com "for (const auto& [chave, valor] : estoque)"
    // e adicione a chave ao resultado quando valor == 0.
    return {};
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::map<std::string, int> estoque = {{"parafuso", 0}, {"prego", 5}, {"arruela", 0}};
    auto resultado = chaves_com_valor_zero(estoque);
    std::vector<std::string> esperado = {"arruela", "parafuso"};
    assert(resultado == esperado);

    std::map<std::string, int> vazio = {};
    assert(chaves_com_valor_zero(vazio).empty());

    std::cout << "Todos os testes passaram!\n";
    return 0;
}