c++ - que - std:: vector recorrer

¿Se pueden crear instancias de plantillas de contenedor estándar con tipos incompletos?

Question

Algunas veces es útil crear una instancia de un contenedor 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 funcionar porque los contenedores no tienen miembros de tipo value_type o funciones de miembro que pasan o devuelven cualquier valor value_type 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 solo las funciones pueden llamar y crear instancias de otras funciones, restringir "operaciones en tipos ..." a aquellas en el ámbito de bloque parecería mantener el contenido de las funciones miembro en un requisito más estricto que el contenido de las firmas y las definiciones de clase de miembro. Después de todo, ciertamente no tiene sentido hacer nada con un multi_tree_node hasta que el tipo esté completo. Y esto se extiende a 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 para no molestarme en probar el ejemplo de trie_node , e incluso lo he intentado antes. Es lo mismo que el ejemplo de rotura en el artículo enlazado con @Ise. Sin embargo, aunque el artículo parece dar por sentado que "nada de eso podría funcionar", la solución me parece simple std::map la clase tree_node interna de std::map 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 nitidez sobre estar bajo el subtítulo de "requisitos de funciones" es solo eso.

Answer 1

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

El estándar simplemente dice que no debe hacer esto, a pesar de que una implementación concreta determinada no tenga problemas para respaldar 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, el estándar 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.

_{Solo para aclarar esto: si defines tu propia plantilla de clase, es perfectamente posible diseñarla de tal forma que admita 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 ).}

Answer 2

Personalmente, creo que la redacción de la instancia en 17.6.4.8/2 es un poco ambigua, pero de acuerdo con este artículo , la intención del estándar parece no permitir el tipo de datos recursivos utilizando contenedores estándar.

En una nota relacionada, VC2005 emite un error para la class C { std::deque< C > x; }; class C { std::deque< C > x; }; , mientras compila la class C { std::vector< C > x; }; class C { std::vector< C > x; }; ...
Sin embargo, en mi entender, esta restricción es solo para ampliar la libertad de la implementación de contenedores estándar. Así que, como mencionó Kerrek SB , puede haber contenedores que permitan una estructura de datos recursiva, y Boost.Container parece proporcionar esta facilidad.