Comment parcourir à travers un conteneur dans une autre classe?

Question

J'ai rencontré ce problème plusieurs fois et je voudrais savoir s'il existe une méthode ou un modèle simple que je peux utiliser pour le résoudre. Imaginez une structure arborescente dans laquelle chaque nœud contient un conteneur STL (vecteur) de pointeurs vers des enfants. Je veux que le code client puisse traverser cette arborescence et parcourir les conteneurs enfants pour accéder aux autres parties.

Mon problème est que je veux maintenir l'encapsulation pour mes nœuds tout en permettant aux clients de voir facilement tous les enfants pour ce nœud. Je veux également m'assurer que si un client obtient une référence const au nœud racine dans l'arbre, alors tous les accès aux parties suivantes de l'arbre sont aussi const. Dois-je essayer de créer une classe d'itérateur pour mon type de nœud, avoir une méthode de nœud pour renvoyer des itérateurs vectoriels, ou y a-t-il un modèle plus élégant qui me manque?

Edit: Je tiens à souligner à nouveau que si je vois quelques bonnes idées présentées, j'ai des conteneurs de pointeurs à d'autres nœuds. Renvoyer un vector<node *>::const_iterator n'empêchera pas les clients d'appeler des méthodes non-const sur le nœud. Il protège seulement les pointeurs eux-mêmes de pointer sur différents objets.

Answer 1

Quelque chose comme cela est généralement suffisant:

class node 
{ 
public: 
    typedef std::vector<node> node_list; 
    typedef node_list::const_iterator const_iterator; 

    const_iterator begin() const { return children_.begin(); } 
    const_iterator end() const { return children_.end(); } 

private: 
    node_list children_; 
} 

Cela vous permet de changer le type de conteneur sous-jacent sans changement de code qui itère sur un enfant de node.

Cela présente l'inconvénient qu'il fuit un détail de mise en œuvre parce que le code qui utilise votre node::const_iterator savent qu'il est un itérateur d'accès aléatoire (parce que std::vector:: const_iterator est un itérateur d'accès aléatoire), de sorte que vous pourriez avoir du mal à passer à un conteneur cela ne supportait pas l'accès aléatoire.

Si vous souhaitez contrôler vous-même la catégorie de l'itérateur, vous voudrez probablement créer votre propre classe iterator qui fournit le comportement exact que vous voulez fournir.

Answer 2

Pour traverser l'arbre entier, vous devez créer votre propre classe d'itérateur, pour juste traverser les enfants, vous pouvez retourner en toute sécurité les itérateurs vectoriels.

Answer 3

Ceci n'est pas une réponse directe à votre question, mais plutôt une approche alternative. Plutôt que de faire exécuter le spectacle par le code client, vous pouvez opter pour control inversion en enregistrant un foncteur de rappel. Par exemple:

// Derive from this class to create a visitor 
class AbstractVisitor 
{ 
public: 
    virtual void operator() (const T &) = 0; 
}; 


// Your recursive data-structure class 
class MyClass 
{ 
public: 
    void walk(AbstractVisitor &v) const 
    { 
     // Call the client callback 
     v(payload); 
     for (std::vector<MyClass>::const_iterator it = children.begin(); 
      it != children.end(); ++it) 
     { 
      // Recurse 
      it->walk(v); 
     } 
    } 

private: 
    T payload; // Some sort of payload associated with the class 
    std::vector<MyClass> children; 
}; 


// You could have different visitor classes to do different things 
class MyVisitor : public AbstractVisitor 
{ 
public: 
    virtual void operator() (const T &t) 
    { 
     // Do something with t 
    } 
} 


int main() 
{ 
    MyClass m; 
    MyVisitor v; 
    ... 
    m.walk(v); 
} 

Encapsulation complète réalisée!