infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Andrei Misarca din Aprilie 02, 2008, 18:10:09



Titlul: Folosirea STL
Scris de: Andrei Misarca din Aprilie 02, 2008, 18:10:09
Am citit zilele trecute despre vectorii din STL... cu ce e mai bun un vector declarat  vector<int> v decat int v[N]?


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Grigorean din Aprilie 02, 2008, 18:16:02
Pai daca vrei sa retii un graf cu liste de adiacenta nu poti cu vectori alocati static, in shimb vector<int> face treaba ;).


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 02, 2008, 18:28:42
adica vector<int> v tine loc listelor, va sa zica  :-k


Titlul: Răspuns: Folosirea STL
Scris de: Cosmin Negruseri din Aprilie 02, 2008, 18:33:00
Nu tine locul listelor. Intr-un vector redimensionabil stergi/inserezi un element in O(n) pe cand intr-o lista daca esti deja pe pozitia pe care vrei stergi/inserezi in O(1).


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 02, 2008, 18:36:39
v.pop_back() are complexitate O(n) ?


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Grigorean din Aprilie 02, 2008, 18:49:04
Nu, pop_back() e O(1).


Titlul: Răspuns: Folosirea STL
Scris de: Sima Cotizo din Aprilie 02, 2008, 18:53:46
El se referea la push_back, cred... stiam ca push_back e O(n) doar cand V.size() e putere a lui 2 (si face redimensionare)... gresesc?


Titlul: Răspuns: Folosirea STL
Scris de: Adrian Diaconu din Aprilie 02, 2008, 18:56:50
push_back() e O(1) amortizat. Intr-adevar cand vectorul se umple isi dubleaza spatiul alocat si cand este mai putin de jumatate plin isi injumatateste spatiul alocat (cred :) ).

Cred ca se referea la erase(x) care este O(n), stergerea unui element din interiorul vectorului (x - iterator)


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 02, 2008, 19:05:42
Iar daca vreau sa fac lee cu alocare dinamica de exemplu, ce e mai bine sa folosesc... vectori din stl sau liste simplu inlantuite?


Titlul: Răspuns: Folosirea STL
Scris de: Bogdan-Cristian Tataroiu din Aprilie 02, 2008, 19:06:51
Vectorii cred ca ocupa mai putina memorie (la list trebuie si 2 pointeri pt prev si next) si diferenta de performanta e insesizabila :P


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 02, 2008, 19:09:52
Oricum e mai usoara scrierea cu vectori decat cu liste  :) Multzam fain

L.E. Cum se poate face o sortare a vectorului folosind functia sort(din stl)... care sunt parametrii


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Bondane Cosmin din Aprilie 02, 2008, 19:29:32
Oricum e mai usoara scrierea cu vectori decat cu liste  :) Multzam fain

L.E. Cum se poate face o sortare a vectorului folosind functia sort(din stl)... care sunt parametrii

vector<int> L;
........
sort( L.begin(), L.end() );


