Практика метапрограммирования на C++: бінарне дерево пошуку на етапі компіляції

Творці шаблонів в C++ заклали основу цілого напряму для досліджень і розробки: виявилося, що мова шаблонів C++ володіє повнотою по Тьюрингу, тобто метапрограми (програми, призначені для роботи на етапі компіляції) C++ в змозі обчислити всі вычислимое. На практиці міць шаблонів найчастіше застосовується при описі узагальнених структур даних і алгоритмів: STL (Standard Template Library) тому живий приклад.

Однак, з приходом C++11 з його
variadic
-шаблонами, бібліотекою
type_traits
, кортежами і
constexpr
'ами метапрограмування стало більш зручним і наочним, відкривши дорогу до реалізації багатьох ідей, які раніше можна було втілити тільки за допомогою розширень конкретного компілятора або складних багатоповерхових макросів.

У даній статті буде розроблена реалізація бінарного дерева пошуку часу компіляції: структури даних, що є логічним «розширенням» кортежу. Ми втілимо бінарне дерево у вигляді шаблону і попрактикуємось в метапрограммировании: перенесення рекурсивних і не тільки алгоритмів на мову шаблонів C++.

Зміст
Трохи теорії
Для початку згадаємо деякі визначення та поняття про структури даних та алгоритмах. Можна пропустити цей розділ і відразу перейти до деталей реалізації, якщо читач знайомий з основами теорії графів та/або уявляє, що таке бінарні дерева і як їх можна готувати.

Визначення і не тільки:Вільне дерево (дерево без виділеного кореня) або просто дерево — ациклічний неорієнтований граф.

Дерево з коренем — вільне дерево, в якому виділена одна вершина, звана коренем (root).

Сайти (nodes) — вершини дерева з коренем.

Батьківський вузол або батько вузла X — останній вузол, що передує X на шляху від кореня R до цього сайту X. В такому випадку вузол X називається дочірнім до описаного батьківського сайту Y. Корінь дерева не має батька.

— вузол, у якого немає дочірніх вузлів.

Внутрішній вузол — вузол, який не є листом.

Ступінь вузла X — кількість дочірніх вузлів цього сайту X.

Глибина вузла X — довжина шляху від кореня R до цього сайту X.

Висота вузла (height) — довжина найдовшого простого (без повернень) спадного шляху від вузла до листа.

Висота дерева — висота коріння цього дерева.

Впорядковане дерево — дерево з коренем, у якому дочірні вузли кожного вузла впорядковані (тобто задано відображення безлічі дочірніх вузлів на безліч натуральних чисел від 1 до k, k — загальна кількість дочірніх вузлів цього вузла). Простими словами, кожному дочірньому сайту присвоєно ім'я: «перший», «другий», ..., "k-тий".

Бінарне дерево (binary tree) — (рекурсивно), або порожня множина (не містить вузлів), або складається з трьох непересічних множин вузлів: кореневий вузол, бінарне дерево, зване лівим поддеревом і бінарне дерево, зване правим поддеревом. Таким чином, бінарне дерево — це впорядкований дерево, у якого кожен вузол має ступінь не більше 2 і має «лівий» і/або/або «правий» дочірні вузли.

Повністю бінарне дерево (full binary tree) — бінарне дерево, у якого кожен вузол або лист, або має ступінь два. Повністю бінарне дерево можна отримати з бінарного додаванням фіктивних дочірніх аркушів кожного вузла ступеня 1.

Бінарне дерево пошуку — пов'язана структура даних, реалізована за допомогою бінарного дерева, кожен вузол якого може бути представлений об'єктом, що містить ключ (key) і супутні дані, посилання на ліве і праве піддерева і посилання на батьківський вузол. Ключі бінарного дерева пошуку задовольняють властивості бінарного дерева пошуку:
якщо X — вузол, вузол Y знаходиться в лівому поддереве X, Y. keyX. key. Якщо вузол Y знаходиться у правому поддереве X, X. keyY. key.
мається на Увазі, що ми вміємо порівнювати ключі (на множині значень ключа задано транзитивное відношення порядку, тобто простіше кажучи операція «менше») і говорити про рівність ключів. У реалізації без обмеження спільності ми будемо оперувати строгими нерівностей порядку, використовуючи тільки операцію "<" і "==", побудовану на її основі зі співвідношення
$inline$x=y\;\Leftrightarrow\;\;!(x<y)\:\&\:!(y<x)$inline$
Обхід дерева — формування списку вузлів, порядок визначається типом обходу.
Розминка: операції з кортежами і перетворення числа в клас
Перш ніж поринути з головою в рекурсивні нетрі і насолодитися розмаїттям кутових дужок, поупражняемся в написанні метафункций. Далі нам знадобляться функції конкатенації кортежів і функція додавання типу в існуючий кортеж:

template < class U, class V>
struct tuple_concat;

template < class Tuple, class T>
struct tuple_push;

Про операції над типами:Зрозуміло, ні про які «конкатенації» і «додавання» типів «контейнери типів» мови не йде. Це загальна і важлива особливість світу часу компіляції: певний тип (клас) ніяким чином модифікувати вже неможливо, але можливо визначити новий (або серед раніше визначених вибрати існуючий) тип, що має необхідні нам властивості.

