Aprendre a programar aux - La STL

Amb l'aparició de C++, apareixen dues coses que ho canvien tot. Són les classes i els templates (que ho podríem traduir a plantilles). Les classes, de fet, són el que històricament va fer que C++ s'escindís de C (i per això, inicialment, es coneixia com a "C amb classes", o "C amb classe". Però, si les classes fan que C++ s'escindeixi de C, els templates aporten a C++ la seva màgia.

Explicaré què són les classes i una mica de POO (Programació Orientada a Objectes) en algun altre article, segurament. Si a algú li interessa, a internet hi ha molta informació sobre això.

Què és un template?

Imaginem que volem crear una classe per emmagatzemar dades. Com les definim internament? Com a enter? Com a caràcters? Què passa si volem emmagatzemar dades més grans? 

Un template és la solució a aquest problema. És una plantilla que actua com si fos un tipus. Després, quan fem una instància de la classe o una crida de la funció on l'utilitzem, es substitueix el template pel tipus en qüestió. Per posar un exemple, si declarem la funció següent:

template<typename T>

T max (T a, T b) {

    return a>b?a:b;

}

Si cridem la funció max amb dos enters, ens retornarà un enter. Si la cridem amb dos double, ens retornarà un double. Per declarar-ho es fa així:

template<typename nom_tipus> tipus_retorn nom_funcio(paràmetres) {codi_funcio}

És a dir, si ho dividim en parts:

template<typename nom_tipus>

Això el que fa és crear la plantilla, que es diu nom_tipus. 

tipus_retorn nom_funcio(paràmetres) {codi funcio}

Això és simplement una declaració d'una funció. El template en qüestió estarà a algun paràmetre, i potser també a tipus_retorn

Normalment, aquestes dues parts estan separades línies diferents, com en el meu exemple

Això es pot extendre a una classe. Podem fer

template<typename T>

class Hola {

...

}:

Hi ha gent que utilitza la paraula class enlloc de la paraula typename, però jo penso que és barrejar coses. No obstant, és qüestió de gustos. Podem veure coses així, i és el mateix que abans
template<class T>
class Hola {
...
};

La STL

Aprofitant l'existència de classes i de templates, es poden crear moltes coses. Per exemple, podem crear una estructura de dades que emmagatzema dades de manera contigua (és a dir, un vector). Així que l'Alexander Stepanov va pensar que es podia fer una sèrie de llibreries incorporant funcions i classes que utilitzin aquestes templates. És a dir, igual que a C hi havia una sèrie de llibreries estàndard, aquí en farien unes quantes més aprofitant que ara hi ha noves eines. Li va dir Standard Template Library, coneguda popularment com a STL. Aquesta és suportada per tots els compiladors, i funciona a tots els sistemes operatius. És molt, molt extensa, i té moltes coses. Jo crec que si dic que no sé per què serveixen la meitat de llibreries, em quedo curt. Per tant, aquí només hi ha un resum, molt simple, amb les coses que són més conegudes. No obstant, es pot consultar tota la informació a diverses pàgines. Jo personalment en recomano dues:
http://www.cplusplus.com/reference/: Està molt, però molt ben feta. Exemples, bones explicacions... Jo la utilitzo molt
http://en.cppreference.com/w/: D'informació és bastant igual que l'anterior, però el disseny, almenys a mi, em dificulta molt la seva lectura. No obstant, és un dels documents disponibles al Jutge per fer examens i concursos, juntament amb la Xuleta d'EDA. Acostumar-s'hi, per tant, és una bona idea

Contenidors

El primer tipus són els contenidors. Com diu el nom, contenen dades. N'hi ha molts. A PRO1 se n'utilitzen un o dos, a PRO2 uns quants més, a EDA encara més...Aquí, una petita llista. Si no dic el contrari, cada un el trobem a una llibreria amb el mateix nom

pair

És, probablement, l'estructura més simple. Serveix per desar dos dades juntes. Les dades poden ser de diferent tipus. Té dos elements públics, que són first, i second. S'hi accedeix utilitzant el . per separar entre el nom de la parella i el nom de l'element. 

pair<int,int> p;

p.first=3;

p.second=4;

Té un parell d'operadors, que són el constructor i l'assignació. Podem fer

pair<int,int> p(3,4);

...

p=pair<int,int>(60,70);

Si utilitzem C++11 o posterior, podem inicialitzar-lo amb una llista d'inicialització, amb dos elements. Per exemple
pair<int,string> p={10,"hola"};

De la mateixa manera, té programades dues funcions, que són el swap (per intercanviar dues parelles), i el make_pair. El make_pair rep dos paràmetres, i retorna una parella que els conté. Per exemple

pair<sting,string> p=make_pair("Los amantes de Teruel: ","Tonta ella, tonto él");

La implementació de la parella està a la llibreria utility

vector

Típica. Ens fem un tip d'utilitzar-los. Des d'un punt de vista de les estructures de dades, sabem que s'emmagatzemen en posicions de memòria contínues (és a dir, v[1] està just després de v[0]), que permeten accés aleatori (podem accedir a l'element que vulguem) en temps constant, i insertar i eliminar elements al final en temps constant amortitzat. En canvi, al principi i al mig el temps és lineal

