Discussion :

[vandamme]

J'ai un pb tres simple, je veux tranformer un const vector<T> en un vector<T*>.
Voici un extrait de mon code qui le fait :

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
    template<typename T>
    struct ToPtr : public std::unary_function<T, T*>
    {
        T* operator()(const T& value)
        {
            return const_cast<T*>(&value);
        }            
    };
 
template<typename T>
    void MyClass::order(const vector<T>& in,
                        vector<T*>& out) const
    {
 
            out.reserve(in.size());
            std::transform(in.begin(),
                               in.end(),
                               std::back_inserter(out),
                               ToPtr<T>());
}

Ce code marche tres bien mais ce qui me gene c'est le const_cast dans le foncteur. Est - ce qu'il existe une meilleure conception pour convertir un const vector<T> en vector<T*> ?

[JolyLoic]

Tu as un vector<T> const, donc une variable à partir de laquelle tu promets de ne pas modifier le contenu du vecteur. Tu veux obtenir un vector<T*>, qui permet donc de modifier les T contenue dans le premier vecteur.

Il me semble donc normal que tu aies besoin d'un const_cast, puisque tu souhaites ne pas permettre la modification d'objets constants.

Ton code est moralement équivalent à :

Code :

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

1
2
int const i = 3;
int *j = &i;

La vrai question est pourquoi tu souhaites faire ça...

[vandamme]

Simplement parce que T est un tres gros type et que je veux trier les elements du vecteur. Donc je passe par un vecteur de T* qui sera beaucoup plus rapide a trier qu'un vecteur de T .
Mais si tu as une autre solution, je suis preneur.

[koala01]

Simplement parce que T est un tres gros type et que je veux trier les elements du vecteur. Donc je passe par un vecteur de T* qui sera beaucoup plus rapide a trier qu'un vecteur de T .
Mais si tu as une autre solution, je suis preneur.

Qu'est ce qui te fait penser que le T* sera plus rapide à trier que le T&

Si tu veux trier les ardresses, peut etre, mais autrement, je n'en suis pas sur du tout

[Laurent Gomila]

Qu'est ce qui te fait penser que le T* sera plus rapide à trier que le T&

Les nombreuses recopies induites par le tri.

Mais si tu as une autre solution, je suis preneur.

Transforme en vector<const T*>, tu n'auras pas besoin de casser le const.

[koala01]

Les nombreuses recopies induites par le tri.

Ah oui, je n'y avais pas pensé, à celles là

[vandamme]

Les nombreuses recopies induites par le tri.


Transforme en vector<const T*>, tu n'auras pas besoin de casser le const.

OK. j'essaierai cette solution. En fait je pensais que const vector<T*> etait equivalent a vector<const T*>.

Par contre une autre idee me vient pour le tri.
Est ce qu'en utilisant une list au lieu d'un vector, et en particulier sa fonction membre sort, je peux eviter les recopies lors du tri ?

[Laurent Gomila]

Par contre une autre idee me vient pour le tri.
Est ce qu'en utilisant une list au lieu d'un vector, et en particulier sa fonction membre sort, je peux eviter les recopies lors du tri ?

Carrément pas. Comment veux-tu ordonner les éléments sans les déplacer (ie. les recopier) ? En plus, le tri sur std::list sera encore plus lent du fait que ses itérateurs ne sont pas à accès aléatoire.

[vandamme]

Carrément pas. Comment veux-tu ordonner les éléments sans les déplacer (ie. les recopier) ? En plus, le tri sur std::list sera encore plus lent du fait que ses itérateurs ne sont pas à accès aléatoire.

Ah d'accord.
Je pensais en fait que un node dans une liste etait compose d'un element T et d'un pointeur vers le suivant et/ou le precedent T. Et je pensais que seul le pointeur etait modifie pdt le tri mais que les elements n'etaient pas inpactes.

[Laurent Gomila]

Je pensais en fait que un node dans une liste etait compose d'un element T et d'un pointeur vers le suivant et/ou le precedent T. Et je pensais que seul le pointeur etait modifie pdt le tri mais que les elements n'etaient pas inpactes.

En fait... oui (faut vraiment plus que je réponde avant d'avoir bu mon café du matin)

[screetch]

std::sort ne marche que sur les iterateurs a acces aleatoire, donc pas sur les listes, ce qui resout le probleme

en revanche std::list a une fonction sort()

exemple :

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
#include <vector>
#include <list>
#include <algorithm>
 
static int numCopies;
static int numAffectations;
 
struct StructureATrier
{
	int m_value;
	StructureATrier(int value) :
		m_value(value)
	{}
	StructureATrier(const StructureATrier& other) :
		m_value(other.m_value)
	{ numCopies++; }
	StructureATrier& operator=(const StructureATrier& other)
	{ m_value = other.m_value;  numAffectations++;  return *this; }
};
 
bool operator<(const StructureATrier& _Left, const StructureATrier& _Right)
{ return _Left.m_value < _Right.m_value; }
 
 
int main(int argc, char** argv)
{
	std::vector< StructureATrier > v;
	std::list< StructureATrier > l;
	for(int i = 72; i >= 0; --i)
	{
		v.push_back(StructureATrier(i));
		l.push_back(StructureATrier(i));
	}
	numCopies = numAffectations = 0;
	std::sort(v.begin(), v.end());
	printf("vector : %d copies, %d affectations\n", numCopies, numAffectations);
	numCopies = numAffectations = 0;
	l.sort();
	printf("list : %d copies, %d affectations\n", numCopies, numAffectations);
}

Resultat instructif, surtout pour ceux qui ont pas pris le café ^^

[vandamme]

Oui tout a fait.
D'ailleurs je parlais bien de la fonction membre sort de list et non pas de l'algo standard

[screetch]

trier une liste a la meme complexite algorithmique que trier un vector mais evite les copies. Les insertions au milieu sont plus rapides, mais tout depend de la taille.

Si tu vas traiter 50 elements tu ne verras meme pas la difference ^^