infoarena

Am vazut pe cplusplus.com noul C standard din 2011, dar care nu este pus pe compilatoare, e doar versiunea de test sau ceva gen. Are noi librarii, si noi functii, spre ex. <array> din STL. Daca includ acest header, compilerul imi spune asa :
As fi curios cum pot sa fac sa activez acele "compiler options" si daca se poate pe infoarena.

Numai una din cele 2 comenzi o sa mearga. Ele sunt pentru linux.

Daca vrei pentru 4.6 sa-ti compilezi in c++0x atunci faci asa

g++ sursa.cpp -o sursa --std=gnu++0x

L.E: Si se poate si pe infoarena dar inca nu am decis sa facem asta in principiu pentru ca nici olimpiada nu face asta.

Si inca 2 intrebari care ma framanta si cu asta am terminat : unordered_map este inlocuitorul lui hash_map (resp. _set), si daca da merge la olimpiada cu <tr1/un...> ? Si daca am un array mai mare, si vreau sa-l fac dinamic, la olimpiada sa nu-mi scada daca pun ch[MAX_N], in caz ca MAX_N este foarte mare, sau alte cazuri, se poate folosi vector <> declarat dinamic, pastrand viteza ?

unordered_map unordered_set sunt in standard da. Ca sa le incluzi faci #include <unordered_set> // sau map pentru map-uri.

De mentionat ca ai si unordered_multimat si unordered_multiset.

In rest declararea tot al fel ramane. Daca puteai face ch[MAX_N] inainte poti si acuma. Desi e bine de stiut ca compilatorul cu -O2 face in asa fel incat un vector<> de marime MAX_N declarat din start atat de mare sa se comporta identic ca un array normal cand e vorba de viteza. Cand faci

tot ce e in plus fata de acelasi cod folosind un array normal este o initializare a vectorului(care e O(1))

Am inteles, daca fac unordered_set, fara tr1/ in fata, desi includ namespace-ul tr1, imi apare aceeasi eroare de la C++11, ca mai sus. Si in legatura cu array-urile, daca am program asa :
Ramane la fel viteza, pentru ca eu il declar acum ca fiind cu un numar fix de elemente. Si inca ceva, din cate am inteles, push_back-ul redimensioneaza vectorul, facand-ul de dimensiunea puterilor lui 2. Se poate, daca am sa zicem un numar de elemente (nu stiu cate), si fac push_back, la final (sau nu stiu) sa fac ca acest vector sa fie fix, adica daca am citit 1000 elemente si el este de 1024 (putere a lui 2), sa fie de fix 1000, ca din cate am inteles resize nu elibereaza memoria, doar redimensioneaza vectorul.

Daca vrei sa faci un vector sa aiba capacitatea cat marimea lui faci vector<int>(ch).swap(ch); daca il declarasesi pe ch ca tip vector<int>.

Nu mai trebuie sa dai using namespace tr1 in c++11. Si iti trebuie acea comanda la compilare(care merge numai pe linux, cred) --gnu=std++0x

Ce se intampla in cazul vector (c++) si ArrayList in java e ca de fiecare daca cand adaugi un element la vector si depasesti capacitatea de memorie alocatata, se mai aloca inca pe atata memorie. Asta face ca N operatii push_back sa aiba complexitatea amortizata O(N), chiar daca una poate avea complexitate O(N). (Motivul de a inmulti cu doi de fiecare data este ca 1 + 2 + 4 + ... + 2^K = 2^(K+1) - 1 = O(N) ).

Folosind g++, daca faci:
sau
atunci se aloca 100 de elemente, nu 128.

Poti testa ce se intampla pe compilatorul pe care il folosesti astfel:

Ca un comentariu final, in C++11 exista functia shrink_to_fit care ar trebui sa elibereze diferenta de memorie dintre capacity si size, dar g++ nu o implementeaza corect (de exemplu, nu functioneaza pentru vector<string>).