c++ - C++中存在量化的等价物？

Question

为了帮助自学 C++，我正在研究一个红黑树实现。来自(哪里Haskell，我认为看看我是否可以强制执行 properties of ared-black tree 会很有趣。静态地在 C++ 的类型系统中:

1. A node is either red or black.
2. The root is black [...]
3. All leaves (NIL) are black.
4. If a node is red, then both its children are black.
5. Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. [...]

我想出了如何为树的节点设计类型以满足约束 1，3、4、5使用模板:

template <typename Key, typename Value>
class RedBlackTree {
private:
  enum class color { Black, Red };

  // [1. A node is either red or black]
  template <color Color, size_t Height>
  struct Node {};

  // [3. All leaves are black]
  struct Leaf : public Node<color::Black, 0> {};

  template <color Left, color Right, size_t ChildHeight>
  struct Branch {
  public:
    template <color ChildColor>
    using Child = unique_ptr<Node<ChildColor, ChildHeight>>;

    Key key;
    Value value;
    Child<Left> left;
    Child<Right> right;

    Branch(Key&& key, Value&& value, Child<Left> left, Child<Right> right) :
      key { key }, value { value }, left { left }, right { right } {}
  };

  // [4. If a node is red, then both its children are black.]
  // [5. Every path from a given node to any of its descendant NIL nodes contains 
  //     the same number of black nodes.]
  template <size_t Height>
  struct RedBranch: public Node<color::Red, Height>
                  , public Branch<color::Black, color::Black, Height> {
  public:
    using RedBlackTree::Branch;
  };

  // [5. Every path from a given node to any of its descendant NIL nodes contains 
  //     the same number of black nodes.]
  template <size_t Height, color Left, color Right>
  struct BlackBranch: public Node<color::Black, Height>
                    , public Branch<Left, Right, Height-1> {
  public:
    using RedBlackTree::Branch;
  };

  // ...
};

我遇到困难的地方是提供 root 指针，该指针将存储在 RedBlackTree 中实例化满足属性 2 但仍然有用的类型。

我想要的是这样的:

template <typename Key, typename Value>
class RedBlackTree {
  //...
  unique_ptr<Node<color::Black,?>> root = std::make_unique<Leaf>();
  //...
}

(从 Java 借用语法)，所以我可以在树的高度上使用通配符。这个当然，不起作用。

如果我这样做了，我可以编译我的代码

template <typename Key, typename Value, size_t TreeHeight>
class RedBlackTree {
  //...
  unique_ptr<Node<color::Black,TreeHeight>> root = std::make_unique<Leaf>();
  //...
}

但这不是我想要的树的类型 - 我不想要树本身的类型反射(reflect)它的高度，否则当我插入一个树时，我的树的类型可能会改变键值对。我希望能够更新我的 root 以包含指向黑色的指针任意高度的节点。

回到haskell-land，我会使用existential解决这个问题量化:

data Color = Black | Red

data Node (color :: Color) (height :: Nat) key value where
  Leaf :: Node 'Black 0 key value
  BlackBranch :: Branch left right height key value -> Node 'Black (height+1) key value
  RedBranch :: Branch 'Black 'Black height key value -> Node 'Red height key value

data Branch (left :: Color) (right :: Color) (childHeight :: Nat) key value = Branch
  { left  :: Node left childHeight key value
  , right :: Node right childHeight key value
  , key   :: key
  , value :: value
  }

data RedBlackTree key value where
  RedBlackTree :: { root :: Node 'Black height key value } -> RedBlackTree key value

在 C++14(或者可能是 C++17)中是否有等效的概念，或者我可以编写 struct 定义以赋予 root 有用且正确的类型？

Answer 1

template<class K, class T>
struct NodeView {
  virtual NodeView const* left() const = 0;
  virtual NodeView const* right() const = 0;
  virtual K const& key() const = 0;
  virtual T const& value() const = 0;
private:
  ~NodeView() {} // no deleting it!
};

这是一个界面。

让你的树节点实现这个接口(interface)。允许并鼓励他们返回 nullptr当他们在一侧或另一侧没有 child 时。

在基础结构中，取一个根节点作为模板参数。使用模板 tomfoolery 检查它是否为黑色。

使用 make_shared将其存储在 std::shared_ptr

auto tree = std::make_shared<std::decay_t<decltype(tree)>>(decltype(tree)(tree));
std::shared_ptr<NodeView const> m_tree = std::move(tree);

m_tree 在哪里member 是您的根管理结构的成员。

您现在拥有对通用树的只读访问权限。存储它的代码保证在编译时它是一个平衡的红黑树。在运行时，它只是保证是一棵树。

您可以将更多保证信息泄漏到我在上面编写的界面中，但这会使界面困惑，超出读者通常需要知道的范围。 (例如，具有不同的 Red 和 Black 接口(interface)节点类型)。

现在，如果一个短函数的主体太过于信任，而您宁愿信任一堵模板代码，我们可以这样做:

template<template<class...>class Test, class T>
struct restricted_shared_ptr {
  template<class U,
    std::enable_if_t< Test<U>{}, int> = 0
  >
  restricted_shared_ptr( std::shared_ptr<U> pin ):ptr(std::move(pin)) {}
  restricted_shared_ptr(restricted_shared_ptr const&)=default;
  restricted_shared_ptr(restricted_shared_ptr &&)=default;
  restricted_shared_ptr& operator=(restricted_shared_ptr const&)=default;
  restricted_shared_ptr& operator=(restricted_shared_ptr &&)=default;
  restricted_shared_ptr() = default;
  T* get() const { return ptr.get(); }
  explicit operator bool() const { return (bool)ptr; }
  T& operator*() const { return *ptr.get(); }
  T* operator->() const { return ptr.get(); }
private:
  std::shared_ptr<T> ptr;
};

现在我们只需编写一个任意模板检查，上面写着“这足以让我满意”。

并存储一个 restricted_shared_ptr< MyCheck, NodeView<K,T> const > .无法将 a 类型存储在此共享指针中，该指针未通过 MyCheck没有未定义的行为。

在这里，您需要信任 MyCheck的构造函数按照它所说的去做。

template<class T>
struct IsBlackNode:std::false_type{};

template<class K, class V, std::size_t Height, class Left, class Right>
struct IsBlackNode< BlackNode<K, V, Height, Left, Right> >:std::true_type{};

这是一个要求，只有 BlackNode s可以通过。

所以一个 restricted_shared_ptr< IsBlackNode, NodeView<K, T> const >是指向通过 IsBlackNode 的东西的共享指针测试和实现NodeView<K,T>界面。