Conteneurs récursifs en C++?

Question

Possible en double:
Are C++ recursive type definitions possible, in particular can I put a vector<T> within the definition of T ?

Je regardais à travers un code récemment et a remarqué une structure de données similaire à ce qui suit:

class TreeNode { 
    std::vector<TreeNode> subNodes; 
}; 

Comme vous pouvez le voir, la conteneur est instancié avec TreeNode avant TreeNode a été défini. Le code compile sous GCC et MSVC, mais je me souviens avoir vu quelque chose disant que ce comportement n'est pas garanti. Malheureusement, je ne trouve rien du tout dans la norme.

Comment ces conteneurs peuvent-ils être mis en œuvre? Ce comportement est-il garanti par la norme? Si cela n'est pas garanti par la norme, quelles alternatives ai-je à ce design?

Answer 1

Ceci est correct car la classe std::vector<T> ne contient aucune instance concrète de type T: elle est généralement implémentée à l'aide de pointeurs. L'instanciation de modèle std::vector<TreeNode> ne nécessite pas la définition complète de TreeNode.

std::vector<T> est généralement mis en œuvre comme un triplet de pointeurs (bien que cela ne soit pas requis par la norme):

template <typename T> 
class vector 
{ 
    ... 
    T* start; 
    T* end; 
    T* end_of_storage; 
}; 

Si std::vector<T>ne contiennent des exemples concrets de T en elle, alors vous avez un problème . Ce qui suit n'est pas légal C++, car il crée une circulaire "a une" définition:

template <typename T> 
class container 
{ 
    T x; 
}; 

class TreeNode 
{ 
    container<TreeNode> subNodes; 
};