Titlul: Răspuns: Folosirea STL
Scris de: Bogdan-Alexandru Stoica din Aprilie 02, 2008, 23:28:54
Poti intra aici (http://www.sgi.com/tech/stl/) pentru a te documenta.


Titlul: Răspuns: Folosirea STL
Scris de: Savin Tiberiu din Aprilie 02, 2008, 23:36:48
Citat

vector<int> L;
........
sort( L.begin(), L.end() );

chestia asta o folosesti cand sortezi crescator. Daca vrei sa sortezi altfel adaugi o functie de comparare:

Cod:

int cmp( tip a, tip b)
{
//returneaza 1 daca a trebuie sa apara inaintea lui b, 0 invers
}

....

sort(v.begin(), v.end(), cmp);

De asemenea poti sa folosesti pairuri pentru a evita functia de comparare. Daca ai un vector de pairuri si ii dai sort fara functie de comparare va sorta crescator dupa first si in caz de egalitate dupa second (bineinteles chestia aste merge recursiv, adik pot sa am si un vector de genu : vector< pair< pair< pair < pair <int, int> , int> ,int >, int > ).


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Grigorean din Aprilie 02, 2008, 23:52:13
Daca vrei sa sortezi descrescator poti sa dai

Cod:
sort(v.rbegin(), v.rend());


Titlul: Răspuns: Folosirea STL
Scris de: Alina Ene din Aprilie 03, 2008, 03:50:13
Sau
Cod:
sort(v.begin(), v.end(), greater<int>());



Titlul: Răspuns: Folosirea STL
Scris de: Tabara Mihai din Aprilie 03, 2008, 07:40:03
sau
Cod:
sort(v.begin(), v.end() );
reverse( v.begin(), v.end() );
:wink:


Titlul: Răspuns: Folosirea STL
Scris de: Marius Stroe din Aprilie 03, 2008, 22:33:33
Sau

http://www.cplusplus.com/reference/algorithm/sort.html

De pe www.cplusplus.com/reference am invat sa folosesc set si map, in general, STL. Mi se pare mai usor decat Sgi.


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 03, 2008, 23:13:55
Foarte tare saitu, explica foarte bine si pentru incepatori in stl si alte chestii de genu :D


Titlul: Răspuns: Folosirea STL
Scris de: Cosmin Negruseri din Aprilie 05, 2008, 00:34:45
Uitati-va si la tutorialele de pe topcoder:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 06, 2008, 19:42:01
Am o intrebare... am fragmentu asta de cod
Cod:
vector <char *> v;

void citire()
{
  char s[100];
  scanf("%d",&n);
  for(int i=0; i<n; i++)
  {
    scanf("%s",&s);
    int k = strlen(s);
    if(s[k-1] == '\n')
      s[k-1] = 0;
    v.push_back(s);
    printf("%s\n",v.back());
  }
 
  for(vector <char *> :: iterator it = v.begin(); it!= v.end(); it++)
    printf("%s\n",*it);
}
in fisieru de intrare am
Cod:
5
asdaf
dsfsdfasdf
sadfsrcr
c
sdcsdf
si uite ce afisaza
Cod:
asdaf
dsfsdfasdf
sadfsrcr
c
sdcsdf
sdcsdf
sdcsdf
sdcsdf
sdcsdf
sdcsdf
care-i explicatia logica a faptului ca la sfarsit tot vectoru e plin doar cu ultima chestie?  :?


Titlul: Răspuns: Folosirea STL
Scris de: Adrian Diaconu din Aprilie 06, 2008, 19:48:03
Cod:
vector <char *> v; 
Tu ai aici un vector de pointeri in care introduci de N ori adresa lui s(s este si el un pointer). Deci in final afisezi de N ori ce se afla la adresa lui s adica exact ultimul sir de carctere citit.


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 06, 2008, 19:53:38
Si dak vreu sa retin in v cuvinte(siruri de caractere) cam ce ar trebui sa fac?


Titlul: Răspuns: Folosirea STL
Scris de: Adrian Diaconu din Aprilie 06, 2008, 20:00:02
Eu folosesc string pentru asta. Este si mai usor de folosit(de exemplu ai definit operatorul + pentru concatenare). Si la afisare trebuie sa faci doar ceva de genu printf("%s",x.c_str()).  Si conversia din char * in string este deja definita.


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 06, 2008, 20:03:27
Si cum se defineste?  :)


Titlul: Răspuns: Folosirea STL
Scris de: Adrian Diaconu din Aprilie 06, 2008, 20:09:42
Pentru exemplul dat de tine poti sa faci ceva de genul asta. Sper ca am modificat tot ce trebuia.(in plus la headere trebuie sa mai incluzi <string>)
Cod:
vector <string> v;

void citire()
{
  char s[100];
  scanf("%d",&n);
  for(int i=0; i<n; i++)
  {
    scanf("%s",&s);
    int k = strlen(s);
    if(s[k-1] == '\n')
      s[k-1] = 0;
    v.push_back(s);
    printf("%s\n",v.back().c_str());
  }
 
  for(vector <string> :: iterator it = v.begin(); it!= v.end(); it++)
    printf("%s\n",(*it).c_str());
}


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Aprilie 06, 2008, 20:19:57
Multzam fain


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Grigorean din Aprilie 06, 2008, 22:24:58
Poti afla mai multe despre string si despre STL in general aici (http://www.sgi.com/tech/stl/table_of_contents.html).


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Mai 08, 2008, 11:06:17
Am o intrebare... cum se sorteaza un vector <pair <int,int> > folosind sort din algorithm crescator dupa prima componenta, iar in caz de egalitate descrescator dupa a doua componenta, de exemplu  :)


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Parvu din Mai 08, 2008, 11:31:24
pai faci o functie de comparare de genu:
Cod:
int cmp(pair<int, int> a, pair<int, int > b){
if (a.first != b.first)
return a.first < b.first;
return a.second < b.second;
}

