mise en œuvre FIFO

Question

Alors que la mise en œuvre d'un FIFO j'ai utilisé la structure suivante:

struct Node 
{ 
    T info_; 
    Node* link_; 
    Node(T info, Node* link=0): info_(info), link_(link) 
    {} 
}; 

Je pense que ce un truc bien connu pour beaucoup de conteneurs STL (par exemple pour la liste). Est-ce une bonne pratique? Qu'est-ce que cela signifie pour le compilateur lorsque vous dites que Node a un membre avec un type de pointeur? Est-ce une sorte de boucle infinie?

Enfin, si c'est une mauvaise pratique, comment pourrais-je implémenter une meilleure FIFO.

EDIT: Les gens, tout est question d'implémentation. Je suis assez familier avec la bibliothèque STL, et je connais beaucoup de conteneurs de plusieurs bibliothèques. Juste je veux discuter avec des gens qui peuvent donner une bonne implémentation ou un bon conseil.

Answer 1

Les pointeurs vers des objets de type déclaré sont corrects dans C et C++. Ceci est basé sur le fait que les pointeurs sont des objets de taille fixe (par exemple, des entiers 32 bits sur une plate-forme 32 bits). Vous n'avez donc pas besoin de connaître la taille complète du type pointé. En fait, vous n'avez même pas besoin d'une déclaration de type complète pour déclarer un pointeur.Une déclaration avant suffirait:

class A; // forward declared type 

struct B 
{ 
    A* pa; //< pointer to A - perfectly legal 
}; 

Bien sûr, vous avez besoin d'une déclaration complète portée au moment où vous accédez réellement membres:

#include <A.hpp> // bring in full declaration of class A 
... 
B b; 
b.pa = &a; // address of some instance of A 
... 
b.pa->func(); // invoke A's member function - this needs full declaration 

Pour FIFO se pencher sur std::queue. Les deux std::list, std::deque, et std::vector pourraient être utilisés à cette fin, mais fournissent également d'autres facilités.

Answer 2

Vous pouvez utiliser le fichier FIFO existant, std::queue.

Answer 3

Est-ce une bonne pratique?

Je ne vois rien de mal à cela.

Qu'est-ce que cela signifie pour le compilateur lorsque vous dites que le noeud a un membre avec un type de pointeur?

Il n'y a rien de mal à ce qu'une classe stocke un pointeur sur un objet de la même classe.

Enfin, si cela est une mauvaise pratique, comment puis-je implémenter une meilleure FIFO.

j'utiliser std::queue;)

Answer 4

C'est une bonne façon de mettre en œuvre un nœud. Le pointeur de noeud est utilisé pour créer le lien vers le noeud suivant dans le conteneur. Vous avez raison, il peut être utilisé pour créer une boucle. Si le dernier nœud du conteneur référence le premier, itérer ce conteneur ferait une boucle sur tous les nœuds. Par exemple, si le conteneur est une file d'attente FIFO, le pointeur référencera le nœud suivant dans la file d'attente. Par exemple, si le conteneur est une file d'attente FIFO. C'est-à-dire que la valeur de link_ serait l'adresse d'une autre instance de la classe Node.

Si le type de valeur T mis en œuvre un constructeur de copie cher, une classe Node plus efficace serait

struct Node 
{ 
    T * info_; 
    Node* link_; 
    Node(T * info, Node* link=0): info_(info), link_(link) 
    {} 
}; 

Notez que info_ est maintenant un pointeur vers une instance de T. L'idée derrière l'utilisation d'un pointeur est que l'attribution d'un pointeur est moins coûteuse que la copie d'objets complexes.

Answer 5

Il est évident que vous utilisez linked-list comme implémentation sous-jacente de votre file d'attente. Il n'y a rien de particulièrement mauvais à ce sujet. Mais juste pour info, en termes d'implémentation, std :: queue utilise lui-même std :: deque comme implémentation sous-jacente. std :: deque est une structure de données plus sophistiquée composée de blocs de tableaux dynamiques intelligemment gérés. Il finit par être mieux que la liste chaînée parce que:

1. Avec liste chaînée, chaque insertion signifie que vous devez faire une allocation dynamique de mémoire coûteuse. Avec les tableaux dynamiques, ce n'est pas le cas. Vous n'allouez de la mémoire que lorsque le tampon doit croître.
2. Les éléments de tableau sont contigus et cela signifie que l'accès aux éléments peut être facilement mis en cache dans le matériel.