Стандарт C++11 вводить заголовковий файл
<a href="http://en.cppreference.com/w/cpp/header/type_traits">type_traits</a>
(як частина бібліотеки підтримки типів), що містить колекцію корисних метафункций. Всі вони є шаблонами структур, і після инстанцирования визначають локально якийсь тип
type
або числову константу
value
(або нічого, як у випадку відключення перевантаження з використанням
std::enable_if
). Ми будемо дотримуватися тих же принципів проектування метафункций.
Перша функція приймає в якості аргументів шаблону два кортежу, друга — кортеж і тип, який необхідно додати в кортеж. Підстановка в якості аргументів невідповідних типів (наприклад, при спробі зробити конкатенацию
int
та
float
) — операція безглузда, тому базовий шаблон цих структур не визначається (це запобіжить його инстанцирование для довільних типів), а вся корисна робота робиться в часткових спеціалізаціях:

template <template < class...> class T, class... Alist, class... Blist>
struct tuple_concat<T<Alist...>, T<Blist...>> { using type = T<Alist..., Blist...>; };

template <template < class...> class Tuple, class... Args, class T>
struct tuple_push<Tuple<Args...>,T> { using type = Tuple<Args..., T>; };

Приблизний переклад на людську мову спеціалізації
tuple_concat
:

Якщо в якості аргументів шаблону виступають два класи, які в свою чергу є результатами инстанцирования одного і того ж шаблону класу (
T
) зі змінним числом аргументів, і вони були инстанцированы з parameter pack'ами
Alist
та
Blist
, визначити локально псевдонім
type
як инстанцированую версію шаблону класу
T
з конкатенированным списком аргументів, т.е.
T<Alist..., Blist...>
.


термінології:Далі в статті часто будуть ототожнюватися поняття «инстанцирование шаблону структури метафункции» (правильніше і мудріший) і «виклик метафункции» (коротше і наочніше), по суті означають одне і те ж: «у цьому місці програми з шаблону відбудеться генерація структури з усіма витікаючими наслідками: вона придбає розмір, всередині визначаться псевдоніми і класи і т. д. і т. п.»
Звучить зловісно, але на практиці все простіше, ніж здається: при спробі викликати
tuple_concat
з двома кортежами одного виду (наприклад, з двома
std::tuple
), всередині структури визначиться тип того ж кортежу з «зшитою» списком аргументів вхідних кортежів. Інші спроби инстанцирования просто не скомпилируются (компілятор не зможе вивести типи для певної вище часткової спеціалізації, а инстанцирование загального шаблону виявиться неможливим через відсутність його тіла). Приклад:

using t1 = std::tuple<char,int>;
using t2 = std::tuple<float,double>;
using t3 = std::tuple<char,int,float,double>;

using conc = typename tuple_concat<t1,t2>::type;
// using err = typename tuple_concat<int,bool>::type; // помилка

static_assert(std::is_same<t3,conc>::value, ""); // твердження істинне, типи однакові

У світлі вищесказаного розгляд спеціалізації
tuple_push
не повинно становити великої праці. Додатково, для зручності визначимо відповідні псевдоніми шаблонів:

template < typename U, typename V>
using tuple_concat_t = typename tuple_concat<U,V>::type;

template < typename Tuple, typename T>
using tuple_push_t = typename tuple_push<Tuple,T>::type;

Ця зручна можливість з'явилася у мові C++11 стандарті: вона, наприклад, для доступу до
type
замість заковыристого
typename tuple_concat<t1,t2>::type
писати просто
tuple_concat_t<t1,t2>
.

Про конкатенації:Стандартний заголовок
tuple
містить визначення (не мета-)функції
tuple_cat()
, конструюючої кортеж допомогою конкатенації невизначеного числа
std::tuple
'їй, переданих в якості аргументів. Уважний читач може помітити, що
tuple_concat
може бути простіше реалізована за допомогою виводу типу результату
decltype(tuple_cat(...))
, але, по-перше, отримана вище реалізація не обмежена типом кортежу
std::tuple
, а по-друге, це було розминкою вправою для поступового занурення в більш складну арифметику типів.
Останні приготування: не для справи, а для душі дебага навчимося перетворювати цілі числа типи: у вузлах дерева треба щось зберігати, а що може бути простіше і зручніше для налагодження, ніж зберігати в них звичайні числа? Але так як дерево у нас не просте, а з типами (і часу компіляції), то й числа повинні бути непростими. Насправді, реалізація вкрай проста і відома:

/// Модно-молодіжно STL-like шляхом
template<size_t number>
struct num_t : std::integral_constant<size_t, number> {};

// АБО класично визначимо внутрішність руками
template<size_t number>
struct num_t { enum : size_t { value = number } };

Сенс в обох визначень один: инстанцирование шаблону з різними чисельними аргументами буде приводити до визначення різних типів:
num_t<0>
,
num_t<13>
,
num_t<42>
і т. д. Не більш ніж для зручності наделим цю структуру статичним числовим значенням
value
, що дозволить нам отримувати назад число з аргументу шаблону (за допомогою доступу
some_num_type::value
) без прибегания до висновку типу.

Бінарне дерево пошуку
Рекурсивне визначення бінарного дерева пошуку виявляється зручним для безпосереднього втілення у вигляді шаблону. Спрощене визначення

ДЕРЕВО: NIL | [ДЕРЕВО, ДАНІ, ДЕРЕВО]
можна перефразувати як «дерево — ЦЕ пусте безліч АБО безліч з трьох елементів: дерево (т. зв. ліве піддерево), дані, дерево (т. зв. праве піддерево)».