si apoi sortarea o faci

Cod:
sort(v.begin(), v.end(), cmp);


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Grigorean din Mai 08, 2008, 12:44:07
pai faci o functie de comparare de genu:
Cod:
int cmp(pair<int, int> a, pair<int, int > b){
if (a.first != b.first)
return a.first < b.first;
return a.second < b.second;
}

Ca sa sortezi descrescator dupa a doua componenta trebuie sa ai:
Cod:
int cmp(pair<int, int> a, pair<int, int > b){
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
}


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Mai 05, 2009, 19:01:37
Am citit in mai multe locuri despre set si map din STL, dar tot nu am inteles cu exactitate ce tip de operatii suporta cele 2 containere. Aveti un link catre un site unde zice sau poate cineva sa povesteasca concret ce operatii se pot face pe cele 2 :D


Titlul: Răspuns: Folosirea STL
Scris de: Pripoae Teodor Anton din Mai 05, 2009, 20:12:35
Pe set ai : insert, erase, find, lower_bound, upper_bound, chestii pe care le ai si pe map, doar ca pe map poti face ceva gen Map["string"] (poti accesa elementele ca la un vector normal). Din cate stiu map-ul functioneaza ca un avl pe hashurile elementelor (eu il folosesc la normalizare).


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Mai 05, 2009, 20:39:32
si lower_bound intoarce iteratorul unde se afla prima aparitie a unui element?


Titlul: Răspuns: Folosirea STL
Scris de: Pripoae Teodor Anton din Mai 05, 2009, 21:08:46
lower_bound returneaza iterator catre pozitia primului element mai mare sau egal decat valoarea cautata, iar upper_bound returneaza iterator catre pozitia primului element mai mare strict decat valoarea cautata.


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Mai 05, 2009, 21:12:19
Mersi :D

Si mai am o intrebare... exista vro functie care returneaza al k-lea element in ordine crescatoare dintr-un map/ set? (in complexitate logN)


Titlul: Răspuns: Folosirea STL
Scris de: Pripoae Teodor Anton din Mai 05, 2009, 21:39:53
Din cate stiu eu, nu exista. Trebuie sa implementezi tu AVL-ul de mana.


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Mircea Dima din Mai 05, 2009, 22:54:28
Pe set ai : insert, erase, find, lower_bound, upper_bound, chestii pe care le ai si pe map, doar ca pe map poti face ceva gen Map["string"] (poti accesa elementele ca la un vector normal). Din cate stiu map-ul functioneaza ca un avl pe hashurile elementelor (eu il folosesc la normalizare).


De unde stii tu faza cu avl pe hashuri? ;;)

set, multiset,map, multimap sunt implementate folosind Red-Black Tree :)


Titlul: Răspuns: Folosirea STL
Scris de: Pripoae Teodor Anton din Mai 06, 2009, 13:21:30
Ma rog, red black tree (nu stiu foarte bine diferenta intre cele 2). Si legat de hashuri, avand in vedere ca tu poti mapa chestii de dimensiuni diferite, imi inchipui ca ar merge pe un hash, sau ceva de genul (ca sa nu mai compari in arbore in o(lungime * logn) de fiecare data cand inserezi sau stergi), doar ca se pare ca se strica ordinea pt lower_bound si upper_bound.


Titlul: Răspuns: Folosirea STL
Scris de: Sanduleac Dan din Mai 08, 2009, 15:04:49
Am o intrebare... cum se sorteaza un vector <pair <int,int> > folosind sort din algorithm crescator dupa prima componenta, iar in caz de egalitate descrescator dupa a doua componenta, de exemplu  :)

