Aprendre a programar 17 - Implementació de classes i Makefile

Anem ja per la sessió 8 de laboratori, i cada cop queda menys. Aquesta sessió la dedicarem a implementar classes. Al lab programareu rentadores i cubetes, però us donen ja les capçaleres implementades, i a mi això no m'agrada. Per tant, jo explicaré des de 0, com fer capçaleres, i després com fer el seu codi.

Capçaleres

Aquest és el fitxer .hh, amb les declaracions de la classe. Només conté capçaleres, perquè el que fa la directiva include és substituir-se pel que hi ha al fitxer indicat. Això es fa al moment de compilar, de manera que si tinguéssim el codi al .hh, ens carregaríem la modularitat

Una mica de preprocessador

Primer de tot, cal explicar com funciona la directiva include. En C i C++, abans de compilar es fa una passada del preprocessador. Aquest té unes quantes directives. Nosaltres fins ara només hem utilitzat aquesta, include. El que fa és substituir-se pel contingut del fitxer que indiquem. Així, quan incloem vector, el que fem és buscar aquest fitxer, agafar les seves declaracions, i posar-les allà. 

Un problema que ens pot passar és que incloguem dos cops el mateix fitxer. Per exemple, si tenim un programa que utilitza vector i Cjt_estudiants, Cjt_estudiants inclou també vector, estaríem incloent dos cops les mateixes declaracions. I això dóna error de compilació. Per evitar aquest problema, fem el següent
#ifndef CLASSE_HH

#define CLASSE_HH

totes les capçaleres

#endif

Podríem parlar molt del preprocessador, però aquí només ens cal parlar de dues directives. La primera és ifndef. Aquesta és, bàsicament, un condicional. Si no està definida la macro CLASSE_HH, s'avalua el que hi ha dins, fins arribar al seu corresponent endif. Dins d'això, com que el que ens interessa és que tota la part d'aquest codi es compili només un cop, hem de definir CLASSE_HH. Així, a la propera inclusió, estarà ja definit, i no entrarem aquí.
A partir d'aquí, toca escriure tot el contingut d'aquesta classe

Inclusions

Ara toca incloure tot el que necessitem per aquesta classe. Per exemple, si volem utilitzar set, list i iostream, faríem

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

#endif

Comencem amb la classe

Ara toca posar la declaració de la classe. Aquesta es declara igual que una struct, de manera que ens quedaria

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

class Hola {

};

#endif

Atributs privats

Una classe tindrà sempre uns atributs, que jo els prefereixo com a privats. És on tindrem tot desat. Una cosa així:

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

class Hola {

private: //Optatiu, no cal posar-ho

    int a, b;

    set<int> c;

    list<double> d;

};

#endif

Allà on posa private, no és obligatori. Per defecte, en una classe, tot és privat fins que s'indica el contrari. No obstant, està bé posar-ho per claredat. 

Si volem posar funcions que ens ajudin a fer alguna cosa, les podem posar aquí. Aquestes no seran accessibles directament des de fora de la classe, sinó que només s'hi pot accedir des d'altres mètodes de la classe

Funcions públiques

Aquestes són les funcions que interactuen amb l'objecte. Les podem dividir en les categories següents:

Constructores:

Són les que creen una nova instància de la classe. Per això no retornen res, però tampoc són void. Simplement tenen el nom de la classe i, opcionalment, paràmetres

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

class Hola {

private: //Optatiu, no cal posar-ho

    int a, b;

    set<int> c;

    list<double> d;

public:

    //Constructores

    Hola();

    Hola(int a, int b);

    Hola(const Hola& h);

};

#endif

En el meu exemple, he fet que hi ha una que crea una instància de la classe buida, una altra que té els dos enters, i una altra que fa una còpia del paràmetre

Destructores:

Normalment només n'hi ha una, que destrueix l'objecte quan sortim del seu àmbit. En les classes que fem de moment, no ens cal fer res, ja que tot el que utilitzem ja es destrueix sol (tant els tipus bàsics, com les classes de la STL, ja tenen programades les funcions destructores). No obstant, quan fem classes amb punters, allà sí que haurem de programar la destructora. Aquí la posem buida, quedant així:

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

class Hola {

private: //Optatiu, no cal posar-ho

    int a, b;

    set<int> c;

    list<double> d;

public:

    //Constructores

    Hola();

    Hola(int a, int b);

    Hola(const Hola& h);

    //Destructora

    ~Hola();

};

#endif

Modificadores

Aquestes serveixen per modificar l'objecte. Normalment són funcions void, ja que només les volem per modificar coses, però per res més. Una cosa així:

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

class Hola {

private: //Optatiu, no cal posar-ho

    int a, b;

    set<int> c;

    list<double> d;

public:

    //Constructores

    Hola();

    Hola(int a, int b);

    Hola(const Hola& h);

    //Destructora

    ~Hola();

    //Modificadores

    /*

     * Pre: Cert

     * Post: La classe conté un nou element, que és n

     */

    void afegir(int n);

    /*

     * Pre: Existeix un element igual a n

     * Post: L'element ha sigut eliminat

     */

    void eliminar(int n);

};

#endif

En algun cas sí que retornen alguna cosa. Per exemple, poden retornar un booleà, que confirmi que s'ha eliminat allò

Normalment posem en un comentari què fa la funció, amb una precondició (que s'ha de complir per executar la funció), una postcondició (que es complirà quan haguem executat la funció), i, opcionalment, un resum del que fa

Consultores

Aquestes consulten coses a l'objecte. Per tant, retornen alguna cosa, sigui un booleà, un enter, o qualsevol cosa que ens pugui interessar. Jo no afegeixo les pre i post, perquè m'estic inventant la classe i no fa res útil, però realment s'haurien de posar

#ifndef CLASSE_HH

#define CLASSE_HH

#include <iostream>

#include <set>

#include <list>

using namespace std;

class Hola {

private: //Optatiu, no cal posar-ho

    int a, b;

    set<int> c;

    list<double> d;

public:

    //Constructores

    Hola();

    Hola(int a, int b);

    Hola(const Hola& h);

    //Destructora

    ~Hola();

    //Modificadores

    /*

     * Pre: Cert

     * Post: La classe conté un nou element, que és n

     */

    void afegir(int n);

    /*

     * Pre: Existeix un element igual a n

     * Post: L'element ha sigut eliminat

     */

    void eliminar(int n);

    //Consultores

    bool hi_es(int n);

    int maxim();

    int minim();

};

#endif

El codi

Ara ens toca implementar totes les funcions que hem fet. La cosa no és gaire difícil. Primer de tot, hem d'incloure les capçaleres que ja hem creat. Podem incloure més coses aquí, però jo personalment, penso que totes les inclusions estan millor al .hh. Igual que l'ordre "using namespace std", penso que també està millor al .hh. Per tant, inicialment tindríem en el codi, una cosa així:

#include "Hola.hh"

Ara toca començar a implementar tot. Començarem per ordre, tot i que això ja és indiferent, aquí l'ordre pot ser el que ens vingui de gust. Per indicar on està la funció, ho fem amb ::. És a dir, posem la classe, els ::, i el nom de la funció. Una cosa així:

#include "Hola.hh"

Hola::Hola() {

    a=b=0,

    c=set<int>();

    d=list<double>();

}

Hola::Hola(int a, int b) {

    this->a=a;

    this->b=b;

    //Aquí inicialitzaríem c i d

}

Hola::Hola(const Hola& h) {

    a=h.a;
    b=h.b;

    c=h.c;

    d=h.d;

}

Aquí estem veient les 3 inicialitzadores. 

La primera, com que està buida, li poso 0 als números, i tant el conjunt com la llista els poso buits. 

La segona, rebem un valor de a i de b, així que els posem. Per distingir entre la a paràmetre, i la a atribut, el que fem és utilitzar el punter this, que és un punter que apunta a la nostra classe. Si fem this->a, la a serà l'atribut, mentre que si posem a a seques, serà el paràmetre (ja que emmascara l'atribut). 

La tercera, el que fa és copiar un objecte. Per tant, copiem tots els membres i ja. Veurem gent que utilitza this per deixar clar quin és l'atribut destí i quin l'atribut de l'objecte copiat. 

Quedaria afegir les altres funcions. Seria fent així amb totes:

void Hola::afegir(int n) {

    //Codi de la implementació

}

