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

[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

[spamsink]

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

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

[vak]

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

[spamsink]

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