¿Pueden crearse instancias de plantillas de contenedor estándar con tipos incompletos?

Question

A veces es útil para crear instancias de un recipiente estándar con un tipo incompleto para obtener una estructura recursiva:

struct multi_tree_node { // Does work in most implementations 
    std::vector<multi_tree_node> child; 
}; 

struct trie_node { // Does not work in most implementations 
    std::map< char, trie_node > next; 
}; 

Esto tiende a trabajar porque los recipientes no tienen miembros de tipo value_type o miembro funciones que pasan o devuelve ningún value_type objetos por valor El estándar no parece decir mucho sobre argumentos de plantilla incompletos, pero hay un bit bajo C++ 11 §17.6.4.8 [lib.res.on.functions], "requisitos sobre otras funciones":

En particular, los efectos no están definidos en los siguientes casos: ... si se utiliza un tipo incompleto (3.9) como argumento de plantilla al crear una instancia de un componente de plantilla, a menos que esté específicamente permitido para ese componente.

¿Esto hace que las construcciones anteriores sean ilegales, a pesar de que las instancias no están en el alcance del bloque? ¿Se incluye esto en "operaciones sobre tipos utilizados para crear instancias de componentes de plantilla de biblioteca estándar" (también 17.6.4.8)? ¿O está prohibida la implementación de una biblioteca para incurrir en instancias de plantillas que pueden fallar para tipos incompletos cuando todas las instancias requeridas específicamente tienen éxito?

Editar: Dado que sólo las funciones pueden llamar e instanciar otras funciones, la restricción "sobre tipos de ..." a las de ámbito de bloque parecen mantener el contenido de las funciones miembro de un requisito más estricto que el contenido de firmas y miembro definiciones de clase. Después de todo, ciertamente no tiene sentido que haga cualquier cosa con un multi_tree_node hasta que el tipo esté completo. Y esto se extiende al std::unique_ptr que admite explícitamente un argumento de tipo incompleto, , incluso cuando se usa en el alcance del bloque.

Editar 2: Me sirve bien para no molestarme en probar el ejemplo trie_node, e incluso lo he probado antes. Es lo mismo que el ejemplo de rotura en the article que enlazó @Ise. Sin embargo, aunque el artículo parece dar por hecho que "nada de eso podría funcionar", la solución me parece simple: std::map, la clase interna tree_node debe ser una plantilla no miembro, no una clase miembro que no sea de plantilla.

De todos modos, ese artículo establece la intención de diseño bastante bien, así que supongo que mi nitpick sobre estar bajo el subtítulo de "requisitos de funciones" es solo eso.

Answer 1

Personalmente, siento la redacción instanciando en 17.6.4.8/2 es un poco de ambigua, pero de acuerdo con this article, la intención de la norma parece no permitir que el tipo de datos recursiva utilizando contenedores estándar.

En una nota relacionada, VC2005 emite un error de class C { std::deque<C> x; };, mientras que compila class C { std::vector<C> x; }; ...
Sin embargo, en mi entender, esta restricción es sólo para la ampliación de la libertad de la aplicación de los contenedores estándar. Así como kerrek SB mencionado, no puede haber contenedores que permiten estructura de datos recursiva, y Boost.Container parece proporcionar este servicio.

Answer 2

Aquí está mi intento de una interpretación:

La norma dice simplemente que no debe hacer esto, a pesar de que ninguna aplicación concreta dada puede tener problemas para apoyar dicha construcción. Pero imagínese, por ejemplo, si alguien quisiera escribir una optimización de "vector pequeño" mediante la cual un vector siempre contiene espacio para, digamos, cinco elementos. Inmediatamente estarías en problemas porque tendrías un tipo autorreferencial. Esto sería un problema incluso si el vector empleara algún tipo de ramificación estática dependiendo del tamaño del tipo de valor.

Por lo tanto, para no impedir que las implementaciones incluyan tales construcciones, la norma simplemente dice que solo debe usar tipos completos. En otras palabras, el hecho de que la mayoría de los contenedores solo contenga referencias o indicadores para el tipo de valor es un detalle de implementación en lugar de un requisito estándar.

_{sólo para aclarar esto: si define su propia plantilla clase , es perfectamente posible diseñar de una manera tal que apoya explícitamente tipos incompletos. Un ejemplo del estándar es std::unique_ptr, que está perfectamente satisfecho con el parámetro de tipo incompleto T[] (o incluso void).}