Constant amortitzat vol dir que, quan utilitzem el push_back, reservem més espai del que ens cal. Així, després, en podem fer uns quants més que ens surten gairebé gratis. 

Té moltes funcions i operadors, evidentment, però les que utilitzem són principalment

-begin: Retorna un iterador que apunta al primer element

-end: Un iterador que apunta a l'element "de després de l'últim". És a dir, no forma part del vector com a tal

-size: Retorna la mida

-resize: Canvia la mida del vector. Si ha d'eliminar elements, elimina els del mig

-empty: Retorna cert si la mida del vector és 0

-operador []: Serveix per accedir als elements. Li passes la posició respecte a l'inici, i et retorna una referència a l'element
-operador =: Bàsicament, el que fa a tot arreu. Copia un vector a un altre. Té cost lineal respecte la mida del vector

-front: Retorna el primer element

-back: Retorna l'últim element

-push_back: Incrementa en 1 el vector, i posa l'element en qüestió a la última posició

-pop_back: Elimina l'últim element del vector

vector<bool>

Ja que un vector, per emmagatzemar, internament utilitza un array, ens trobem amb un problema, i és que un booleà ocupa 1 byte, mentre que només necessita 1 bit. Utilitzant un array, estaríem utilitzant 8 vegades més espai del necessari. Imaginem, per exemple, que tenim un mapa 100*100, i volem desar quines posicions hem visitat. Podem utilitzar una matriu de booleans mida 100*100. Si utilitzem un array normal, ocuparem 100.000 bytes. Amb un vector<bool>, està optimitzat de manera que utilitzarà una mica més de 100.000 bits. Compte, no és despreciable, si enlloc de tenir 100*100 fos 1000*1000, comença a ser molt gran. Hi ha moltes coses del vector que aquest no té, però perquè tampoc és que calguin. Amb l'operador [], i l'inicialitzador, ja fem

list

De les estructures que s'estudien a PRO2, probablement la més inútil, al menys per mi. Com a curiositat, en el joc d'EDA de la FIB, hi havia una plantilla amb totes les inclusions de la stl que consideraven que utilitzaríem. Unes quantes ni les havíem estudiat. La list no hi era

Bàsicament és una estructura que té accés lent als elements, però per contra, insercions i eliminacions ràpides. Els elements no estan junts, sinó que té una implementació que cada element apunta a l'anterior i al  següent. És una estructura de dades recursiva. Anem a veure les seves funcions:

-begin i end: Retornen respectivament un iterador al primer i un iterador a l'últim element

-empty: retorna si està buit o no. Igual que al vector, vaja

-size: No cal dir res

-front i back: El mateix, primer i últim element

-push_front, pop_front, push_back i pop_back: El mateix que en el vector, però aquí tots tenen temps constant sempre

-insert: Aquest al vector no l'hem vist. Hi és, però no s'utilitza gaire. Té diverses versions, la més típica és la que rep un iterador i un element, i inserta l'element a la posició que li hem dit. Retorna un iterador que apunta al nou element. Les altres versions, i exemples, aquí

