Рекурсивные типы в Си++

[vak]

Оказывается, в Си++ есть возможность определять рекурсивные типы. Представьте, что нам нужны списки вида std::list, где элементом списка может быть число, строка или тот же список.

Решение в лоб не работает:

using Integer = long long;
using String  = std::string;
using List    = std::list<Term>;    ⟸ здесь Term не определено
using Term    = std::variant<Integer, String, List>;

Поменяем местами, опять не годится:

using Integer = long long;
using String  = std::string;
using Term    = std::variant<Integer, String, List>;    ⟸ здесь List не определено
using List    = std::list<Term>;

Ситуация не безнадёжна, однако. Есть способ определить List отложенным образом:

#include <string>
#include <variant>
#include <list>
#include <iostream>

using Integer = long long;
using String  = std::string;
struct List;
using Term    = std::variant<Integer, String, List>;

struct List : public std::list<Term> {};

int main()
{
    std::cout << "sizeof Integer = " << sizeof(Integer) << '\n';
    std::cout << "sizeof String  = " << sizeof(String) << '\n';
    std::cout << "sizeof List    = " << sizeof(List) << '\n';
    std::cout << "sizeof Term    = " << sizeof(Term) << '\n';
}

Эта программа выдаёт:

sizeof Integer = 8
sizeof String  = 24
sizeof List    = 24
sizeof Term    = 32

Comments

[flamedancerii]

Семён Семёныч - ну это ж классика, declaration vs definition.
Техника называется forward declaration.

Добавлено:
Ну это как в самом файле сначала написать (хоть много раз)
extern int a;

потом
void f() {
a=0;
}

потом

int a;

И я похоже отстал от жизни - forward declaration оказывается устаревший термин, просто declaration покрывает кейс.
https://stackoverflow.com/questions/4926105/what-is-forward-declaration-in-c/4926698#4926698

[vak]

Я вижу, вы не поняли, о чём идёт речь. Но решили высказать своё категорическое мнение по данному вопросу. 😀

[juan_gandhi]

О, что-то очень знакомое. Вот этот трюк с рекурсией.

[vak]

Проблема в том, что нельзя сделать forward typedef. Или using вместо typedef в данном случае. Но можно обойти это ограничение, применив forward объявление структуры (или класса).

[sab123]

Или напрямую использовать указатель/ссылку. Объявление вперед реботает только потому, что внутри там используется не объект напрямую, а ссылка на него, поэтому размер контейнера не зависит от размера объекта.

[vak]

Верно.

[spamsink]

См. https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

Мне по работе пришлось сделать практически то же самое, что ты описываешь, только с векторами вместо списков, буквально пару-тройку месяцев назад.

[vak]

Ага, я помню, ты рассказывал. А я размышлял на досуге, как можно бы простым способом изобразить на Си++ структуру данных для Рефала. Напрашивается как раз такой рекурсивный список. Стал гуглить - набрёл на решение.

[spamsink]

Можно, конечно, попытаться передрать какую-нибудь компактную реализацию Рефала с Си на Паскаль...