Makefile

Ara ens queda el makefile. Aquest és un arxiu que serveix per compilar un projecte, de manera que no haguem d'escriure totes les ordres cada vegada que vulguem compilar. A més, ell mateix s'ocupa de tornar a compilar només els fitxers que calguin, de manera que si tenim 3 classes, i només hem modificat una, la única que tornem a compilar és aquella. 

Per explicar-ho, imaginarem que tenim un projecte format per

-C1

-C2, que inclou C1

-C3, que també inclou C1

-main.cc, que inclou C2 i C3

El fitxer és el següent:

OPCIONS = -D_JUDGE_ -D_GLIBCXX_DEBUG -O2 -Wall -Wextra -Wno-uninitialized -Wno-sign-compare -std=c++0x

all: main.exe

main.exe: main.o C1.o C2.o C3.o

    g++ $OPCIONS -o main.o C1.o C2.o C3.o -o main.exe

main.o: main.cc C1.hh C2.hh C3.hh

    g++ $OPCIONS -c main.cc

C2.o: C2.cc C2.hh C1.o C1.hh

    g++ $OPCIONS -c C2.cc

C3.o: C3.cc C3.hh C1.o C1.hh

    g++ $OPCIONS -c C3.cc

C1.o: C1.cc C1.hh

    g++ $OPCIONS -c C1.cc

clean:

    rm *.o

    rm main.exe

La primera línia fa que, quan posem $OPCIONS, sigui igual a tot el següent. Són els flags que s'utilitzaven a PRO2 quan la vaig fer i, en general, crec que encara són els mateixos més o menys. 

Aleshores, tenim les opcions. All, que es crida per defecte si no diem res, i tota la resta (main.exe, main.o, C2.o, C3.o, C1.o i clean). Cada una té, després dels dos punts, les de les que depèn i, a sota i amb un tabulat (compte, ha d'estar TABULAT, no serveixen espais), la o les instruccions que serveixen per crear-lo. Per exemple, per crear C1.o depenem de que existeixin C1.cc i C1.hh, i ho fem amb g++ $OPCIONS -c C1.cc. Això serveix perquè, quan cridem al make (per defecte anirà a all), mirarem si tenim main.exe actualitzat. Si no el tenim, mirarem què cal per tenir-lo. Necessitem tenir main.o, C1.o, C2.o i C3.o. Els farem en aquest ordre. Podem veure que tant main.exe, com C2.o, com C3.o, necessiten a C1.o. La gràcia del makefile és que només compila si hem modificat algun dels fitxers font, de manera que compilarà només un cop C1.o, i la resta ja sabrà que el tenim creat i actualitzat. 

Tenint aquest fitxer, podem compilar fàcilment qualsevol dels fitxers, compilar-ho tot a l'hora, netejar quan haguem acabat. 

$make

Aquesta compila tot el projecte

$make C1.o

Aquesta ens crea C1.o

$make main.o

Aquesta ens crea main.o, i tots els fitxers necessaris per crear-lo

$make clean

Aquesta elimina els fitxers .o, i main.exe

Aprendre a programar 16 - Sets i maps

Un cop arribats a aquest punt, ja tenim una estructura de dades que permet l'accés aleatori en temps constant a costa de tenir insercions i eliminacions en cost lineal, i una altra que permet insercions i eliminacions en cost constant, a costa de tenir l'accés aleatori en temps lineal. Ara imaginem, però, que volem llegir uns quants nombres, i tenir emmagatzemat quins hem llegit ja. Com ho podríem fer?

Vector de booleans?

És una opció. Un vector de booleans, inicialment a false, que quan apareix un element posi la seva posició a true. El problema és que tindrem un vector enorme, que probablement no aprofitarem. Imaginem, si no, que volem emmagatzemar tots els enters positius existents. 

Vector ordenat amb els números?

Una altra opció. Inicialment és buit. Quan apareix un número, l'insertem a la posició on hauria d'anar (cost lineal). Per localitzar el número, fem una cerca dicotòmica, temps logarítmic. 

Llista ordenada amb els números?

Una altra opció. Insertar té cost constant un cop tenim la posició, però trobar-la té cost lineal (ja que no hi podem fer una cerca dicotòmica). Per tant, té cost lineal tant la cerca com la inserció

Llista no ordenada amb els números?

Insertar té cost constant (insertem on vulguem i au). La cerca té cost lineal, ja que hem de recórrer tota la llista. El problema és que si volem evitar repeticions, hem de fer que abans d'insertar busqui si ja hi és o no, per tant, tindríem cost lineal

Nota: insertar al final d'un vector en general és més ràpid que fer-ho en una llista, tot i que ara no ve al cas la raó

Sembla que de moment no hem estudiat cap estructura de dades que ens permeti representar un conjunt matemàtic de manera eficient. Cap? No! En tenim una de molt bona (que te la pots saltar si només t'interessa aprovar l'assignatura, anant directament al set)

Arbres binaris de cerca

Un arbre binari de cerca és un arbre definit de manera que els elements del fill esquerre són menors o iguals que l'arrel, i els elements del fill dret són més grans o iguals. Per tant, per trobar un element, seria una cosa així:

bool cerca (Arbre<int>& a, int x) {

    if (a.es_buit()) return false;

    if (a.arrel()==x) return true;

    int ar=a.arrel();

    Arbre<int> fe,fd;

    a.fills(fe,fd);

    if (ar<x) {

        if (cerca(fd,x)) {

            a.plantar(ar,fe,fd);

            return true;

        }

    }

    else {

        if (cerca(fe,x)) {

            a.plantar(ar,fe,fd);

            return true;

        }

    }

    a.plantar(ar,fe,fd);

    return false;

}

Mirem el node actual. Si hi és, retornem cert. Si no, mirem si hauria d'estar a la dreta o a l'esquerra, i mirem allà. Això ens permet mirar només un node per nivell. La gràcia d'això és que, al anar duplicant la quantitat de nodes a cada nivell, la quantitat de nivells és logarítmicament proporcional a la quantitat d'elements (un arbre complet de 255 elements té 8 nivells, un de 511 en té 9...)

Al final, ens trobem amb que cercar un element té cost logarítmic, ja que, com a molt, haurem de visitar un cop cada nivell. Per tant, la cerca té cost logarítmic. 

Si volem insertar, primer hem de decidir si acceptem repeticions. En el que volem ara, que és emmagatzemar si un número ja ha aparegut o encara no, jo no n'acceptaré. 

//Pre: cert

//Post: x està a l'arbre. Si ja hi era, retorna false

// Si l'hem insertat, retorna true

bool insertar (Arbre<int>& a, int x) {

    if (a.es_buit()) {

        Arbre<int> fe,fd;

        a.plantar(x,fe,fd);

        return true;

    }

    if (a.arrel()==x) return false;

    Arbre<int> fe,fd;

    int ar=a.arrel();

    a.fills(fe,fd);

    bool res;

    if (x<ar) res=insertar(fe,x);

    else res=insertar(fd,x);

    a.plantar(ar,fe,fd);

    return res;

}

És a dir, fem la nostra cerca, i si el trobem, vol dir que ja hem acabat. Si ens acabem l'arbre i no l'hem trobat, l'insertem. Insertar té temps constant, ja que només crea el nou node i l'enganxa. Per tant, fer la inserció té temps logarítmic, ja que hem de buscar on insertem, i fer-ho. 

Amb això implementarem la següent estructura de dades. 

Set

Un set és, en essència, un conjunt matemàtic. Emmagatzema les dades ordenades, sense repeticions, permetent-nos afegir, eliminar i consultar eficientment. Concretament, té les següents funcions:

begin i end:

Retornen els respectius iteradors

empty i size:

El que podríem esperar

insert:

Inserta l'element. La seva capçalera és:
pair<iterator,bool> insert (const value_type& val);

La posició on s'insertarà la busca automàticament. El retorn són una parella, on el primer element apunta a la posició on tenim el valor, i el segon ens indica si l'hem insertat o no.

La funció té temps logarítmic

També tenim una versió que rep un iterador que fa de pista. Aquest apunta a un element proper, i ens serveix per insertar l'element més ràpid. 

erase:

Elimina l'element. Hi ha tres versions, que són:

iterator  erase (const_iterator position);

size_type erase (const value_type& val);

iterator  erase (const_iterator first, const_iterator last);

La primera versió rep un iterador que apunta a l'element que volem eliminar. Té, per tant, temps constant amortitzat (ja tenim la posició a eliminar, només hem d'eliminar-lo). Retorna un iterador que apunta al següent element

