Discussion :

[camboui]

Bonjour,

J'ai une structure comme ceci:

Code :

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

1
2
3
4
5
6
template <typename K>
struct MonoStruct
{
	K s_;
	explicit MonoStruct(K const & s): s_(s) {}
};

Puis-je faire un reinterpret_cast<> en toute sécurité dans tous les cas comme ceci ?

Code :

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

1
2
	a_type a;
	MonoStruct<a_type> *ptr=reinterpret_cast<MonoStruct<a_type> *>(&a);

A priori je dirais oui, quelque soit le a_type.
Mais j'aimerais votre confirmation avant de faire une bêtise

[Bousk]

Salut,

je suis pas expert en trucs tordus comme ça^^ mais il faudrait y aller au crash test pour s'en assurer.
Sinon, je dirais que oui, tant que MonoStruct ne contient pas de méthodes virtual, auquel cas la vtable va poser problème dans ton reinterpret_cast amha.

[koala01]

Salut,

Si l'idée est de pouvoir profiter de quelque chose proche du DP décorateur, tu peux aisément remplacer l'instance de K s par... une référence (éventuellement constante) sur un objet de type K, sous une forme proche de

Code :

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

1
2
3
4
5
6
template <typename K>
struct MonoStruct
{
    K /* const */ & s;
    explicit MonoStruct(K /* const */ & s):s(s){}
};

qui pourrait très bien être utilisé sous la forme de

Code :

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

1
2
3
4
5
6
class MaClass : public MonoStruct<MaClass>
{
    public:
        MaClass(/* ...*/):MonoStruct<MaClass>(*this)/*,...*/{}
        /* ... */
};

Dés ce moment, tu n'a même plus besoin de "jouer" avec le transtypage car s étant une référence vers un objet de type K (qui est en fait l'objet dérivé de MonoStruct<K> pointé par this ), tu as directement accès à toutes les fonctions publiques de la classe K pour l'objet pointé par this

La seule chose, c'est qu'il faudra sans doute "déporter" la définition des fonctions qui font directement appel à s parce que tu risque d'avoir un problème au niveau de la compilation que la déclaration anticipée ne permettra pas de résoudre:

En effet, le code suivant ne fonctionnerait pas:

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
template <typename K>
struct MonoStruct
{
    K /* const */ & s; // pas de problème typename K sert de déclaration
                        // anticipée et l'on travaille avec une référence ;)
    MonoStruct(K /* const */ & s: s(s){} //idem
    void bar() /* const */
    {
        s.foo(); //Ouppps: K est connu du compilateur, mais K::foo() ne l'est pas
    }
 
};
class MaClass :: MonoStruct<MaClass>
{
    public:
        /* comme précédemment*/
        void foo()/* const */;
};

Il faut donc que l'implémentation de MonoStruct::bar puisse se trouver après la définition de Monostruct, sous une forme proche de

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 K>
struct MonoStruct
{
    K /* const */ & s; // pas de problème typename K sert de déclaration
                        // anticipée et l'on travaille avec une référence ;)
    MonoStruct(K /* const */ & s: s(s){} //idem
    void bar() /* const */;
 
};
class MaClass :: MonoStruct<MaClass>
{
    public:
        /* comme précédemment*/
        void foo()/* const */;
};
template <typename K>
void MonoStruct<K>::bar() /* const */
    {
        s.foo(); //aucun problème ici: K::bar() est connu :D
    }

NOTA: Peut être que l'utilisation intelligente de typename pourras profiter du SFINAE, mais je n'en suis pas sur du tout

[Flob90]

Oui, c'est valide. La raison est que ton type MonoStruct<T> est standard layout (norme 9 paragraphe 7, 9.2 paragraphe 19). Je te laisse lire l'ensemble des conditions exactes à respecter, mais elles sont au final assez large si tu fais attention.

Après je ne sais pas ce que tu cherches à faire, et la réponse de Koala sera peut-être plus adapté. Dans l'idée, si tu peux éviter ce reinterpret_cast, je te conseil de le faire (ça s'utilise, mais avec tellement de précautions qu'une fausse manipulation conduisant à un UB est vite arrivé, AMA).

[camboui]

Wow, Koala01

Bousk parlait de truc tordu, mais là c'est plus tordu encore je trouve. J'en ai les méninges toutes retournées et je vais avoir du mal à les remettre en place
A première vue, il s'agit d'avoir une classe de base qui contient la référence de toute instance de classe dérivée, ou en d'autres mots, une référence sur elle même.

Plus en détail.
J'optimize du code et il y a ça et là des copies et/ou des redondances que j'aimerais éviter lors de l'utilisation de containers.
Je pense que je devrais aussi regarder les nouvelles fonctionnalités de C++11 qui améliorent peut-être ces aspets (l'op move-ref && ?).

Exemple, le std::set<D> et son find(D const &).
Déjà, je n'aime pas trop que std::set gère des copies de D en interne.
De plus, je déplore de devoir instancier un type D entier lors d'une recherche alors qu'un nombre restreint de ses membres y suffiraient, genre find(K const &), sachant que D dérive de K.
(Entre parenthèse, il me semble avoir vu cette possibilité dans des containers de boost avec des méthodes supplémentaires genre find(Key const & k, Pred p))

Pour améliorer les choses, j'ai "triché" et j'utilise std::set<D *> (avec un pooler en parallèle et la gestion et les précautions qui vont avec).
Du coup, le paramètre de find() peut être "n'importe quoi", il suffit de caster en pointeur par un cast<D * const &> (d'où ma question initiale).

Voici le code avec la copie de trop à la fin à mon goût:

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
template <typename K>
struct MonoStruct
{
	K s_;
	explicit MonoStruct(K const & s): s_(s) {}
};
 
template <typename K, typename D>
struct FullStruct: MonoStruct<K>
{
	D v_;
	explicit FullStruct(K const & s): MonoStruct<K>(s) {}
	[...]
};
 
//du code...
 
std::set<MonoStruct<K> *, MonoStruct_PTR_LESS> aset;
...
FullStruct<K, D> *ptr=new(my_pooler.new_mem()) FullStruct<K, D>(k);
aset.insert(ptr);//introduction dans le container d'un pointeur de classe dérivée !
...
 
 
template<typename K>
void traitement(K const & k)
{
#if 0
	MonoStruct<K> tmp(k);
	//Oooh que je n'aime pas cette copie inutile, grrr :-(
	it=aset.find(&tmp);
#else
	MonoStruct<K> *ptmp=reinterpret_cast<MonoStruct<K> *>(&k);
	//Aaah, je me sens mieux, un simple cast suffit ;-)
	it=aset.find(ptmp);
#endif
...
}

Après relecture du post de koala01, je ne crois pas que son idée soit applicable ici (mais je me trompe peut-être). En effet, il n'y a qu'une seule instance de K, et elle se trouve dans FullStruct<K, D> via le pooler et après initialisation par (une seule) copie.
Si on remplace par une référence, où sera l'instance ?

Mais je vous vois venir...
Pourquoi ne pas utiliser std::map<> ?
J'aime pas trop les std::pair<>. Et je crois que les map sont un peu plus gourmands que les set (à tord ?)
Mais de fait, j'y songe, peut-être comme ceci:

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
template <typename K, typename D>
struct FullStruct
{
	K s_;
	D v_;
	explicit FullStruct(K const & s): s_(s) {}
	[...]
};
 
//du code...
 
std::map<K *, FullStruct<K, D> *, K_PTR_LESS> amap;
...
FullStruct<K, D> *ptr=new(my_pooler.new_mem()) FullStruct<K, D>(k);
amap.insert(make_pair(&ptr->s_, ptr));
...
 
 
template<typename K>
void traitement(K const & k)
{
	it=amap.find(&k);//tout simplement !
...
}

Et puis il y a l'obsession ultime du maniaco compulsif qui ne veut ni copie ni allocation de mémoire, après une phase unique d'initialisation, tout en consommant un minimum de mémoire.
Ce sera pour plus tard avec boost::intrusive::set<> (ou alors boost::intrusive::unordered_set<> ou boost::intrusive::unordered_map<>)

[Flob90]

Pourquoi ne pas utiliser l'algorithme std::find en version prédicat de l'en-tête algorithm, si ton objectif est juste de ne pas créer un D pour faire la recherche ?

[camboui]

Avec predicat il me semble que c'est std::find_if().

Cependant... Tu suggères une recherche linéaire dans les set ?
Je ne pense pas que ce soit très efficace

Mais comme je le disais, je crois que les boost::set contiennent justement un tel find() avec predicat.
Mais pourquoi ils ne les ont pas ajouter dans C++11 ?

[Flob90]

Si tu veux un prédicat perso, tu pourras pas faire mieux que linéaire dans le cas général, AMA.

http://www.boost.org/doc/libs/1_53_0...idp14056736-bb

Tu l'as trouvé où ton boost::set::find avec prédicat ? Parce que le fait l'algo soit logarithmique c'est du à la structure interne, si tu changes le prédicat de recherche, tu ne peux pas assurer cette performance.

[camboui]

C'est clair que le prédicat doit être cohérent avec celui de déclaration de classe set<> (qui est par défaut std::less je pense).
Je ne m'en suis jamais servi, j'avais juste aperçu ça il y a un temps déjà.

Voici un code de boost, extrait de boost::intrusive::set.hpp:

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
   //! <b>Effects</b>: Finds an iterator to the first element whose value is 
   //!   "value" or end() if that element does not exist.
   //!
   //! <b>Complexity</b>: Logarithmic.
   //! 
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
   iterator find(const_reference value)
   {  return tree_.find(value);  }
 
   //! <b>Requires</b>: comp must imply the same element order as
   //!   value_compare. Usually key is the part of the value_type
   //!   that is used in the ordering functor.
   //!
   //! <b>Effects</b>: Finds an iterator to the first element whose key is 
   //!   "key" according to the comparison functor or end() if that element 
   //!   does not exist.
   //!
   //! <b>Complexity</b>: Logarithmic.
   //! 
   //! <b>Throws</b>: If comp ordering function throws.
   //!
   //! <b>Note</b>: This function is used when constructing a value_type
   //!   is expensive and the value_type can be compared with a cheaper
   //!   key type. Usually this key is part of the value_type.
   template<class KeyType, class KeyValueCompare>
   iterator find(const KeyType& key, KeyValueCompare comp)
   {  return tree_.find(key, comp);  }

Et un autre, extrait de boost::unordered_set.hpp:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
        const_iterator find(const key_type& k) const
        {
            return const_iterator(table_.find(k));
        }
 
        template <class CompatibleKey, class CompatibleHash,
            class CompatiblePredicate>
        const_iterator find(
            CompatibleKey const& k,
            CompatibleHash const& hash,
            CompatiblePredicate const& eq) const
        {
            return iterator(table_.find(k, hash, eq));
        }

J'ose espérer qu'ils sont aussi efficaces que possible en fonction du container. En regardant le code, cela semble bien le cas pour unordered_set (à vérifier pour les autres).
Sinon c'est sans intérêt et autant ne pas les proposer, std::find_if suffisait.

[Flob90]

C'est intrusif ce boost::intrusive::set, tu ne peux pas le comparer à std::set, c'est différent : le caractère intrusif fait que les éléments stockés doivent avoir une certaine forme (et il ne sont pas copié).

En modifiant ta classe, il doit être possible d'autoriser une classe prédicat perso à construire uniquement "partiellement" un D, et ensuite l'utiliser avec ton find. Par contre je suis pas convaincu de l'utilité, il est vraiment lourd à construire ton temporaire ? Et sinon std::map résoudrait ton problème (tu sépares ta classe en deux), et je pense pas qu'il soit vraiment plus lent que std::set.

Je serais toi, je regarderais aussi du côté d'un vecteur avec recherche linéaire, c'est une solution qui, bien qu'en complexité moins bonne, se révèle parfois plus efficace.