(6) Escreva uma função genérica que recebe como parâmetro um vector de valores de qualquer tipo e retorna true se os elementos estiverem ordenados ou false, caso contrário. Na função main, faça a chamada da função para valores do tipo int, float e char.
(7) Crie e preencha um deque de elementos inteiros na função main. Crie funções em seu programa, que encontrem e retornem (deve ser criada uma função para cada tópico abaixo):
- o maior elemento;
- o menor elemento;
- a quantidade de vezes que o maior elemento aparece na lista;
- a quantidade de vezes que o menor elemento aparece na lista.
(8) Crie uma função capaz de mesclar (unir preservando a ordenação dos elementos) duas listas (list) previamente ordenadas, percorrendo apenas uma vez essas listas. Observações: uma nova lista deve ser criada e retornada e as listas originais não devem ser alteradas.
(7) Crie e preencha um deque de elementos inteiros na função main. Crie funções em seu programa, que encontrem e retornem (deve ser criada uma função para cada tópico abaixo):
(8) Crie uma função capaz de mesclar (unir preservando a ordenação dos elementos) duas listas (list) previamente ordenadas, percorrendo apenas uma vez essas listas. Observações: uma nova lista deve ser criada e retornada e as listas originais não devem ser alteradas.
Passo 1
Beleza, o exercício junta três temas de C++ bem legais:
- Função genérica (template) que recebe um
std::vector<T>
e diz se ele está ordenado; - Uso de
std::deque<int>
, criando funções para encontrar o maior, o menor e contar quantas vezes cada um aparece; - Função para mesclar (merge) duas
std::list<T>
já ordenadas, caminhando apenas uma vez em cada lista.
Pra resolver isso vamos usar template functions, iteradores da STL e lógica de comparação simples.
Passo 2
(Exercício 6) Função genérica para testar se um vector está ordenado
- Criar um template
<typename T> bool isSorted(const std::vector<T>& v)
. - Percorrer o vetor com um laço de
i = 1
atév.size() - 1
. - Em cada passo, comparar
v[i]
comv[i-1]
. Sev[i] < v[i-1]
, não está ordenado → retornafalse
. - Se sair do laço sem achar quebra, retorna
true
.
Explicando a teoria: usamos template pra aceitar qualquer tipo que suporte operador
<
. A checagem é linha-a-linha, comparando pares consecutivos.Passo 3
(Exercício 7) Deque de inteiros e funções sobre ele
- Em
main()
, preencher umstd::deque<int> d{ … }
. - Criar quatro funções:
int findMax(const std::deque<int>& d)
: faz um scan, guarda o maior visto.int findMin(const std::deque<int>& d)
: igual, mas acha o menor.int countMax(const std::deque<int>& d)
: primeiro chamafindMax
, depois faz outro scan contando quantas vezes o valor aparece.int countMin(const std::deque<int>& d)
: idem para o mínimo.
Teoria: deque funciona como vetor duplo. Iterar é O(n). Guardamos valor e incrementamos contador quando bate.
Passo 4
(Exercício 8) Mesclando duas listas ordenadas
- Declarar template
<typename T> std::list<T> mergeLists(const std::list<T>& a, const std::list<T>& b)
. - Criar duas iterators
itA = a.begin()
,itB = b.begin()
. - Enquanto
itA != a.end()
eitB != b.end()
, comparar*itA
e*itB
:- Se
*itA < *itB
,push_back(*itA++)
na lista resultado. - Senão,
push_back(*itB++)
.
- Se
- Quando um acabar, joga o resto do outro na lista resultado.
- Retorna a lista mesclada, sem alterar
a
eb
.
Isso é o famoso algoritmo de merge de listas – percorre cada lista uma única vez, O(n+m).
Resposta
#include <iostream>
#include <vector>
#include <deque>
#include <list>
// Exercício 6: função genérica para vetor ordenado
template<typename T>
bool isSorted(const std::vector<T>& v) {
if (v.size() < 2) return true;
for (size_t i = 1; i < v.size(); ++i) {
if (v[i] < v[i-1])
return false;
}
return true;
}
// Exercício 7: funções para deque<int>
int findMax(const std::deque<int>& d) {
if (d.empty()) throw std::runtime_error("Deque vazio");
int m = d.front();
for (int x : d)
if (x > m) m = x;
return m;
}
int findMin(const std::deque<int>& d) {
if (d.empty()) throw std::runtime_error("Deque vazio");
int m = d.front();
for (int x : d)
if (x < m) m = x;
return m;
}
int countMax(const std::deque<int>& d) {
int m = findMax(d), cnt = 0;
for (int x : d)
if (x == m) ++cnt;
return cnt;
}
int countMin(const std::deque<int>& d) {
int m = findMin(d), cnt = 0;
for (int x : d)
if (x == m) ++cnt;
return cnt;
}
// Exercício 8: merge de duas listas ordenadas
template<typename T>
std::list<T> mergeLists(const std::list<T>& a, const std::list<T>& b) {
std::list<T> result;
auto itA = a.begin(), itB = b.begin();
while (itA != a.end() && itB != b.end()) {
if (*itA < *itB) {
result.push_back(*itA);
++itA;
} else {
result.push_back(*itB);
++itB;
}
}
// joga o resto
while (itA != a.end()) result.push_back(*itA++);
while (itB != b.end()) result.push_back(*itB++);
return result;
}
int main() {
// Testando exercício 6
std::vector<int> vi {1, 2, 3, 3, 5};
std::vector<float> vf {1.0f, 0.5f, 2.3f};
std::vector<char> vc {'a', 'b', 'c'};
std::cout << std::boolalpha;
std::cout << "vi ordenado? " << isSorted(vi) << "\n";
std::cout << "vf ordenado? " << isSorted(vf) << "\n";
std::cout << "vc ordenado? " << isSorted(vc) << "\n\n";
// Exercício 7
std::deque<int> dq {5, 3, 9, 3, 9, 1, 9};
std::cout << "Maior: " << findMax(dq) << "\n";
std::cout << "Menor: " << findMin(dq) << "\n";
std::cout << "Qtde máximo: " << countMax(dq) << "\n";
std::cout << "Qtde mínimo: " << countMin(dq) << "\n\n";
// Exercício 8
std::list<int> la {1, 4, 6, 8};
std::list<int> lb {2, 3, 5, 7, 9};
std::list<int> lm = mergeLists(la, lb);
std::cout << "Merge: ";
for (int x : lm) std::cout << x << ' ';
std::cout << '\n';
return 0;
}