Piles i Cues

C++

En aquesta sessió introduirem algunes idees noves sobre classes:

• una convenció sobre el nom dels membres privats,
• mètodes inline,
• llistes d'inicialitzadors, i
• l'assert.

Sovint els membres privats d'una classe s'anomenen usant una convenció

Quan implementem mètodes en un fitxer .cc, donat que els membres privats no es poden discernir d'altres variables sense consultar el fitxer .hh, és típic que es faci servir algun tipus de nomenclatura que simplifiqui el fet de veure ràpidament quins membres són privats.

Farem servir la més moderna, que posa un suffix _ als membres privats (tant camps com mètodes). Hi ha, de fet, vàries maneres de fer-ho, i diferents projectes en fan servir una o altra. Si un variable es digués membre com a variable normal, però és el membre privat d'una classe, es pot posar:

• membre_ (el que farem servir a PRO2, que també fan servir a Google).
• _membre (igual que l'anterior però es perd l'aliniament).
• m_membre (força utilitzat, però més antic).

Tot i que aquesta forma d'anomenar els membres privats no té cap efecte en el codi resultant, és útil perquè redueix l'esforç cognitiu de llegir-lo. També va bé per trencar l'ambigüitat que sovint sorgeix entre paràmetres d'un constructor o mètode i els membres privats, que potser volem anomenar de forma anàloga (com ara dia, mes i any aquí sota):

class Data {
    int dia_, mes_, any_;
public:
    Data(int dia, int mes, int any);
};

Data::Data(int dia, int mes, int any) {
    dia_ = dia; // <- Aquí el '_' va bé per distingir
    mes_ = mes; // <- els paràmetres dels camps
    any_ = any; // <-
}

Veureu, doncs, que totes les classes que es posen d'exemple tenen aquesta convenció.

Quan declarem i alhora implementem un mètode, aquest esdevé inline

La següent classe mínima:

té 3 mètodes (constructor incrementa i valor), però tots 3 s'han implementat directament després de la declaració, abans de les claus que tanquen la classe. Això implica que les crides als mètodes no es compilen com a funcions normals, sinó que quan fem una cosa com:

Comptador a;
a.incrementa();
cout << a.valor() << endl;

el compilador no es molesta en cridar els mètodes sinó que "incrusta" el codi dels mètodes directament allà a on els cridem, per tant el codi compilat quedarà aproximadament com:

int c_ = 0;
c_++;
cout << c_ << endl;

L'avantatge de no cridar a funcions que tenen un número d'instruccions molt curt és que és més eficient, ja que una crida a una funció té un cert cost fixe, i si la funció és molt curta i s'utilitza molt sovint, paguem el cost de la crida cada vegada.

El desavantatge és que si s'incrusta el codi a cada crida, i la funció no és prou curta, llavors el programa explota en tamany, perquè allà a on hi havia un crida, ara hi haurà tot el codi, i si el número de crides és gran, el programa creixerà molt.

Per tant, només és bona idea posar mètodes inline quan aquests són molt curts, o bé si es criden una o dues vegades.

Quan una classe conté un objecte cal fer servir una llista d'inicialitzadors

Donat que les classes tenen constructors, què passa quan una classe Gran conté un objecte d'una classe Petita, i la classe Petita té un constructor?

class Petita {
    int x_;
public:
    Petita(int x) { x_ = x; }
};

class Gran {
    Petita petit_;
    char c_;
public:
    Gran(int a, char c);  // Com implmentem aquest constructor?
}

És a dir, com cridem el constructor de Petita quan es construeix Gran?

C++ ofereix un mecanisme especial per fer això que són les llistes d'inicialitzadors:

• Cal escriure la llista just abans del cos del constructor, després dels paràmetres.
• Comença amb el caràcter :.
• Cal posar els inicialitzadors (les crides als constructors dels membres) separats per comes.

En el cas de Gran:

Gran::Gran(int a, char c)
    : petit_(a)  // <-- Llista d'inicialitzadors
{
    c_ = c;
}