La segona versió rep el valor que volem eliminar. Té, per tant, temps logarítmic, ja que l'hem de buscar. Retorna la quantitat d'elements eliminats (és a dir, o 0 o 1). 

La tercera versió rep dos iteradors, i elimina els elements que hi ha al rang. Té cost lineal respecte a la quantitat d'elements

find:

Retorna un iterador que apunta a l'element (si hi és), o a l'end (si no hi és). Cost logarítmic

Un exercici

Podem fer un exercici, ja que, de fet, en el Jutge és el que hi ha. El problema X83904. 

void llegir_set(set<string>& S) {

    string s;

    while (cin >>s and s!=".") S.insert(s);

}

void actualitzar_totes(set<string>& totes, const set<string>& S) {

    set<string>::iterator it=totes.begin();

    while (it!=totes.end()) {

        if (S.find(*it)!=S.end()) ++it;

        else it=totes.erase(it);

    }

}

void actualitzar_cap(set<string> &cap, const set<string> &S) {

    set<string>::iterator it=cap.begin();

    while (it!=cap.end()) {

        if (S.find(*it)!=S.end()) {

            it=cap.erase(it);

        }

        else ++it;

    }

}

void mostrar_set(const set<string>& S) {

    for (set<string>::const_iterator it=S.begin();it!=S.end();++it) cout <<' '<<*it;

    cout <<endl;

}

int main(){

    set<string> cap_activitat;

    llegir_set(cap_activitat);

    int n;

    cin >>n;

    set<string> totes_activitats(cap_activitat);

    for (int i=0;i<n;++i) {

        set<string> actual;

        llegir_set(actual);

        actualitzar_totes(totes_activitats, actual);

        actualitzar_cap(cap_activitat,actual);

    }

    cout <<"Totes les activitats:";

    mostrar_set(totes_activitats);

    cout <<"Cap activitat:";

    mostrar_set(cap_activitat);

}

És a dir, llegim tots els elements, i tenim dues còpies, ja que inicialment, els que fan totes les activitats són els mateixos que no en fan cap. Aleshores, anem llegint els que fan cada activitat. Fem una funció que actualitzi totes, de manera que si un no apareix, l'eliminem, i una altra que actualitzi cap, de manera que si apareix un, l'eliminem. I ja està

Map:

Ara presento una estructura molt similar al set. Aquest és el map, o diccionari. És com un set, però amb un valor associat. És a dir, té una sèrie de claus, i a cada clau un valor. Està ordenat per les claus, i les que no poden repetir-se són les claus. 

Les funcions que té són en essència les mateixes que el set, però canviant l'element per una parella. És a dir, l'insert, enlloc de rebre un element, rep una parella. La desreferència de l'iterador igual, ens dóna una parella

A més d'això, tenim l'operador []. Aquest el que fa és, si no hi ha l'element, el crea, i si hi és, el modifica. I no, no és un embarbussament. La diferència fonamental és:
map<int,int> m, m2;
m.insert(pair<int,int>(3,3));
m2.insert(pair<int,int>(3,3));
...
m[3]=4;
m2.insert(pair<int,int>(3,4));

Si miréssim com queden, veuríem que hem modificat m, mentre que m2 queda igual. Aquesta és la diferència fonamental

Truc amb els iteradors

Ara els iteradors fan referència a una parella, enlloc de fer-la a un sol element. Per tant, si volem accedir al segon de la parella (per exemple, per incrementar), el que faríem intuitivament seria

++(*it).second;

No obstant, tenim una altra eina, que és l'operador ->. Aquest el que fa és que, quan estem apuntant a una estructura, donar-nos aquell element en concret. Per exemple

++it->second;

Ens dóna el segon element. Això és heretat dels punters, però és molt pràctic

Un exercici

Podem fer l'exercici X34352 del jutge. 

int main() {

    map<string,int> m;

    char c;

    string s;

    while(cin >>c>>s) {

        if (c=='a') {

            map<string,int>::iterator it=m.find(s);

            if (it!=m.end()) ++it->second;

            else m[s]=1;

        }

        else {

            map<string,int>::iterator it=m.find(s);

            if (it!=m.end()) cout<<it->second<<endl;

            else cout<<0<<endl;

        }

    }

}

Fem un map que tingui un string com a clau, i un enter com a valor. Anem llegint l'entrada, si hem d'afegir, mirem si hi és o no. Si ja hi és, incrementem el valor. Si no hi és, l'afegim i li posem un 1. Si volem mostrar, mirem si hi és. Si hi és, mostrem la freqüència, i si no hi és, un 0. 

Vectors de mida variable

Això ho poso aquí perquè, malgrat que no té a veure amb els sets ni amb els maps, es fa a la mateixa sessió. A més n'he parlat una mica al principi, així que ho poso 

Mai us heu preguntat com funciona internament un vector? Porteu des de PRO1 utilitzant-los. Normalment ens diuen que reserva espai a posicions de memòria seguides, i realment no és fals. Però no és gaire precís tampoc. 

Un vector, internament, conté una sèrie d'atributs, tals com la mida actual, o un punter que apunta al primer element. La memòria es reserva utilitzant l'operador new[], que ara no cal explicar què fa.

Quan declarem un vector de mida n, el que fa és reservar espai per exactament n elements. Ara, què passa si ens adonem de que necessitem més espai? O si no sabem la mida que necessitarem. Existeix una funció, a la que molts professors de PRO1 tenen mania, que és el push_back. Aquest, el que fa és incrementar en 1 la mida del vector, i posar allà l'element que volem posar

Espera un moment, no havies dit que reservàvem exactament la mida del vector? Això com es menja?

Fàcil.

Reservar més espai, i moure'ns allà

Si tenim espai per n elements, i volem tenir-ne n+1, el que hem de fer és reservar més espai, i desplaçar el vector cap allà. El problema que ens trobem, aleshores, és que desplaçar un vector té cost lineal respecte la quantitat d'elements que desplacem. Però aleshores, la solució és fàcil. Reservar més espai del necessari. Enlloc de reservar espai per n+1 elements, reservem només per potències de 2. Aleshores, si tenim un codi com el següent:

vector<int> v;

for(int i=0;i<n;++i) v.push_back(i);

Imaginem que n=63. Aleshores, faríem:

-Reservem espai per 1 element. Posem el primer

-Reservem espai per 2 elements. Posem el segon

-Reservem espai per 4 elements. Posem el tercer

-Posem el quart

-Reservem espai per 8 elements. Posem el cinquè

-Posem el sisè

-Posem el setè

-Posem el vuitè

-Reservem espai per 16 elements. Posem el novè

...

-Reservem espai per 32 elements. Posem el dissetè

...

-Posem el 63è

Podríem calcular el cost d'això. En molts casos és constant, i en alguns lineal. No obstant, l'important és saber quin cost en tindrà quan en fem molts. Si en fem molts, fent la mitjana, veiem que és cost constant amortitzat. No creix el cost en funció de la quantitat d'elements. Tinguem 8 elements o 800.000, el cost en mitjana serà el mateix

Oju (que vol dir ull)

Als professors no els agrada que utilitzem push_back sense una justificació. Per exemple, un dia vaig llegir un codi com el següent, en una pàgina que teòricament ensenyava a programar

En els vectors

int n;

vector<int> v;

cin >>n;

int a;

for (int i=0;i<n;++i) {

    cin >>a;

    v.push_back(a);

}

Utilitzar push_back aquí no té cap justificació lògica. Sabem quants elements tindrem, i sabem que reservar l'espai inicialment és més eficient que anar modificant la mida. Per tant, fer això restaria de nota manual. 

piles/cues

bool ben_parentitzat(const string& s) {

    vector<char> v;

    for (int i=0;i<int(s.length());++i) {

        if (s[i]=='(' or s[i]=='[' or s[i]=='{') {

            v.push_back(s[i]);

        }

        else {

    if (v.empty()) return false;

            if (s[i]==')' and v.back()!='(') return false;

            else if (s[i]==']' and v.back()!='[') return false; 

            else if (s[i]=='}' and v.back()!='{') return false;

            v.pop_back();

        }

    }

    return v.empty();

}

