Lista 08 · Iteradores, algorithm e lambdas¶
Exercícios da Semana 9 — Iteradores, algorithm e lambdas. Use as funções de <algorithm> sempre que fizer sentido — é o que este capítulo pede para você praticar.
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 ordena_crescente, que recebe um std::vector<int>& e o ordena em ordem crescente usando std::sort (nada de ordenar na mão aqui).
// 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 <vector>
#include <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX01_H
#define EX01_H
// Ordena v em ordem crescente (use std::sort).
void ordena_crescente(std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void ordena_crescente(std::vector<int>& v) {
// TODO: chame std::sort(v.begin(), v.end());
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> a = {5, 1, 4, 2};
ordena_crescente(a);
std::vector<int> esperado_a = {1, 2, 4, 5};
assert(a == esperado_a);
std::vector<int> b = {1};
ordena_crescente(b);
std::vector<int> esperado_b = {1};
assert(b == esperado_b);
std::vector<int> c = {};
ordena_crescente(c);
assert(c.empty());
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex02¶
Escreva conta_maiores_que, que recebe um std::vector<int> e um limite, e devolve quantos elementos são maiores que o limite — usando std::count_if com uma lambda.
// 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 <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX02_H
#define EX02_H
// Retorna quantos elementos de v sao maiores que "limite" (use std::count_if).
int conta_maiores_que(const std::vector<int>& v, int limite);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int conta_maiores_que(const std::vector<int>& v, int limite) {
// TODO: use std::count_if(v.begin(), v.end(), lambda) e retorne o resultado
// (o retorno de count_if e um inteiro grande o suficiente; converta para int).
return 0;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(conta_maiores_que({1, 5, 8, 3, 9}, 4) == 3);
assert(conta_maiores_que({1, 2, 3}, 10) == 0);
assert(conta_maiores_que({}, 0) == 0);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex03¶
Escreva existe_negativo, que recebe um std::vector<int> e devolve true se algum elemento for negativo — usando std::any_of.
// 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 <vector>
#include <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX03_H
#define EX03_H
// Retorna true se algum elemento de v for negativo (use std::any_of).
bool existe_negativo(const std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool existe_negativo(const std::vector<int>& v) {
// TODO: use std::any_of(v.begin(), v.end(), lambda).
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(existe_negativo({1, -2, 3}));
assert(!(existe_negativo({1, 2, 3})));
assert(!(existe_negativo({})));
assert(existe_negativo({-1}));
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex04¶
Escreva dobra_valores, que recebe um std::vector<int> e devolve um novo vector com cada elemento dobrado — usando std::transform.
// 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 <vector>
#include <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX04_H
#define EX04_H
// Retorna um novo vector com cada elemento de v dobrado (use std::transform).
std::vector<int> dobra_valores(const std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::vector<int> dobra_valores(const std::vector<int>& v) {
// TODO: crie um vector "resultado" do mesmo tamanho de v e use
// std::transform(v.begin(), v.end(), resultado.begin(), lambda).
return {};
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> esperado1 = {2, 4, 6};
assert(dobra_valores({1, 2, 3}) == esperado1);
std::vector<int> esperado2 = {};
assert(dobra_valores({}) == esperado2);
std::vector<int> esperado3 = {-2, 0, 2};
assert(dobra_valores({-1, 0, 1}) == esperado3);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex05¶
Escreva soma_quadrados, que recebe um std::vector<int> e devolve a soma dos quadrados de cada elemento — usando std::accumulate com uma lambda de dois parâmetros (acumulador, elemento).
// 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 <vector>
#include <numeric>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX05_H
#define EX05_H
// Retorna a soma dos quadrados dos elementos de v (use std::accumulate).
int soma_quadrados(const std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int soma_quadrados(const std::vector<int>& v) {
// TODO: use std::accumulate(v.begin(), v.end(), 0, lambda(acumulador, x)).
return 0;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(soma_quadrados({1, 2, 3}) == 14);
assert(soma_quadrados({}) == 0);
assert(soma_quadrados({5}) == 25);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex06¶
Escreva maior_string, que recebe um std::vector<std::string> não vazio e devolve a string mais longa (se houver empate, devolva a primeira que aparecer). Use std::max_element com uma lambda que compara .size().
// 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 <vector>
#include <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX06_H
#define EX06_H
// Retorna a string mais longa de v (assume que v nao esta vazio).
// Use std::max_element.
std::string maior_string(const std::vector<std::string>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::string maior_string(const std::vector<std::string>& v) {
// TODO: use std::max_element(v.begin(), v.end(), lambda que compara .size())
// e retorne *iterador.
return "";
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(maior_string({"a", "abc", "ab"}) == std::string("abc"));
assert(maior_string({"x"}) == std::string("x"));
assert(maior_string({"aa", "bb", "c"}) == std::string("aa"));
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex07¶
Você tem um vector com leituras de tensão de um laboratório e precisa descartar as medições fora da faixa aceitável. Escreva filtra_faixa, que recebe um std::vector<double>& e remove do próprio vector todas as leituras menores que minimo ou maiores que maximo, preservando a ordem das que ficam.
Use o idioma erase-remove: std::remove_if empurra para o fim os elementos que a lambda marca como true e devolve o novo fim lógico; v.erase(novo_fim, v.end()) é quem encolhe o vector de verdade.
std::vector<double> tensoes = {5.0, 127.0, 250.0, 220.0};
filtra_faixa(tensoes, 10.0, 240.0);
// tensoes agora vale {127.0, 220.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 <vector>
#include <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX07_H
#define EX07_H
// Remove do proprio vector todas as leituras fora da faixa [minimo, maximo],
// preservando a ordem das que permanecem.
void filtra_faixa(std::vector<double>& leituras, double minimo, double maximo);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void filtra_faixa(std::vector<double>& leituras, double minimo, double maximo) {
// TODO: use std::remove_if com uma lambda que devolve true para as leituras
// fora da faixa, e depois leituras.erase(...) ate leituras.end().
// A lambda precisa capturar minimo e maximo: [minimo, maximo](double x) { ... }
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<double> tensoes = {5.0, 127.0, 250.0, 220.0};
filtra_faixa(tensoes, 10.0, 240.0);
assert(tensoes.size() == 2);
assert(tensoes[0] == 127.0);
assert(tensoes[1] == 220.0);
// Os limites entram: a faixa e fechada.
std::vector<double> limites = {10.0, 240.0};
filtra_faixa(limites, 10.0, 240.0);
assert(limites.size() == 2);
std::vector<double> nenhuma_valida = {1.0, 2.0, 999.0};
filtra_faixa(nenhuma_valida, 10.0, 240.0);
assert(nenhuma_valida.empty());
std::vector<double> vazio;
filtra_faixa(vazio, 10.0, 240.0);
assert(vazio.empty());
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex08¶
Dada a struct Musica (campos nome e duracao, em segundos, já declarada), escreva ordena_por_duracao, que recebe um std::vector<Musica>& e ordena a playlist da música mais curta para a mais longa, usando std::sort com uma lambda que compara as durações.
std::vector<Musica> playlist = {{"longa", 300}, {"curta", 120}};
ordena_por_duracao(playlist);
// playlist agora comeca por {"curta", 120}
// 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 <string>
#include <vector>
#include <algorithm>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX08_H
#define EX08_H
struct Musica {
std::string nome;
int duracao;
};
// Ordena a playlist pela duracao, em ordem crescente.
void ordena_por_duracao(std::vector<Musica>& playlist);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void ordena_por_duracao(std::vector<Musica>& playlist) {
// TODO: chame std::sort passando uma lambda que recebe duas Musica
// e devolve true quando a primeira e mais curta que a segunda.
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<Musica> playlist = {
{"longa", 300},
{"curta", 120},
{"media", 210},
};
ordena_por_duracao(playlist);
assert(playlist[0].nome == std::string("curta"));
assert(playlist[1].nome == std::string("media"));
assert(playlist[2].nome == std::string("longa"));
std::vector<Musica> ja_ordenada = {{"a", 1}, {"b", 2}};
ordena_por_duracao(ja_ordenada);
assert(ja_ordenada[0].nome == std::string("a"));
std::vector<Musica> vazia;
ordena_por_duracao(vazia);
assert(vazia.empty());
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex09¶
Este exercício é o mesmo ex09 da Lista 05 — o k-ésimo menor valor. Lá você teve que escrever o bubble sort inteiro para poder ordenar; aqui, reescreva usando std::sort.
As regras são as mesmas: k conta a partir de 1, o vector vem por valor (para ordenar a cópia, e não o vector do chamador), o resultado sai por um parâmetro de referência, e k fora do intervalo [1, v.size()] devolve false.
Compare as duas soluções lado a lado quando terminar. A da Lista 05 tem umas quinze linhas de bubble sort, com um laço duplo e dois limites para errar; esta tem uma chamada. E std::sort não é um bubble sort com nome bonito: ele é assintoticamente melhor, o que para dez mil elementos é a diferença entre cerca de 130 mil comparações e cerca de cem milhões.
Se quiser ir além depois de fazer funcionar: std::nth_element(v.begin(), v.begin() + (k - 1), v.end()) resolve este problema sem ordenar o vector inteiro — ele só garante que a posição k - 1 fique com o elemento certo, que é exatamente o que a pergunta pede.
int r;
k_esimo_menor({7, 3, 9, 1}, 2, r) // -> true, e r vale 3
k_esimo_menor({7, 3, 9, 1}, 5, r) // -> false
// 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
// Escreve em "valor" o k-esimo menor elemento de "v". k comeca em 1.
// Devolve true se k estiver em [1, v.size()]; devolve false e nao mexe em
// "valor" caso contrario.
// Recebe o vector por valor porque precisa ordenar uma copia.
// O MESMO k_esimo_menor do ex09 da Lista 05 -- agora usando std::sort.
bool k_esimo_menor(std::vector<int> v, int k, int& valor);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool k_esimo_menor(std::vector<int> v, int k, int& valor) {
// TODO: mesma logica do ex09 da Lista 05, mas com std::sort no lugar
// do bubble sort escrito a mao. Nao esqueca o #include <algorithm>.
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> v = {7, 3, 9, 1};
int r = 0;
assert(k_esimo_menor(v, 1, r));
assert(r == 1);
assert(k_esimo_menor(v, 2, r));
assert(r == 3);
assert(k_esimo_menor(v, 3, r));
assert(r == 7);
assert(k_esimo_menor(v, 4, r));
assert(r == 9);
// k fora do intervalo: devolve false e nao mexe no parametro de saida
r = 99;
assert(!k_esimo_menor(v, 0, r));
assert(!k_esimo_menor(v, 5, r));
assert(!k_esimo_menor(v, -1, r));
assert(r == 99);
// o vector de quem chamou NAO pode ter sido ordenado
assert((v == std::vector<int>{7, 3, 9, 1}));
// repetidos ocupam posicoes proprias
assert(k_esimo_menor({5, 1, 5}, 2, r));
assert(r == 5);
assert(k_esimo_menor({5, 1, 5}, 3, r));
assert(r == 5);
// negativos
assert(k_esimo_menor({-2, -9, 0}, 1, r));
assert(r == -9);
// um elemento so
assert(k_esimo_menor({42}, 1, r));
assert(r == 42);
// vector vazio: qualquer k esta fora do intervalo
std::vector<int> vazio;
assert(!k_esimo_menor(vazio, 1, r));
std::cout << "Todos os testes passaram!\n";
return 0;
}