Крім цього, як уже згадувалося, бінарне дерево пошуку вимагає завдання відношення порядку на множині значень, що зберігаються у вузлах дерева (ми повинні вміти якось порівнювати й упорядковувати вузли, тобто мати операцію «менше»). Канонічним підходом є розбиття даних вузла на ключ (ключі порівнюємо значення просто зберігаємо), але в нашій реалізації в цілях спрощення структури без обмеження загальності будемо вважати дані сайту єдиним типом, для завдання ж відносини порядку скористаємося спеціальним типом
Comp
(comparator, поговоримо про нього далі).

/// Порожня множина
struct NIL {};

/// Вузол
template < typename T, typename Left, typename Right, typename Comp>
struct node {
using type = T; // node value
using LT = Left; // left subtree
using RT = Right; // right subtree
using comp = Comp; // types comparator
};

/// Лист: вузол без нащадків (псевдонім шаблону)
template < typename T, typename Comp>
using leaf = node<T NIL,NIL,Comp>;

Незважаючи на те, що відношення порядку все-таки задано на множині збережених у вузлах типів, зручно приписати його дереву і зберігати як частину типу цього дерева: при виклику метафункций пошуку, вставки і обходу непустого дерева немає необхідності в додатковому вказівці компаратора.

Про батьків і дітей:Уважний читач зверне увагу на те, що в представленій структурі не вистачає одного важливого для реалізації більшості алгоритмів елемента: посилання на батьківський вузол (у нашому випадку — псевдоніма типу батьківського дерева). Помітивши це і спробувавши виправити цю несправедливість, читач рано чи пізно в жахом усвідомлює, що в даному випадку буде мати місце циклічна залежність псевдонімів.

Сама по собі ситуація не критична і має виправленням у вигляді поділу оголошень і визначень типів:
template<...>
struct one {
struct two;
using three = one<two, ...>;
struct two : one<three, ...> {};
};
Примітка: експериментальним шляхом виявлено, що такі структури створюються і инстанцируются сучасними gcc і clang, тим не менш, я поки не перевіряв суворе відповідність стандарту оголошень таких незвичайних шаблонів.
Однак на практиці працювати з такими сутностями і створювати їх виявляється дуже, ДУЖЕ складно. Зворотній посилання на батьківський елемент виробляє цікавий ефект: фактично наше «односвязное дерево» перетворюється на справжній граф (смачно!), який при будь-якій модифікації повинен инстанцировать себе «одноразово», заново і повністю (сумно). Більш глибокий аналіз цієї ситуації виходить за межі цієї статті і входить в число моїх подальших планів по дослідженню можливостей метапрограммирования в C++.
Це не єдиний спосіб реалізації та подання дерева (наприклад, можна зберігати вузли в кортежі і проводити їх індексацію), однак такий опис більш наочно і зручно для безпосереднього застосування алгоритмів роботи з деревом.

Відношення порядку
Структура
Comp
має містити метафункции порівняння типів (тобто шаблони операцій «менше» і «дорівнює»). Напишемо приклад такого сравнителя, заснованого на
sizeof
'ах типів (можливо, єдина числова характеристика, визначена для всіх повних типів):

struct sizeof_comp {
template < typename U, typename V>
struct lt : std::integral_constant<bool, (sizeof(U) < sizeof(V))> {}; // менше

template < typename U, typename V>
struct eq : std::integral_constant<bool, (sizeof(U) == sizeof(V))> {}; // одно
};

Тут все повинно бути прозоро:
lt
— метафункция «менше» для типів,
eq
— метафункция «одно». Використаний підхід, показаний раніше для визначення типів чисел: спадкування від
std::integral_constant
наділить инстанцированные
lt
та
eq
статичними булевими операторами значеннями
value
.

На практиці конкретні дерева конкретних типів повинні забезпечуватися сравнителем, специфічним для даної задачі. Наприклад, напишемо порівняльна для описаного раніше класу «числових типів»:

struct num_comp {
template < typename U, typename V>
struct lt : std::integral_constant<bool, (U::value < V::value)> {};

template < typename U, typename V>
struct eq : std::integral_constant<bool, (U::value == V::value)> {};
};

Такий компаратор, взагалі кажучи, універсальний і вміє порівнювати будь-які типи, містять статичне значення
value
.

