Aprendre a programar 6 - Vectors i Matrius

Imaginem el següent problema: Tenim una seqüència no buida d'enters, i volem comptar quants són iguals a l'últim (és a dir, el P14130). Com ho podem fer? Si fos el primer, seria fàcil, faríem un tractament seqüencial i ja. Però volem comparar amb l'últim element, així que no ens queda una altra opció que desar tots els números que llegim. Com?

Si sabéssim que llegirem 4 números, podríem fer:

int primer, segon, tercer, quart;
cin >>primer>>segon>>tercer>>quart;
int r=0;
if (primer==quart) ++r;
if (segon==quart) ++r;
if (tercer==quart) ++r;
cout <<r<<endl;

Què passa? Que la quantitat d'elements és n, i ens la diran. Com podem fer-ho, aleshores?

Els vectors

Un vector, en el context de la programació, és una estructura que conté una sèrie de dades, una darrere l'altra, ubicades en memòria una darrere l'altra. Quan crees un vector, tens una única variable, a través de la qual pots accedir a tots els elements del vector. 

Al lio. 

Com es declara un vector?

Hi ha tres formes de declarar un vector:

vector<T> v;//Crea un vector buit, que es diu v

vector<T> v(n);//Crea un vector de mida n, que es diu v

vector<T> v(n,algo);//Crea un vector de mida n, que es diu v, i que a cada una de les n posicions conté algo

En els tres casos, els elements que conté el vector són de tipus T. Recordem que, per utilitzar els vectors, necessitem incloure la llibreria vector, fent

#include <vector>

Com s'accedeix als elements d'un vector?

Als elements d'un vector s'hi accedeix mitjançant un índex. Si vols accedir al primer element (element 0), fas v[0] (o v.front()). Per accedir al segon (element 1), v[1]. Per accedir a l'últim (element n-1), v[n-1] (o també es pot fer v.back()). És a dir, es comença a comptar pel 0, i a partir d'aquí, es tenen tots els elements. 

Funcions útils:

Operador =:

Serveix per copiar un vector a un altre. v=v2 el que faria és copiar tot el vector v2, i posar-ho a v. Té cost lineal, ja que se l'ha de recórrer sencer

size:

Retorna la mida del vector. És a dir, si tenim un vector del qual no sabem la mida, i fem

int n=v.size();

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

Ens recorrem tot el vector

resize(int):

Canvia la mida del vector. Si la nova mida és menor que l'actual, cost constant. Si és més gran, pot ser constant o pot ser lineal respecte la nova mida. 

push_back(T):

Augmenta en 1 la mida, i afegeix l'element que rep al final. Té cost constant amortitzat, que vol dir que, a la llarga, el cost és constant. Això és perquè a vegades té cost lineal, mentre que la majoria de vegades el té constant. Si podem evitar-lo, l'evitarem, però si no ens queda cap altra opció, el podem utilitzar. 

A resoldre el problema

Un cop sabem com es fa per declarar vectors i per operar amb ells, anem a resoldre el problema

int n;

cin >>n;

vector<int> v(n);

for (int i=0;i<n;++i) cin >>v[i];

int r=0;

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

    if (v[i]==v[n-1]) ++r;

}

cout <<r<<endl;

És a dir, una mica el que esperaríem. Llegim la n, fem un vector de mida n, llegim els n elements, i finalment comptem quants són iguals a l'últim

Vectors i funcions

Què passa si volem passar un vector a una funció? Imaginem que volem comptar els elements en una funció. Com ho faríem?

Una opció intuïtiva és la següent:

int comptar(vector<int> v) {

    int n=v.size();

    int r=0;

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

        if (v[i]==v[n-1]) ++r;

    }

    return r;

}

Si ho provem, funciona. Però no és del tot correcte. Recordeu que vaig explicar que els paràmetres d'una funció es passaven per còpia? Imagineu que tenim un vector de mida 1.000.000. Hauríem de copiar 1.000.000 d'elements, només per comptar després. Molt cost, no?

Referències i referències constants:

Una cosa que podríem fer és passar el vector per referència. Això, si volem modificar-lo, és bàsic. No obstant, si no tenim intenció de modificar-lo, pot portar-nos problemes, ja que ens podem equivocar i canviar alguna cosa. Per això apareixen les referències constants. 