-erase: Ve a ser com l'insert, però al revés. Rep un iterador i elimina l'element aquell. Retorna un iterador que apunta a l'element següent. Compte, l'iterador que hem utilitzat com a paràmetre ja no existeix

-splice: Rep un iterador i una llista, i inserta tots els elements de la llista a continuació de l'element apuntat per l'iterador

Com a curiositat, en C++98, la funció size trigava temps lineal. En C++11, algú va pensar que, sent tan fàcil fer que tingui temps constant, es podien fer les coses bé 

deque

Ve a ser un vector on podem insertar en temps constant a l'inici, a més de poder-ho fer al final. El nom és un acrònim de "double ended queue". Una cua és una estructura de dades que només permet insertar al final. Aquesta permet també al principi i, a més, permet accedir als elements com un vector

En essència, té el mateix que un vector, afegint-li el push_front i el pop_front, que existeixen també al vector, però allà amb temps lineal

queue

Suposo que tocava, no? Aquesta és una estructura de dades tipus FIFO (acrònim de First In-First Out, és a dir, que el primer element insertat és el primer extret. S'utilitza per programar l'algorisme de Cerca en Amplada, o BFS, entre altres coses. Les seves funcions són:

-empty i size: Ja les coneixem

-front: primer element

-back: últim element. Si utilitzes una cua, no t'hauria de caldre utilitzar-lo, però hi és

-push: Inserta un element al final

-pop: Elimina el primer element

priority_queue

Aquesta és una estructura curiosa. És com una cua, és a dir, només podem eliminar el primer element, i accedim només a ell. No obstant, es manté ordenada, de manera que l'element insertat no va al final. Normalment ordena utilitzant l'operador <, i utilitza un vector per emmagatzemar les dades, però això no cal que sigui així. Podem dir-li que ho ordeni de diferent manera, o que ho emmagatzemi d'una altra manera. Només cal que permeti accés aleatori, operacions front(), push_back() i pop_back(). Si no utilitzem el vector, normalment és per utilitzar una deque, tot i que es poden utilitzar també llistes

La cua de prioritat s'utilitza per programar l'algorisme de Dijkstra, entre altres coses

Té les mateixes funcions que la cua, ja que realment, és una cua. No obstant, cal veure com la declarem.

Tenim la declaració típica, que és, si volguéssim fer una cua de prioritat d'enters
priority_queue<int> pq;
Després, si volem que ordeni diferent, haurem d'utilitzar la declaració completa. Li hem de passar el tipus, el contenidor, i l'ordenació. Un exemple, si volem utilitzar una cua de prioritat ordenada amb l'operador greater, podem fer
priority_queue<int,vector<int>,greater<int>()> pq;

stack

Aquesta és una estructura de dades tipus LIFO (Last In-First Out). L'últim element insertat és el primer que surt. Té exactament les mateixes funcions que la cua, però per accedir al primer element, enlloc de tenir la funció front, tenim la funció top, i no podem accedir a l'element de sota

Internament, per emmagatzemar les dades locals de les funcions, s'utilitza una pila. Per això, si fem una funció recursiva que no arriba mai al cas base, surt l'error "stack overflow". Si, per altra banda, programem una funció en assemblador i no ho fem bé, podem tenir un error que sigui "stack underflow"

set

Aquest es correspon als conjunts matemàtics. No permet repeticions, i els elements estan ordenats. Les insercions tenen cost logarítmic, igual que les cerques. Es pot utilitzar per moltes coses, a vegades s'utilitza per emmagatzemar si un element ha aparegut o no. No obstant, hi ha mètodes millors per fer això.
Internament utilitza un arbre binari de cerca, per això qualsevol cosa que impliqui trobar un element té cost logarítmic

Les seves funcions són:

-begin i end: Igual que a totes les altres estructures de dades

-empty i size: El mateix

-insert: inserta un element. La versió típica rep un element, i retorna una pair<iterator,bool>. L'iterador apunta a la posició on està aquell element, mentre que el booleà ens diu si l'hem insertat (true), o si ja hi era (false). Aquesta versió té temps logarítmic. Hi ha una versió que rep també un iterador que fa de pista, de manera que, si la pista és bona, la funció té temps constant amortitzat

-erase: Elimina l'element indicat. Pot rebre un iterador que apunta al valor següent a l'eliminat, o rebre un element i retornar la mida del conjunt resultant

-find: retorna l'iterador on està l'element que li passem, si hi és. Si no hi és, apunta a l'end

multiset

El mateix que el set, però pot contenir elements repetits. Aquest es troba també a la llibreria set

map

El map, també conegut com a diccionari, és una estructura similar al set. Té una clau i un valor associat a aquesta. Està ordenat en funció de les claus, i no hi poden haver repeticions (de claus). Se'l coneix com a diccionari, perquè és bàsicament el mateix. Un diccionari seria un map<string,string>, on la clau fos la paraula, i el valor la definició.
El map conté bàsicament les funcions del set, amb algunes modificacions, i alguna cosa afegida. Les insercions segueixen tenint cost logarítmic, i el find també.

Si volem insertar a un map, podem fer-ho de dues maneres. Suposem que tenim un map<T1,T2> m. Doncs la primera seria utilitzar l'insert, que espera rebre una pair<T1,T2>. Podríem fer, per tant, una de les següents
m.insert(pair<T1,T2>(clau,valor));
m.insert(make_pair(clau,valor));
m.insert({clau,valor});//Només C++11
Notem que a la tercera versió utilitzo una llista d'inicialització, que apareixen a C++11. Em sembla la manera més elegant

Enlloc d'utilitzar un insert, podem utilitzar l'operador []. Seria una cosa així:
m[clau]=valor;
Notem que, mentre que en un vector i en un array el que passem és la posició, aquí li passem la clau de l'element al que volem accedir. De la mateixa manera que un insert o un find, té cost logarítmic

La diferència fonamental és que, en el cas de l'insert, es comporta com l'insert d'un set. Si ja hi ha un element amb la clau que li posem, no canviarà res, i el booleà de la parella que ens retorna serà false. En el cas de l'operador [], si la clau hi és, la modifica, mentre que si no hi és, la crea.

multimap

Aquest és com el map, però permetent elements duplicats. Es troba a la llibreria map

unordered_set

Aquest és com un set, però sense ordre (sí, capità obvi). Internament utilitza una taula de hash. L'avantatge que té respecte al set, és el cost. El desavantatge, doncs suposo que està clar, que no està ordenat. Els costs de les insercions, eliminacions i cerques és constant en el cas mitjà, i lineal en el cas pitjor. Aquesta apareix amb C++11, així que amb versions anteriors, no es pot utilitzar

unordered_multiset

Només cal dir que el trobem a la llibreria unordered_set

unordered_map

Sembla també clar, no? 

unordered_multimap

El mateix, es troba a la llibreria unordered_map

Llistes d'inicialització

En C, per emmagatzemar dades utilitzàvem arrays. Fèiem una cosa així:

int arr[10];

I ja podíem emmagatzemar 10 enters. No obstant, no era la única manera de declarar-lo:

int arr[10]={0,1,2,3,4,5,6,7,8,9};

int arr[]={0,1,2,3,4,5,6,7,8,9};

La primera versió donava la mida i el contingut que havia de tenir. La segona només el contingut, ja que el compilador és prou hàbil per calcular la mida. 

Això a C++98 no va ser exportat pels contenidors de la STL. No podíem fer

vector<int> v={0,1,2,3,4,5,6,7,8,9};

Per sort, quan va arribar C++11, es van adonar de l'error, i van decidir arreglar-ho. Van crear les llistes d'inicialització. 

La gràcia de les llistes d'inicialització és que es creen automàticament, només fent {e1,e2,...}. A més, tenen conversió a bastants contenidors de la STL, així com als nostres propis. Així, podem fer

set<int> primers_menors_de_deu={2,3,5,7};

A més d'això, s'analitzen recursivament. Una llista d'inicialització pot contenir-ne una altra dins. Així, podríem fer

vector<pair,int,int>> v={{1,2},{3,4},{5,6},{7,8}};

map<string,int> m={{"Hola",3},{"Adeu",4},{"Vint-i-cinc",25}};

A més, mentre que a C això servia per inicialitzar al moment de la declaració i ja, en C++ podem fer moltes altres coses

map<int,int> m;

...

int a, b;

cin >>a>>b;

m.insert({a,b});

int random(int min, int max) {

    return min+rand()%(max-min);

}

pair<int,int> parella_aleatoria(int min, int max) {

    return {random(min,max),random(min,max));

}

I moltes més coses que se'ns poden acudir. 

Per altra banda, podem fer coses així:

struct S{

    int a, int b;

    string s;

};

...

struct S={1,2,"Hola"};

o fins i tot

struct Salts {

    string saltador;

    double alcada;

};

...

vector<Salts> grans_salts={{"Stefka Kostadinova",2.09},{"Javier Sotomayor",2.45},{"Luís Carrero Blanco",numeric_limits<double>::infinity()}};

Iteradors

Hem vist que totes les estructures de dades anteriors, excepte la parella, el vector de booleans, pila i cua (normal i de prioritat), tenen iteradors. Però, realment què és un iterador?

Per entendre la necessitat dels iteradors, hem de saber com s'emmagatzemen les estructures de dades internament. Només ens interessaran les que disposen d'iteradors, ja que és el que volem veure

vector: s'emmagatzemen els elements en posicions de memòria seguides. Dins de la classe hi ha un atribut que és un punter que apunta al primer element. Si cada element té mida N, per accedir a v[i] només cal accedir a @v+N*i.
List: cada element consta d'un valor, un punter a l'element anterior, i un punter a l'element següent. Una cosa així:
struct Element {
    T valor;
    Element* node_ant, node_seg;
};
Aleshores, si volguéssim accedir a l'element ièssim, hauríem de fer un bucle que anés recorrent elements, des del primer fins a l'últim. Això faria que tingués cost lineal respecte i, cosa que fa que necessitem una manera d'emmagatzemar quin element estem visitant. Una idea seria utilitzar un punter que hi apunti
Set i map: Normalment s'implementen utilitzant arbres binaris de cerca. Per recórrer és senzill, però saltar d'un element a un altre és una cosa molt més complexa i, a diferència de la llista, no li podríem deixar a l'usuari de la classe
Unordered set/map: S'implementen utilitzant taules de hash. No entraré molt al tema, ja que és un tema complex

Aleshores, tenim una sèrie d'estructures de dades, que internament s'implementen de maneres molt diferents. I volem fer algorismes genèrics per ells. Així que necessitem un mètode per iterar pels elements de l'estructura, que funcioni igual a tots (si més no, amb els mateixos operadors). Per això s'inventen els iteradors.

Un iterador és una manera de recórrer una estructura de dades. Totes les estructures de dades tenen una funció begin, que retorna un iterador que apunta al primer element, i una funció end, que retorna un iterador que apunta a l'element "de després de l'últim". És com una manera de delimitar l'estructura, quan un iterador arriba a ser igual a l'end, ja has acabat.

Un iterador, realment, és molt similar a un punter. El que es fa és canviar-li una mica els operadors. En el cas dels punters, l'operador ++ passa a apuntar a l'element que està a la següent posició de memòria, mentre que en els iteradors, això només es compleix amb el vector i la deque. Per tant, hem de sobrecarregar aquests operadors, de manera que

Existeixen diferents tipus d'iteradors:

Input/output: l'iterador més bàsic. Si és d'entrada, permet accedir al valor, i ja està. Si és de sortida, accedir-hi per modificar-lo.
Forward: Compleix el que compleixen els anteriors, i permet recórrer l'estructura de dades, però només endavant.
Bidirectional: Compleix el que compleixen els anteriors, i a més permet anar enrere
Random Access: A més de complir el que compleixen els anteriors, permet sumar-li i restar-li números, comparacions de desigualtat (mirar si un és menor que un altre, per exemple), i l'operador []

Per accedir a un element, utilitzem l'operador de desreferència *, com en els punters. Si conté una estructura (una pair, per exemple), podríem utilitzar també l'operador ->, per accedir a cada un dels elements de l'estructura. Per desplaçar l'iterador endavant, utilitzem l'operador ++, mentre que per fer-ho enrere, l'operador --
Aleshores, imaginem que tenim una llista, i volem incrementar els seus elements. Podríem fer:

for (list<int>::iterator it=l.begin();it!=l.end();++it) {
    ++(*it);
}

Si tenim un map i volem incrementar els valors, per exemple, podríem fer

for(map<int>::iterator it=m.begin();it!=m.end();++it) {
    ++it->second;//Un map conté, en essència, parelles d'elements
}

Si volguéssim mostrar-ho, en canvi, faríem
for(map<int>::const_iterator it=m.begin();it!=m.end();++it) {
    cout<<it->first<<' '<<it->second<<endl;
}

Posant que sigui un iterador constant, fem que no permeti modificar l'estructura de dades. Això serveix per posar-nos una autolimitació, si ens equivoquem i en algun moment ho modifica, tindrem un error

Com podem veure, els iteradors ens permeten tenir algorismes més genèrics. Un algorisme aplicable a un vector, en general ho serà també a una llista (a no ser, clar, que necessiti un iterador Random Access, que la llista no pot proporcionar).

Algorismes:

Hi ha molts algorismes, molt útils. Tenim les ordenacions, cerca dicotòmica, el garbell d'Erastostenes... Imagineu que cada cop que volem ordenar un vector, haguéssim de programar una ordenació. Ens passaríem la vida programant coses que no són les més importants. Per això s'han programat diversos algorismes a la STL. Els més importants els trobem a la llibreria algorithm. Faré una petita llista dels que he trobat

for_each: Aplica una funció a un rang. Això, sumant-li les funcions lambda, és una eina molt poderosa. 

find: Troba en un rang

find_if: Busca l'element que compleix la funció que li passem. Igual que el for_each, funciona molt bé amb les funcions lambda

transform: Rep un rang, i un iterador que apunta a l'inici d'una estructura de dades. Fa la modificació indicada, i ho deixa a partir de l'iterador indicat

random_shuffle: ordena aleatòriament un rang. Serviria per barrejar una baralla de cartes, per exemple

sort: ordena en un rang. Ja l'hem estudiat. Se li pot passar una funció o un functor (següent punt) que defineixi l'ordre

stable_sort: ordena en un rang, preservant l'ordre dels valors iguals. Això serviria si, per exemple, tenim un vector<pair<int,int>> i hem definit que ordeni segons el primer element, entre dos elements que tinguin aquest igual, conservarà l'ordre que tingués

partial_sort: ordena de manera que els elements més petits estan a la meitat inferior i ordenats, mentre que la resta estan desordenats

lower_bound: retorna el primer element del rang que no és major al que li passem (és a dir, el primer que és <=. Com que utilitza la cerca dicotòmica, cal que estigui ordenat

upper_bound: Retorna el primer element major al que li passem (és a dir, el primer >). Cal que estigui ordenat per les mateixes raons

binary_search: La cerca dicotòmica, tal qual. Retorna true si hi és, false si no hi és

merge: rep dos rangs ordenats, i els combina de manera que el resultant estigui ordenat

set_union, set_intersection, set_difference: Les tres operacions sobre conjunts

min, max: Retornen respectivament el mínim i el màxim. La gràcia és que operen sobre templates

min_element, max_element: El mateix, però en un rang

El sort, per exemple, necessita un iterador Random Access. Com que la llista no el pot proporcionar, la solució ha sigut implementar una funció pròpia dins de la llista. No sé ben bé com ho fa, però ordena una llista en temps similar al sort típic

Functors:

Realment no sé com traduir la paraula. Functor ve de l'anglès "function operator". És una classe/struct que té sobrecarregat l'operador (), de manera que actua com una funció. Un exemple seria la classe greater, té sobrecarregat l'operador () de manera que rep dos elements, i retorna true si el primer és major que el segon. Això té diversos avantatges. 

Conservar valors

const int N=5;

struct Functor {

  int valor;
    Functor(int x) {

  valor=x;

  }
    int operator()(int y) {

  return y+valor;

  }

};

int main() {

    vector<int> v(N);

    for(int& x:v) cin >>x;

    vector<int> res(N);

    transform(v.begin(),v.end(),res.begin(),Functor(5));

    for(int x:res) cout <<x<<' ';

    cout<<endl;

}

Com podem veure, aquí hem creat un Functor (que es diu així), que servirà per sumar un número a un altre. En aquest cas, utilitzem l'algorisme per sumar 5 a un vector. Podem sumar 5, 6, o qualsevol enter. 

Observem que quan cridem a transform, fem Functor(5). Aquí no cridem l'operador(), sinó que estem cridant la funció creadora (Functor(int x)). Si, un cop el tenim creat, fem () sobre ell, estarem cridant l'operador

const int N=15;
struct Functor {
    int valor;
    int sumes=0;
    Functor(int x) {
        valor=x;
    }
    int operator()(int y) {
        if(sumes++>10) cerr<<"ERROR!"<<endl;
        return y+valor;
    }
};

int main() {

    vector<int> v(N);

    for(int& x:v) cin >>x;

    vector<int> res(N);

    transform(v.begin(),v.end(),res.begin(),Functor(5));

    for(int x:res) cout <<x<<' ';

    cout<<endl;

}

Aquí imaginem que no volem cridar la funció més de 10 cops. Doncs bé, el functor mateix emmagatzema quantes vegades ha sigut cridat, de manera que no ens n'hem de preocupar

Eficiència

Si fem que una funció rebi un punter a una altra, el compilador no pot fer inlining, sinó que haurà de cridar-la cada cop que la necessiti. Recordem que cridar una funció implica una sèrie de passos en assemblador

- Desar el valor dels registres que es poden modificar en una funció, si els necessitem

- Apilar els paràmetres

- Saltar a l'inici de la funció, desant %eip i %ebp. 

- Desar el valor dels registres que la funció ha de preservar, si els necessitem

- Executar la funció

- Col·locar el resultat a %eax

- Recuperar el valor dels registres desats

- Recuperar el valor de %ebp

- Retornar on estàvem, recuperant el valor de %eip

- Recuperar el valor dels registres desats

- Seguir amb l'execució del programa

Hi ha funcions on fer tot això és absurd. Per exemple, una funció on el que farem és retornar a>b, no cal fer tot això. Inlining vol dir agafar el cos de la funció, i substituir-lo a cada lloc on se la crida, de manera que no calgui fer tots aquests passos. Normalment el compilador ho fa amb les funcions que veu que és absurd cridar-les així. Se li pot aconsellar al compilador que ho faci, posant la paraula "inline" davant de la declaració de la funció. 

El problema és que, quan passem una funció com a paràmetre d'un altre, el que estem fent és passar un punter a aquella. I el compilador es troba que no pot fer-ho. Per això, la std, enlloc d'utilitzar funcions per comparar, utilitza functors. Això permet que una funció que utilitza less<T> per comparar, es comporti igual que una que utilitzi l'operador <, ja que realment, ho està fent

Un petit resum

Tenim uns quants functors a la llibreria functional. Aquí, un petit resum:

bit_and: Retorna a&b

bit_or: Retorna a|b

bit_xor: Retorna a^b

divides: Retorna a/b

equal_to, greater, greater_equal, less, less_equal: Retornen a==b, a>b, a>=b, a<b i a<=b, respectivament

logical_and, logical_not, logical_or: Retornen a and b, not a i a or b, respectivament

minus: a-b

modulus: a%b

multiplies: a*b

negate: -a

not_equal_to: a!=b

plus: a+b

Un exemple de l'us seria:

struct Persona {

    int edat, alcada;

    string nom;

    friend bool operator>(const Persona& a, const Persona& b) {

        if (a.edat!=b.edat) return a.edat>b.edat;

        if (a.alcada!=b.alcada) return a.alcada>b.alcada;

        return a.nom>b.nom;

    }

};

int main() {

  vector<Persona> v(N);

  for(Persona& x:v) cin >>x.nom>>x.edat>>x.alcada;
    sort(v.begin(),v.end(),greater<Persona>());

  for (Persona x:v) cout <<x.nom<<' '<<x.edat<<' '<<x.alcada<<endl;

}

Aquí tenim una struct Persona, que té definit l'operador >. Això ens permet utilitzar el functor greater per ordenar.