cod c++ gresit (?)

[•astronomy]

Cod:

#include <algorithm>
using namespace std;

typedef struct edge { int x, y, c; } edge;

int P;
edge A[200010];

int cmp(edge a, edge b)
{
	return a.c <= b.c;
}

// A are P = 100.000 elemente, A[1], A[2]... A[P]
sort(A+1, A+P+1, cmp);

Spre surprinderea mea, la iesirea din functia sort P este egal cu 0 si A contine si el date eronate. Are cineva vreo idee de ce?

[•Prostu]

Sortarea se face dupa o functie de ordonare stricta intre doua elemente.
De asemeni iti recomand sa nu implementezi o functie separata de comparatie, ci sa supraincarci operatorul '<'. In general e mai comod, daca trebuie apelata de mai multe ori.

Cod:

#include <algorithm>
using namespace std;

typedef struct edge { int x, y, c; } edge;

bool operator<(const edge &a, const edge &b) {
      return a.c < b.c;
}

sort(A+1, A+P+1);

[•azotlichid]

Si STL-ul o mai da pe langa  si am patit si eu chestia asta.
Daca micsorezi P sau daca schimbi struct-ul cu ceva mai mic o sa mearga.

[•wefgef]

Si eu am patit sa o ia STL-ul pe aratura chiar ieri la o problema de pe ZJU. Se mai intampla...

[•domino]

Cum s-o ia pe aratura?  STL-ul merge foarte bine daca e folosit cum trebuie...

[•azotlichid]

Are dreptate Stefan, functia de ordonare trebuie sa fie stricta. Schimba "<=" cu "<" in functia de comparare si o sa mearga

[•wefgef]

Cum s-o ia pe aratura?  STL-ul merge foarte bine daca e folosit cum trebuie...

cod care nu merge :

Cod:

if (A[j-1][start[j-1]].x > i-s[j-1].sz()) break;

cod care merge :

Cod:

aux1 = A[j-1][start[j-1]].x;
aux2 = i-s[j-1].sz();
if (aux1 > aux2) break;

[•Prostu]

cod care nu merge :

Cod:

if (A[j-1][start[j-1]].x > i-s[j-1].sz()) break;

cod care merge :

Cod:

aux1 = A[j-1][start[j-1]].x;
aux2 = i-s[j-1].sz();
if (aux1 > aux2) break;

Nu am reusit sa recreez bug-ul. Dar de ce nu merge? Ce valori difera? Merge la fel daca scoti define-ul pentru size?
Vrem detalii, stimabile.

[•wefgef]

aveti aici portiunile din codul meu care intereseaza:

Cod:

#define x first
#define y second
#define sz size

vector<string> s;
vector< pair<int, int> > A[Lmax];

int start[Nmax];
int aux1, aux2, i, j;

aux1 = A[j-1][start[j-1]].x;
aux2 = i-s[j-1].sz();
if (aux1 > aux2) break;

In cazul in care compar direct, fara sa ma folosesc de variabile auxiliare, primesc runtime error. Si culmea e ca la fel se intampla si la mine pe calculator.

Am luat testele oficiale si imi merge totusi pe 9/10 teste in cazul compararii directe.

Probabil ca exista o explicatie logica pentru ceea ce se intampla, insa pe mine ma depaseste situatia.

[•svalentin]

wefgef, ai incercat sa pui paranteze? si sa faci type-casting?

Cod:

if ((int)(A[j-1][start[j-1]].x) > (int)(i-s[j-1].sz())) break;

[•flo_demon]

Cod:

s[j-1].sz();

wefgef, greseala pe care o faci este ca folosesti .size() la clasa string
corect ar fi .length() .
[later edit] Sorry my bad, implemntarea la Dev c++ arata ca e acelasi lucru...

[mai later edit] 
Ok credca am solutia
Nu se poate sa fie de la faptul ca ai declarat un vector<...> A[] ? practic ai declarat un pointer la o clasa vector ar putea aparea complicatii avand in vedere ca vectorul e alocat dinamic, iar numarul elementelor din vector cand depasesc capacitatea vectorului, acesta se realoca dublandu-si capcitatea.
Astfel daca depasesti sa zicem un anumit numar de elemente (iar acele elemente nu mai au loc dupa coada vectorului sa fie alocate), se produce o realocare, acesta fiind realocat la o alta zona, unde incape. Schimbandu-si locatia. vectorul vechi se distruge si astfel tu accesezi o zona de memorie unde nu ai voie.
Declara vector<vector<..> >

[•varuvasi]

 ...

[•flo_demon]

Credca wefgef a vrut sa declare o matrice de pair, nu un sir.
Dupa cum spuneam nu e bine sa fie declarata asa datorita mecanismului de ralocare a vectorului. Corect ar fi vector<vector<pair<int, int > > >

[•svalentin]

 

Cod:

vector< pair<int, int> > A[Lmax];

declara Lmax vectori de pair<int, int>.. deci A[0] este un vector<parit<int, int> >, A[1] altul..
A[Lmax].size() o sa iasa in balarii... daca declar A[10], pot accesa elementele de la A[0] la A[9]

Codul lui wefgef este foarte bun si sunt sigur ca stie cum merg vectorii.. lucrul pe care l-a constat el este legat de if! Florin, nu ii trebuie vector de vector, pentru prima dimensiune stie exact dimensiunea necesare si nu iese din ea.. si eu sunt curios cum intretine indexarile (vectorul A[1] se redimensioneaza, cum mai stie cum sa acceseze A[2].. sau chiar A[1]?), dar se pare ca merge..
Singurul lucru mai "ciudat" este cum acel if da un rezultat odata si alt rezultat daca se folosesc variabile temporare pentru calculele intermediare -- singura diferenta pe care o vad eu este cea sugerata, cu variabile temporare fortezi sa faca calculele intr-o anumita ordine si comparatia sa fie intre inturi, altceva nu prea vad.
Ar mai putea fi pur si simplu un bug de compilator.. (binarul generat fara variabile temporare sa faca putin altfel calculele alea si sa le faca prost)

[•varuvasi]

i see now. credeam ca vrea sa declare un vector de Lmax elemente de tipul pair<int, int>.

[•bogdan2412]

Un vector din stl nu e pur si simplu o zona continua de memorie... Pe langa elementele sale, se mai tin cateva variabile care nu se realoca... v._Myfirst (denumirea probabil variaza in functie de implementare) tine pointer catre zona continua de memorie in care sunt puse elementele vectorului.. si nu conteaza daca este realocata aceasta zona... v._Myfirst ramane in acelasi loc si nu sunt probleme daca tii un pointer la un vector stl ... A[1] nu pointeaza pe elementele vectorului, ci pe acele variabile statice..

[•StTwister]

Ai incercat sa compilezi cu diferite nivele de opimizari? Poate da compilatorul rateuri..

[•wefgef]

wefgef, ai incercat sa pui paranteze? si sa faci type-casting?

Cod:

if ((int)(A[j-1][start[j-1]].x) > (int)(i-s[j-1].sz())) break;

  se pare ca asta era. Merge codul postat de tine

[•wefgef]

Am aflat de ce nu mergea . Se pare ca size() e unsigned. Pana la urma nu o lua pe aratura