int comptar(const vector<int>& v) {

    int n=v.size();

    int r=0;

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

        if (v[i]==v[n-1]) ++r;

    }

    return r;

}

Ara ja no copiaríem tot el vector, sinó que indicaríem a la funció on trobar-lo. I també li estaríem dient "ei, es mira però no es toca ehh". No es podrà modificar res del vector des d'aquesta funció. En canvi, podríem fer una funció

void llegir(vector<int>& v) {

    for (int i=0;i<int(v.size());++i) cin >>v[i];

}

Aquesta funció funciona perfectament, i serveix per llegir els elements del vector. Una cosa destacable és aquell "i<int(v.size())". Això és perquè la funció size retorna un unsigned int, i nosaltres estem comptant amb un int. Per tant, ho convertim explícitament i ja està. Si no ho convertim, el compilador es queixarà

Un altre exemple. Imaginem que volem invertir una seqüència d'enters (el P67268). Com ho faríem?

void llegir(vector<int>& v) {

    for(int i=0;i<int(v.size());++i) {

        cin >>v[i];

    }

}

void girar(vector<int>& v) {

    int n=v.size();

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

        swap(v[i],v[n-i-1]);

    }

}

void mostrar(const vector<int>& v) {

    for (int i=0;i<int(v.size());++i) {

        if (i!=0) cout <<' ';

        cout <<v[i];

    }

    cout <<endl;

}

int main() {

    int n;

    while (cin >>n) {

        vector<int>v(n);

        llegir(v);

        girar(v);

        mostrar(v);

    }

}

Fixeu-vos que aquí he fet un main molt mínim. Declaro les variables que necessitaré (el vector i la mida), i crido a les funcions que ho fan tot. Una per llegir la seqüència, una per girar-la i una per mostrar-la. La gent, a PRO1, tendeix a fer-ho tot en el main, quan és molt millor fer-ho en funcions, com he fet jo

La funció que té una mica de gràcia és girar. El que faig és un for que recorre mig vector, i canvia la posició i per la n-i-1. Això serveix per canviar la primera per la última, la segona per la penúltima... Si ho féssim pel vector sencer, tindríem un problema, perquè intercanviaria cada parella 2 cops, quedant igual que al principi. Per fer l'intercanvi utilitzo la funció swap, que ja està programada, i el que fa és canviar els valors de dues variables. Ho he fet per introduir-ne l'us, ja que en aquest cas, gairebé seria millor mostrar el vector a la inversa, fent un recorregut des de n-1 fins a 0 (inclòs). 

Aquest programa també el podríem fer sense utilitzar vectors, utilitzant una funció recursiva. El codi seria el següent:

void recursiva(int i, int n) {

    if (i==n) return;

    int num;

    cin >>num;

    recursiva(i+1,n);

    if (i+1!=n) cout <<' ';

    cout <<num;

}

void girar(int n) {

    recursiva(0,n);

    cout <<endl;

}

int main () {

    int n;

    while(cin >>n) girar(n);

}

Bàsicament el que fa això és fer n+1 crides recursives. A la última no fa res, sinó que surt. A les altres n, el que fa és llegir el número, cridar-se a ella mateixa, i mostrar el número

I els strings?

Recordeu que quan vaig parlar dels strings, vaig dir que amb els vectors ampliaríem la informació? Doncs ja toca. Un string vindria a ser com un vector de chars, de manera que podem treballar amb ell com si fos un vector. Per exemple, si volguéssim invertir l'ordre de les lletres d'una paraula (P78548), podríem fer un programa com el següent:

void girar(string s) {

    int n=s.length();

    for (int i=n-1;i>=0;--i) {

        cout <<s[i];

    }

    cout <<endl;

}

int main () {

    string s;

    while (cin >>s) {

        girar(s);

    }

}

Aquí sí que no intercanvio els elements, sinó que recorro el string a la inversa. Com a apunt, no el passo per referència perquè tampoc és tan gran, si tinguéssim la bíblia en vers, el passaria per referència constant

Per últim, podem resoldre el problema P50497, per mirar si un string és un palíndrom (és a dir, si és capicua). Podríem fer-ho així:

bool es_palindrom(const string& s) {

int n=s.length();

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

if (s[i]!=s[n-i-1]) return false;

}

return true;

}

El que fem, bàsicament, és recórrer el vector, comparant el primer amb l'últim, el segon amb el penúltim... Si en algun moment són diferents, ja retornem false directament, no cal mirar res més. Si acabem de recórrer tot, voldrà dir que no hem trobat cap moment on siguin diferents, per tant, és capicua, i retornem true

