La STL és la teva amiga
La STL (Standard Template Library) són una sèrie de llibreries, que contenen classes, funcions i functors molt útils. A PRO1 la veiem molt superficialment, i a PRO2 la veiem una mica més, però tampoc molt. No obstant, sense tornar-nos uns experts tampoc, podem aprofitar-la una mica
Llistes, les justes
Quan hem de triar una estructura de dades, molts cops acabem triant la llista. És molt típic que, si volem tenir una estructura de dades que la seva mida vagi canviant, utilitzem la llista. Però molts cops això és una mala elecció.
Si volem insertar només al final, o ens és indiferent la posició: En aquest cas, jo utilitzaria un vector. El push_back en un vector té temps constant amortitzat. Però en general, és més ràpid fer push_back en un vector que en una llista, cosa que es pot entendre quan estudiem la implementació interna de les llistes. A més, així conservem l'accés aleatori en temps constant.
Si volem insertar al principi, o principi i final: En aquest cas, jo optaria per la deque. Té un funcionament similar al vector, però podem insertar en temps constant tant al principi com al final (constant de debò, no amortitzat). El push_back a més és molt més ràpid que en un vector
I, molt important, no les utilitzem si és obvi que hem d'utilitzar una altra. Hi ha vegades que és obvi que una clsa s'ha pensat per ser resolta d'una manera determinada. Per exemple, a la pràctica del Q2 2016-2017, s'havia de generar un arbre genealògic. Aquí, el millor era utilitzar un arbre, ja sigui el que ens donen els professors, com un propi (millor el que ens donen, per temps bàsicament). Hi ha gent que va utilitzar una llista per fer-ho. Ens en podem sortir, sí, però de la mateixa manera, pot ser que no ens en sortim, i la caguem.
Si l'ordre no importa, per què mantenir-lo?
Fins ara hem estudiat els sets i els maps. Però, i si us digués que tenir-ho ordenat no sempre és positiu? Sí, ja sé que el que ens permet insertar i eliminar en temps logarítmic és justament que estan ordenats. Però existeixen un parell d'estructures a la STL, que es diuen unordered_set i unordered_map. Tenen les mateixes funcions que els sets i els maps, però internament estan implementats amb taules de hash. Què vol dir això? Doncs, que a nosaltres ens afecti, que insertar, eliminar i buscar triguen temps constant en el cas mitjà, de manera que, si l'ordre no ens importa, tot anirà molt més ràpid
Per utilitzar aquestes dues, hem d'utilitzar C++11. És el que s'utilitza a PRO2, però si vols assegurar-te de que l'utilitzes, fixa't si quan compiles tens el flag -std=c++11 o -std=c++0x. Si hi ha un dels dos, ja està. Si hi ha algun superior a C++11, igual, tot i que m'estranyaria
Per utilitzar aquestes dues, hem d'utilitzar C++11. És el que s'utilitza a PRO2, però si vols assegurar-te de que l'utilitzes, fixa't si quan compiles tens el flag -std=c++11 o -std=c++0x. Si hi ha un dels dos, ja està. Si hi ha algun superior a C++11, igual, tot i que m'estranyaria
No programis el que ja està programat
Sembla una tonteria, no? Quants cops hem fet una cosa així?
sort(v.begin(),v.end(),cmp);
Milers i milers. Molts cops, per ordenar decreixentment. Doncs bé, la pròpia STL té un functor que és greater<T>, de manera que podem fer
sort(v.begin(),v.end(),greater<T>());
Només cal que T tingui definit l'operador >
A la llibreria functional en trobem molts més d'aquest estil. Les típiques coses que podem necessitar, és probable que hi siguin
Cout, els justos
És típic. Volem veure on comença a fallar el programa, i posem molts cout per tot el programa, que ens van avisant d'on estem. Així podem identificar on està l'error. Ara, quan hem arreglat el problema, ens hem de posar a eliminar tots els cout, i és molt fàcil que ens en deixem uns quants.
Però la pròpia llibreria iostream ens dóna una eina per fer això. El flux de sortida cerr. Normalment tenim una sèrie de canals d'entrada i sortida. En C podíem utilitzar les funcions read i write per operar a través d'ells. Teníem el canal 0, que era el de lectura (en C++ hi podem accedir amb cin), el canal 1, que era el d'escriptura normal (en C++ hi podem accedir amb cout), i el canal 2, que era el d'errors (en C++ hi podem accedir amb cerr).
La gràcia d'aquest flux de sortida, és que com que utilitza un canal diferent, pel jutge és "invisible". Sí que veu el seu contingut, però no l'avalua. Per tant, si se'ns cola un, no serà un vermell, afectarà (molt poc) al rendiment i ja. De la mateixa manera, no ens cal eliminar-los mentre estiguem fent proves, redirigim la sortida normal a un fitxer, i els errors a un altre, i cap problema
Per redirigir la sortida d'errors, es fa amb 2>. Com ja sabeu, l'entrada és amb <, i la sortida estàndard amb >. Aleshores, si volem que l'entrada surti del fitxer entrada.txt, la sortida normal vagi a sortida.txt, i la d'errors a errors.txt, faríem
$./programa <entrada.txt >sortida.txt 2>errors.txt
Compte!
S'ha d'anar amb compte amb una cosa. Que el Jutge no miri la sortida d'errors, no vol dir que els professors no la vegin. I, si poseu missatges com "bitch", "puta", "polla", "hey madafaka", doncs tindreu una imatge que potser us interessa poc. Així que poseu missatges aptes per ser llegits per un professor, perquè ha passat
Compte 2!
Que el Jutge no els vegi, no vol dir que no els faci. Què vol dir això? Que faran anar el programa una mica més lent. Per exemple, al joc d'EDA, hi va haver uns quants estudiants eliminats només per això, tenien tants missatges d'error que els petava el jugador. Així que, per l'enviament definitiu, assegura't de treure'ls tots. Per les teves proves és indiferent
No es retornen iteradors
Aquesta és molt important. A la meva pràctica, per exemple, vam fer una classe Biblioteca, que en un moment havia de retornar un Text. Un Text tenia un set<string> i un vector<Frase>, de manera que vam pensar que, ja que retornar-lo sencer era una burrada de cost, podíem retornar un iterador que hi apunti, i ja està. MALAMENT! En el meu cas, era un map<string,Text>::iterator, de manera que el primer element era el títol, i el segon el text. Què passa si de cop decideixo que vull canviar la implementació interna, i tenir el text en un unordered_map? O en una estructura més diferent encara? No només hauríem de modificar aquesta classe, sinó que tocaria modificar el main, que utilitzava aquesta funció. I la idea de la programació modular, és que els mòduls siguin independents entre ells.
La solució?
La solució és clara. No cal retornar un iterador, quan podem retornar una referència. És a dir, igual que en la funció següent no copiem la matriu, sinó que indiquem on és, per què no podem fer el mateix, però retornant?
void escriure (const Matriu& mat);
Sí, quan sortim d'una funció, tot el que haguem declarat dins d'aquesta desapareix. Per això, normalment, no s'explica res d'això a PRO1. Podríem cometre l'error de fer
vector<int>& llegir(int n) {
vector<int> v(n);
for(int i=0;i<n;++i) cin >>v[i];
return v;
}
I, un cop haguem sortit, v desapareix, i falla. No obstant, la gràcia aquí és que volem retornar coses que segueixen existint, ja que fins que no destruïm la classe, tot seguirà allà.
Retornar per referència és una cosa així:
vector<int>& fila_mes_llarga(Matriu& mat){
int pos_max=0;
for (int i=1;i<int(mat.size());++i) {
if (v[i].size()>v[pos_max].size()) pos_max=i;
}
return mat[pos_max];
}
Aquí no copiem la fila aquesta, sinó que indiquem on està.
Compte a l'hora d'agafar-ho!
Quan ho agafem, hem de vigilar. Estem retornant una referència, però si volem desar-ho en una variable normal, acabarà copiant-se igualment.
vector<int> v=fila_mes_llarga(mat); //Aquí ho copiem
Per tant, ha de ser desat en una referència. Una cosa així:
vector<int>& v=fila_mes_llarga(mat);
També hem d'anar amb compte. Si ara modifiquem v, es modificarà la fila corresponent a mat. Si no volem modificar-ho, el millor que podem fer és que sigui constant
Sobrecàrrega d'operadors
Quan tu crees una classe, la classe no té els operadors que tenen els tipus bàsics. No tenim els operadors de comparació, no podem sumar, restar... Però això té una solució fàcil. I és programar-los.
Operadors de comparació
Són els primers que vaig necessitar sobrecarregar. Normalment el que es fa és programar l'operador <, i potser també el ==, i la resta es fan en funció d'aquests. Al cap i a la fi, tenim les següents propietats
a>b <-> b<a
a<=b <-> not a>b
a>=b <-> not a<b
a==b <-> not (a<b or b<a)
a!=b <-> not a==b
Com que la comparació == implica fer dos comparacions de <, molts cops preferim fer-la també, ja que així va més ràpid.
class Frase {
private:
vector<string> paraules;
...
public:
...
bool operator<(const Frase& f);
bool operator<=(const Frase& f);
bool operator>(const Frase& f);
bool operator>=(const Frase& f);
bool operator==(const Frase& f);
bool operator!=(const Frase& f);
};
bool Frase::operator<(const Frase& f) {
int n=min(paraules.size(),f.paraules.size());
for (int i=0;i<n;++i) {
if (paraules[i]!=f.paraules[i]) return paraules[i]<f.paraules[i];
}
return paraules.size()<f.paraules.size();
}
bool Frase::operator>(const Frase& f) {
return f<*this;
}
bool Frase::operator<=(const Frase& f) {
return not *this>f;
}
bool Frase::operator>=(const Frase& f) {
return not *this<f;
}
bool Frase::operator==(const Frase& f) {
if (paraules.size()!=f.paraules.size()) return false;
int n=paraules.size();
for (int i=0;i<n;++i) {
if (paraules[i]!=f.paraules[i]) return false;
}
return true;
}
bool Frase::operator!=(const Frase& f) {
return not *this==f;
}
És a dir, la funció es diu operator< (o el que sigui), i rep un altre objecte del mateix tipus. Aleshores, els comparem, i retornem cert si el paràmetre implicit és menor (o el que sigui) que l'altre
Per comparar amb una altra classe diferent, ho faríem com una funció friend. No ho poso aquí, però si algú en algun moment ho necessita, pot posar-me un comentari, i li explico
a>b <-> b<a
a<=b <-> not a>b
a>=b <-> not a<b
a==b <-> not (a<b or b<a)
a!=b <-> not a==b
Com que la comparació == implica fer dos comparacions de <, molts cops preferim fer-la també, ja que així va més ràpid.
class Frase {
private:
vector<string> paraules;
...
public:
...
bool operator<(const Frase& f);
bool operator<=(const Frase& f);
bool operator>(const Frase& f);
bool operator>=(const Frase& f);
bool operator==(const Frase& f);
bool operator!=(const Frase& f);
};
bool Frase::operator<(const Frase& f) {
int n=min(paraules.size(),f.paraules.size());
for (int i=0;i<n;++i) {
if (paraules[i]!=f.paraules[i]) return paraules[i]<f.paraules[i];
}
return paraules.size()<f.paraules.size();
}
bool Frase::operator>(const Frase& f) {
return f<*this;
}
bool Frase::operator<=(const Frase& f) {
return not *this>f;
}
bool Frase::operator>=(const Frase& f) {
return not *this<f;
}
bool Frase::operator==(const Frase& f) {
if (paraules.size()!=f.paraules.size()) return false;
int n=paraules.size();
for (int i=0;i<n;++i) {
if (paraules[i]!=f.paraules[i]) return false;
}
return true;
}
bool Frase::operator!=(const Frase& f) {
return not *this==f;
}
Per comparar amb una altra classe diferent, ho faríem com una funció friend. No ho poso aquí, però si algú en algun moment ho necessita, pot posar-me un comentari, i li explico
Operador d'assignació
Aquest és l'operador =. Tindria una forma així:
Frase& operator=(const Frase& f);//Capçalera, al fitxer .hh
Frase& Frase::operator=(const Frase& f) {
paraules=f.paraules;
return *this;
}
La idea és, bàsicament, copiar el que hi hagi, i retornar una referència a l'element actual. Això és per poder fer a=b=c=d. Quan fem c=d, retornem el valor per referència, de manera que li podem posar a b, i igual amb b
Lectura
Una cosa que hem treballat molt poc és la lectura i escriptura de variables. El que se'ns ha explicat sempre és que si fem cin>>v, llegirem la variable v. Però, per què això funciona?
Flux d'entrada
En realitat, cin no és cap funció que llegeixi. cin és un flux de dades d'entrada, que les llegeix del canal estàndard (el número 0). Nosaltres el que fem és llegir d'allà utilitzant l'operador >>, que en els fluxos està sobrecarregat per fer que la seva funció sigui llegir. Està fet de manera que els espais, tabulats i salts de línia siguin els que indiquen que s'ha acabat el valor actual. Per això, si fem
string s;
cin>>s;
I l'entrada és "Hola que tal", el que hi haurà a s és "Hola". En canvi, si inicialment haguéssim fet cin.get(), i després cin>>s, el valor retornat per cin.get() seria 'H', i a s hi hauria "ola"
Getline, la clau
Imaginem que ens diuen que a cada línia hi haurà una ordre, i una sèrie de números, que hauràs d'operar segons això. Per exemple, posem que les ordres són "SUMA", "MITJANA" i "PRODUCTE". Una cosa que podem fer és anar llegint com a string, i si veiem que no és cap instrucció, suposar que és un número, convertir-lo i operar. Però per què complicar-nos?
Podem fer una cosa així:
string s;
getline(cin,s);
getline(cin,s);
I a s ens quedarà tota la línia. És a dir, enlloc de llegir fins al primer separador, llegirà fins al primer salt de línia
Crear els nostres fluxos
Un cop tenim llegida tota la línia, queda decidir com treballem amb ella. I, com que estem acostumats a treballar amb fluxos, per què no seguir així?
Tenim una llibreria, que és sstream (amb doble s), que serveix per crear fluxos amb un string. Ens interessa, concretament, tenir un flux d'entrada (istringstream). Així que el que faríem és
string s;
while (getline(cin,s)) {
istringstream flux(s);
flux>>s;
if (s=="SUMA") {
int res=0;
int act;
while (flux>>act) res+=act;
cout<<res<<endl;
}
else if (s=="MITJANA"){
int i=0, act;
double res=0;
while(flux>>act) {
res+=act;
++i;
}
res/=i;
cout<<res<<endl;
}
else if (s=="PRODUCTE") {
int res=1;
int act;
while (flux>>act) res*=act;
cout<<res<<endl;
}
else cout<<"ERROR"<<endl;
}
Funcions útils
Hi ha una sèrie de coses que són tan, però tan típiques, que programar-les de nou és absurd. Estan ja programades, ja sigui en llibreries, o en webs i llocs així. He pensat que podia fer-ne un petit resum, i anar-lo ampliant
Convertir un string a enter
stoi
Aquesta és bastant simple. Està a la llibreria string, rep un string, i retorna l'enter al que representa. No obstant, per experiència pròpia, a vegades falla i no sé per què. En aquest cas, hi ha una altra opció
atoi
Aquesta és molt típica. En C, i a C++ ho heretem, podem passar arguments al main. És a dir, quan fem
$./programa hola adeu
Podem fer que el programa rebi "hola" i "adeu". Els rebíem com un vector de strings (strings de C), de manera que, si hi havia un número, l'havíem de convertir a enter (o al tipus que sigui). Ho fèiem amb la funció atoi (Array TO Integer). Aquesta rep un array de chars, i retorna l'enter al que representa. Per fer-ho, haurem d'utilitzar la funció c_str, de la classe string, que retorna l'array que representa al nostre string. És a dir, una cosa així
int n=atoi(s.c_str());
La funcio atoi està a la llibreria cstdlib
Implementacions pròpies
Si no ens funciona stoi, podem implementar-lo nosaltres. Per fer-ho, se m'acudeixen dues maneres
int stoi(const string& s) {
return atoi(s.c_str());
}
int stoi(const string& s) {
istringstream f(s);
int res;
f>>res;
return res;
}
La primera, bàsicament, utilitza atoi. Molt simple, i no ens compliquem la vida. La segona, per altra banda, utilitza un flux d'entrada, creat amb la llibreria sstream.
Altres usos
Aquí he mostrat com convertir un string a enter. Podem convertir a altres, per exemple, tenim stol (per convertir a long), stoll (per convertir a long long), stof i stod (per convertir a float i a double, respectivament). Amb atoi funciona igual, tenim atol, atoll...
Convertir un número a string
Per convertir a string, és prou fàcil. Tenim la funció to_string, de la llibreria string, que converteix un número a string (el número pot ser de qualsevol tipus).
Si no ens funciona la funció, sempre podem fer això:
string to_string(int n) {
ostringstream f;
f<<n;
return f.str();
}
Nombres aleatoris
Imaginem que volem un número aleatori. Això, per la pràctica de PRO2, no hauria de fer falta, però mai se sap. De qualsevol manera, mai està de més saber-ho fer
Estil C
En C, la manera de generar nombres aleatoris utilitzant funcions estàndard era utilitzant la funció rand(). Aquesta retornava un enter aleatori entre 0 i RAND_MAX (està definit a la mateixa llibreria). El que fèiem és acotar aquest interval fent el mòdul, i sumant. Una cosa així
int random(int min, int max) {
return rand()%(max-min+1)+min;
}
És senzill. Volem tenir max-min números. Fem el mòdul, i tenim un número a l'interval [0,max-min]. Per tant, li sumem el mínim, i tindrem un número a l'interval [min,max].
Per fer que sigui gairebé aleatori, hem de fer que a cada execució del programa sigui diferent. Això es faria posant la crida següent a l'inici del main
srand(time(NULL));
La funció srand serveix per inicialitzar la seed dels nombres aleatoris. La funció time retorna un valor que serà diferent cada vegada que la cridem, tampoc cal saber gaire més.
Aleshores, per fer això, hauríem d'incloure la llibreria cstdlib (per les funcions rand i srand), i la llibreria ctime (per la funció time)
Estil C++
Com hem vist, a C la cosa estava molt limitada. Podíem generar nombres aleatoris, sí, però només enters, i ens havíem de complicar massa la vida. Per això a C++ apareix la llibreria random, que ens permet generar nombres pseudoaleatoris molt millor
Primer de tot, hem de fer un generador. Tenim una classe per això, que és default_random_engine. Un cop tenim aquest generador, podem utilitzar les diverses funcions que té per crear nombres aleatoris. Les més interessants per nosaltres són uniform_int_distribution i uniform_real_distribution, que generen nombres aleatoris utilitzant una distribució uniforme (la qual té la característica que tots els seus elements tenen la mateixa probabilitat). En tenim altres, com bernoulli, binomial, exponencial, poisson, normal... Les podem veure aquí. Un exemple d'us seria
int main() {
default_random_engine generador;
uniform_int_distribution<int> aleatori(0,9);
for (int i=0;i<10;++i) {
cout<<aleatori(generador)<<endl;
}
}
És a dir, declarem el generador i el functor que ens farà nombres aleatoris. Cada cop que volem cridar nombres aleatoris, cridem al functor, passant-li com a paràmetre el generador.
Temps
A vegades dubtem entre dues implementacions, i volem comprovar si afecten significativament a l'eficiència. Estant a PRO2, no sabem gaire de calcular eficiència, així que ens pot ser útil mirar-ho empíricament. I, com que no ens posarem a cronometrar-ho amb el rellotge, és útil aprendre a fer-ho amb l'ordinador
Des de la consola
Aquesta opció només l'he provat a consoles de Linux. Suposo que en altres hi ha manera de fer-ho, però no la conec. Bàsicament utilitzem l'instrucció time. Així:
$time ./programa.exe <entrada.txt >sortida.txt
És important que l'entrada vingui d'un fitxer, ja que si la posem manualment, aquest temps també el compta. I ens pot tergiversar els càlculs. La sortida prefereixo redirigir-la perquè així només ens surti a la consola el temps.
Editant el codi
Aquesta opció també és útil, tot i que prefereixo la primera, ja que no ens fa modificar el codi. Utilitzarem la llibreria ctime, que té una funció (clock) que ens retorna els ticks de rellotge consumits fins al moment. Aquests depenen de la unitat, però tenim una constant, que és CLOCKS_PER_SEC, que serveix per convertir els ticks de rellotge a segons.
Sabent això, la idea és agafar els ticks a l'inici i al final, calcular la diferència, i convertir a segons. És a dir:
int main() {
int c=clock();
...
c=clock()-c;
cout<<double(c)/CLOCKS_PER_SEC<<endl;
}
Per altra banda, si no volem saber el temps en segons, sinó que volem comparar entre dues opcions, el més senzill és mostrar c directament, sense passar-ho a segons
Per altra banda, si no volem saber el temps en segons, sinó que volem comparar entre dues opcions, el més senzill és mostrar c directament, sense passar-ho a segons
Limits numèrics
Mai us ha passat que voleu tenir el nombre més gran possible? O el més petit? O qualsevol dada així? És una putada, perquè clar, la mida dels números pot variar en funció del sistema
Mètode cutre
Per aquest mètode necessitem conèixer la representació interna dels números. Sabem que els enters amb signe es representen utilitzant Complement a 2, de manera que el bit de més pes és negatiu, i la resta positius. Així, si tenim nombres de 32 bits, el nombre més petit possible serà 0x80000000, i el més gran 0x7FFFFFFFF.
Per altra banda, com a dada important, el -1 és 0xFFFFFFFF. Sabent això, ja podem aconseguir els mínims i màxims
int max=(-1)>>1;
int min=1<<(sizeof(int)*8-1);
És a dir, la primera és agafar el -1 (0xFFFFFFFF), i desplaçar-lo una posició a la dreta (quedant 0x7FFFFFFF). La segona, per la seva banda, és desplaçar 1 cap a la dreta tantes posicions com bits representin el número menys 1. Així tindrem un 1 al bit de més pes
Per fer els respectius mínims i màxims d'enters sense signe, és encara més fàcil. El mínim sense signe és 0 (òbviament). El màxim serà -1 (per una raó molt simple, -1 és 0xFF..., que si no hi ha signe, és el màxim).
Mètode guai
Aquest mètode és el que us recomanaria. No ens compliquem la vida en càlculs estranys. Què passaria si intentem calcular el mínim d'un enter amb signe en un sistema on els bytes no són de 8 bits? Perquè un byte no necessàriament és de 8 bits, malgrat que és el més comú
Per fer-ho bé, utilitzarem la llibreria limits. Aquesta conté una classe, que és numeric_limits, amb funcions que ens permeten obtenir informació sobre cada tipus numèric (no només de tipus enter, també de coma flotant). Les funcions que em semblen més útils són:
min: En els enters, retorna el número més petit representable. En coma flotant, el més petit positiu i diferent de 0 (un possible valor de retorn seria 1.17549e-038).
max: Retorna el màxim valor finit
lowest: En enters, igual que min. En coma flotant, normalment retorna -max()
En general, amb aquestes 3 ja faríem. En tenim moltes més, les podeu consultar aquí
int minima_diferencia(const vector<int>& v) {
int min_dif=numeric_limits<int>::max();
int n=v.size();
for (int i=0;i<n-1;++i) {
int a=v[i];
for (int j=i+1;j<n;++j) {
int aux=abs(a-v[j]);
if (min_dif>aux) min_dif=aux;
}
}
return min_dif;
}
Un exemple d'us seria aquest
C++11
C++11 és una actualització de C++ que apareix al 2011 (sí, sóc un geni). Inclou moltes coses molt i molt útils. Està més explicada aquí, però faré un resum de coses que poden ser útils
Inferència de tipus
No us heu plantejat que hi ha situacions on el tipus d'una variable té el nom molt llarg, i realment no cal que ho sigui. Si tenim un map<int,pair<string,int>>, i volem fer-ne un iterador, quedaria una cosa així
map<int,pair<string,int>>::iterator
Molt llarg. I, si volem fer un for, queda encara més llarg
for(map<int,pair<string,int>>::iterator it=m.begin();it!=m.end();++it)...
I, realment, la funció begin() sempre retorna un iterador. Així que, per què no deixar al compilador que dedueixi ell sol?
Doncs C++11 permet fer això. Utilitzant la paraula clau auto (que abans tenia un altre significat), li diem que determini ell mateix el tipus
for (auto it=m.begin();it!=m.end();++it)...
En general, la idea d'això és fer-ho en casos on sigui molt obvi, i al moment. No serveix fer
auto x;
...
x=m.begin();
Hem de tenir sempre un inicialitzador, que utilitzem per saber quin és el tipus
For en un rang
Sóc molt fan d'aquesta. Permet recórrer tota una estructura de dades, de manera més senzilla. Bàsicament fem:
for (T x:estructura) {
...
}
Sempre i quant l'estructura emmagatzemi elements de tipus T. Per exemple, per recórrer una llista d'enters faríem
list<int> l;
...
for (int x;l) {
...
}
Això equivaldria a fer
for (list<int>::iterator it=l.begin();it!=l.end();++it) {
int x=*it;
...
}
Però què passaria si volem modificar l'estructura? Per exemple per llegir-la. En aquest cas, faríem
for (int& x:l) ...
Això serveix perquè x faci referència als elements, permetent-nos modificar l'estructura.
Com deveu intuir, això només serveix amb estructures que tinguin iteradors. Per altra banda, utilitzant la paraula clau auto, podem fer coses molt guais
Llistes d'inicialització
Això és molt útil encara. Imaginem que volem fer un programa que faci coses relacionades amb els escacs. I penses "ei, anem a fer un vector amb els moviments possibles del cavall". Aquest no canviarà, de manera que el podem fer constant. Però com l'inicialitzem?
Abans de C++11, amb un vector no es podia fer, i havíem d'utilitzar un array. Amb C++11, podem fer això amb les estructures de dades de la STD:
const vector<int> v={1,2,3};
I v tindrà els elements 1, 2 i 3.
Recursivitat: La clau
Una llista d'inicialització es defineix recursivament. Podem dir que està composada per una de les dues opcions següents:
-Una sèrie d'elements, separats per comes
-Una sèrie de llistes d'inicialització, separades per comes
És bastant senzill, aleshores. Podem fer
vector<pair<int,int>> SALTS={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
És a dir, s'analitzen primer les llistes més internes. Com que sabem que ha de ser un vector<pair<int,int>>, sabem que les llistes internes seran parelles.
/*
* Pre: v no buit
* Retorna el mínim i el màxim del vector
* Post: el primer element de la parella retornada és el mínim,
* El segon és el màxim
*/
pair<int,int> min_max(const vector<int>& v) {
int minim, maxim;
minim=maxim=0;
for (int x:v) {
if (x<minim) minim=x;
if (x>maxim) maxim=x;
}
return {minim,maxim};
}
Com podem veure, podem utilitzar les llistes d'inicialització, no només per inicialitzar variables, sinó també per crear el valor de retorn d'una funció
