Discussion :

[Chewbi]

Bonjour,

J'ai la structure suivante (paire de polynomes):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 
struct Paire {
	Paire () {}
	Paire (const Paire& p) { // utile pour les push_back ?!
		p1=p.p1;
		p2=p.p2;
	}
	bool operator<(Paire pa) const { // precondition: paire non nulle 
		// calcul des ppcm des monomes de tete
		Term ppcmPa=pa.p1[0].ppcm(pa.p2[0]); 
		Term ppcm=p1[0].ppcm(p2[0]);
		if (ppcm.infLex(ppcmPa)) return true;
		else return false;
	}
	PolPlusVarLex p1;
	PolPlusVarLex p2;
};

ainsi que le bout de code suivant, utilisé pour ajouter une paire définie ci-dessus à un vecteur de paires S (std::vector<Paire> S)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
 
// range une paire (non nulle) dans S (trié!) en fonction de son ppcm (ordre croissant)
// question: push_back + sort plus rapide que recherche lineaire + insert?!
void AlgoClassiquesLex::ajoutePaire(Paire pr) {
         //if (pr.p1.getSize()!=0 && pr.p2.getSize()!=0) sort(S.begin(),S.end());
         //return;
	if (pr.p1.getSize()==0 || pr.p2.getSize()==0) return;
	int p,s=S.size(),degre=(pr.p1[0].ppcm(pr.p2[0])).getDeg();
        for (p=s-1; p>=0; p--) 
            if ((S[p].p1[0].ppcm(S[p].p2[0])).getDeg()>=degre) break;
        if (p==s-1)  { 
                S.push_back(pr);  // --> PLANTAGE ICI
		return;
	}
	if (p<0) { 
		S.insert(S.begin(),pr);
		return;
	}
	std::vector<Paire>::iterator it=S.begin();
	for (int i=0; i<=p; i++) it++; 
        S.insert(it,pr);
	return;
}

J'appelle la fonction precedente plusieurs fois, et lorsque S atteint la taille 30 avec le contenu suivant:

etat de S:
4*X1*X4 + 93*X1*X2 et X2^2*X4 + 99*X2 + X4
4*X1*X4 + 93*X1*X2 et 97*X1*X2^2 + 97*X1
97*X1*X2^2 + 97*X1 et 2*X2*X3 + 2*X2 + 99*X4
97*X1*X2^2 + 97*X1 et 99*X2*X4 + 2 + 99*X3
97*X1*X2^2 + 97*X1 et 2*X2*X3 + 2*X2 + 99*X4
97*X1*X2^2 + 97*X1 et X2^2*X4 + 99*X2 + X4
97*X1*X2^2 + 97*X1 et X2^2*X4 + 99*X2 + X4
97*X1*X2^2 + 97*X1 et 2*X2*X3 + 2*X2 + 99*X4
97*X1*X2^2 + 97*X1 et 99*X2*X4 + 2 + 99*X3
97*X1*X2^2 + 97*X1 et 2*X2*X3 + 2*X2 + 99*X4
97*X1*X2^2 + 97*X1 et X2^2*X4 + 99*X2 + X4
97*X1*X2^2 + 97*X1 et 4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4
97*X1*X2^2 + 97*X1 et X1*X2^4 + 2*X1*X2^2 + X1
97*X1*X2^2 + 97*X1 et X1*X2^4 + 2*X1*X2^2 + X1
97*X1*X2^2 + 97*X1 et X1*X2^4 + 2*X1*X2^2 + X1
97*X1*X2^2 + 97*X1 et X1*X2^4 + 2*X1*X2^2 + X1
97*X1*X2^2 + 97*X1 et 97*X3^2 + 97*X4^2 + 4
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et X2^2*X4 + 99*X2 + X4
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et 2*X2*X3 + 2*X2 + 99*X4
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et X1*X2^4 + 2*X1*X2^2 + X1
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et 99*X2*X4 + 2 + 99*X3
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et X1*X2^4 + 2*X1*X2^2 + X1
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et 2*X2*X3 + 2*X2 + 99*X4
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et X2^2*X4 + 99*X2 + X4
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et X1*X2^4 + 2*X1*X2^2 + X1
4*X1*X2^3 + 2*X1*X2^2*X4 + 2*X1*X4 et 97*X3^2 + 97*X4^2 + 4
2*X2*X3 + 2*X2 + 99*X4 et X1*X2^4 + 2*X1*X2^2 + X1
X1*X2^4 + 2*X1*X2^2 + X1 et X2^2*X4 + 99*X2 + X4
X1*X2^4 + 2*X1*X2^2 + X1 et X2^2*X3 + X2^2 + X3 + 100
97*X3^2 + 97*X4^2 + 4 et X1*X2^4 + 2*X1*X2^2 + X1
97*X3^2 + 97*X4^2 + 4 et X1*X2^4 + 2*X1*X2^2 + X1
j'insere en 30 la paire 4*X1*X4 + 93*X1*X2,2*X2*X3 + 2*X2 + 99*X4

