Ciudat

[•APOCALYPTO]

Am scris o sursa pentru problema Gmin max si se intampla ceva ciudat cu bucata urmatoare de cod
 

Cod:

      for(it=G[bex].begin();it!=G[bex].end();it++)//pentru toti vecinii lui bex
        {vector<int>::iterator it1;
            for(it1=G[*it].begin();it1!=G[*it].end();it1++) // cauta-l pe bex intre vecinii lui *it ca sa-l 
            {
            if(*it1==bex) //stergi si sa micsorezi gradul lui *it si sa updatezi heapul  :-' 
            {
            G[*it].erase(it1);
            g[*it]--;
            upheap(poz[*it]);
            }
            }
        }

si am observat ca programul pur si simplu nu se oprea la G[*it].end(); si cicla pana cand probabil it ajungea intr-un spatiu de memorie nealocata.
apoi am inlocuit cu

Cod:

        for(it=G[bex].begin();it!=G[bex].end();it++)
        {vector<int>::iterator it1;
            for(it1=G[*it].begin();it1-G[*it].begin()+1<=g[*it];it1++)
            {
            if(*it1==bex)
            {
            G[*it].erase(it1);
            g[*it]--;
            upheap(poz[*it]);
            }
            }
            
        }

unde g[ i ] repezinta numarul de vecini ai nodului i si am luat 100.
Are cineva idee ce s-a intamplat?

[•Florian]

Din cauza ca faci G[*it].erase(it1);

[•APOCALYPTO]

Din cauza ca faci G[*it].erase(it1);

Ok dar fac asta la ambele surse. Si pe deasupra cum as putea elimina un element din vector in afara de a folosi erase?

[•BitOne]

Dupa fiecare stergere trebuie sa dereferentiezi iteratorul altfel poti avea niste surprize foarte urate. Alta functie ar fi remove.
Daca G[*it] are un singur element si acesta este egal cu bex ?  Il stergi si vectorul devine vid, apoi mai dai si cu ++it1 pentru incrementare ce rezulta la un Kill by signal 11.

[•APOCALYPTO]

Dupa fiecare stergere trebuie sa dereferentiezi iteratorul altfel poti avea niste surprize foarte urate. Alta functie ar fi remove.
Daca G[*it] are un singur element si acesta este egal cu bex ?  Il stergi si vectorul devine vid, apoi mai dai si cu ++it1 pentru incrementare ce rezulta la un Kill by signal 11.

Deci atunci cand parcurg un vector din care sterg si elemente cel mai corect este sa fac ca mai sus sau asa:

Cod:

       for(it=G[bex].begin();it!=G[bex].end();it++)
        {vector<int>::iterator it1;
            for(it1=G[*it].begin();!(it1>=G[*it].end());it1++)
            {
            if(*it1==bex)
            {int bahh;
            G[*it].erase(it1);
            g[*it]--;

            bahh=poz[*it];

            upheap(bahh);

            }
            }

        }

?

[•BitOne]

Cel mai corect este

Cod:

G[*it].erase(it1);
it1=G[*it].begin(); 

Daca vrei poti folosi remove_if

[•APOCALYPTO]

Cel mai corect este

Cod:

G[*it].erase(it1);
it1=G[*it].begin(); 

Daca vrei poti folosi remove_if

Pai da dar nu sterg  incepand cu primul element mereu.
Si daac folosesc remove_if mai merge sa scad gradele:(?

[•BitOne]

Eu am scris doar o bucata de cod, odata ce ai sters un element o ei de la inceput nu continui cu ++it  
LE: Da merge, pui in functie ce tre sa faca ....

Cod:

inline bool TobeRemoved( int x )
{
        if( x == with_something )
       {
                 do something;
                 return true;
        }
        return false;
}
//apelzi asa :
vector< int >::iterator new_end=remove_if( v.begin(), v.end(), TobeRemoved ); /*va sterge toate elementele pt face TobeRemoved(x) == true. Noul "sfarsit" al vectorului este new_end */

[•APOCALYPTO]

Eu am scris doar o bucata de cod, odata ce ai sters un element o ei de la inceput nu continui cu ++it  

Am inteles dar in conditii de concurs iti dai seama cat timp pierzi  ?

[•BitOne]

Am inteles dar in conditii de concurs iti dai seama cat timp pierzi  ?

Prefer TLE decat Kill by Signal 11  ) ( adica sa mearga dar nu optim, decat optim si sa crape )
Oricand poti folosi liste simplu inlantuite, chiar si din STL cred ( n-am incercat ).