Avís pels programadors de C:

Suposo que haureu vist que això és molt diferent a com es feia en C. En C s'utilitzen arrays enlloc de vectors. Un array sempre es passa per referència, de fet, no hi ha cap manera de passar-lo per còpia. Per altra banda, suposo que haureu notat que té avantatges evidents (calcular la mida sense trucs estranys, poder-li canviar la mida quan vulguem...)

El que en C seria

int vec[n];

En C++ és 

vector<int> vec(n);

Per calcular la longitud en C faríem

int n=sizeof(vec)/sizeof(vec[0]);

Mentre que en C++, fem

int n=vec.size();

Els arrays es poden utilitzar també en C++, però no a PRO1. Utilitzar-los a PRO1 és gairebé sinònim de suspendre l'assignatura, per la qual cosa jo els evitaria a tota costa.

Matrius:

Què és una matriu? La podem veure com una matriu matemàtica. És un vector que a dins conté un vector. Això fa que tingui forma de taula. 

Com es declara?

Realment això és una mica guarro de fer. Mentre que en C es feia

int mat[n][m];

I ja teníem una matriu de mida n*m, aquí és una cosa més complicada. Hem dit que és un vector de vectors, no? Per tant, hauríem de fer un vector de vectors. Si ho féssim a pèl, quedaria una cosa així

vector<vector<int> > mat;

Hi ha d'haver un espai entre el primer > i el segon >, si utilitzem versions de C++ anteriors a C++11. La que s'utilitza a PRO1 és anterior, per tant el posarem. Jo és possible que me'ls oblidi, però no és correcte no posar-los

Què passa? Aquesta matriu està buida, té mida 0*0. Anem a donar-li la quantitat de files

vector<vector<int> > mat(n);

Perfecte. Ara volem donar-li també a les columnes. Com que hem quedat en que una matriu era un vector de vectors, volem dir-li que, a cada una de les n posicions (que representen les files) ens posi un vector de mida m. Com ho fem?

vector<vector<int> > mat (n, vector<int>(m));

Molt lleig, no? És una guarrada, la veritat, però és el que hi ha. Podem fer-ho una mica menys lleig utilitzant la sentència typedef. Aquesta serveix per "definir nous tipus". En realitat no crea nous tipus, sinó que ens serveix per definir una macro. És a dir, si fem

typedef unsigned char byte;

El que fa això és que la última paraula que li haguem posat (byte) passa a voler dir tot el que hi ha abans (unsigned char). Si volem declarar una variable d'un byte, en qualsevol moment podem utilitzar

byte b=255;

Això ho podem traslladar a les matrius. Sabem que una fila d'una matriu és un vector, no? Doncs fem

typedef vector<bool> Filabool;

I a partir d'aquest moment, Filabool voldrà dir vector<bool>. Podem aprofitar-ho per fer

typedef vector<Filabool> Matbool;

I ja està, Matbool serà una matriu de booleans. Els typedef es poden fer en diversos llocs, però per evitar-nos problemes, jo els faig sempre entre el "using namespace std", i la primera funció que haguem declarat. A l'hora de declarar una matriu de mida n*m, quedaria així:
typedef vector<int> Fila;
typedef vector<Fila> Matriu;
...
...

Matriu mat(n,Fila(m));

Com treballem amb matrius?

Exactament igual que amb els vectors. Tenim l'operador [], que serveix per accedir a la fila que vulguem. Per exemple, imaginem que tenim una matriu, i volem accedir a la fila i, columna j, per incrementar el seu valor. Podríem fer

++mat[i][j];

Tenim també la funció size(), que retorna la quantitat de files que té la matriu. Per exemple, si volem llegir una matriu, fem:

typedef vector<int> Fila;

typedef vector<Fila> Matriu;

void llegir_matriu(Matriu& mat) {

    int n=mat.size();

    int m=mat[0].size();

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

        for (int j=0;j<m;++j) {

            cin >>mat[i][j];

        }

    }

}

Al cap i a la fi, si és una matriu, totes les files han de tenir la mateixa quantitat de columnes. 

També tenim altres funcions, com push_back(), resize(), i totes les que té definides un vector. No obstant, les importants són l'operador [], l'operador =, i la size(). 