En aquest cas, estem utilitzant un vector enlloc d'una pila. No utilitzem res del que permet el vector. Ni l'accés aleatori, ni el recorrem... Només accedim a l'últim element, i això ja ens ho fa una pila (de manera més eficient)

Nota: una pila de la STL es pot implementar internament amb una deque o un vector (per defecte, una deque). Una deque s'implementa amb un vector de punters, de manera que realment, utilitzant una pila, estem utilitzant un vector. No obstant, es pot fer la prova per veure què va més ràpid, si fer push_back en un vector, o fer push en una pila. No l'he fet, però m'apostaria alguna cosa a que és més ràpid fer-ho en una pila

llistes

Si necessitem insertar només al final, o ens és indiferent la posició, jo realment utilitzaria un vector. Contràriament al que pot semblar, és més eficient fer push_back en un vector, que en una llista

Per altra banda, si vols tenir l'estructura ordenada, potser també surt més a compte utilitzar el vector. Insertar tindrà cost lineal, perquè haurem de desplaçar els elements del vector per fer espai, però amb la llista hauríem de buscar la posició també en temps lineal (a no ser que tinguem ja la posició). El que ens aporta aquí utilitzar el vector, és que hi podem fer una cerca dicotòmica

Aprendre a programar 15 - Llistes i arbres binaris

Ja tenim 3 estructures de dades. Us semblen moltes? HA! No heu vist res encara. N'hi ha moltes més encara. La llista completa seria: Array, deque, forward_list, list, map, multimap, multiset, priority_queue, queue, set, stack, unordered_map, unordered_multimap, unordered_set, unordered_multiset, vector i vector<bool>. Per sort per nosaltres, només utilitzarem list, map, queue, set, stack, vector i vector<bool>. I ara quina deu tocar?

Llistes

Ara veiem les llistes. Fins ara hem vist que en una pila podem insertar només a dalt, i en una cua només al final. En un vector també podem insertar al final en temps constant amortitzat. Ara, què passa si necessitem insertar molts cops i que no sigui al final? Amb el vector, hauríem de desplaçar els elements per fer espai pel nou, cosa que té temps lineal. Massa temps, si n'hem de fer moltes. Per això apareixen les llistes

Insercions i eliminacions en temps constant

Una llista té una implementació interna que permet insertar i eliminar en temps constant, a la posició que sigui. Principi, final, o qualsevol, totes en temps constant. Tingui un element o un milió, trigarem similar en insertar un element. Podem veure com funcionen

Iteradors

Un iterador és una classe que utilitzem per recórrer una estructura de dades. No és una cosa nova del tot, ja que els vectors també en tenien, però en els vectors podíem obviar la seva existència i recorre'ls per l'índex. Aquí no podem, ja que els elements d'una llista no s'emmagatzemen en posicions contínues. Així que anem pas a pas

Què és un iterador?

Un iterador és una classe que fa referència a un element d'una estructura de dades i, en la majoria de casos, s'utilitza per recórrer aquesta estructura

Com es declara?

Si volem declarar un iterador d'una llista d'enters, seria fent list<int>::iterator o list<int>::const_iterator. Si el volem declarar d'un vector de char, seria fent vector<char>::iterator o vector<char>::const_iterator

Diferències entre iterator i const_iterator?

iterator permet modificar el contingut de l'objecte. const_iterator no, podem recórrer l'objecte, però es queda com estava

Iteradors importants?

Bàsicament hi ha dos. Són begin() i end(). Begin apunta al primer element de l'estructura, i end apunta a fora de l'estructura. És a dir, l'estructura està al rang d'iteradors [begin,end). 

Com ens movem per l'estructura?

Amb els operadors ++ i --. ++it fa que apunti al següent element, mentre que --it fa que apunti a l'anterior. Els vectors, per exemple, permeten sumar-hi números, però les llistes no. 

Com consultem l'element?

Amb l'operador de desreferència *. Si tenim que it apunta a un element, fent *it consultem aquest element

Funcions de la classe list:

Un cop sabem com recórrer una llista, necessitem saber com treballar-hi. I, en aquest cas, tenim bastantes més funcions que als anteriors. Posaré les que em semblin més necessàries, si en voleu més, estan aquí. Són les següents:

begin: 

Retorna un iterador que apunta al primer element de la llista

end:

Retorna un iterador que apunta a l'end, és a dir, passat l'últim element. 

size:

Retorna la mida de la llista

front i back:

Retornen el primer i l'últim element, respectivament

push_front i push_back:

Afegeixen un element al principi i al final, respectivament. 

pop_front i pop_back:

Eliminen el primer i l'últim element, respectivament

insert:

Inserta un element. La versió més utilitzada rep un iterador indicant la posició on volem insertar, i l'element que insertem, i retorna un iterador que apunta a l'element insertat. 

erase:

Elimina un element. Rep un iterador apuntant a l'element que volem eliminar, i retorna un iterador apuntant al següent del que hem eliminat. Compte! L'iterador que li hem passat ja no és vàlid. Una cosa típica és recórrer la llista eliminant sota certes condicions. En aquest cas, hauríem de fer

...

if(*it==n) it=erase(it);

...

Així l'iterador que estem utilitzant segueix sent vàlid (ja que la funció retorna un iterador a l'element de després de l'eliminat. 

splice:

Hi ha diverses versions, la més utilitzada és la que transfereix una llista a l'altra. És a dir, si féssim

l.splice(l.begin(),llista2);

El que estaríem fent és transferir els elements de llista2 al principi de l. La llista2 quedaría buida

Tenim més funcions, i les que he posat són molt més extenses. Com sempre, Google i aquesta pàgina tenen les respostes que volem. Nosaltres encara tenim estructures per conèixer

Arbre binari:

NOTA: la classe explicada aquí ha quedat obsoleta. Han creat una nova classe, de la que parlo aquí. Malgrat tot, tot el que he explicat aquí es pot aplicar amb la nova classe, simplement canviant les funcions que utilitzem

Espera espera, arbres binaris? Això no sortia a la llista d'estructures de dades que vas fer, no? Realment no. És una estructura de dades no estàndard, que ens donen els professors de PRO2.

La definició de l'arbre binari és recursiva. Un arbre binari pot ser:

-Buit

-Un node (pare), i dos arbres binaris com a fills. 

No ens preocuparem (per ara) de com s'implementa internament. Només hem de saber això, que un arbre pot ser buit, o un node i dos arbres com a fills. 

Un detall que podem observar és que al fitxer Arbre.hh tenim tota la implementació. No acostuma a ser bona idea implementar coses al fitxer hh, però quan utilitzem templates, ens hi veiem obligats (per raons que no venen al cas).

Glossari:

Això no és res més que una sèrie de termes sobre els arbres (de moment, binaris) bastant utilitzats.
Node: Un arbre no deixa de ser un graf (si feu o heu fet M1, perfecte, si no... Bé, busca a Google, tampoc cal saber-ne gaire). Els elements de l'arbre, per tant, són nodes
Arrel: El node pare d'un arbre
Subarbre: El fill de l'arbre. En els arbres binaris, en tenim dos
Fulla: Un node que no té fills (normalment fem que siguin fills buits)

Funcions:

a_buit: Converteix el paràmetre implícit en un arbre buit

swap: Intercanvia els dos arbres

plantar: Rep un valor i dos arbres. El paràmetre implícit es transforma en un arbre tal que el pare té el valor, i els fills són els arbres que li hem passat

fills: Rep dos arbres buits. El primer es converteix en el fill esquerre del paràmetre implícit, i el segon en el dret. El paràmetre implícit deixa de ser vàlid, per altra banda

arrel: Retorna l'arrel de l'arbre

es_buit: Retorna true si l'arbre és buit, false si no

I ja està. No hi ha més funcions, i tampoc calen. La recursivitat farà la màgia

Iterar és màgic, recursivar és diví

Anem a fer uns quants exemples de coses que podem fer amb arbres.

Llegir en preordre:

La idea és anar llegint com si ens recorreguéssim l'arbre amb una cerca en profunditat. La lectura en preordre es defineix recursivament (sí, sóc un pesat) de la següent manera:

-llegim el pare

-llegim el fill esquerre

-llegim el fill dret

