Discussion :

[elraton]

Bonjour,


Bon voila j'ai un probleme au niveau des sorts en C++, et je me pose plusieurs questions.

Pour résumer l'idée: J'ai une image, et une liste de petit patch 20x20 pixels a differentes positions sur cette images.

chaque patch à :

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
 
class MptIIMPatch {
private:
	uint32 _x,_y; //Coordonées du patch sur l'image
	int _nof_histo;
	double _entropy; //Entropy de l'histogram du patch
public:
	uint32 *histo; //Tableaux representant un histogram a 16 niveaux
        uint32 mean,var; //moyenne et variance du patch sur l'image.
 
 
	// Constructor Destructeur etc..
...
 
};

mon but etant donc de tester environ 500 patchs aléatoirements et de les trier selon leur entropy pour recuperer les 50 meilleurs.

Alors comme je commence le c++ j'essaye d'utiliser au plus les library.

Idée 1:
Remplir un vecteur avec chaque entropy, remplir un autre avec des index de 0 à 499, et faire un sort sur l'entropy et de swaper l'index simultanéments. (Pour ceux qui utilise matlab je pense que vous avez déjà testé cette fonction)

Le but etant donc d'avoir un tableaux avec l'entropie ordonnée mais aussi un autre avec l'ancien index de l'entropie avant le sort. ainsi je prend les 50 premiers index et retrouve les 50 meilleurs patchs.

J'ai cherché un peu dans la stl mais j'ai rien trouvé qui puisse faire ca.

Idée 2:
utiliser le custom sort du FAQ. : http://c.developpez.com/faq/cpp/?pag...TL_custom_sort

Malheureusement ca marche pas avec ma class

Voila ce que j'ai fait (dans une classe contenant plusieurs object dont un vecteur de MptIIMPatch;

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
/* in MptLayIIM.hpp */
 
#include <vector>
#include <algorithm>
#include "MptIIMPatch"
 
class MptLayIIM {
private:
        ...
	std::vector<MptIIMPatch> _patchVec; 
public:
...
};
 
/* in MptLayIIM.cpp */
 
struct SortByEntropy
{ 
    bool operator ()(const MptIIMPatch & p1,const MptIIMPatch & p2 ) const 
    { 
        return p1.getEntropy() < p2.getEntropy(); 
    } 
}; 
 
void MptLayIIM::getGoodPatches(int nof_patch) {
	//Check Vector size
	if(_patchVec.size() != nof_selected) _patchVec.resize(nof_patch);
	//Build new random coordinate value
	this->setRandPatchesCoord(nof_patch);
	//Get Patches Values for testing
	this->getPatchesValues(nof_patch);
 
	for(int i(0);i<N_PTEST;++i) {
			_patchVec[i].setEntropy();
		}
		std::sort(_patchVec.begin(),_patchVec.end(), SortByEntropy()); 
 
}

Bon ma premiere erreur sont les const qui ne marche pas mais meme si je les enleves j'ai bcp d'erreur provenant de la stl

Ex:/usr/lib/gcc/i486-linux-gnu/4.0.3/../../../../include/c++/4.0.3/bits/stl_algo.h: In function «const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = MptIIMPatch, _Compare = SortByEntropy]»:

