Discussion :

[camboui]

Pour placer les instances d'une classe dans un container intrusif, il faut que cette classe dérive d'un "hook".

Mais je souhaite introduire des pointeurs vers des instances de classes dans un container intrusif. Comment faire ?

Code :

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

1
2
3
4
5
cell: boost::intrusive::unordered_set_base_hook<>
{
};
boost::intrusive::unordered_set<cell>  cell_set;//OK
boost::intrusive::unordered_set<cell *>  cellptr_set;//PAS OK

Merci.

[Emmanuel Deloget]

Pour placer les instances d'une classe dans un container intrusif, il faut que cette classe dérive d'un "hook".

Mais je souhaite introduire des pointeurs vers des instances de classes dans un container intrusif. Comment faire ?

Code :

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

1
2
3
4
5
cell: boost::intrusive::unordered_set_base_hook<>
{
};
boost::intrusive::unordered_set<cell>  cell_set;//OK
boost::intrusive::unordered_set<cell *>  cellptr_set;//PAS OK

Merci.

Est-ce que encapsuler cell* est possible ? (je n'en sait rien - je n'ai jamais utilisé boost::intrusive)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class cell_ptr : public boost::intrusive::unordered_set_base_hook<>
{
  cell* c;
public:
  cell_ptr(cell* ptr) : c(ptr) { }
  cell_ptr() : c(NULL) { }
  cell_ptr(const cell_ptr& other) : c(other.c) { }
  cell_ptr& operator=(const cell_ptr& other)
  { c = other.c; return *this; }
  cell* operator->() { return c; }
  cell& operator*() { return *c; }
  const cell& operator*() const { return *c; }
}

[Arzar]

Il ne me semble pas que ce soit possible, sauf peut être en bricolant un smart_ptr maison...

Mais à vrai dire, je ne comprends pas bien l'intérêt de la manoeuvre.
Pourquoi un cell* ? L'avantage des conteneurs de boost.intrusive, c'est justement qu'ils ne copient pas l'instance mais au contraire travaillent directement dessus, sans aucune allocation supplémentaire et en se limitant à modifier les liens contenus dans le hook, non ?

[camboui]

Intrusif ou pas, il y a des raisons pour lesquelles on fait des conteneurs de pointeur. La première qui me vient à l'esprit est d'éviter de dédoubler des instances dans de multiples conteneurs.

Dans mon cas, j'ai déjà une conteneur intrusif de type list. Je souhaite un autre conteneur de type unordered_set qui contient des pointeurs vers les instances de la liste.

Alors oui il semble qu'on puisse enrober les pointeurs comme le suggère Manu. En tout cas ça compile. Mais j'ai un warning que je ne parviens pas à comprendre (ni même à situer dans le code, car il est perdu dans boost::labyrinte::usine-a-gaz) et, surtout, ça plante à l'exécution.

Arzar, tu te souviens du cache template il y a quelques mois ?
Je suis revenu dessus en le "terminant"
Reste que tu avais proposé une superbe solution en utilisant les intrusives de boost. Malheureusement, dans ta proposition tu dédoublais les instances internes du cache dans une intrusive_list et dans un intrusive_unordered_set. Je me demande d'ailleurs si je ne devrais pas ressortir cette discussion dans l'autre forum car il y a un truc que je n'ai jamais compris: comment donc on spécifie quels prédicats sont utilisés dans le intrusive_unordered_set ?

[Arzar]

Je ne comprends pas trop de quel dédoublement il est question ? (ou alors j'ai mal compris comment le fonctionnement de boost.intrusive)

La taille de l'objet augmente un peu à chaque hook ajouté (deux pointeurs pour une liste, trois pointeurs pour un unordered_set), c'est ça que tu désignes par "dédoublement" ?

Par exemple (de mémoire)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
struct S : public hook_list, public hook_unordered_set
{
};
 
std::vector<S> sVec;
boost::intrusive::list<S> sList;
boost::intrusive::unoredered_set<S> sHash;
 
sVec.push_back(S());
sList.push_back(sVec.back());
sHash.push_back(sVec.back());

Toutes les instances de S sont stockés dans le vecteur et uniquement dans le vecteur. La liste intrusive et le hash intrusif n'allouent aucune instance supplémentaire. Ils se contentent de modifier les instances contenus dans le vecteur. Le "push_back" de la liste intrusive va juste setter comme il faut les pointeurs prev et next de l'élement précédent et du nouveau.

D'ailleurs si l'on détruit toutes les instances sous-jacentes à la liste intrusive par un clear() du vecteur, alors toute utilisation de la liste nous crachera un assert à la figure. (en fait uniquement si les hooks sont des "safe-hook", mais par défaut ils le sont)

Si l'on tient vraiment à du S*, alors il me semble qu'il faut faire comme ça :

Code :

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

1
2
3
4
5
6
 
std::vector<S*> sVecPtr;
boost::intrusive::list<S> sList;
//...
sVec.push_back(new S);
sList.push_back(*(sVec.back()));

[camboui]

C'est peut-être moi qui est mal compris alors
Voici un copier de ton code de l'époque:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   typedef boost::intrusive::list<Entry> EntryList;
   typedef boost::intrusive::unordered_set<Entry>  EntryHashSet;
   typedef typename EntryHashSet::bucket_type  BucketType;
   typedef typename EntryHashSet::bucket_traits  BucketTraits;
   
   //ici, un vector avec les instances pour la liste
   std::vector<Entry> entryPool_;
   EntryList entryList_;
   
   // BE CAREFUL, the vector of bucket must be declared before the unordered set, 
   // in order to be initialized first in the constructor's initialization list
   //ici, un autre vector avec les instances pour le set
   std::vector<BucketType> buckets_;
   EntryHashSet entryHashSet_;

ps: j'ai relancé l'autre discussion

[Arzar]

Mince, désolé d'avoir induit en erreur, le commentaire est complètement faux.

Le deuxième vecteur n'est pas du tout utilisé pour "les instances du set". Les instances sont toujours bien contenus entièrement dans le vecteur entryPool_. En fait, unordered_set est une exception car c'est un conteneur semi-intrusif qui a besoin en plus des hook d'un bloc de mémoire auxiliaire (pour maintenir la tale de hashage, j'imagine ?). Avec un intrusive_set classique, il n'y aurait pas du tout eu besoin du deuxième vecteur.

Boost.Intrusive also offers hashed containers that can be very useful to implement fast-lookup containers. These containers (unordered_set and unordered_multiset) are semi-intrusive containers: they need additional memory apart from the hook stored in the value_type. This additional memory must be passed in the constructor of the container.

[...]

Apart from expected hash and equality function objects, Boost.Intrusive unordered associative containers' constructors take an argument specifying an auxiliary bucket vector to be used by the container.
unordered_set and unordered_multiset performance notes

The size overhead for a hashed container is moderate: 1 pointer per value plus a bucket array per container. The size of an element of the bucket array is usually one pointer. To obtain a good performance hashed container, the bucket length is usually the same as the number of elements that the container contains, so a well-balanced hashed container (bucket_count() is equal to size() ) will have an equivalent overhead of two pointers per element.