Es pot fer de moltes maneres, però hem de trobar una manera d'indicar que ja ha acabat aquella branca. Per exemple, jo ho faré amb el 0, de manera que en el meu arbre no hi ha 0. Per llegir-ho, seria una cosa així:

void llegir(Arbre<int>& A) {

    int n;

    cin >>n;

    if (n!=0) {

        Arbre<int> fe, fd;

        llegir(fe);

        llegir(fd);

        A.plantar(n,fe,fd);

    }

}

És a dir, llegim l'element que serà el pare de l'arbre actual. Si és diferent de 0, vol dir que hem de llegir els fills esquerre i dreta, i plantar-ho. Si és 0, vol dir que aquest arbre ha de ser nul, per tant no fem res. 

Comprovar si un element hi és

bool hi_es (int x, Arbre<int>& A) {

    if (A.es_buit()) return false;

    Arbre<int> fe, fd;

    if(A.arrel()==x) return true;

    A.fills(fe,fd);

    bool r=hi_es(x,fe) or hi_es(x,fd);

    A.plantar(fe,fd);

    return r;

}

Anem a fer algun problema

Podem fer l'exercici 1 de l'examen del 14/11/2016. Aquest ens demana calcular la mitjana i la desviació dels elements d'un arbre binari. Ens demana implementar dues funcions, i en una d'elles hem de triar els paràmetres que passem. Aquesta és la funció d'immersió, que és la que entra dins de l'arbre. Podem dir que és la que fa i desfà. 

Com ho fem?

Tant per calcular la mitjana com per calcular la desviació necessitem conèixer la suma dels elements, i la quantitat d'elements. Per tant, farem que la capçalera d'immersió sigui

void i_estadist(Arbre<double>& a, double& suma, int& n)

Aleshores, volem calcular tant la suma com la quantitat d'elements, no? Podem fer que quedi una cosa així:

// Pre: a=A, suma=0 i n=0

// Post: suma representa la suma dels elements de l'arbre A

// n representa la quantitat d'elements de l'arbre A

void i_estadist(Arbre<double>& a, double& suma, int& n) {

    if (a.es_buit()) return;

    double valor=a.arrel();

    Arbre<double> fe, fd;

    a.fills(fe,fd);

    double suma_e=0, suma_d=0;

    int ne=0, nd=0;

    i_estadist(fe,suma_e,ne);

    i_estadist(fd,suma_d,nd);

    a.plantar(valor,fe,fd);

    suma=suma_e+suma_d+valor;

    n=ne+nd+1;

}

// Pre: a = A és un arbre no buit

// Post: mitjana representa la mitjana dels elements de l’arbre A,

// desviacio representa la desviaci´o dels elements de l’arbre A

void estadist(Arbre<double>& a, double& mitjana, double& desviacio) {

    double suma=0;

    int n=0;

    i_estadist(a,suma,n);

    mitjana=suma/n;

    desviacio=suma*suma/(n*n);

}

Si a és buit, no hem de sumar res, ni comptar cap element. Si no és buit, calculem la suma i la quantitat d'elements de cada fill. La suma de l'arbre serà la suma del fill esquerre més la del fill dret més el valor de l'arrel. La quantitat d'elements de l'arbre serà la quantitat d'elements del fill esquerre més la del dret més 1. 

Per últim, ens demanen demostrar que això funciona. I, per fer-ho, utilitzarem un mètode que als informàtics ens encanta, i és la inducció. La meva serà de pa sucat amb oli, però a un examen s'ha de fer bé. 

Cas base: En el cas buit, com que no modifiquem res, tenim que suma=0 i n=0. No hi ha elements, i per tant, no sumen res. Correcte

Inducció: Suposarem que la funció funciona. En aquest cas, la suma dels elements d'un arbre no buit serà la suma dels del fill esquerre més la dels del fill dret més l'arrel (Correcte). La quantitat d'elements serà la quantitat del fill esquerre més la del fill dret més 1. Correctes els dos.

Apunts importants sobre els arbres

Hi ha una sèrie de coses importants a tenir en compte a l'hora de programar utilitzant arbres. Actualment no sabem com funcionen els arbres per dins, però sí que penso que és important conèixer alguna cosa. Si més no, el cost de les funcions. En essència m'interessen unes funcions concretes

Plantar: Aquesta té cost constant en la majoria dels casos. L'únic cas on el cost no és constant és quan els dos arbres són el mateix (no que siguin iguals, compte, que siguin el mateix objecte exactament). En aquest cas, té cost lineal respecte als elements d'aquest arbre. 

Fills: Aquesta sempre té cost constant

Arrel: Aquesta té cost constant respecte la quantitat d'elements de l'arbre. Òbviament, si és un arbre de vectors, el temps dependrà de la quantitat d'elements del vector

Per què em sembla important remarcar aquests 3 costos? Fàcil. Quan no sabem com funciona la classe internament, podem pensar que les dues primeres tenen cost lineal respecte a la mida. Al cap i a la fi, sembla que copia els elements dels fills al pare, o del pare als fills. No obstant, funciona diferent. Si no ho sabem, podem trobar-nos que intentem utilitzar-los molt poc, però l'alternativa utilitzada tingui un cost més elevat. Sabent això, sabem que utilitzar-les no és un drama 

Aprendre a programar 14 - Piles i cues

Arribats a aquest punt, toca aprendre a utilitzar altres estructures de dades. Fins ara hem utilitzat vectors, però no sempre ens va bé utilitzar vectors. A vegades necessitem emmagatzemar les dades de diferent manera, o necessitem estructures de dades més complexes, o més simples... Per això tenim més estructures de dades (JA! Us pensàveu que amb els vectors en teníem prou? No sabeu res hahaha). A PRO2 en veurem unes quantes, de les moltes que hi ha a la STL.

Pila

La primera estructura que veurem és la pila. És una estructura del tipus LIFO (Last In - First Out), que vol dir que traiem els elements de més recents a menys recents. Ens la podem imaginar com si traguéssim els plats del rentaplats, i els poséssim en una pila per passar-los a l'armari. El primer plat que podrem agafar serà l'últim que haguem posat a la pila

Per utilitzar-la, s'utilitza la classe stack, que trobem a la llibreria stack (esperable, no?). Tenim bàsicament les següents funcions:

push: Afegeix un element a la pila

pop: Elimina l'element de dalt de tot (és a dir, l'últim que hem afegit)

top: Retorna l'element de dalt

size: Ens retorna la mida

empty: Retorna true si la mida és 0, false si és diferent

Aleshores, treballar amb una pila és bastant senzill. Per afegir utilitzem push, per treure pop, per consultar top

Podem provar de fer alguna cosa. Per exemple, mirar si una expressió està ben parentitzada. És a dir, una expressió ben parentitzada es podria definir:

buit: Ben parentitzada

(expressió): Ben parentitzada

[expressió]: Ben parentitzada

{expressió}: Ben parentitzada 

És a dir, un string buit seria una expressió ben parentitzada. () també. (()) també. ([]) també. ([({})]) també. 

Podem veure com cada parèntesi obert té un que el tanca. Sabent això, podem utilitzar una pila per fer-ho:

bool ben_parentitzat(const string& s) {

    stack<char> st;

    for(int i=0;i<int(s.length());++i) {

        char c=s[i];

        if (c==')') {

            if (s.top()!='(') return false;

            s.pop();

        }

        else if (c==']') {

            if (s.top()!='[') return false;

            s.pop();

        }

        else if (c=='}') {

            if (s.top()!='[') return false;

            s.pop();

        }

        else s.push(c);

    }

    return s.empty();

}

int main() {

    string s;

    while(cin>>s) {

        if (ben_parentitzat(s)) cout <<"SI"<<endl;

        else cout<<"NO"<<endl;

    }

}

És a dir, si obrim el parèntesi, l'empilem. Si el tanquem, comprovem que coincideixi amb l'últim obert i, si coincideix, vol dir que ja hem tancat l'últim, de manera que el podem treure. Si no coincideix, acabem directe. Quan acabem, si la pila està buida, vol dir que estava bé, mentre que si té contingut, vol dir que faltaven parèntesis per tancar

