Можно ли создавать экземпляры стандартных шаблонов контейнеров с неполными типами?

Иногда полезно создать стандартный контейнер с неполным типом, чтобы получить рекурсивную структуру:

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;
};

Обычно это работает, потому что у контейнеров нет элементов типа value_type или функций-членов, которые передают или возвращают какие-либо объекты value_type по значению. Стандарт, похоже, не очень много говорит о неполных аргументах шаблона, но есть один бит в С++ 11 §17.6.4.8 [lib.res.on.functions], «требования к другим функциям»:

В частности, эффекты не определены в следующих случаях: … если неполный тип (3.9) используется в качестве аргумента шаблона при создании экземпляра компонента шаблона, если это специально не разрешено для этого компонента.

Делает ли это приведенные выше конструкции незаконными, даже если экземпляры не находятся в области блока? Подпадает ли это под «операции над типами, используемыми для создания экземпляров компонентов шаблона стандартной библиотеки» (также 17.6.4.8)? Или реализации библиотеки запрещено создавать экземпляры шаблонов, которые могут дать сбой для неполных типов, когда все конкретно требуемые экземпляры выполняются успешно?

Редактировать: Поскольку только функции могут вызывать и создавать экземпляры других функций, ограничение «операций над типами…» теми, которые находятся в области блока, казалось бы, предъявляет к содержимому функций-членов более строгие требования, чем к содержимому сигнатур и определения классов-членов. В конце концов, безусловно, нет смысла делать что-либо с multi_tree_node, пока тип не будет завершен. И это распространяется на std::unique_ptr, который явно поддерживает аргумент неполного типа, даже при использовании в области блока.

Правка 2: мне очень хорошо, что я не удосужился протестировать пример trie_node — а я уже пробовал его раньше. Это то же самое, что и пример поломки в статье, на которую ссылается @Ise. Однако, хотя в статье кажется само собой разумеющимся, что «ничего подобного не может работать», решение кажется мне простым — внутренний класс std::map tree_node должен быть шаблоном, не являющимся членом, а не классом, не являющимся членом.

В любом случае, эта статья довольно хорошо устанавливает замысел дизайна, поэтому я думаю, что моя придирка к подзаголовку «требования к функциям» - это только это.


c++ templates stl incomplete-type
person Potatoswatter    schedule 30.11.2011    source источник
comment
Я не вижу неполных типов в коде, который вы разместили?   -  person John Dibling    schedule 30.11.2011
comment
@JohnDibling: trie_node является неполным при определении next.   -  person Matthieu M.    schedule 30.11.2011
comment
@JohnDibling Внутри собственной области класса он неполный.   -  person Potatoswatter    schedule 30.11.2011
comment
Связано: stackoverflow.com/questions/7210286/   -  person Björn Pollex    schedule 30.11.2011
comment
Кстати, это [17.4.3.6] в стандарте С++ 03, для всех, кто заинтересован. Кроме того, лучше всего также добавить тег, под которым идет абзац, в данном случае [lib.res.on.functions].   -  person Xeo    schedule 30.11.2011
comment
Подводя итог ссылке Бьорна, можно сказать, что создание экземпляра шаблона происходит путем ленивых вычислений, поэтому содержимое функций-членов и шаблонов-членов видно только при их первом использовании. Однако сигнатуры функций и определения классов-членов, не являющихся шаблонами, должны быть действительными с учетом любых неполных аргументов.   -  person Potatoswatter    schedule 30.11.2011
comment
@Potatoswatter: К вашему сведению, эта статья объясняет связанную с этим проблему.   -  person Ise Wisteria    schedule 30.11.2011
comment
@IseWisteria Спасибо, если вы просто напишите это в ответ, я приму это.   -  person Potatoswatter    schedule 01.12.2011
comment
@Potatoswatter: Спасибо, дайте мне минутку!   -  person Ise Wisteria    schedule 01.12.2011

Ответы (3)


arrow_upward
4
arrow_downward

Лично я считаю, что формулировка создание экземпляра в 17.6.4.8/2 немного двусмысленна, но согласно этому article, намерение стандарта, по-видимому, не разрешает рекурсивный тип данных с использованием стандартных контейнеров.

Кстати, VC2005 выдает ошибку для class C { std::deque< C > x; };, а компилирует class C { std::vector< C > x; };...
Однако, в моем понимании, это ограничение как раз для расширения свободы реализации стандартных контейнеров. Итак, как упомянул Керрек С.Б., могут быть контейнеры, допускающие рекурсивную структуру данных, и Boost.Container, похоже, предоставляет эту возможность.

person Ise Wisteria    schedule 30.11.2011

arrow_upward
11
arrow_downward

Вот моя попытка интерпретации:

Стандарт просто говорит, что вы не должны этого делать, хотя любая конкретная реализация может без проблем поддерживать такую ​​конструкцию. Но представьте, например, что кто-то хочет написать оптимизацию «малого вектора», при которой вектор всегда содержит место, скажем, для пяти элементов. Сразу же у вас будут проблемы, потому что у вас будет самореферентный тип. Это было бы проблемой, даже если бы вектор использовал какое-то статическое ветвление в зависимости от размера типа значения.

Поэтому, чтобы не препятствовать включению таких конструкций в реализации, стандарт просто говорит, что вы должны использовать только полные типы. Другими словами, тот факт, что большинство контейнеров содержат только ссылки или указатели на тип значения, является деталью реализации, а не стандартным требованием.

Просто поясню: если вы определяете свой собственный шаблон класса, вполне возможно спроектировать его таким образом, чтобы он явно поддерживал неполные типы. Примером из стандарта является std::unique_ptr, который вполне устраивает неполный параметр типа T[] (или даже void).

person Kerrek SB    schedule 30.11.2011
comment
+1 отличный пример, но я подожду какой-нибудь стандартной интерпретации ab initio… мой код, безусловно, нарушает цитируемое требование, но другая часть вопроса заключается в том, применяется ли это требование вне области действия функции/блока и каким образом. (Поскольку только функции могут вызывать и создавать экземпляры других функций, это, по-видимому, удерживает содержимое функций-членов в соответствии с другим стандартом, чем содержимое сигнатур и определений классов-членов.) - person Potatoswatter; 30.11.2011
comment
маленький вектор не лучший пример; эта оптимизация не разрешена стандартом. - person T.C.; 07.03.2015

arrow_upward
2
arrow_downward

В общем, использование неполного типа в качестве параметра шаблона для стандартного библиотечного компонента является UB. Вот ссылка:

Если неполный тип ([basic.types]) используется в качестве аргумента шаблона при создании экземпляра компонента шаблона или оценке концепции, если это специально не разрешено для этого компонента.

Обратите внимание, что, начиная с С++ 17, std::vector было предоставлено явное разрешение на неполные типы. Вот ссылка:

Неполный тип T может использоваться при создании экземпляра вектора, если распределитель удовлетворяет требованиям полноты распределителя. T должен быть завершен до того, как будет сделана ссылка на любой элемент результирующей специализации вектора.

Итак, в вашем примере multi_tree_node правильно сформировано, но trie_node — это UB.

person cigien    schedule 23.07.2020