генерації компаратора допомогою CRTP:Раніше в теоретичному розділі згадувалося, що операції «менше», взагалі кажучи, досить, щоб інтуїтивно визначити і операцію «одно». Використовуємо підхід аналогічний CRTP (Curiously recurring template pattern, щоб визначити повний компаратор на основі тільки компаратора, що містить операцію (метафункцию) «менше»:
/// Шаблон для базового класу всіх згенерованих компараторів
template < typename lt_traits>
struct eq_comp {
template < typename U, typename V>
struct lt : std::integral_constant<bool, lt_traits::template lt<U,V>::value> {};

template < typename U, typename V>
struct eq : std::integral_constant<bool, (!lt<U,V>::value && !lt<V,U>::value)> {};
};

/// Переписаний компаратор sizeof, спадкування наділить його метафункцией eq_comp::eq
struct sizeof_comp : public eq_comp<sizeof_comp> {
template < typename U, typename V>
struct lt : std::integral_constant<bool, (sizeof(U) < sizeof(V))> {};
};

/// Переписаний компаратор num_t
struct num_comp : public eq_comp<num_comp> {
template < typename U, typename V>
struct lt : std::integral_constant<bool, (U::value < V::value)> {};
};
Розмір визначення зменшився і з'явилася математична підґрунтя — хіба це не прекрасно? =)
Тепер у нас є все для того, щоб явно, «руками», визначити перше дерево типів:

using t1 = node<
num_t<5>,
node<
num_t<3>,
leaf<num_t<2>>,
leaf<num_t<4>>
>,
node<
num_t<7>,
NIL,
leaf<num_t<8>>
>
>;
Примітка: Тут і далі в прикладах за замовчуванням мається на увазі порівняльне
num_comp
, вказівка його в списку аргументів шаблонів опускається. Взагалі, після розробки операції
insert
нам не доведеться будувати дерева таким чином (явним визначенням).
Описане дерево зображене на малюнку.

Про налагодження на етапі компіляції:Як нам переконатися, що визначений нами клас точно описує те, що ми задумали?

Ця окрема цікава тема для дискусії і дослідження — налагодження метапрограм. У нас немає ні стека викликів, ні змінних, ні, чорт візьми, банального
printf/std::cout
. Є техніки, які дозволяють друкувати всередині повідомлень про помилки компілятора удобочитаемые виведені типи, і, в принципі, це досить корисна можливість перевірки згенерованих структур (наприклад, після модифікації дерева).

Не будемо тут торкатися питання многомегабайтных повідомлень про помилки просто у випадку некоректної програми: після деякої практики це перестає бути проблемою, так як в переважній більшості випадків лише перша помилка инстанцироания веде до каскаду подальших помилок: налагодження у такому випадку ведеться методом послідовних наближень».

Але, як би парадоксально це не звучало, що робити, якщо програма скомпилировалось успішно? Тут вже автор більш вільний у виборі методів налагодження. Тип результату метафункций зразок визначених
type_trairs
можна просто друкувати у вигляді
typeid(t).name()
(починаючи з C++11 можна легально підглядати в RTTI). Прості структури даних можна виводити на екран спеціальними метафункциями з хвостової рекурсією, для складних доведеться городити «принтери», зіставні по складності з операціями над самою структурою.

Бібліотека дерев містить такий принтер і приклади його використання, читач може ознайомитися з ними за посиланням на github в кінці статті. Ось, наприклад, надруковане дерево з прикладу вище:
/--{2}
/--{3}--<
\--{4}
--{5}---<
\--{7}--\
\--{8}

Висота
Подивимося на рекурсивні функцію обчислення висоти бінарного дерева:

/// Вхід: T — дерево, вихід: h — висотаВИСОТА(T):
ЯКЩО T == NIL
ВИСНОВОК 0
ІНАКШЕ
ВИСНОВОК 1 + MAX(ВИСОТА(T. LEFT), ВИСОТА(T. RIGHT))

Вона прекрасна. Просто беремо і переносимо цю функцію на C++:

/// Оголошення загального шаблону
template < typename Tree>
struct height;

/// Часткова спеціалізація: "ЯКЩО T == NIL"
template <>
struct height<NIL> : std::integral_constant<size_t, 0> {};

/// Визначення загального шаблона (рекурсивне)
template < typename Tree>
struct height {
static constexpr size_t value = 1 + max(
height<typename Tree::LT>::value,
height<typename Tree::RT>::value
);
};
Примітка: ми свідомо пішли на невелике спрощення, з-за якого обчислена висота дерева буде на 1 більше її математичного визначення (висота порожнього безлічі не визначена). Читач без праці зможе виправити при необхідності цю особливість, додавши ще один рівень побічності і явно віднімаючи 1 з результату виклику метафункции, однак тоді доведеться заборонити инстанцирование
height
для порожнього дерева.
Код досить простий: при спробі виклику
height
з порожнім безліччю буде инстанцирована відповідна спеціалізація, що містить статичну
value = 0
, в іншому випадку продовжиться каскад инстанцирований, поки ми не натрапимо на порожнє дерево (тобто той же самий
NIL
), на якому рекурсія і зупиниться. Це характерна особливість реалізації рекурсивних функцій за допомогою шаблонів C++: ми зобов'язані спеціалізувати дно рекурсії, інакше каскад инстанцирований або не зупиниться (компілятор видасть помилку про перевищення ліміту вкладених инстанцирований), або на одному з кроків відбудеться спроба доступу до неіснуючого члену або значенням у класі (без спеціалізації описана вище функція в певний момент не змогла б отримати
Tree::LT
, коли
Tree
було б одно порожньому поддереву
NIL
).

У коді вище використовується функція
max
. Вона повинна бути
constexpr
(або просто метафункцией, тоді її виклик трохи зміниться), приклад простий і відомої реалізації:

template < typename T> constexpr T max(T a, T b) { return a < b ? b : a; }

Нарешті, використання функції
height
:

static_assert(height<t1>::value == 3, "");

Скажімо про «складності» функції
height
: потрібно n инстанцирований, де n — число вузлів дерева; глибина инстанцирования дорівнює h — тобто висоті дерева.

Яка ще складність і навіщо вона тут?!Справа в тому, що, хоча всю роботу по рекурсивного обчислення робить компілятор, його потужність не безмежна: з легкої руки винахідників шаблонів наділений обов'язком вирішувати проблему зупинки (!), компілятор все-таки повинен контролювати своє власне стан і не вдаватися в крайності, займаючись майнингом биткоинов божевільного метапрограммиста. А якщо серйозно, компілятор сам повинен вміти зупинитися: для цього вводяться обмеження на глибину инстанцирований шаблонів, рекурсивних викликів
constexpr
-функцій і довжину variadic-списків аргументів.