j'obtiens une seg_fault pour laquelle gdb me dit:

Program received signal SIGSEGV, Segmentation fault.
0x200000000011d780 in std::__default_alloc_template<true, 0>::allocate ()
from /usr/lib/libstdc++.so.5
(gdb) bt
#0 0x200000000011d780 in std::__default_alloc_template<true, 0>::allocate ()
from /usr/lib/libstdc++.so.5
#1 0x4000000000010360 in std::__simple_alloc<Term, std::__default_alloc_template<true, 0> >::allocate ()
#2 0x400000000000f200 in std::_Vector_alloc_base<Term, std::allocator<Term>, true>::_M_allocate ()
#3 0x400000000000e310 in std::vector<Term, std::allocator<Term> >::_M_allocate_and_copy<__gnu_cxx::__normal_iterator<Term const*, std::vector<Term, std::allocator<Term> > > > ()
#4 0x400000000000c630 in std::vector<Term, std::allocator<Term> >::operator=
()
#5 0x400000000000b720 in PolPlusVarLex::operator= ()
#6 0x400000000002bc10 in Paire:aire ()
#7 0x4000000000027d00 in std::_Construct<Paire, Paire> ()
#8 0x40000000000266f0 in std::vector<Paire, std::allocator<Paire> >::push_back
()
#9 0x4000000000023690 in AlgoClassiquesLex::ajoutePaire ()
#10 0x4000000000025500 in AlgoClassiquesLex::BuchOpt ()
#11 0x4000000000006a00 in main ()

Je n'y comprend rien..
Pourtant j'ai bien défini des constructeurs par recopie dans PolPlusVarLex (classe pour des polynomes a plusieurs variables ordre lexicographique), et dans Paire. J'ai bien fait attention à distinguer les cas où on insère en fin et au début, il y a bien "include <vector>", bref normalement tout (ou presque je suppose) est en ordre.

Si vous avez aussi une réponse à la question en en-tête de ajoutePaire, je prends aussi mais c'est moins vital

Merci d'avance,
Benjamin

[Rafy]

Si tu ne définie pas de constructeur de copie, alors le compilateur le fera tout seul. Donc dans ton cas tu n'es pas obligé de le définir.

[Rafy]

Il serai plus judicieux d'utiliser un autre conteneur que le vector.
Tu peux regarder Ici pour choisir ce conteneur...
Il existe des conteneurs qui trient tout seul les éléments qu'ils contiennent, ça pourrait t'aider...

[Chewbi]

Thx! Je ne connaissais pas cette page, j'essaye tt de suite avec une priority_queue

[David Fleury]

Si tu veux garder ton vector,
tu peux utiliser aussi upper_bound pour insérer dans le vector
(ou lower_bound, je ne me souviens jamais).

Sinon, ton operator <, souvent on le mets avec 2 operandes et à l'extérieure de la classe (ou struct)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
bool operator < ( const Paire& lhs, const Paire& rhs )
{
   return ...;
}

et ton ajouter reviens à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
void AlgoClassiquesLex::ajoutePaire( const Paire& pr) 
{
    S.insert( std::upper_bound( S.begin(), S.end(), pr ), pr );
}

ou un truc dans l'idée, ça doit pas compiler, j'ai pas le courage

[Chewbi]

bah en fait une file de priorité est plus adapté à ce que je veux faire (je veux juste choisir des paires de polynomes avec un ppcm à peu près décroissant, mais l'ordre n'est pas crucial)

en tout cas ça marche à présent :p