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.

[camboui]

Bien... Je vais retourner à mes études

Faut dire que je commence à peine à voir ces intrusives... neuf mois après toi

[Arzar]

Bon, par curiosité j'ai finalement fouiné directement dans le code source de boost::intrusive::list, dans les tripes même de la bestiole, et une fois dépiauté ce grand bazar, il apparait...
Ben qu'en fait, c'est tout con
Ça ressemble à:

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
 
class list_impl
{
//...
node root_;
//...
   void push_back(reference value) 
   {
      // blablabla, recupère la partie hook de l'élément
      node_ptr to_insert = get_real_value_traits().to_node_ptr(value);
 
     // qu'on insère devant le nœud racine. Vu que la liste est circulaire
     // il va se retrouver dernier.   
     node_algorithms::link_before(this->get_root_node(), to_insert);
  }
};

Avec link_before :

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
 
   //! <b>Requires</b>: nxt_node must be a node of a circular list.
   //! 
   //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
   //! 
   //! <b>Complexity</b>: Constant 
   //! 
   //! <b>Throws</b>: Nothing.
 static void link_before(node_ptr nxt_node, node_ptr this_node)
 {
    node_ptr prev(NodeTraits::get_previous(nxt_node)); 
    NodeTraits::set_previous(this_node, prev);
    NodeTraits::set_next(prev, this_node);
    NodeTraits::set_previous(nxt_node, this_node);
    NodeTraits::set_next(this_node, nxt_node);
 }

Si on traduisait en C/C++ basique, sans généricité, template et trait de la mort, ça serait juste une liste circulaire doublement chainée, la même qu'on retrouve dans les demandes d'aides du sous-forum débutant tous les dix sujets

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
struct Hook
{
   Hook* prev;
   Hook* next;
};
 
struct Entry : public Hook
{
  int i;
};
 
struct intrusive_list
{
   Hook* first;
   void push_back(Entry& entry);
   void links_before(Hook* next, Hook* hook);
};
 
void intrusive_list::push_back(Entry& entry)
{
   links_before(first, static_cast<Hook*>(&entry));
}
 
void intrusive_list::links_before(Hook* next, Hook* hook)
{
   Hook* prev = next->prev;
   hook->prev = prev;
   prev->next = hook;
   next->prev = hook;
   hook->next = next ;
}

[camboui]

Les entrailles de boost::intrusive_unordered_set c'est à peine plus compliqué, du niveau débutant confirmé

[Emmanuel Deloget]

J'ai essayé d'aller le plus loin possible (pour moi) dans la modification du comportement de intrusive::unordered_set, sans succès. Ma limite est l'implémentation des différentes méthodes de hastable_impl, qui s'attendent à manipuler des références. J'avais pourtant fait une bonne partie du chemin avec cette petite définition :

Code :

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

1
2
3
4
5
6
7
8
 
namespace boost { namespace intrusive { namespace detail {
template <>
struct default_uset_hook::apply<cell*>
{
	typedef cell::default_uset_hook type;
};
} } }

Cette petite définition dit à unordered_set que les value_traits (donc les node_traits, ...) de cell* sont ceux de cell. Ce n'est pas forcément une bonne solution.

En tout cas, c'est insuffisant. La méthode insert() (par exemple) s'attend à avoir en paramètre une référence mais je lui passe un pointeur (ben oui). En lui passant une référence sur un pointeur, d'autres erreurs surviennent (je ne vais pas vous ressortir le log ; c'est assez... complexe).

Si quelqu'un d'autre à une idée grandiose...

[camboui]

J'ai fait un peu ce que tu suggérais au 2ème post et ça "compile".

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
	struct cell_ptr: boost::intrusive::unordered_set_base_hook<>
	{
		cell *f_ptr;
		cell_ptr(cell *ptr):f_ptr(ptr) {}
		operator cell &() const { return *f_ptr; }
		operator cell *() const	{ return f_ptr; }
	};
   typedef boost::intrusive::unordered_set<cell_ptr>  cell_intrusive_set;
   typedef typename cell_intrusive_set::bucket_type  bucket_type;
   typedef typename cell_intrusive_set::bucket_traits  bucket_traits;
 
...
 
   std::vector<bucket_type> buckets_(maxCell); 
   cell_intrusive_set f_set(bucket_traits(&buckets_[0], maxCell));//predicates ?

Mais ça plante. Je ne vois quand il faut préciser les prédicats nécessaires quand il n'y a pas d'operator<() (ou plutôt les fonctions hash et equal).

[Arzar]

Bah c'est bien, mais je ne comprends toujours pas quel peut être le moindre intéret à un intrusive::unordered_set<T*>...
Toutes les raisons données plus haut...

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.

ne s'appliquent pas aux conteneurs intrusifs de boost. (qui ne "contiennent" rien).

Mais ça plante. Je ne vois quand il faut préciser les prédicats nécessaires quand il n'y a pas d'operator<() (ou plutôt les fonctions hash et equal).

D'après la doc, c'est qqchose comme :

Code :

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

1
2
 
typedef boost::intrusive::unordered_set<cell, hash<FoncteurDeHash>> cell_intrusive_set;

[camboui]

On est bien d'accord que l'intérêt d'avoir des pointeurs dans des intrusives est limité (sauf peut-être pour faire du polymorphisme).
Mais ça reste un exercice intéressant de voir comment faire.

[Arzar]

Ok, d'accord, c'était pour le sport

Tiens, d'ailleurs, pour le polymorphisme, je me demande si...
Après tout, les conteneurs de boost::intrusive semblent ne manipuler que des pointeurs ou des références sans faire aucune copie, donc si ça se trouve, le polymorphisme marche direct !

Edit :

Yes, ça marche !
Il faut mettre le hook dans la classe mère.

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
#include "boost/intrusive/list.hpp"
#include <vector>
 
struct A : public boost::intrusive::list_base_hook<>
{
   virtual void print()
   {
      printf("A\n");
   }
};
 
struct B : public A
{
   virtual void print()
   {
      printf("B\n");
   }
};
 
struct C : public A
{
   virtual void print()
   {
      printf("C\n");
   }
};
 
int main()
{
   std::vector<A*> v;
   v.push_back(new A);
   v.push_back(new B);
   v.push_back(new C);
 
   boost::intrusive::list<A> l;
   l.push_back(*v[0]);
   l.push_back(*v[1]);
   l.push_back(*v[2]);
 
   boost::intrusive::list<A>::iterator it = l.begin();
   for(; it != l.end() ; ++it)
   {
      it->print();
   }
}

[camboui]

Ah ben oui tiens
Mais du coup il faut allouer chaque instance une à une. Pas de bloc contigu dans ce cas.

Pour en revenir aux pointeurs dans les intrusifs, au départ de ce fil j'y pensais très sérieusement, mais tu m'as convaincu de l'inutilité de la chose
J'y suis quand même arrivé, pour le sport. J'avais de plus un sérieux soucis avec les foncteurs hash et equal. En fait le template unordered_set est une sorte de variadic template, les paramètres étant des "options". C'est plutôt curieux et inhabituelle, ça rend le code boost #include opaque

EDIT: on a parlé de intrusive::unordered_set. Mais voilà que je constate qu'il n'y a pas de intrusive::unordered_map
Par contre, il y a pas mal d'autres containers intrusive, des variantes de tree (avl, splay), etc.
Leur équivalent "normal" n'existe pas, Boost et ses mystères...

[camboui]

J'ai un assez bon aperçu des intrusive désormais.
Arzar, merci encore