Imprimă pagina

Titlul: Ciudat
Scris de: Dragos din Iunie 22, 2010, 14:39:14

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?

Titlul: RÄƒspuns: Ciudat
Scris de: Florian Marcu din Iunie 22, 2010, 14:59:54

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

Titlul: RÄƒspuns: Ciudat
Scris de: Dragos din Iunie 22, 2010, 16:37:22

Citat din mesajul lui: Marcu Florian din Iunie 22, 2010, 14:59:54

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?

Titlul: RÄƒspuns: Ciudat
Scris de: SAlexandru din Iunie 22, 2010, 16:54:10

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.

Titlul: RÄƒspuns: Ciudat
Scris de: Dragos din Iunie 22, 2010, 17:38:11

Citat din mesajul lui: SAlexandru din Iunie 22, 2010, 16:54:10

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);

            }
            }

        }

Titlul: RÄƒspuns: Ciudat
Scris de: SAlexandru din Iunie 22, 2010, 17:45:32

Cel mai corect este

Cod:

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

Daca vrei poti folosi remove_if (http://www.sgi.com/tech/stl/remove_if.html)

Titlul: RÄƒspuns: Ciudat
Scris de: Dragos din Iunie 22, 2010, 17:52:13

Citat din mesajul lui: SAlexandru din Iunie 22, 2010, 17:45:32

Cel mai corect este

Cod:

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

Daca vrei poti folosi remove_if (http://www.sgi.com/tech/stl/remove_if.html)

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

Titlul: RÄƒspuns: Ciudat
Scris de: SAlexandru din Iunie 22, 2010, 17:56:25

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 */

Titlul: RÄƒspuns: Ciudat
Scris de: Dragos din Iunie 22, 2010, 18:09:02

Citat din mesajul lui: SAlexandru din Iunie 22, 2010, 17:56:25

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 :sad:?

Titlul: RÄƒspuns: Ciudat
Scris de: SAlexandru din Iunie 22, 2010, 18:14:51

Citat din mesajul lui: Dragos din Iunie 22, 2010, 18:09:02

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

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 ).

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Dragos din Iunie 22, 2010, 14:39:14