1

¿Como hago para imprimir todos los elementos de una lista (std::list) de pairs en c++, que contengan max_elemnt repetidos?

list<pair<int, int>> l;
l.push_back ( std::make_pair ( 1, 90 ) );
l.push_back ( std::make_pair ( 2, 90 ) );
l.push_back ( std::make_pair ( 3, 75 ) );
l.push_back ( std::make_pair ( 4, 40 ) );
l.push_back ( std::make_pair ( 5, 90 ) );

Es decir... si tengo esa lista de arriba, cómo hago para que la salida sea:

Alumno 1: 90.
Alumno 2: 90.
Alumno 5: 90.

...Mostrando no solo el mayor elemento, si no que el mayor elemento y todos los repetidos. No se si me expreso bien.

Tengo entendido que max_element tan solo me retorna el primer elemento de la lista. Si tengo una lista con los elementos {3,7,9,5,6,4,9}, y como podemos ver hay dos repetidos, si hago algo como:

int myints[] = {3,7,9,5,6,4,9};
std::cout << *std::max_element(myints,myints+7) << '\n';

La salida seria:

9

Necesito que la salida sea todos los números repetidos, o sea como hay 2, pues que imprima todos los números mayores repetidos, pero usando el pair que vemos en el primer ejemplo.

¿Existe alguna utilidad que muestre todos los repetidos?

10
  • ¿por qué la restricción en el uso de bucles? No hay forma de resolverlo sin usar un bucle. Aunque no lo escribas tu, si existe una rutina que te devuelva lo que buscas, la rutina, internamente, de una forma u otra utilizará bucles.
    – jachguate
    el 2 sep. 2016 a las 13:22
  • No me importa si internamente haga con bucles. El caso es que como existe max_element que retorna el mayor valor cómodamente, puede exista algo parecido que retorne todos los valores y no solo uno. Ya sabes... por el del aprovechamiento. =) Me parece un absurdo que tengamos que programar algo para imprimir valores repetidos y que sin embargo tengamos una función para obtener el mayor valor. ¿No crees?
    – vangodp
    el 2 sep. 2016 a las 13:31
  • @vangodp No, no es absurdo. La función max_element() es sólo para sacar el mayor valor, no importa cuantas veces se repita. Un aproximado de por qué los devs no hicieron esa comodidad que buscas, es que hay algoritmos para uniones, intersecciones que varian en rendimiento, dependiendo de la plataforma. Prácticamente, estas pidiendo una nueva lista, que haga push_back a un par que tenga el mismo valor, cosa que es posible pero complicado cuando hablamos de genéricos en C++...
    – NaCl
    el 2 sep. 2016 a las 14:02
  • @vangodp puedes transformar tu lista en un heap con make_heap y luego sacar los elementos hasta encontrar uno más chico que el primer elemento del heap. Entiendo que deberías armar un función de compare para poder comparar sólo una parte del par. Otra opción, armas un hash donde la clave son las notas y mientras lo armas, guardas la nota más alta. Luego buscas en el hash los valores asociados a la nota más alta.
    – El Asiduo
    el 3 sep. 2016 a las 4:35
  • @El Asiduo Gracias por la sugerencia man, voy a dar una mirada en lo que sugieres para ver que onda, pero buscaba algo simples, al parecer no hay nada simples para ese caso. >_< ¡Gracias de todos modos!
    – vangodp
    el 3 sep. 2016 a las 4:39

2 respuestas 2

3

Una forma, que si pones en un .h, podría ser "la utilidad" :)

inline
void mostrarMayores(std::list<std::pair<int,int>> l)
// recibe una copia para no modificar la lista original
{
    auto comp = [](const std::pair<int,int>& a, const std::pair<int,int>& b) {
        return a.second > b.second;
    };

    auto as_str = [](const std::pair<int, int>& p) {
        std::ostringstream ss;
        ss << "Alumno " << p.first << ": " << p.second;
        return ss.str();
    };

    l.sort(comp);

    std::transform(l.begin(), std::upper_bound(l.begin(), l.end(), *l.begin(), comp),
                   std::ostream_iterator< std::string >( std::cout, "\n" ),
                   as_str);
}
3
  • Me parece que sí... esa va ser la única forma, implementarlo yo mismo =(. Gracias man.
    – vangodp
    el 3 sep. 2016 a las 3:50
  • @vangodp Bueno, esta es una forma de implementarlo. No esperabas que el lenguaje tuviera algún algoritmo mágico std::solve_what_i_am_thinking(), ¿verdad?
    – user4717
    el 3 sep. 2016 a las 3:58
  • Púes lo tiene para muchas cosas. ¿Quieres que te ponga ejemplos?>_<
    – vangodp
    el 3 sep. 2016 a las 4:34
0

No conozco ninguna utilidad que haga directamente muestre todos los repetidos.

Pero sí es posible hacerlo sin bucles. Usando recursividad.

Primero obtendremos el máximo con una función dameMax.

#include <cstdlib>
#include <list>
#include<stdexcept>
#include<iostream>
using namespace std;

int dameMaxRecursivo( int max, std::list<pair<int, int>>::const_iterator it,
                      std::list<pair<int,int>>::const_iterator end )
{
    if ( it==end )
        return max;
    if ( it->second>max )
        return dameMaxRecursivo( it->second, ++it, end );
    else
        return dameMaxRecursivo( max, ++it, end );
}

int dameMax( const std::list<pair<int, int>>& lista )
{
    if ( lista.size()==0 )
        throw invalid_argument("dameMax requiere una lista no vacia.");
    auto it = lista.begin();
    int max = it->second;
    ++it;
    return dameMaxRecursivo( max, it, lista.end() );
}

dameMax comprueba que la lista no esté vacía y llama a la función recursiva pasando el máximo hasta ahora (el valor del primer elemento de la lista) y un iterador al siguiente elemento. También pasa iterador al final para que la función recursiva sepa cuando parar.

Primero la función recursiva comprueba si ha llegado al final. Si no compara el máximo hasta ahora con el elemento en el iterador recibido. Si es mayor se llama a si misma con este nuevo valor que es mayor y con el iterador apuntando al siguiente elemento, si no es mayor se llama a si misma con el máximo hasta ahora y también con el iterador apuntando al siguiente elemento.

Para imprimirlos sin bucles usamos la misma técnica:

void mostarMayoresRecursivo( int max, std::list<pair<int, 
                             int>>::const_iterator it,
                             std::list<pair<int,int>>::const_iterator end)
{
    if ( it==end ) 
        return;
    if ( it->second == max )
      std::cout<<"Alumno " << it->first << ":" << it->second << std::endl;
    mostarMayoresRecursivo( max, ++it, end );
}

void mostrarMayores( const std::list<pair<int, int>>& lista )
{
    if ( lista.size()==0 )
        return;
    int max = dameMax( lista );
    mostarMayoresRecursivo( max, lista.begin(), lista.end() );
}

Un lector avezado podrá observar que todavía hay bucles. Es muy posible que el operador << para streams esté implementado con algún bucle. Por supuesto esto también es posible implementarlo sin bucles usando la misma técnica.
La recursión utilizada, que es recursión de cola, puede ser optimizada por algunos compiladores a un bucle. Pero también es posible obligar al compilador a no hacerlo.
Y es posible que las llamadas a sistema para imprimir en pantalla usen un mecanismo de buffer y acaben imprimiendo en un bucle pese a que les pases los caracteres de uno en uno sin bucles. Pero esto ya es algo externo a tu programa.

Que se pueda hacer así no significa que sea recomendable. Hay casos en que sí es recomendable, es una técnica habitual en programación funcional.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.