Quan C++ va adoptar aquesta forma d'inicialització, també es va afegir el fet de considerar la inicialització d'altres membres (de tipus bàsics com int, char i double) amb la mateixa notació, malgrat no ho necessitin. Així doncs, el constructor de Gran pot escriure's així:

Gran::Gran(int a, char c)
    : petit_(a), c_(c) // <-- Llista d'inicialitzadors
{}

Aquí, el membre c_, tot i ser un char, s'inicialitza com si fos un objecte usant parèntesis.

Convertim les pre-condicions en crides a assert

A PRO2 convertirem les pre-condicions (les suposicions que fem sobre els paràmetres d'una funció), en crides a assert. La funció assert el que farà és aturar el programa abruptament si una certa condició no es compleix.

La funció següent, que cerca una paraula en un vector a partir de la posició desde té una pre-condició força clara (la veus??):

int cerca_posicio_desde(const vector<string>& v, string s, int desde) {
    for (int i = desde; i < v.size(); i++) {
        if (v[i] == s) {
            return i;
        }
    }
    return -1;
}

Si la variable desde és negativa, accedirem a una casella del vector fora de rang i el programa experimentarà un desagradable error d'execució (al Jutge sol aparèixer com "EE - invalid memory reference").

Sovint aquests errors són invisibles, perquè accedir a una casella d'un vector que està just a la vora dels límits del vector no fa que el programa malfuncioni inmediatament, sinó que l'error afecta la memòria i apareix molt més tard, en un context diferent, i per tant és molt difícil veure què ha passat realment i d'on prové.

En el cas de cerca_posicio_desde, el que podem fer és posar un assert. (Caldrà que descarreguis el fitxer assert.hh de la pàgina de PRO2 per utilitzar-lo.)

La funció quedarà així:

#include "assert.hh"

int cerca_posicio_desde(const vector<string>& v, string s, int desde) {
    assert(desde >= 0);
    // ...
}

És a dir, de bon principi ens assegurem que desde té un valor major o igual que 0 (si és més gran que el vector no passarà res perquè ja no s'entraria al for). Però veurem l'error just en el moment que es produeix, que ens anirà bé per poder-lo arreglar de seguida i sense massa esforç.

A PRO2 farem servir asserts allà on hi hagi precondicions per poder trobar errors tan bon punt es produeixin.

Piles

Una pila és un contenidor molt simple a on només podem manipular l'element d'un extrem

Normalment les piles ens les imaginem verticals, i si pensem en una seqüència, és típic pensar que l'últim element de la seqüència està a dalt de tot. Es diu que una pila és un contenidor LIFO (Last In First Out, o l'últim que entra és el primer que surt), semblant a una pila de cartes o de plats, on només podem manipular l'element de dalt de tot.

Les piles són un TAD amb només 3 operacions:

• push: posar a la pila (a dalt de tot).
• pop: treure de la pila (de dalt de tot).
• top: consultar o accedir a l'element de dalt de tot.

Aquí hi ha una animació de l'efecte de push sobre la pila:

El mateix per a pop:

Apart, hi ha dues operacions genèriques per saber el tamany (o bé mirar si la pila és buida).

• empty: retorna true si la pila està buida.
• size: retorna el tamany.

No hi ha res més. Les piles ni tan sols es poden recórrer, és a dir, no ens cal haver de mirar elements que no siguin l'últim.

El concepte de pila sorgeix en molts contextos diferents

Per exemple, en un programa, quan una funció f_a crida a una funció f_b, s'ha de:

1. recordar a quin punt estavem a la funció f_a, després
2. saltar a la funció f_b i executar-la, i finalment
3. tornar a on érem a la funció f_a.

Donat que f_b pot cridar a una nova funció f_c, i així successivament, necessitem la pila d'execució, que conté totes les funcions que estan a mitges, és a dir, que esperen que la funció per sobre d'elles a la pila acabi i retorni el resultat.

Altres algoritmes a on apareixen les piles:

• Inversió de l'ordre d'una seqüència.
• Avaluació d'expressions.
• Implementar processos recursius sense usar funcions recursives (com el DFS).
• Determinar si una paraula pertany a un llenguatge formal.
• El problema del "proper element major".

Implementació d'una pila en C++

A PRO2, la implementació de la pila fa servir un vector per dins, de forma que un Stack té el membre elems_, que és un altre objecte (per tant necessitarem una llista d'inicialitzadors), i a més farem tots els mètodes inline, perquè tots són molt curts:

#ifndef STACK_HH
#define STACK_HH

#include <vector>
#include "assert.hh"

namespace pro2 {

template <typename T>
class Stack {
    std::vector<T> elems_;

 public:
    Stack() {}
    Stack(const std::vector<T>& elems) : elems_(elems) {}
    Stack(const Stack& other) : elems_(other.elems_) {}

    int size()   const { return elems_.size(); }
    bool empty() const { return elems_.empty(); }
    void push(const T& x) { elems_.push_back(x); }

    const T& top() const {
        assert(elems_.size() > 0, "top: pila buida!");
        return elems_.back();
    }

    void pop() {
        assert(elems_.size() > 0, "pop: pila buida!");
        elems_.pop_back();
    }
};

}  

Plantilles

Però perquè hi ha el template abans de la classe? De moment no entrarem en gran detall però tal com l'hem escrit, la classe Stack no és una classe, és una plantilla per fer classes. La plantilla té un "forat", que és el tipus T. Si posem un tipus entre els angles < i >, aquell es converteix en T, o sigui que Stack<int> equival a fer que T sigui int. A la implementació, la T es fa servir allà a on volem mencionar el tipus dels elements de la pila. Tot plegat permet que la nostra pila (com el vector), ens permeti escollir el tipus dels seus elements, en comptes d'haver de fer una pila per a cada tipus. Això es diu programació genèrica.

Exemple: avaluació d'expressions en notació postfixa

Un exemple clàssic d'ús de piles és l'avaluació d'expressions aritmètiques en notació polonesa inversa (també dita notació postfixa). En aquesta notació, els operadors van després dels operands: per exemple, 3 4 + equival a 3 + 4. L'algorisme llegeix tokens d'esquerra a dreta: si és un número, l'apila; si és un operador, desapila dos operands, calcula el resultat i l'apila. Al final, el resultat és l'únic element que queda a la pila.

#include <iostream>
using namespace std;

#include "stack.hh"
using namespace pro2;

int pop(Stack<int>& S) {
    int x = S.top();
    S.pop();
    return x;
}

bool is_number(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (!isdigit(s[i])) {
            return false;
        }
    }
    return true;
}

int main() {
    string token;
    Stack<int> S;
    while (cin >> token) {
        if (token == "+") {
            int a = pop(S), b = pop(S);
            S.push(a + b);
        } else if (token == "-") {
            int a = pop(S), b = pop(S);
            S.push(a - b);
        } else if (token == "*") {
            int a = pop(S), b = pop(S);
            S.push(a * b);
        } else if (token == ) {
             a = (S), b = (S);
            S.(a / b);
        }   ((token)) {
            S.((token));
        }  {
            cerr <<  << token << endl;
            ();
        }
    }
     (S.() == ) {
        cout << S.() << endl;
    }  {
        cerr <<  << endl;
    }
}

Cues

Una cua és un contenidor a on només podem manipular els elements dels extrems

Una cua es diu que és un contenidor FIFO (First In First Out, o el primer que entra és el primer que surt), semblant a una cua de persones en un supermercat, on només podem afegir elements al final i treure'n del davant.

Les cues són un TAD amb només 3 operacions:

• push: posar a la cua (al final).
• pop: treure de la cua (del davant).
• front: consultar o accedir a l'element del davant.

Apart, hi ha dues operacions genèriques per saber el tamany (o bé mirar si la cua és buida).

• empty: retorna true si la cua està buida.
• size: retorna el tamany.

Però res més. Les cues ni tan sols es poden recórrer, és a dir, no ens cal haver de mirar elements que no siguin el primer.

El concepte de cua sorgeix en molts contextos diferents

Per exemple, en un programa, quan volem processar tasques en l'ordre en què han arribat (com peticions a un servidor, o esdeveniments d'entrada), fem servir una cua. També en cerques en amplada (BFS) en grafs o arbres, on els vèrtexos pendents es gestionen amb una cua.

