Trie de pointeurs dans un vecteur

Version imprimable

22/09/2009, 22h00
toams69

Trie de pointeurs dans un vecteur

Bonjour a tous,

Je suis actuellement entrain de coder l'algorithme de Huffman, et tout se passe bien mis a part le fait que j'ai un temps de compression tres long.
J'ai reussi a cibler le probleme, celui ci se trouve dans mon Vector<GSheet>.
Il s'agit d'un Vector que j'ai code, celui possede des methodes qui permettent d'ajouter un element au meilleur endroit afin que le Vector soit toujours trie.
Ceci fonctionne tres bien car j'ai surcharge l'operateur<= de ma classe GSheet.
Mais cela ne fonctionne pas lorsque j'ai un Vector<GSheet*> car la comparaison ne se fait non pas sur l'element mais sur l'adresse en memoire du pointeur. Ce qui ne m'interesse pas evidement.
J'ai essaye beaucoup de surcharges d'operateur friend ou non. Rien ne passe.
Si quelqu'un a une idee. Merci de me la communiquer car je l'attend avec impatience, je n'ai pas reussi a trouver en y passant l'apres midi.

Merci d'avance

Sans quelques bribes de code, on ne peut rien faire.

Mais voici un code rapide d'exemple:

Code:

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
#include <iostream>
#include <algorithm>
#include <vector>
 
struct Sorter
{
    template <class T> bool operator()(const T a,const T b)
    {
	return a<b;
    }
 
    template <class T> bool operator()(const T* a,const T* b)
    {
	return *a<*b;
    }
};
 
struct Deleter
{
    template<class T> void operator()(T* t)
    {
	delete t;
    }
};
 
int main(int argc, char const *argv[])
{
    std::vector<int*> v;
    v.push_back(new int(1));v.push_back(new int(5));v.push_back(new int(2));v.push_back(new int(-5));
    std::sort(v.begin(),v.end(),Sorter());
 
    for(int i=0;i<v.size();++i)
	std::cout<<*v[i]<<std::endl;
 
    std::for_each(v.begin(),v.end(),Deleter());
    v.clear();
std::cout<<"====="<<std::endl;
    std::vector<int> v2;
    v2.push_back(1);v2.push_back(5);v2.push_back(2);v2.push_back(-5);
    std::sort(v2.begin(),v2.end(),Sorter());
 
    for(int i=0;i<v2.size();++i)
	std::cout<<v2[i]<<std::endl;
 
 
    return 0;
}

Tu peux utiliser les templates pour résoudre ce problème:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
template< class T >
struct IsPointer
{
	enum { type = false };
};
 
template< class T >
struct IsPointer< T* >
{
	enum { type = true };
};
 
struct s{};
 
int main()
{
	std::cout << IsPointer< s >::type << "\n"; // false
	std::cout << IsPointer< s* >::type << "\n"; // true
}

Et ensuite adapter ton code:

Code:

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
#include <iostream>
#include <vector>
 
template< class T >
struct IsPointer
{
	enum { pointer = false };
};
 
template< class T >
struct IsPointer< T* >
{	
	enum { pointer = true };
};
 
template< int T >
struct Selector 
{
	enum { val = T };
};
 
template< class T >
class Vector
{
	void insert_impl( T a, Selector< true > ) // pointer
	{
		std::cout << "inserting referenced value = " << *a;
	}
 
	void insert_impl( T a, Selector< false > ) // non-pointer
	{
		std::cout << "inserting value = " << a;
	}
public:
	void insert( T a )
	{
		insert_impl( a, Selector< IsPointer< T >::pointer >() );
	}
};
 
 
int main()
{	
	Vector< int* > v;
	v.insert( new int(1) );
 
	Vector< int > v2;
	v2.insert( 2 );
}

Edit: En fait, la méthode de David est plusse mieux si tu peux l'appliquer :)

22/09/2009, 23h12
toams69

Merci pour vos reponses.
Mais je ne veux pas utiliser la librairie std, c'est d'ailleurs pour cela que je la recode.
J'ai trouve une solution a l'instant qui m'a permis de passer de 40sec a 400ms de temps de traitement.
Et le code de mes vector etant templete je ne peux y ajouter de specificites.
Ma solution est donc simple : plutot que de faire determiner a la classe vector ou je dois placer cet element, je le fais faire par la methode qui ajoute dans le vecteur.
Je vais quand meme prendre le temps d'etudier vos reponses, car elles peuvent mettre utiles pour la suite. La deuxieme me parrait bien car (je suis desole pour la std) elle n'utilise pas la std et permet pas mal d'adaptibilite.

Merci beaucoup en tout cas.
Et a bientot.
22/09/2009, 23h22
Goten

Le code est voué à être exécuté dans de l'embarqué? (ou autre système critique?)
Sinon y'a aucune raison de pas vouloir de la STL. (et même dans ces cas là...)
23/09/2009, 10h05
Alp

Pourquoi ne pas utiliser un std::set ?

Quand à l'adaptabilité, je ne veux pas être méchant mais je pense que la STL fait bien mieux que la plupart des gens...