pointeurs et intrusive container

Version imprimable

10/12/2009, 13h11
camboui

pointeurs et intrusive container
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:

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.

Citation:
Envoyé par 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:

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:

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; } }

10/12/2009, 15h37
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 ? :koi:
10/12/2009, 16h14
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" :D
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 ? :oops:

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:

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:

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()));

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

Code:

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 ;)

10/12/2009, 18h54
Arzar

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

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. :?

Citation:

Envoyé par Doc de Boost.Intrusive

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.
10/12/2009, 22h44
camboui

Bien... Je vais retourner à mes études :oops:

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

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 8O
Ça ressemble à:

Code:

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:

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 :mrgreen:

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
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 ;
}

11/12/2009, 13h07
camboui

Les entrailles de boost::intrusive_unordered_set c'est à peine plus compliqué, du niveau débutant confirmé :mrgreen:
11/12/2009, 14h01
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:

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... :)

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

Code:

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).

14/12/2009, 13h39
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...

Citation:

Envoyé par 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.

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

Citation:

Envoyé par Camboui

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:

1 2 typedef boost::intrusive::unordered_set<cell, hash<FoncteurDeHash>> cell_intrusive_set;
14/12/2009, 14h44
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.

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

Tiens, d'ailleurs, pour le polymorphisme, je me demande si... :koi:
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 ! :ccool:
Il faut mettre le hook dans la classe mère.
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 #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(); } }

14/12/2009, 21h40
camboui

Ah ben oui tiens :D
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 :furax:

EDIT: on a parlé de intrusive::unordered_set. Mais voilà que je constate qu'il n'y a pas de intrusive::unordered_map 8O
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...
17/12/2009, 17h51
camboui

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