Sembla una estructura molt senzilla, no? Doncs té moltes utilitats. Per exemple, per programar l'algorisme DFS iteratiu fa falta una pila. També s'utilitza una pila per emmagatzemar les variables locals de les funcions, així com pel pas de paràmetres d'una funció a una altra. Per això mateix, quan fem una funció recursiva infinita, ens acaba sortint l'error "stack overflow". 

Cua:

Un cop hem après què és una pila, podem mirar-nos la cua. La cua és una estructura FIFO (First In - First Out). Això vol dir que el primer element que entra és el primer que surt. Ho podem veure com la cua del super, el primer que s'hi posa és el primer en ser atès, i l'últim que s'hi posa és l'últim en ser atès (deixant de banda la gent que es cola). Les seves funcions són:

push: Afegeix un element a la cua

pop: Elimina l'element de davant (és a dir, el primer que hem afegit)

front: Retorna l'element de davant

size: Ens retorna la mida

empty: Retorna true si la mida és 0, false si és diferent

Aleshores la idea d'utilitzar una cua és que el primer element insertat és el primer que surt. Formats FIFO s'utilitzen per moltes coses. Per exemple, per programar l'algorisme DFS, que es fa a EDA, s'utilitzen cues.. O, per exemple, els fluxs de dades (cin, cout, cerr) funcionen igual, el primer que entra al flux és el primer que en surt. El mateix amb les pipes de Linux. I podríem seguir. 

La classe queue la trobem a la llibreria queue (sorprenent). 

Aprendre a programar 13 - L'examen de lab de PRO2

Ara ja hem fet les 3 primeres sessions, i se suposa que ja sabem més o menys modificar una classe. La sessió 4 és per practicar per l'examen de laboratori, que consistirà en modificar una classe que, en general, acostuma a ser Cjt_estudiants. Aquí, a diferència dels altres problemes, acostumen a donar-nos de manera que només haguem de fer dos o tres funcions. No té gaire diferència respecte les sessions anteriors, i, per tant, penso que no cal dedicar un article només a això. Així que he pensat que parlaré del meu examen de lab, que va ser completament diferent a la majoria. Si més tard veig necessari completar amb altres examens, els afegiré al final

Quan et canvien completament el format

Suposo que el lector, igual que jo, estudia els examens de la universitat com si fos l'autoescola. Es mira què entra, i es posa a fer examens per veure com ho porta. És molt típic, i conec molta gent que ho fa així. A algunes assignatures ja avisen que no és una bona manera, i que es pot patinar. I això és el que va passar el meu any (2015-2016 Q2). 

Sí, imagineu la sorpresa dels estudiants del torn 1, quan arriben i es troben que han d'implementar una cua. Sobretot pels que no tenen gaire clar què és una cua, ja que no entraven a aquest examen. 

Si algú vol l'examen, pot trobar-lo aquí, amb el PDF, els fitxers i una solució (que va treure un 10 a l'examen). Jo proposo que intenteu resoldre'l, després us podeu mirar les idees que dono per resoldre-ho, i finalment la meva solució

Primera idea:

Una primera idea seria la següent. 

Per fer el push, seria tan senzill com afegir l'element a v[t], i incrementar t i n.Evidentment, retoquem la suma i nest_amb_nota, si toca

Per fer el pop, simplement desplacem tots els elements al rang [1,t) una posició a l'esquerra. Decrementem t i n. De la mateixa manera, si cal, retoquem la suma i nest_amb_nota

Per escriure, simplement faríem un for i escriuríem cada estudiant

Aquesta solució és bastant intuïtiva. I, si no ens fixem gaire en l'invariant, doncs és el que se'ns passarà pel cap. 

El seu problema:

Aquesta solució té un problema, i és que cada pop que fem implica desplaçar tots els elements. A més, l'invariant ens diu que tenim un membre de la classe que es diu p, que indica l'inici de la cua, un que es diu t, que indica el final, i un que es diu n, que indica la mida. Amb la nostra solució, són inútils, ja que el primer sempre serà 0, i el final sempre serà n. 

Però la classe es torna més simple, podríeu dir. Sí, és cert, però es torna més lenta. Un pop implica desplaçar n-1 estudiants. Sí, en principi la mida màxima és 10, de manera que com a molt estarem desplaçant 9 estudiants. Però per què desplaçar 9, si ho podem fer bé i no desplaçar-ne cap? O, mirem d'una altra manera. Imaginem que necessitem una cua que pugui tenir fins a 1.000.000 d'estudiants. Seria divertit fer pop, no?

I tan malament està això?

Sí. Perquè us feu una idea, l'examen era 60% automàtica, i 40% manual. Hi va haver una quantitat desproporcionada de gent amb un 6, perquè tenien un 10 d'automàtica, i un 0 de manual. Semblava que només hi haguessin 3 notes (0, 6 i 10). Sobretot 6, després 0, i pocs 10. Però notes diferents, encara menys. 

Una bona solució?

Doncs una bona solució seria aprofitar tots els atributs de la classe. 

Fer un push és senzill, posem la variable a la posició t, incrementem n i recalculem t. Si l'estudiant té nota, ho retoquem una mica, i ja està

Fer el pop és similar. Si té nota, retoquem, i aleshores incrementem p i decrementem n. Si p ha arribat al màxim, ho posem a 0, i ale

Fer l'escriure és bastant trivial. Et recorres de p fins a t (no inclòs), i mostres els estudiants. Pots utilitzar la funció escriure, o fer-te el xulo com vaig fer jo, i fer-ho a mà (millor la primera)

Aprendre a programar 12 - Modificar una classe

Un cop hem arribat aquí, ja sabem com utilitzar la classe Estudiant, i Cjt_estudiants. Pot haver costat més o menys aconseguir-ho, però al final ho hem aconseguit. Doncs bé, ara ja no haurem d'escriure programes que la utilitzin. Com us quedeu?

Funcionament intern d'una classe

A l'article anterior vèiem com funciona una classe des del punt de vista de l'usuari extern. Aquí veurem com funciona des de dins

Públic vs privat

Una classe té 3 tipus d'atributs i mètodes. Són públics, privats i protegits. Als protegits no els farem gaire cas, a PRO2 no els utilitzem. 

Públic:

Normalment tenim mètodes públics, més que atributs. Són els mètodes amb els que treballem des de fora, i serveixen per interactuar amb la classe sense preocupar-nos del funcionament intern. En algun cas, també hi ha atributs, com per exemple en el cas de la classe pair, que tenim dos atributs públics (first i second)

Privat:

Aquí tenim mètodes i atributs. Normalment els atributs són els que emmagatzemen la informació que necessitem, mentre que els mètodes (s'entén que privats) són auxiliars cridats per les funcions públiques. Per exemple, a Cjt_estudiants tenim un mètode públic que és consultar_estudiant, que rep un DNI i retorna l'estudiant corresponent. Doncs ho fa utilitzant una funció auxiliar que fa la cerca dicotòmica, i que està com a privada. A aquesta no hi podem accedir des de fora, ja que és privada

Com funciona Cjt_estudiants?

Sí, comencem directament per aquí. El funcionament d'Estudiant és bastant senzill, i a més, no ens la faran modificar. Si a algú li interessa, és trivial, però per nosaltres seguirà sent una caixa negra. 

Atributs privats:

Bàsicament tenim 3 atributs privats. 

MAX_NEST:

És un enter que indica la mida màxima del conjunt. Pot ser 10, 60, 30.000, o qualsevol altra cosa. La idea és que hi puguin cabre tots els estudiants que vulguem

vest:

Aquest és el vector que emmagatzema els estudiants. És un vector<Estudiant> de mida MAX_NEST

nest.

És un enter que emmagatzema la quantitat d'estudiants que tenim. La idea és que estaran emmagatzemats entre la posició 0 i la posició nest-1

Mètodes públics

Afegir estudiant:

Aquesta el que fa és desplaçar tots els elements amb dni>est.dni una posició cap a la dreta, i un cop ha arribat al punt on el dni ja no és més gran, posa allà l'estudiant. Això, evidentment, si hi cap. Per tant, té cost lineal respecte a la mida

Modificar estudiant:

Fa la cerca dicotòmica per buscar on està aquell dni, i modifica aquella posició perquè hi hagi l'estudiant que volem

Modificar ièssim

Modifica l'ièssim, sempre que la posició sigui vàlida

Mida i mida màxima:

Retornen l'enter corresponent

Existeix estudiant:

Fa la cerca dicotòmica buscant el dni, i retorna si hi és o no

Consultar estudiant

Fa la cerca dicotòmica, i retorna l'estudiant que està a la posició retornada

Consultar ièssim:

Retorna vest[i-1]

Llegir:

Llegeix nest. Després fa nest iteracions, fent vest[i].llegir(). Finalment ordena el conjunt

Escriure:

Fa nest iteracions, fent vest[i].escriure()

Com modifiquem?

Normalment ens fan fer exercicis on ens diuen "hem afegit tal atribut privat, i tal funció. Modifica-ho perquè funcioni". El primer que hem de fer és descarregar els arxius del Jutge, allà hi ha les capçaleres i tot. Un cop ho tenim, modifiquem allà directament

Un exemple. Fem l'exercici X68173, que, com podeu veure a l'imatge, no és gaire difícil

No, de debò, no és gaire difícil. El que passa és que, al no haver-hi casos de proves, el que feia era provar-los directament al jutge, comprovant que compilessin i ja (excepte a l'enviament 1 i 15, que se'm va passar). No obstant, jo us diria que us feu un joc de prova (o més), i així no tindreu tants errors

Dit això:

Conjunt d'estudiants amb imax - X68173

Descarreguem els arxius, i veiem que tenim PRO2Exepcio.hh, Estudiant.hh, Estudiant.cc i Cjt_estudiants.hh. Per tant, el que ens toca fer és Cjt_estudiants.cc. De fet, l'únic que ens cal és afegir-hi les dues operacions que ens demanen, i modificar les que calgui. Comencem triant quines funcions cal modificar.

Constructores?

Només en tenim una. No cal fer-hi res, no hi ha màxim perquè està buit. Podem posar-li un valor fora del rang, perquè quedi clar que no tenim màxim. Depenent de com decidim implementar-ho, però jo crec que millor modificar-la

Modificadores?

Afegir estudiant, per si afegim un estudiant amb nota major, o la posició de l'estudiant amb nota màxima canvia

Modificar estudiant, per si modifiquem l'estudiant que té la nota màxima

Modificar ièssim, pel mateix

Esborrar estudiant, que de fet no està implementada

És a dir, totes

Consultores?

Aquí no n'hem de modificar cap. Al cap i a la fi, no modifiquen, consulten. L'únic que hem de fer és implementar estudiant nota max

Lectura/escriptura?

A la de lectura hem de mirar quina és la posició amb nota més gran. A la d'escriptura, res

Ja sabem quines hem de modificar. Ara toca fer-ho. Pots, o currar-te de comprovar si s'ha modificat alguna cosa, si cal recórrer tot el conjunt... O pots simplement recalcular el màxim al final. Jo vaig aconseguir el verd així, per tant, es pot fer així i no et compliques la vida. O pots fer-ho bé, esforçant-te. Això ja depèn de tu

Aprendre a programar 11 - Introducció a la Programació Modular

Doncs sembla que ja hem acabat PRO1. Arribats a aquest punt, espero que als lectors els hagin agradat els meus articles, i els hagin ajudat a entendre coses. Aquí començarem a explicar l'assignatura de PRO2. En aquesta, el laboratori està més dividit en sessions, així que jo també ho faré així. Posaré més o menys de quina sessió és cada cosa. Ara començarem pel principi, que és la sessió 1 i la sessió 2. Les sessions i tot el que és necessari està a disposició de tothom, així que no cal estar estudiant PRO2 per fer això

Què és la programació modular?

La programació modular consisteix en dividir un programa en subprogrames més petits. Això ens permet tenir diferents mòduls escrits per diferents programadors, així com fer-lo més llegible i modificable. En essència, dividim un problema en problemes més petits, que són més fàcils de resoldre, i els resolem. Finalment, ho ajuntem tot. En C++, això es fa utilitzant una eina, que és la Classe. 

Què és una classe?

Una classe és una abstracció d'un objecte. Conté dins mètodes i atributs. Aquests poden ser privats, protegits i públics, tot i que a PRO2 els protegits no s'utilitzen. Per exemple, podem tenir una classe com la següent:

class Complex {

private:

double r, i;

public:

void inicialitzar (double real, double imaginaria) {

r=real;

i=imaginaria;

}

double real() {

return r;

}

double imaginaria() {

return i;

}

void mostrar() {

if(i<0) cout <<r<<" - "<<abs(i)<<'i'<<endl;

else cout <<r<<" + "<<i<<'i'<<endl;

}

};

Aquí tenim una classe que serviria per representar nombres complexos. Podem veure que d'atributs tenim dos nombres reals, corresponents a la part real i la part imaginària. No obstant, fixem-nos que són privats. Això ens impedeix accedir-hi directament. Per accedir-hi hem d'utilitzar les funcions públiques. És a dir, podem veure dos codis:

//Codi erroni, intentem accedir als atributs privats

Complex c;

c.r=3;

c.i=4;

c.mostrar();

//Codi correcte

Complex c;

c.inicialitzar(3,4);

c.mostrar();

Podem veure que no li passem c com a paràmetre. Això és perquè cada objecte (cada variable que creem amb una classe és un objecte) és propietari dels seus mètodes. 

Utilitzar classes permet que qui les utilitzi no s'hagi de preocupar gens per com funcionen les coses internament. Què més dóna si emmagatzemem la part real i la part imaginària en dues variables, en una parella, o de qualsevol manera? Només ens importa que ens les doni si les demanem. 

Com utilitzem les classes?

Inicialment no en programarem cap, sinó que utilitzarem les que ens donen. Ens donaran bàsicament tres fitxers, que són les capçaleres, el codi i un pdf on explica què tenim. 

Espera, per què fitxers diferents?

Hem dit que una de les raons per utilitzar programació modular és que podem tenir diversos programadors programant diferents mòduls. Aleshores, hem de permetre que cada mòdul es programi en un fitxer diferent, i després es pugui ajuntar fàcilment (i no em refereixo a copiar el codi de tots els mòduls en un únic fitxer). Per tant, el que es fa normalment és crear dos fitxers per cada mòdul

Capçaleres:

Podem dir que és un fitxer que ens diu "què tindrem". És a dir, conté les declaracions de les classes, funcions i tot el que necessitem, però sense el seu codi. És com dir-nos "ei, quan ajuntis el codi amb el meu fitxer, tindràs aquestes funcions". Per això, aquest fitxer l'ha de tenir tothom qui pretengui utilitzar el mòdul. Nosaltres farem que sigui un fitxer amb extensió hh (la h de headers), i l'inclourem mitjançant la directiva

#include "capçalera.hh"

Utilitzem "" enlloc de <> perquè, en el cas de <>, primer busca als directoris estàndard (que és on troba iostream, vector, algorithm i totes aquestes) i si no ho troba allà, se'n va al nostre directori. En canvi, amb "", primer busca al nostre directori i, si no ho troba, se'n va allà. 

Codi:

Aquí tenim el codi de tot el que hem declarat a les capçaleres. És un fitxer amb extensió cc, com els que hem utilitzat sempre. Aquest es pot compilar per separat de la resta, quedant un fitxer amb extensió o (d'objecte), i només necessitem tenir les capçaleres que utilitzarem, sense el seu codi. Per exemple, si tenim una classe Rectangle, que utilitza la classe Punt, només necessitarem Rectangle.hh, Rectangle.cc i Punt.hh. Quan compilem, tindrem un arxiu Rectangle.o. Això ens permet utilitzar classes sense saber ni quin és el seu codi, ja que a l'hora d'enllaçar tots els codis, utilitzarem els fitxers .o

Aleshores, com va això de compilar i enllaçar?

Fàcil. Primer compilem tots els mòduls, i després els enllacem. Així:

$g++ -c Classe1.cc

...

$g++ -c main.cc

$g++ Classe1.o Classe2.o ... main.o -o programa.exe

És a dir, primer compilem utilitzant -c, i un cop tenim tots els mòduls (recordem que ens cal un main que cridi tot), podem linkar. Utilitzant -o, diem com volem que es digui l'arxiu de sortida. Fixem-nos, però, que molts professors de PRO2 prefereixen fer

$g++ -o programa.exe Classe1.o Classe2.o ... main.o

És el mateix, simplement ho canvien d'ordre. Jo prefereixo la primera forma, però crec que és també qüestió de gustos.

Per altra banda, a PRO2 s'utilitza p2++, que és un àlies, igual que ho era p1++. Jo penso que és important utilitzar-lo, i parlo des de l'experiència, ja que no vaig arribar a utiltizar p1++ ni p2++. Si no el fas servir, et pots trobar que executes un programa que utilitza alguna cosa de C++11, i no et funciona (recordem que p2++ utilitza C++11). Si decideixes passar olímpicament, al menys recorda utilitzar els flags -Wall i -std=c++11

Comencem: La classe Estudiant

Els primers exercicis que utilitzen classes no estàndard són els que utilitzen Estudiant. Per utilitzar-ho ens donen un fitxer .pdf on crec recordar que està ben explicat. No obstant, en el moment que escric això, no tinc accés al disc de la FIB, i parlo de memòria. Per sort, m'he aconseguit els .hh i .cc. 

La classe en qüestió conté les següents funcions

Estudiant(): Declara un estudiant sense cap paràmetre. Concretament, li posa dni 0, i cap nota
Estudiant(int dni): Declara un estudiant amb dni=dni, i sense nota. El dni ha de ser >=0

void afegir_nota(double nota): Li afegeix una nota a un estudiant sense nota. Cal que estigui entre 0 i nota_maxima() incloses, cosa que en general, vol dir 0<=nota<=10. No obstant, no sempre és així
void modificar_nota(double nota): Modifica la nota. Cal que tingui nota abans

int consultar_DNI() const: Retorna el dni de l'estudiant
double consultar_nota() const: Retorna la nota de l'estudiant
static double nota_maxima(): Retorna la nota màxima d'un estudiant (per tots serà la mateixa). És static perquè així no cal declarar cap estudiant, pots fer Estudiant::nota_maxima(), ja que per tots serà la mateixa
bool te_nota()  const: Retorna true si l'estudiant té nota, false si no

void llegir(): Llegeix pel canal estàndard un estudiant (és a dir, dos enters, el dni i la nota). Si la nota no està al rang [0,nota_maxima()], l'estudiant resultant no té nota
void escriure() const: Escriu pel canal estàndard de sortida l'estudiant. Si no té nota, escriu un NP

És a dir, per utilitzar la classe Estudiant, tenim aquestes, i només aquestes (records de FM) funcions. Les dues primeres són les constructores, serveixen per crear un estudiant. Les 2 següents, són per modificar un estudiant ja existent. Les 4 següents, per consultar en un estudiant, i les dos últimes, de lectura i escriptura.
Per exemple, podríem tenir un exercici que digui "donat un estudiant i una sèrie de notes, treu pel canal estàndard el seu dni i la nota màxima". Podríem fer-ho així:

int main() {
    int dni;
    cin >>dni;
    Estudiant e(dni);
    double nota;
    while (cin >>nota) {
        if (e.te_nota()) {
            if (nota>e.consultar_nota() and nota<=e.nota_maxima())
                e.modificar_nota(nota);
        }
        else {
            if (nota>=0 and nota<=e.nota_maxima()) e.afegir_nota(nota);
        }
    }
    e.escriure();
}


Suposo que es veu més o menys com funciona. Bàsicament una manera senzilla d'imaginar-se això és
- Un objecte és la representació informàtica d'alguna cosa. El cotxe de la teva mare, o tu
- Una classe és l'abstracció d'un objecte. La classe Cotxe, per exemple, o la classe Estudiant
- Per tant, cada instància que fem d'una classe és un objecte
Aleshores, per interactuar amb qualsevol objecte, ens ho imaginem com una caixa negra. No podem veure què hi ha dins, i, per tant, no ho podem modificar. Però tenim les funcions que ens permeten interactuar amb ell, ja sigui consultar coses, modificar-les...

Resum de la classe Estudiant:

Com es crea un estudiant?

Crear un estudiant es fa amb les funcions creadores. En aquest cas tenim dues versions. La primera crea un estudiant buit, la segona amb dni. Com que no podem modificar el dni de l'estudiant, la primera versió serà només per llegir-lo per l'entrada estàndard, mentre que la segona serà la que ens permetrà afegir-li la nota directament. Es criden igual que quan creàvem una variable entera, o un vector (recordem que el vector és una classe). És a dir

Estudiant e1;//Crea un estudiant buit

Estudiant e2(666);//Crea un estudiant amb el DNI de Satanàs

Com es modifica l'estudiant?

Bàsicament podem actuar sobre la nota. Hi ha dues possibilitats. Si no té nota, li podem afegir, mentre que si ja la té, la podem modificar. Per exemple

Estudiant e(666);

double d, d2;

cin >>d;

e.afegir_nota(d);

cin >>d2;

if(d2>d) e.modificar_nota(d2);

Aquí no he tingut en compte què passaria si una de les notes és <0, o >nota_maxima(), perquè encara no he explicat les consultores. Però caldria fer-ho

Com consultem informació d'un estudiant?

Aquí tenim més coses que podem consultar. Podem consultar el seu DNI. Podem consultar també la seva nota. O la nota màxima, ja que no necessàriament ha de ser 10. Finalment, podem consultar si té nota o no, perquè potser encara no té nota. Es faria així:

Estudiant e;

...

double nota;

cin >>nota;

if (e.te_nota()) {

    if (nota>e.consultar_nota() and nota>=0 and nota<=e.nota_maxima())

        e.modificar_nota(nota);

}

else {

    if (nota>=0 and nota<=e.nota_maxima()) e.afegir_nota(nota);

}

Com es llegeix i escriu?

Aquesta és la més fàcil de totes. Simplement tenim dues funcions, una llegeix i una escriu. La de lectura llegeix dos números, un és el DNI i un és la nota. La d'escriptura escriu el DNI i la nota, si en té, o "NP" si no

Dit tot això, jo crec que ja es poden resoldre tots els exercicis de la classe Estudiant

La classe Cjt_estudiants:

Un cop ja hem entès a la perfecció la classe Estudiant, comencem amb la classe Cjt_estudiants. Aquesta és una classe més complexa, que emmagatzema una sèrie d'estudiants. Té més funcions públiques, que són

Cjt_estudiants(): Constructora. Crea un conjunt buit

void afegir_estudiant(const Estudiant &est): Afegeix l'estudiant est. Aquest no hi ha de ser, i el conjunt ha de tenir espai

void modificar_estudiant(const Estudiant &est): Modifica l'estudiant amb el DNI d'est. 

void modificar_iessim(int i, const Estudiant &est): Modifica l'estudiant a la posició i

int mida() const: Ens dóna la mida del conjunt

static int mida_maxima(): Ens dóna la mida màxima. 

bool existeix_estudiant(int dni) const: Ens diu si existeix un estudiant amb DNI=dni

Estudiant consultar_estudiant(int dni) const: Ens retorna l'estudiant amb DNI=dni. Ha d'existir

Estudiant consultar_iessim(int i) const: Ens retorna l'estudiant a la posició i. 1<=i<=mida()

void llegir(): Llegeix un estudiant pel canal estàndard. Primer llegeix un número n, i després n Estudiants

void escriure(): Escriu els estudiants en ordre ascendent per dni

El que hem de tenir controlat és que els estudiants estan ordenats de manera creixent per dni. Això fa que consultar un estudiant per dni tingui cost logarítmic (fem una cerca dicotòmica), mentre que tenint la posició, té cost constant

Podem provar de resoldre el problema X74882, Actualitzar un conjunt d'estudiants. 

void modificar(Cjt_estudiants& c1, const Cjt_estudiants& c2) {

int n=c1.mida();

for (int i=1;i<=n;++i) {

Estudiant e1, e2;

e1=c1.consultar_iessim(i);

e2=c2.consultar_iessim(i);

if (e1.te_nota()) {

if (e2.te_nota() and e1.consultar_nota()<e2.consultar_nota()) 

c1.modificar_iessim(i,e2);

}

else if (e2.te_nota()) c1.modificar_iessim(i,e2);

}

}

int main() {

Cjt_estudiants c1, c2;

c1.llegir();

c2.llegir();

modificar(c1,c2);

c1.escriure();

}

Bàsicament la funció el que fa és recórrer tot el conjunt. Com que sabem que està ordenat, i que consultar l'ièssim és molt més eficient, anem consultant l'element 1, després el 2, després el 3, i així fins al final.