Mai simplu: ai
Cod:
vector<pair<int, int> > A;
// adaugi elementele in felul urmator: daca vrei sa inserezi perechea (x, y), adaugi cu A.push_back( make_pair(x, -y) )
// apoi
sort(A.begin(), A.end());
//apoi cand accesezi elementele din vector, folosesti A[i].first si  -A[i].second pentru a obtine cele doua campuri.


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Tataranu Vlad din Mai 10, 2009, 11:55:05
Pe set ai : insert, erase, find, lower_bound, upper_bound, chestii pe care le ai si pe map, doar ca pe map poti face ceva gen Map["string"] (poti accesa elementele ca la un vector normal). Din cate stiu map-ul functioneaza ca un avl pe hashurile elementelor (eu il folosesc la normalizare).
Din cate stiu eu Map<key,data> (http://www.sgi.com/tech/stl/Map.html) functioneaza ca un arbore rosu-negru in care sunt stocate pair<key, data>.
In niciun caz nu functioneaza pe baza de hashuri. Complexitatea accesarii unui element din map este O(log N * complexitatea comparatorului). Exista hash_map in stl, dar nu l-am folosit niciodata si nu stiu cum merge.
Toni, check this out (http://www.sgi.com/tech/stl/index.html)! :P


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Mai 12, 2009, 21:59:11
Imi puteti recomanda va rog niste probleme care se rezolva cu ajutorul set/map. :) (in afar' de sea2)


Titlul: Răspuns: Folosirea STL
Scris de: Ciprian Tomoiaga din Mai 29, 2009, 19:39:53
am si eu o mica intrebare la STL .... daca am o functie care vreau sa imi preia un vector<int>  ... preia singura? sau cum ar trebui sa procedez?

de ex: int F ( vector <int> p(50), vector <int> b(50) )
si mie mi se transmit catre functie doi vectori... cu pana la 50 de elemente... ii preia functia direct sau trebuie sa o fac eu manual? daca nu, cum fac treaba asta manual:D?


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Mai 29, 2009, 21:38:23
poti pune
Cod:
int F(vector <int> p, vector <int> b)
se descurca el sa ii preia direct :)


Titlul: Răspuns: Folosirea STL
Scris de: Tataranu Vlad din Iunie 06, 2009, 11:10:01
poti pune
Cod:
int F(vector <int> p, vector <int> b)
se descurca el sa ii preia direct :)
Numai sa ai grija ca daca ii transmiti asa ii copiaza si poate sa-ti iasa din memorie, plus ca dureaza ceva sa-i copieze.
Ca sa eviti asta poti sa-i trimiti prin referinta.
Cod:
int F ( vector<int> &p, vector<int> &b )


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Iunie 14, 2009, 11:19:18
Din cate stiu map-ul functioneaza ca un avl pe hashurile elementelor (eu il folosesc la normalizare).
Cum il folosesti? Poti modifica cheia elementelor pe parcurs?


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Tataranu Vlad din Iunie 14, 2009, 14:10:18
Din cate stiu map-ul functioneaza ca un avl pe hashurile elementelor (eu il folosesc la normalizare).
Cum il folosesti? Poti modifica cheia elementelor pe parcurs?

Nu poti modifica cheile, poti muta, insa valorile (second din pair-ul ala).


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Iunie 14, 2009, 19:10:52
Nu poti modifica cheile, poti muta, insa valorile (second din pair-ul ala).

Si cum se face treaba asta?


Titlul: Răspuns: Răspuns: Folosirea STL
Scris de: Tataranu Vlad din Iunie 16, 2009, 08:12:58
Nu poti modifica cheile, poti muta, insa valorile (second din pair-ul ala).

Si cum se face treaba asta?
Daca presupunem ca avem un map<int,int> M:
Cod:
M[5] = M[3];
Poti sa il tratezi ca un vector normal, doar ca tine elementele "pe sarite".


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Iulie 19, 2009, 17:58:44
Ce reprezinta un priority queue declarat
Cod:
priority_queue H <int, vector<int> cmp()>
si cu ce este mai bun decat un priority queue declarat normal. Pe cpluplus.com scrie foarte vag despre chestia asta si nu m-am lamurit


Titlul: Răspuns: Folosirea STL
Scris de: Pripoae Teodor Anton din Iulie 19, 2009, 18:05:38
Priority_queue se poate declara simplu :

Cod:
priority_queue <int> Q;

Caz in care iti creaza un priority_queue pt valori de tip int, care extrage maximul. Daca scrii :

Cod:
priority_queue <int, vector <int>, cmp > Q;

Atunci iti va crea un priority_queue pt valori de tip int, construit pe un container de tip vector <int> cu functia de comparare cmp.


Titlul: Răspuns: Folosirea STL
Scris de: Andrei Misarca din Iulie 19, 2009, 18:08:36
Si care este diferenta majora intre un priority_queue normal si unul facut pe un vector <int> ?


Titlul: Răspuns: Folosirea STL
Scris de: Pripoae Teodor Anton din Iulie 19, 2009, 18:51:30
Priority_queue normal e facut tot pe vector <int>, doar ca asa este template-ul pentru functie de comparare. Nu exista template intermediar din cate stiu.