Altres contextos a on apareixen les cues:

• Simulació de cues d'espera (supermercats, atenció al client).
• Planificació de tasques (round-robin, processament per ordre d'arribada).
• Implementar BFS sense recursió.
• Buffers de dades (streaming, impressió).

Implementació d'una cua en C++

A PRO2, la implementació de la cua fa servir un vector per dins, tal com la pila, de forma que un Queue té el membre elems_, que és un altre objecte (per tant necessitarem una llista d'inicialitzadors), i, també com a la pila, farem tots els mètodes inline, perquè tots són molt curts:

#ifndef QUEUE_HH
#define QUEUE_HH

#include <vector>
#include "assert.hh"

namespace pro2 {

template <typename T>
class Queue {
    std::vector<T> elems_;

 public:
    Queue() {}
    Queue(const std::vector<T>& elems) : elems_(elems) {}
    Queue(const Queue& other) : elems_(other.elems_) {}

    int size()   const { return elems_.size(); }
    bool empty() const { return elems_.empty(); }
    void push(const T& x) { elems_.push_back(x); }

    const T& front() const {
        assert(elems_.size() > 0, "front: cua buida!");
        return elems_.front();
    }

    void pop() {
        assert(elems_.size() > 0, "pop: cua buida!");
        elems_.erase(elems_.());
    }
};

}  

Aquí passa el mateix amb el template que ens passava amb la pila.

Comparació entre piles i cues

Les piles i les cues són contenidors molt semblants, però amb una diferència clau:

En una pila, l'últim element afegit és el primer que surt (com una pila de plats). En una cua, el primer element afegit és el primer que surt (com una cua de persones). La tria entre l'una i l'altra depèn de si l'ordre de processament ha de ser invers (pila) o directe (cua).

Deque

Insertar un element a un vector per l'inici és molt ineficient

La nostra cua té un problema, però, i és que quan esborrem l'element de l'inici, el cost de la operació és proporcional al tamany de la cua, perquè els vectors tenen els següents costos per a cada operació:

La notació $O(1)$ indica, que per a un vector de tamany $n$, el número d'operacions a realitzar és constant (o sigui que no depèn de $n$). La notació $O(n)$ indicaria que la operació és d'un cost proporcional $n$, el tamany del vector.

Afegir un element al final d'un vector és (en general), ràpid. Malgrat no sempre és $O(1)$, només de tant en quant és costós (quan s'ha de moure el vector a una altra zona de memòria), però passa amb molt poca freqüència i per tant aquest cost més gran s'amortitza amb la resta de vegades. Per això es diu que és $O(1)$ amortitzat.

Però afegir un element al principi té un cost proporcional al tamany del vector! Això s'explica perquè els vectors tenen un sol bloc de memòria contingu, i per mantenir-lo així quan s'esborren elements al principi, cal copiar quasi tots els elements una posició cap avall, com quan una fila de gent es mou a la cadira següent en un dinar familiar.

En un deque es pot afegir a cost constant en els dos extrems

Per arreglar aquesta ineficiència, farem un canvi molt senzill però de conseqüències importants, i és utilitzar un deque. El deque és semblant al vector, però emmagatzema els elements en blocs grans d'elements consecutius, i per aquesta raó, quan afegim elements al principi, no ha de tocar els elements de més amunt.

Això fa que les operacions esmentades en un deque siguin:

Així doncs, només canviant el vector de la nostra cua Queue<T> per un deque en tenim prou per aprofitar aquesta propietat del deque. No caldrà tocar res més perquè el deque té mètodes amb exactament els mateixos noms que el vector i és suficient amb canviar el nom del contenidor.