Uns quants problemes de matrius:

Imagineu que volem fer el problema P28318. Com el faríem?

typedef vector<int> Fila;
typedef vector<Fila> Matriu;

void llegir_matriu(Matriu& mat) {
    int n=mat.size();
    int m=mat[0].size();
    for (int i=0;i<n;++i) {
        for (int j=0;j<m;++j) {
            cin >>mat[i][j];
        }
    }
}

void fila(const Matriu& mat, int i) {
    cout <<"fila "<<i<<':';
    int m=mat[i-1].size();
    for (int j=0;j<m;++j) {
        cout <<' '<<mat[i-1][j];
    }
    cout <<endl;
}

void columna(const Matriu& mat, int j) {
    cout <<"columna "<<j<<':';
    int n=mat.size();
    for (int i=0;i<n;++i) {
        cout <<' '<<mat[i][j-1];
    }
    cout <<endl;
}

void element(const Matriu& mat, int i, int j) {
    cout <<"element "<<i<<' '<<j<<": "<<mat[i-1][j-1]<<endl;
}

int main () {
    int n, m;
    cin >>n>>m;
    Matriu mat(n,Fila(m));
    llegir_matriu(mat);
    string s;
    while (cin >>s) {
        if (s=="fila") {
            int i;
            cin >>i;
            fila(mat,i);
        }
        else if (s=="columna") {
            int j;
            cin >>j;
            columna(mat,j);
        }
        else {
            int i, j;
            cin >>i>>j;
            element(mat,i,j);
        }
    }
}

És a dir, llegim la matriu, i anem llegint les instruccions que ens demanen. Si ens demanen la fila, llegim quina fila ens demana, i la mostrem. Igual amb la columna. Si ens demanen un element, llegim les posicions i les mostrem. A destacar, que ells comencen a comptar per 1, però nosaltres per 0. Hem de restar 1 al número que ens donen

Ara fem el problema P27498. Ens demana transposar una matriu. Com ho faríem?

void transposa(Matriu& m) {
    int n=m.size();
    for (int i=0;i<n;++i) {
        for (int j=0;j<i;++j) {
            swap(m[i][j],m[j][i]);
        }
    }
}

Què fem aquí? Imaginem que la matriu la tenim dividida en 3 trossos. Un és la diagonal (quan i=j). L'altre és el triangle inferior (quan j<i). El tercer és el triangle superior (quan j>i). El que demana el problema és intercanviar files per columnes. Això fa que la diagonal es mantingui, el triangle inferior es col·loca al lloc del superior, i el superior al lloc de l'inferior. Això faria que qualsevol posició m[i][j] s'intercanviés per la posició m[j][i]. Però compte, no podem recórrer tota la matriu, perquè aleshores intercanviaríem dos cops les dues posicions, quedant-nos igual. Per això, el que hem de fer és recórrer només un dels dos triangles (en el meu cas, l'inferior), i intercanviar.

Excepció: vector<bool>

Quan emmagatzemem un vector<T> en memòria, el que fa internament és crear un array de T. El que passa és que el byte (recordem que 1 byte no sempre són 8 bits, podria ser més) és la mínima unitat amb la que pot treballar un processador. Per tant, un bool ha d'ocupar 1 byte, quan per dos valors només cal un bit. Aleshores, si volem desar 1000 booleans en un vector, si utilitzéssim un array necessitaríem 1000 bytes de memòria per ell. No obstant, només caldrien 1000 bits. El que es fa és crear una classe diferent pel vector de booleans, que el que fa és exactament això. Que cada element, a la pràctica, ocupi 1 bit enlloc d'un byte. Suposant que estem en un ordinador on el byte ocupa 8 bits, i que ho emmagatzemem en un array de chars, quan li demanem que ens doni el valor de v[i], el que faria internament és similar al següent:

return vec[i/8]&(1<<(i%8))!=0

Si volguéssim consultar l'element 15, per exemple, sabem que aquest està al segon element del l'array (15/8 dóna 1, que és la segona posició d'un array). 1<<(i%8) el que fa és posar un 1 a la posició i%8, i 0 a la resta. Això es coneix com a màscara. Fent la & entre el contingut d'aquesta posició, i la màscara, tindríem 0 si el valor aquest és fals, i diferent de 0 si és cert


I ja estem acabant tot el que es fa a PRO1. Al proper article, més problemes resolts