У документації до свого улюбленого компілятору читач зможе знайти конкретні значення: наприклад, gcc-5.4 «з коробки» (без додаткових опцій) инстанцирует шаблони не глибше 900 рівнів. У світлі вищесказаного це означає, що не можна забувати про оптимізації метафункций (як би дико це не звучало). Наприклад, виклик
height
цілком може відмовитися компілюватися gcc, якщо дерево має висоту > 900. Можна навіть ввести O-позначення для опису складності (хоча часто можна точно порахувати кількість і глибину инстанцирований), і вона буде мати цілком здоровий глузд.

Наприклад, в стандарті C++14 планується ввести шаблон для генерації послідовностей цілих (
std::integer_sequence
): пряма рекурсивна реалізація вимагає N инстанцирований для послідовності 0..N-1, однак існують елегантні деревоподібні рішення, глибина рекурсії яких зростає зі швидкістю логарифму довжини послідовності. Зрештою, ми завжди можемо реалізувати будь-яку функцію повним перебором, але компілятор цього точно не зрадіє, як і ми, годину чекають завершення компіляції 30-рядкової програми або вимушені читати 9000-сторінкові повідомлення про помилки).

Якщо перевищення допустимої глибини инстанцирований може просто перешкодити компіляції, то кількість инстанцирований (тобто викликів метафункций) прямо впливає на час компіляції: для складних метапрограм воно може надати дуже велике. Тут відіграє роль багато факторів (необхідність виведення типів, зіставлення часткових спеціалізацій і т. д.), тому не варто забувати, що компілятор — така ж програма, а механізм шаблонів — свого роду API до внутрішнього кодогенератору компілятора, і користуватися ним треба вчитися так само, як освоювати окремий мова програмування — послідовно і акуратно (і щоб ніяких «Курсів програмування для чайників за 24 години»!).

Обхід центрований (in-order traversal)
Завдання обходу — певним чином сформувати список вузлів (або даних з вузлів, питання термінології і має значення на практиці). Центрований (симетричний) обхід — обхід, при якому корінь дерева займає місце між результатами відповідних обходів лівого та правого піддерев. Разом з властивістю бінарного дерево пошуку (про яке нерівностях, див. теорію) це говорить про те, що центрований обхід бінарного дерева пошуку сформує нам відсортований список вузлів — круто! Ось як буде виглядати обхід визначеного раніше дерева:


Рекурсивний алгоритм обходу досить простий:

/// Вхід: T — дерево, вихід: w — список даних з вузлів in-order обходуINORDER(T):
ЯКЩО T == NIL
ВИСНОВОК {}
ІНАКШЕ
ВИСНОВОК INORDER(T. LEFT) + {T. KEY} + INORDER(T. RIGHT)

Операція "+" в даному випадку позначає конкатенацию списків. Так-так, це саме те, заради чого ми реалізовували конкатенацию кортежів, так як кортежі — це наші списки типів на етапі компіляції. І знову — просто беремо і пишемо код:

/// Оголошення загального шаблону
template < typename Tree>
struct walk;

/// Часткова спеціалізація: "ЯКЩО T == NIL"
template <>
struct walk<NIL> { using type = std::tuple<>; };

/// Визначення загального шаблона (рекурсивне)
template < typename Tree>
struct walk {
private:
// обхід лівого піддерева
using accL = typename walk<typename Tree::LT>::type;

// додаємо корінь
using accX = tuple_push_t<accL, typename Tree::type>;

// конкатенируем з обходом правого піддерева
using accR = tuple_concat_t<accX, typename walk<typename Tree::RT>::type>;

public:
// результат
using type = accR;
};

В даному випадку не більш ніж заради наочності ми скористалися локальними
private
псевдонімами: всі псевдоніми можна підставити одне в одного і отримати фарш, обфусцированный крутіше випадково згенерованої рядка, і навіть відступи нас не врятують. Але ми ж намагаємося для людей, чи не так?