De plus je me demandais comment fonctionnait ce sort,
si il copiait les pointeurs sur les objets (ou leur references) sans copié lchaques champs ou il fait une copie de chaque champs (dans ce cas que ce passe t'il avec uint32 histo[].


PS: Je me souviens d'avoir utiliser une fois en C un sort qui n'est pas complet... c.a.d je sort les 50 premiers et le reste ca m'est égal. si vous vous souvener du nom ca m'interesse.

Merci d'avance !!!

[Luc Hermitte]

Code :

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

1
2
3
4
std::vector<MptIIMPatch> _patchVec; 
....
class MptIIMPatch {
...	uint32 *histo;

j'espère que c'est une vue et non une donnée dont MptIIMPatch est responsable. Tu vas avoir des ennuis sinon.

Tu peux ensuite avoir un vecteur d'indices qui pointent vers _pathVec (NB: le préfixage par _ est globablement réservé aux implémenteurs du standard), et trier ces indices selon un prédicat qui va comparer les _pathVec[] indicés par les éléments triés.

J'avais pas posté une solution qui faisait cela il y a bien longtemps? (*)
Sinon, je crois que boost.multi_index sert dans cette thématique.

Si ton tri tu ne le veux pas complet, tu peux utiliser les autres fonctions de tri de <algorithm>. -> std::partial_sort. (et sa version stable).

(*) Visiblement oui, vu que j'ai retrouvé le code

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <vector>
#include <algorithm>
#include <iostream>
 
struct paire : std::pair<int, int> {
    paire(int i) {
        static int j;
        first = i;
        second = j++;
    }
    friend bool operator<(const paire & p1, const paire & p2) {
        return p1.first < p2.first;
    }
 
    friend std::ostream & operator<<(std::ostream & os, const paire p) {
        return os << p.first << "  -- " << (1+p.second) << "e";
    }
};
typedef std::vector<paire> V;
 
template <typename T>
struct PrintToOs 
{
    PrintToOs(std::ostream & os) : os_(os) {}
    std::ostream & operator() (const T* v) const {
        return os_ << *v << std::endl;
    }
    std::ostream & operator() (const T & v) const {
        return os_ << v << std::endl;
    }
private:
    std::ostream & os_;
};
 
int main (int argc, char **argv)
{
    int tab[] = { 34, 8, 6, 23 };
    V v(tab, tab+(sizeof(tab)/sizeof(tab[0])));
 
    std::sort(v.begin(),v.end());
    std::vector<int> r(sizeof(tab)/sizeof(tab[0]));
    int i=0;
    for (V::const_iterator it=v.begin(); it != v.end(); ++it) {
        r[it->second] = ++i;
    }
 
    std::for_each(v.begin(),v.end(), PrintToOs<paire>(std::cout));
    std::cout << "Résultat:\n";
    std::for_each(r.begin(),r.end(), PrintToOs<int>(std::cout));
 
    return 0;
}

C'est bizarre, il me semblait m'y être déjà pris autrement et bien plus simplement, mais je ne retrouve pas. Mais bon, c'est tellement vite refait.

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <vector>
#include <algorithm>
#include <iostream>
 
template <typename T> struct IndirectCmp
{
    IndirectCmp(T const* first) : first_(first) {}
    bool operator()(int rhs, int lhs) const {
        return first_[rhs] < first_[lhs];
    }
private:
    T const * first_;
};
 
 
int main ()
{
    const int tab[] = { 34, 8, 6, 23, 12 };
    const int S = sizeof(tab)/sizeof(tab[0]);
    std::vector<int> indices(S);
 
    unsigned int nb;
    while (
            std::cout << "\nOn en tri combien (<="<<S<<")?\n-> "
            , std::cin >> nb)
    {
        if (nb > S) { continue; }
 
        for (int i=0; i!=S ; ++i) { indices[i] = i; }
 
        std::partial_sort(
                indices.begin(),
                indices.begin()+nb,
                indices.end(),
                IndirectCmp<int>(&tab[0]));
 
        for (int i=0; i!=S ; ++i) {
            const int idx = indices[i];
            std::cout << "t[" << idx << "]=" << tab[idx] << "\n";
        }
    }
 
    return EXIT_SUCCESS;
}

Je te laisse adapter. Il y a moyen de rendre IndirectCmp plus générique pour utiliser autre chose que "<" pour réaliser la comparaison.

[loufoque]

Bon ma premiere erreur sont les const qui ne marche pas mais meme si je les enleves j'ai bcp d'erreur provenant de la stl

Ta fonction membre getEntropy n'est probablement pas const.
Apprends à écrire de manière const-correcte et plus aucun problème.

Ex:/usr/lib/gcc/i486-linux-gnu/4.0.3/../../../../include/c++/4.0.3/bits/stl_algo.h: In function «const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = MptIIMPatch, _Compare = SortByEntropy]»:

Ceci n'est pas une erreur. Ça indique simplement où l'erreur s'est produite.
Apprends à lire et à comprendre les messages d'erreurs.

uint32 *histo; //Tableaux representant un histogram a 16 niveaux

Fortement déconseillé, à moins que tu cherches à optimiser l'utilisation mémoire de MptIIMPatch.

[elraton]

Hummmm je comprend pas quel est le probleme avec mon tableau d'histogram...?? Je ne suis pas sur voir comment je peux mieux faire?

Je remet le code pour que vous compreniez la construction

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
/* In MptIIMPatch.hpp */
 
class MptIIMPatch {
private:
	uint32 _x,_y; //Coordonées du patch sur l'image
	int _nof_histo;
	double _entropy; //Entropy de l'histogram du patch
public:
	uint32 *histo; //Tableaux representant un histogram a 16 niveaux
        uint32 mean,var; //moyenne et variance du patch sur l'image.
 
 
	/**************************/
 
	// Default Constructor	
	MptIIMPatch();
	// Constructor
	MptIIMPatch(int nb_histo);
	// Destructor
	~MptIIMPatch(void);
 
	/**************************/
 
	void create(int nb_histo);
        inline double getEntropy() const;
...
}
inline double MptIIMPatch::getEntropy() const { return _entropy; }
 
/* In MptIIMPatch.cpp*/
 
#include "MptIIMPatch.hpp"
 
 
MptIIMPatch::MptIIMPatch() 
: _x(0), _y(0),mean(0), var(0), _nof_histo(0), _entropy(0), histo(0) {
}
 
MptIIMPatch::MptIIMPatch(int nb_histo) {
	this->create(nb_histo);
}
 
MptIIMPatch::~MptIIMPatch() {
	delete[] histo;
}
 
void MptIIMPatch::create(int nb_histo) {
	_x=0;  _y=0; 
	_nof_histo = nb_histo;
	_entropy = 0.0;
	mean=0; var=0;
	histo = new uint32[_nof_histo];
}
....

Car je suis obliger de mettre un pointeurs pour pouvoir intialiser mon tableaux ainsi.
Bien sur je pourrais utiliser un vector<uint32> histo, mais j'ai pas vraiment besoin de ca.

EDIT: Bon je crois que j'ai quand meme un probleme dans ma version du custom sort ...
...
Entering sortByEntropy
Entering sortByEntropy
*** glibc detected *** double free or corruption (fasttop): 0x080543a0 ***
Abandon

C'est a dire que je ne sais pas vraiment ou est l'erreur mais ca doit surement venir de mon probleme dans *hito

Le mieux pour moi serait d'avoir un vecteur de pointeur sur les object patch, vector<MptIIMPatch *>
Et de pouvoir reordoné ces pointeurs sans copié les objets MptIIMPatch.

Sinon ca serait la structure paire comme dans l'exemple.

(NB: le préfixage par _ est globablement réservé aux implémenteurs du standard),

Moi j'ai lu que c'etait pour faire la distinction entre les variables private et public...
Enfin bon ...




Sinon pour le const, cela fait que je suis obliger d'appeler getEntropy() avec un objet constant, car j'ai fait un test avec mon _patchVec et ca marche sans avoir besoin de const.

[elraton]

Voila ma solution mais ca reste tres inspiré du C

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
25
 
 
struct SortByEntropyP {
    bool operator ()(const MptIIMPatch* p1,const MptIIMPatch* p2 ) const 
    {
        return p1->getEntropy() < p2->getEntropy(); 
    } 
}; 
 
void MptLayIIM::filtersPatches(int method) {
 
	std::vector<MptIIMPatch *> pPatchVec(N_PTEST);
 
 
	switch(method) {
		// Technique #2 : Entropy (shanon) 
		case ENTROPY_FILTER:
		for(int i(0);i<N_PTEST;++i) {
			_patchVec[i].setEntropy();
			pPatchVec[i] = &_patchVec[i];
		}
         	     std::partial_sort(pPatchVec.begin(),pPatchVec.begin+50,pPatchVec.end(), SortByEntropyP()); 
		for(int i(0);i<70;++i)	pPatchVec[i]->print();
	}
}

Comme ca ca marche parfaitement mais ca reste une solution tres orienté C, C'est dommage que j'ai ce probleme avec l'autre version ...

Qqun peut m'expliquer comment ca marche ce sort (au niveau de la copy des elements) car j'aimerais bien eviter de programmer en C et faire plus orienté C++

[Luc Hermitte]

Ne saute pas d'étapes. C'est normal que tu aies des problèmes avec ça. Reprends la plus simple expression de ta modélisation.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
struct T {
   T() : t_(new int[10]) {}
   ~T() { delete[] t_; }
private:
   int * t_;
};
T ta1;
T ta2(t1); // ka-boum
 
T tb1;
T tb3;
tb3 = tb1; // re ka-boum + fuite de mémoire.

Il y a ici un problème de dangling pointer (quelqu'un a une traduction intelligente?), car après copie tu auras une double destruction de la même zone. Je vois que le message d'erreur de la glic est d'ailleurs on ne peut plus clair.
NB: pour les newbs qui tombent là dessus après une recherche, ce bout de code est le plus pur exemple de mauvais code à bannir!

Bref, quand tu veux une sémantique de copie (ou plus généralement de valeur) pour tes objets, alors que ceux-ci sont responsables d'une (ou plusieurs) ressource(s), alors il faut blinder.

Une des diverses raisons qui fait que l'on préfère systématiquement utiliser des vecteurs qui sont copiables (au prix d'une duplication des éléments) -- une raison bien plus critique est la résistance aux exceptions qu'ils offrent.

Je pense que tu auras divers éléments à assimiler dans la FAQ aux chapitres sur le RAII & cie -- je ne sais plus si elle traite des diverses façon de définir des copies, ou des les interdire.

[elraton]

Oky je pense avoir compris maintenant, dites moi si c'est bien ca ou pas...

le sort doit surement appeler une fonction swap qui prend 2 objets MptIIMPatch en reference et fait ainsi:

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
 
swap(MptIIMPatch &obj1,MptIIMPatch &obj2) {
 
 
if(sortByEntropy(obj1,obj2)) {
    MptIIMPatch obj_tmp;
    obj_tmp=obj1;
    obj1=obj2; 
//pour l'instant tout c'est bien passer car on a bien copié
// l'adresse du pointeur obj2.histo dans obj1.histo 
    obj2=obj_tmp; 
} 
// On sort de la fonction et boum on detruit obj_tmp et on delete le 
// pointeur histo, qui malheureusement represente la meme memoire que obj2... 
//donc obj2 se retrouve avec un delete [] histo qui n'aurait pas du exister
 
}

Donc finalement je garde quand meme mon sort avec des pointeurs car c'est plus efficaces... on evite de copié un objet a chaque swap...


Ceci dit il me reste 2 tites questions apres avoir lu la FAQ...

1--> pour l'initialisation de std::vector<MptIIMPatch> _patchVec

si je doit initialiser ca taille a la construction d'un objet l'englobant, comment je doit faire...???

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 MptLayIIM::MptLayIIM(IplImage * im,int nb_histo) {
	_rows = (int)im->height+1;
	_cols = (int)im->width+1;
	_nof_histo=nb_histo;
	...
	//Create all matching point
	_patchVec.reserve(N_PTEST);
	for(int i(0);i<N_PTEST;i++){
		MptIIMPatch new_patch(_nof_histo);
		_patchVec.push_back(new_patch);
	}
 
}

ou alors il y a une maniere plus intelligente, parceque resize reserverais bien l'espace suiffisant en creant la taille correct mais je ne peux pas construire en meme temps le tableaux histogram dans ma classe MptIIMPatch.

Et enfin pourquoi il faut mettre dans sortByEntropy dans une structure ...???

[Luc Hermitte]

Tu es mort sur les copies et les affectations. Avant même le swap, tu es fini dans le push_back du vecteur qui réalise une copie.
Ton MptIIMPatch a une ressource brute, il en es responsable, mais il ne sait pas se faire copier tout en gérant correctement la ressource.

[elraton]

hummm c'est pas pour etre mauvaise langue mais j'ai pas compris la reponse ...

tu parle de quoi de mon probleme avec le pointeur *histo

ou de ma maniere d'affecter mes variables...

[Luc Hermitte]

C'est le même problème, non?
J'en suis resté à m_histo détruit dans le destructeur, et à l'absence de constructeur de copie et d'opérateur d'affectation. Je me trompe ?

Tant que cela ne sera pas corrigé, ta classe ne sera pas copiable. Tu ne pourras jamais stocker ces élements par valeur dans un vecteur, ou réaliser des swap entre eux.

[elraton]

Oky donc simplement en mettant un std::vector a la place d'un tableau ca a fonctionner...

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
 
/* MptIIMPatch.hpp */
 
#include <vector>
class MptIIMPatch {
private:
	uint32 _x,_y;
	int _nof_histo;
	double _entropy;
public:
	uint32 mean,var;
	std::vector<uint32> histo; 
 
	/**************************/
 
	// Default Constructor	
	MptIIMPatch();
	// Constructor
	MptIIMPatch(int nb_histo);
	// Destructor
	~MptIIMPatch(void);
 
....

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
25
26
 
/* MptIIMPatch.cpp */
 
#include "MptIIMPatch.hpp"
 
MptIIMPatch::MptIIMPatch() 
: _x(0), _y(0),mean(0), var(0), _entropy(0) {
}
 
MptIIMPatch::MptIIMPatch(int nb_histo) {
	this->create(nb_histo);
}
 
MptIIMPatch::~MptIIMPatch() {
	histo.clear();
}
 
/********************************************/
 
void MptIIMPatch::create(int nb_histo) {
	_x=0;  _y=0; 
	_entropy = 0.0;
	mean=0; var=0;
	histo.reserve(nb_histo);
	histo.resize(nb_histo);
}

Avec les std::vector je pense que le copy se fait automatiquement correctement.

Est-ce que j'ai besoin de faire un constructeur par copie?
Est-ce que j'ai besoin de faire un operateur d'affectation?
Est-ce que l'initialisation de histo est juste ou il y a une meilleur maniere?


Et je reviens donc a ma question d'avant sur le vecteur de MptIIMPatch
Est-ce la bonne maniere d'initialiser ce _patchVec ?

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
25
26
 
/*MptLayIIM.hpp*/
class MptLayIIM {
private:
	std::vector<MptIIMPatch> _patchVec;
...
public:
        // Constructor
	MptLayIIM(IplImage * im, int nb_histo=16);
...
}
 
/* MptLayIIM.cpp */
MptLayIIM::MptLayIIM(IplImage * im,int nb_histo) {
	_rows = (int)im->height+1;
	_cols = (int)im->width+1;
	_nof_histo=nb_histo;
	...
	//Create all matching point
	_patchVec.reserve(N_PTEST);
	for(int i(0);i<N_PTEST;i++){
		MptIIMPatch new_patch(_nof_histo);
		_patchVec.push_back(new_patch);
	}
 
}

Je suis désolez mais ce genre de problemes (subtilitée) n'est pas expliquer dans la FAQ ni dans aucun des cours C++ que j'ai lu

[Luc Hermitte]

Je sais bien. Je le rabache régulièrement. Heureusement, cela va faire parti de la prochaine mouture de la FAQ -- merci Laurent.
(Ils n'en parlent pas dans AC++ ? -- je l'ai laissé au taf', et ne sais donc plus.)

En gros. Quand tu as une classe dont tous les membres sont copiables, alors ta classe est copiable sans que tu n'aies rien à écrire (constructeur de copie, opérateur d'affectation, destructeur). Si ta classe est responsable d'une ressource brute, là, il te faut spécifier ces choses.

Autrement,
- Le clear est inutile dans le destructeur -- car implicite
- Si tu fais un resize, le reserve est inutile. resize() appellant reserve(). reserve est une optimisation pour quand on sait combien d'éléments devront être empilés. reserve() est d'ailleurs parfaitement bien utilisé dans le constructeur de MptLayIIM
- Mon expérience est que ta fonction create (généralement appellé init()) est une mauvaise pratique. Tu ne sembles disposer que d'un seul constructeur d'initialisation, fais-y tout. =>

Code :

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

1
2
3
4
5
MptIIMPatch::MptIIMPatch(int nb_histo /*= 0*/)
: x_(0), y_(0), entropy_(0)
, mean_(0), var_(0)
, histo_(nb_histo)
{}

(NB: le préfixage par _ est globablement réservé aux implémenteurs du standard),

Moi j'ai lu que c'etait pour faire la distinction entre les variables private et public...
Enfin bon ...

Peut-être en Java, certainement pas en C et par extension en C++. Tu n'es pas à l'abri d'utiliser un symbole réservé qui aura des effets de bords que tu ne verras même pas venir. "_MAX" est l'exemple typique que tu aurais très bien pu utiliser dans ta classe de statistiques pour représenter une constante membre. Et là, ka-boum avec VC, qui dans droit, l'utilise comme une macro.