Actualizacion de tablas de frecuencias (2) (Ex.Pract. PRO2 Q2-2018-2019 T2) X57485

1. El peso de este ejercicio en la nota del exámen de la práctica es de un 66.66% (2/3 de la nota).
2. Nota manual: 50%, nota automática: 50%
3. El peso de todos los juegos de pruebas en el cálculo de la nota automática es idéntico (público: 2.5/10, privados: 2.5/10 cada uno).

Dadas dos tablas de frecuencias f1=F₁ y f2=F₂, queremos una función que actualiza la primera con los datos de la segunda. Las tablas estarán representadas por map<string,int>. Todas las frecuencias en f1 y f2 son estrictamente positivas.

Como resultado de la actualización la tabla f1 contendrá:

• Si ⟨ s,f⟩ es un par de la tabla F₁ y f2 no contiene ningún par con clave igual a s, entonces ⟨ s,f⟩ está en la tabla f1 final.
• Si ⟨ s,f⟩ es un par de la tabla f2 y F₁ no contiene ningún par con clave igual a s, entonces ⟨ s,f⟩ está en la tabla f1 final.
• Si ⟨ s,f⟩ es un par de la tabla F₁ y ⟨ s,f′⟩ es un par de la tabla f2 entonces ⟨ s,max(f,f′)⟩ está en la tabla f1 final.

Por ejemplo si las tablas f1 y f2 son las mostradas aquí:

entonces después de la actualización f1 será

Implementa la siguiente función

// Pre: y Post: ver la descripción del enunciado
void actualiza_tabla_frec(map<string,int>& f1, const map<string,int>& f2);

Escribe un pequeño programa que lea una tabla de frecuencias f1, y a continuación, entra en un bucle en el que en cada iteración se lee una tabla de frecuencias f2, se actualiza f1 con f2 y se imprime la tabla f1.

N.B. De cara a obtener una solución lo más eficiente posible, tened en cuenta lo siguiente:

1. Recorrer un map mediante iteradores de principio a fin toma tiempo proporcional al tamaño del map—suponiendo que en cada iteración del recoorido se invierte tiempo constante.
2. La clase map tiene un método insert(iterator,par-clave-valor) para dar una “pista” sobre dónde debe insertarse el nuevo elemento. Si insertamos N elementos en orden creciente de clave usando m.insert(m.end(), x) el coste será proporcional a N; si se utilizase el método normal m.insert(x) el coste será mucho mayor, proporcional a Nlog₂ N.

Entrada Cada tabla de frecuencias se representará en la entrada mediante una secuencia que comienza con un entero k≥ 0 seguida de una secuencia de k pares ⟨ s, f⟩ describiendo los pares que constituyen la tabla.

La entrada comienza con la subsecuencia que representa a la tabla f1. A continuación viene una serie de tablas de frecuencia (cada una representada por una secuencia con el formato que hemos descrito arriba). La última tabla de frecuencias de la serie es un tabla vacía (k = 0).

Salida Para cada tabla de frecuencias f2 de la serie, excepto la última tabla vacía que marca el final de la serie, se actualiza la tabla f1 con los datos de f2 y se imprime la tabla f1 actualizada. Una tabla de frecuencias se imprime siguiendo el mismo convenio que para la entrada: primero un entero k con su tamaño y a continuación una secuencia de los k pares ⟨ s, f⟩ que contiene la tabla (separamos las componentes s y f de cada par mediante un espacio en blanco), pero adicionalmente los pares han de estar en orden creciente de clave (ordenados por la s). Después de imprimir la tabla f1 tras cada actualización se imprime un salto de línea.

Observación Utilizad la plantilla (plantilla-solucion.cc_txt) que os damos con los ficheros públicos (icono del gatito) para preparar la solución.