Я пытаюсь придумать некоторые структуры данных с зависимой типизацией для C ++ во время компиляции. Я несколько рассмотрел основной пример, тип списка с его длиной, закодированной в типе, иначе. list<T, length>
, Здесь можно легко сохранить простые инварианты, например, вы можете быть уверены, что добавление двух списков будет иметь сумму длины его части как длины и т. Д. До сих пор тривиально. Сейчас я перехожу на зависимо типизированные деревья, иначе. binary_tree<T, height>
, так что я могу изменить это для достижения сбалансированных по высоте деревьев. Идея состоит в том, чтобы отказаться от любой операции, которая нарушит балансировку по высоте во время компиляции. Все это также является хорошим упражнением в рекурсивном мышлении для меня.
Я собираюсь представить свою попытку и позже спрошу об ошибке.
// A binary tree of height N
template <typename T, std::size_t N>
struct binary_tree
{
constexpr binary_tree(const T &node, binary_tree<T, N-1> left,
binary_tree<T, N-1> right)
:root{node}, left{left}, right{right}, size{left.size + right.size + 1}
{}
const T root;
const binary_tree<T, N-1> left;
const binary_tree<T, N-1> right;
const std::size_t size; // num of elements in tree
constexpr static const std::size_t capacity = 2^N -1;
};
template <typename T>
struct binary_tree<T, 0>
{
const std::size_t size{0};
constexpr static const bool nil = true;
};
template <typename T>
using empty_tree = binary_tree<T,0>;template <typename T, std::size_t N>
constexpr auto insert(const T& elem, const binary_tree<T, N> &tree) {
if constexpr (N == 0)
return binary_tree<T, 1>{elem, empty_tree<T>{}, empty_tree<T>{}};
else if (elem <= tree.root && tree.size < binary_tree<T, N>::capacity)
return binary_tree<T, N>{tree.root,
insert(elem, tree.left),
tree.right};
else if (elem <= tree.root && tree.size == binary_tree<T, N>::capacity)
return binary_tree<T, N + 1>{tree.root,
insert(elem, tree.left),
tree.right};
else if (elem > tree.root && tree.size < binary_tree<T, N>::capacity)
return binary_tree<T, N>{tree.root,
tree.left,
insert(elem, tree.right)};
else if (elem > tree.root && tree.size == binary_tree<T, N>::capacity)
return binary_tree<T, N + 1>{tree.root,
tree.left,
insert(elem, tree.right)};
}
int main() {
constexpr binary_tree<int, 1> tr1{2, empty_tree<int>{}, empty_tree<int> {}};
constexpr auto tr2 = insert(1, tr1);
}
Дело в том, что мой insert
Функция пытается создать вызовы и для других веток, так как только первый constexpr if
, Почему-то мне нужно сделать все дела else if constexpr
но это кажется невозможным, так как сравнение elem
чтобы увидеть, какое поддерево вставить не constexpr
, Почему elem < tree.root
не является constexpr
В конце концов, они являются двумя постоянными значениями.
Редактировать: я понял, что проблематично брать левое и правое поддеревья одинаковой высоты, что не обязательно верно для общих деревьев. Это смущает меня больше.
Задача ещё не решена.
Других решений пока нет …