Llistes amb accés i modificació per índex X18544

En aquest exercici, heu d’implementar un programa que simula una estructura de dades que és una mena de barreja entre llistes d’enters i vectors d’enters. Per una banda, hem de poder afegir elements pel principi i pel final de la llista. Per l’altra, hem de poder accedir i modificar indexadament els elements de la llista.

Aquest és un exemple d’entrada del programa:

v.push_back( 5 );
cout<<v[ 0 ];
v.push_front( 8 );
cout<<v[ 0 ];
cout<<v[ 1 ];
v.push_back( 9 );
cout<<v[ 0 ];
cout<<v[ 1 ];
cout<<v[ 2 ];
v[ 1 ]= 3 ;
cout<<v[ 0 ];
cout<<v[ 1 ];
cout<<v[ 2 ];

La sortida del programa amb aquesta entrada hauria de ser:

5
8
5
8
5
9
8
3
9

Com veieu a l’exemple d’entrada anterior, hi han espais en blanc envoltant cada número per a facilitar la lectura de l’entrada. Podeu llegir i tractar les comandes així:

...
int main()
{
    ...
 string command;
 while (cin >> command) {
     if (command == "v.push_back(") {
         int number;
         cin >> number;
         string ending;
         cin >> ending; // Això consumeix el ");"
         ...
     } else if (command == ...
     ...
 }
}

Us recomanem que comenceu implementant una solució senzilla que superi els jocs de proves públics, obtenint així la meitat de la nota, i que mireu d’optimitzar-la més tard, si teniu temps.

Podeu utilitzar qualsevol de les estructures de dades presentades al curs (vector, stack, queue, list, set, map), i de la forma que considereu oportuna. Fixeu-vos, però, que enfocaments diferents donaran lloc a programes que seran més eficients o menys eficients, i d’això dependrà que pogueu superar només els jocs de proves públics o tots els jocs de proves, cosa que afectarà a la nota.

Existeixen enfocaments que aconsegueixen que totes les operacions tinguin cost constant. Tot i així, de cara a superar tots els jocs de proves, n’hi ha prou amb que aconseguiu que totes les operacions tinguin cost logarítmic com a molt.

Entrada

L’entrada del programa és una seqüència de línies, a on cada línia conté una comanda que pot ser d’un dels següents tipus:

v.push_front( NUMBER );
v.push_back( NUMBER );
cout<<v[ INDEX ];
v[ INDEX ]= NUMBER ;

A on INDEX és un natural entre 0 i el nombre d’elements afegits fins al moment menys 1, i NUMBER és un enter qualsevol.

Sortida

Per a cada instrucció cout<<v[ INDEX ]; el programa escriurà el que suposadament conté la llista a la posició indexada per INDEX en aquell moment.

Observació

Avaluació sobre 10 punts:

• Solució lenta: 5 punts.
• solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost O(nlog(n)) i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.