Складність функції
walk
: O(n) инстанцирований, де n — число вузлів дерева (O-нотація використана для спрощення: акуратний підрахунок дасть приблизно 3n викликів метафункций з урахуванням конкатенаций). Приємно, що функції
tuple_concat
та
tuple_push
виконують свою роботу за 1 инстанцирование, так як вони не рекурсивны (завдяки можливості виведення типів
parameter pack
'ів). Глибина инстанцирований, як і у випадку
height
, дорівнює h — висоті дерева.

Про читабельність коду:Не лінуйтеся додавати синтаксичний цукор і акуратно форматувати код: метапрограми об'єктивно сприймаються гірше, ніж звичайний код, тому стандартні вимоги до облагороджування коду ще більш актуальними в цій справі.

Ще одне зауваження з написання метафункций: читач, можливо, звернув увагу на те, що для останніх двох функцій немає необхідності розділяти оголошення і визначення загального шаблону. Це так, проте я дотримуюся стандартизованого підходу: «від максимально приватного до максимально загального». Багато шаблони цілком працюють на часткових спеціалізаціях, і в такому випадку дуже зручно виявляється описувати ці спеціалізації з зростаючим рівнем спільності: подумки програміст проходить той же шлях, який проходить компілятор в спробах инстанцирования і виведення типів.

Пошук
Пошук за ключем є основною операцією в класичних бінарних деревах пошуку (назва говорить сама за себе). Ми вирішили не розділяти ключ і дані, тому для порівняння сайтів будемо застосовувати введений порівняно
Comp
. Рекурсивний алгоритм пошуку:

/// Вхід: T — дерево, k — тип-ключ,
/// вихід: N — сайт, що містить тип k` == k в термінах сравнителяSEARCH(T,k):
ЯКЩО T == NIL АБО k == T. KEY
ВИСНОВОК T
ІНАКШЕ
ЯКЩО k < T. KEY
ВИСНОВОК SEARCH(T. LEFT, k)
ІНАКШЕ
ВИСНОВОК SEARCH(T. RIGHT, k)

Реалізація зовні схожа на розроблені раніше:

/// Оголошення загального шаблону
template < typename Tree, typename T>
struct search;

/// Спеціалізація для порожнього дерева
template < typename T>
struct search<NIL,T> { using type = NIL; };

/// Визначення загального шаблону
template < typename Tree, typename T>
struct search {
using Comp = typename Tree::comp;
using type = typename std::conditional<
Comp::template eq<T, typename Tree::type>::value, // k == T. KEY ?
Tree, // пошук завершений, інакше:
typename std::conditional<
Comp::template lt<T, typename Tree::type>::value, // k < T. KEY ?
typename search<typename Tree::LT, T>::type, // тоді шукаємо в лівому
typename search<typename Tree::RT, T>::type // інакше-у правому
>::type
>::type;
};

Виглядає дещо складніше, це неспроста: по-перше, сам алгоритм містить більше розгалужень (більше порівнянь і умов), по-друге, тут ми вже повинні застосовувати певний раніше відношення порядку, і на його основі продовжувати пошук рекурсивно або в лівому, або в правому поддереве. Звернемо увагу на деталі:

  • Для порівняння типів використовується порівняно з кореня дерева:
    Tree::comp
    , що логічно: відношення порядку визначає як спосіб побудови дерева, так і наступні операції (в тому числі, пошук), ось чому було зручно помістити псевдонім сравнителя прямо всередину шаблону дерева (
    node<>
    ).
  • Для доступу до шаблоном, залежить від аргументу шаблону (
    Tree::comp::eq<...>
    та
    Tree::comp::lt<...>
    ), необхідно використовувати ключове слово
    template
    .
  • Ми пішли по шляху найменшого опору і використовували
    std::conditional
    — стандартну метафункцию, що визначає результуючий псевдонім залежно від булевої змінної (такий аналог тернарного оператора ?: для типів). Чому це може бути не дуже добре — див. далі, однак з позитивних моментів — бльшая наочність.
Складність такої реалізації
search
— знову-таки O(n) инстанцирований, глибина — h (висота дерева). «Стоп!» — вигукне здивований читач, — «а як же логарифмічна складність пошуку і все таке?»

Тут-то і летять каміння в бік
std::conditional
і виявляється його принципова відмінність від оператора ?:: тернарний оператор не обчислює той вираз, який не буде його результатом (наприклад, ми можемо з чистою совістю розв'язати нульовий покажчик в одному з двох виразів, яке отбросится при перевірці цього покажчика в першому аргументі оператора).
std::conditional
ж инстанцирует всі три аргументи (як звичайна метафункция), саме тому одного тільки
std::conditional
недостатньо для зупинки рекурсії, і ми все ще повинні спеціалізувати дно рекурсії.

Прямий результат — зайві инстанцирования, захоплюючі все дерево цілком від кореня до листків. Особливим чаклунством з додаванням ще одного рівня побічності можна-таки «відключити» на кожному кроці рекурсії инстанцирования по шляху піддерево, в якому точно немає шуканого вузла (написавши ще пачку спеціалізацій для цього рівня побічності) і досягти заповітної складності O(h), проте, на мій погляд, це завдання для більш глибокого дослідження і в даному випадку буде передчасної оптимізацією.

Приклади застосування (використані шаблони псевдонімів, більше прикладів див. в репозиторії):

using found3 = search_t<NIL, num_t<0>, num_comp>; // у порожньому дереві
using found4 = search_t<t1, num_t<5>, num_comp>; // значення в корені
using found5 = search_t<t1, num_t<8>, num_comp>; // значення у листі

static_assert(std::is_same<found3, NIL>::value, ""); // не знайдено
static_assert(std::is_same<found4, t1>::value, ""); // саме дерево
static_assert(std::is_same<found5 leaf<num_t<8>>>::value, ""); // лист

Це може здатися дивним: ми шукаємо в дереві вузол з типом… який фактично вже зазначено в якості аргументу — навіщо? Насправді, нічого незвичайного в цьому немає — ми шукаємо тип, рівний аргументу в термінах сравнителя. Дерева STL (
std::map
) теж зберігають у вузлах пари (
std::pair
), і перший елемент пари вважається ключем, який, власне, і бере участь у порівняннях. Досить зберігати в нашому дереві ту ж
std::pair
і змусити порівняльна
Comp
порівнювати пари по першому типу в парі — і отримаємо класичний асоціативний (мета)контейнер! Ми ще повернемося до цієї ідеї в кінці статті.

Вставити
Настав час навчитися будувати дерева з допомогою метафункций (не для того ж все затівалося, щоб малювати дерева руками так, як ми це зробили раніше?). Наш рекурсивний алгоритм вставки буде створювати нове дерево:

/// Вхід: T — дерево, k — тип-ключ для вставки,
/// вихід: T' — нове дерево зі вставленим елементомINSERT(T,k):
ЯКЩО T == NIL
ВИСНОВОК {NIL, k, NIL}
ІНАКШЕ
ЯКЩО k < T. KEY
ВИСНОВОК {INSERT(T. LEFT,k), T. KEY, T. RIGHT}
ІНАКШЕ
ВИСНОВОК {T. LEFT, T. KEY, INSERT(T. RIGHT,k)}

Пояснимо його роботу: якщо дерево, яке відбувається вставка, порожньо, то вставлений елемент створить нове дерево {NIL,k,NIL}, тобто просто аркуш з цим елементом (дно рекурсії). Якщо ж дерево не пусто, то ми повинні рекурсивно провалюватися до порожнього дерева (тобто до моменту, поки ліве або праве піддерева не виявляться порожніми), і в підсумку сформувати у цьому поддереве той же лист {NIL,k,NIL} замість NIL, по шляху «підвішуючи» себе у вигляді нового лівого або правого піддерева. У світі типів змінювати існуючі типи ми не можемо, але можемо створювати нові — це і відбувається на кожному кроці рекурсії. Реалізація:

template < typename Tree, typename T, typename Comp = typename Tree::comp>
struct insert;

/// Дно рекурсії
template < typename T, typename Comp>
struct insert<NIL,T,Comp> { using type = leaf<T,Comp>; };

/// Основний шаблон
template < typename Tree, typename T, typename Comp>
struct insert {
using type = typename std::conditional<
Comp::template lt<T, typename Tree::type>::value, // k < T. KEY?
node<typename Tree::type, // нове дерево {INSERT(T. LEFT,k), T. KEY, T. RIGHT}
typename insert<typename Tree::LT, T, Comp>::type,
typename Tree::RT,
Comp>,
node<typename Tree::type, // нове дерево {T. LEFT, T. KEY, INSERT(T. RIGHT,k)}
typename Tree::LT,
typename insert<typename Tree::RT, T, Comp>::type,
Comp>
>::type;
};

Для додавання елемента в порожнє дерево треба явно вказати компаратор
Comp
; якщо ж дерево не порожньо, компаратор береться за замовчуванням коріння цього дерева*.

Складність такої вставки: O(n) инстанцирований (n — кількість вже існуючих вузлів), глибина рекурсії дорівнює h (h — висота дерева). Приклад явного використання:

using t2 = leaf<num_t<5>, num_comp>;
using t3 = insert_t<t2, num_t<3>>;
using t4 = insert_t<t3, num_t<7>>;

static_assert(height<t4>::value == 2, ""); // перші 2 рівня

using t5 = insert_t<insert_t<insert_t<t4, num_t<2>>, num_t<4>>, num_t<8>>;

static_assert(std::is_same<t5, t1>::value, ""); // одно початкового дереву

В бібліотеці є реалізація метафункции
insert_tuple
, що дозволяє разом покласти в дерево кортеж типів (під капотом це просто рекурсія
insert
по кортежу), приклад:

using t6 = insert_tuple_t<NIL, std::tuple<
num_t<5>,
num_t<7>,
num_t<3>,
num_t<4>,
num_t<2>,
num_t<8>
>, num_comp>;

static_assert(std::is_same<t1, t6>::value, "");

Обхід в ширину (breadth-first traversal)
Обхід в ширину бінарного дерева (або пошук у ширину з теорії графів) формує список вузлів в порядку «за рівнями» — спочатку виводить корінь, потім вузли з глибиною 1, потім з глибиною 2 і т. д. Алгоритм такого обходу використовує на вузлів для подальшого виведення (а не стек), тому він погано піддається «конвертації» в рекурсивний. Під спойлером далі цікавиться читач знайде спосіб вирішення. Тут зазначимо лише той корисний факт, що «розібраний» обходом завширшки дерево може бути зібрано назад у точно таке ж послідовної вставкою елементів з кортежу результату обходу. На малюнку представлен обхід в ширину нашого тестового дерева:


Рекурсивний обхід в ширину:Ідея проста: проходимся циклом від 0 до висоти дерева h і на кожній ітерації виводимо тільки вузли з потрібного рівня. Остання операція може бути реалізована рекурсивно:

/// Вхід: T — дерево, l — рівень для висновку,
/// вихід: t — список вузлів цього рівняCOLLECT_LEVEL(T,l):
ЯКЩО T == NIL
ВИСНОВОК {}
ІНАКШЕ
ЯКЩО l == 0
ВИСНОВОК {T. KEY}
ІНАКШЕ
ВИСНОВОК COLLECT_LEVEL(T. LEFT,l-1) + COLLECT_LEVEL(T. RIGHT,l-1)

Повну реалізацію на шаблонах читач може знайти в репозиторії. На відміну від усіх розглянутих раніше операцій, обхід в ширину матиме складність O(nh) инстанцирований з-за наявності циклу по висоті (який, хоч і перетвориться в хвостову рекурсію, буде містити перерахунок
collect_level
для всього дерева на кожному кроці).

Видалення?
Видалення вузла — завдання нетривіальне. Класичний підхід розглядає 3 випадки (за кількістю дочірніх вузлів), і в алгоритмі використовуються поняття подальшого батьківського вузла. Без зворотного посилання на батьківський вузол (див. спойлер «Про батьків і дітей»), ефективно реалізувати алгоритм проблематично: кожна операція з підйому вгору по дереву повинна буде мати складність O(n). Наївна реалізація такого видалення призведе до «комбінаторного вибуху» за кількістю инстанцирований (складність щось близько O(nn)). Розробка метафункции видалення вузла входить у подальші плани щодо вдосконалення бібліотеки.

Застосування
Переведемо подих і нарешті приділимо увагу питанню, навіщо може знадобитися бінарне дерево пошуку часу компіляції? Є три відповіді:

Неконструктивний:
*Картинка з тролейбусом*. Опустимо.

Очевидний:
… для що мають дослідницький інтерес
Конструктивний:
Наведемо приклади можливих застосувань такої структури:

  • Сортування типів: симетричний обхід дерева формує кортеж зі списком типів, відсортованих в термінах заданого компаратора. Визначення пари допоміжних шаблонів псевдонімів дозволяє однією командою «відсортувати» заданий кортеж. Як самоціль для розробки дерева — не саме корисне застосування (складність — O(n2) инстанцирований), але як легкий природний бонус — цілком має право на існування.

  • Плоска runtime структура даних: після виконаної роботи не складе особливої праці наділити кожен вузол дерева не тільки статичними полями, але і даними-членами. Після инстанцирования дерево перетвориться на подобу кортежу
    std::tuple
    — плоску структуру даних. Зрозуміло, в runtime змінювати його структуру вже буде не можна, але доступ по типу і обходи все ще будуть корисними операціями, так як будуть розгортатися на етапі компіляції без єдиної рядки машинного коду (як
    std::get
    в застосуванні до
    std::tuple
    ).

  • Асоціативний контейнер в compile-time: у першому наближенні таке дерево можна використовувати як аналог
    std::map
    (або безлічі
    std::set
    ) — якщо згадати, що навіть рядка (точніше, рядкові літерали) особливою магією можна перетворити на типи (і навіть виконувати типові строкові операції — конкатенацию, пошук підрядків і т. д.), таке дерево може грати ту ж роль в compile-time, яку його старші брати грають у runtime реалізаціях самих різних алгоритмів. Приклади: дерева суфіксів, дерево алгоритму Хаффмана, синтаксичні дерева. А ще: відчуваєте цей чудовий аромат рефлексії?

  • Генерація ієрархій: як згадувалося в примітці «Ліричний відступ», Александреску використовував шаблони для генерації складних ієрархій спадкування. Дерево саме по собі вже є ієрархічною структурою, тому, думаю, воно може знайти застосування в аналогічних завдання.
Ліричний відступ:Через книгу «Modern C++ Design: Generic Programming and Design Patterns Applied» (у Росії видана під назвою «Сучасне проектування на С++», див. список літератури) відомого дослідника і популяризатора шаблонного програмування Андрія Александреску червоною ниткою проходить думка: «змусьте компілятор робити за вас як можна більшу частину роботи». Автор книги застосовував
static_assert
до того, як це стало мейнстрімом він офіційно з'явився в стандарті C++11, розробив і дослідив концепцію стратегій (або політик, policy), яка сьогодні застосовується в істотній частині STL, фактично в рамках стандарту C++98 реалізував кортежі («списки типів») і описав процес створення з їх допомогою складних ієрархій наслідувань (мене в свій час дуже вразив той факт, що на момент написання книги багато концепти, введені Александреску і теоретично відповідали стандарту, просто не компілювати більшістю компіляторів того часу).

Власне, це до слова про основний мотивації адептів метапрограммирования: перенести якомога більшу частину роботи в compile-time — правила світу часу компіляції набагато суворіше, однак ціна помилки значно нижче (найчастіше програма лише не відбудеться створення, а не вистрілить в ногу після запуску), а добре налагоджені бібліотеки шаблонів є незамінним підмогою в розробці промислового (на низькому рівні практично будь-який «велосипед», породжений бажаннями замовника, може бути описаний стандартним шаблоном з невеликою кількістю предметно-орієнтованих налаштувань).
В довершення хочу сказати кілька слів про завдання, сподвигнувшей до розробки дерева і написання статті. Існує декілька алгоритмів прямої конвертації регулярного виразу в ДКА (детермінований скінченний автомат), його розпізнає, частина яких оперує т. н. синтаксичним деревом, яке за своєю природою «не більш ніж» бінарне. Таким чином, бінарне дерево пошуку часу компіляції — складова частина (і просто цікава структура для реалізації) compile-time парсера регулярних виразів (після компіляції і вбудовування здатного розвернутися в плоский код ДКА), який, у свою чергу, стане частиною іншого проекту.

Що потім?
Пошепки: Зима...Якщо ця стаття викличе інтерес і знайде свого читача, я з задоволенням продовжу тему метапрограммирования (і, можливо, не тільки) в наступних публікаціях. З смачного — згадувана робота з рядками часу компіляції, математика часу компіляції (наприклад, ро-факторизація Полларда),
std
-сумісний контейнер (з итераторами — сам tutorial по розробці контейнерів повинен бути цікавий). Більш того, на горизонті проект парсера регекспов і деякі інші напрацювання нашої команди.

Конструктивна критика категорично вітається!
Література
  • Кормен, Т., Лейзерсон, Ч., Рівестом, Р., Штайн, К. Алгоритми: побудова й аналіз = Introduction to Algorithms. — 2-е. — М.: Вільямс, 2005. — 1296 с. 
  • Александреску А. Сучасне проектування на С++: Узагальнене програмування та прикладні шаблони проектування = Modern C++ Design: Generic Programming and Design Patterns Applied. — З. П.: Вільямс, 2008. — 336 с. — (С++ in Depth). 
  • Саттер Р., Андрій Александреску. Стандарти програмування на З++. Серія «C++ In-Depth» = C++ Coding Standards: 101 Rules, Guidelines and Best Practices (C++ In-Depth). — М.: «Вільямс», 2014. — 224 с. 
  • Готтшлинг П. Сучасний C++ для програмістів, інженерів і вчених. Серія «C++ In-Depth» = Discovering Modern C++: A Concise Introduction for Scientists and Engineers (C++ In-Depth). — М.: «Вільямс», 2016. — 512 с. 
Репозиторій
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.