相当于C++中的存在量化？

Question

为了帮助自学C++,我正在开发一个红黑树实现.来自Haskell,我认为看看我是否可以 在C++的类型系统中静态强制执行红黑树的属性是很有趣的:

1. 节点为红色或黑色.
2. 根是黑色的[...]
3. 所有叶子(NIL)都是黑色的.
4. 如果节点为红色,则其子节点均为黑色.
5. 从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点.[...]

我想出了如何使用模板为树的节点制作类型以满足约束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>();
  //...
}

但这不是我想要树的类型 - 我不希望树本身的类型反映它的高度,否则当我插入一个键值对时,我的树的类型可能会改变.我希望能够更新我root的包含指向任何高度黑色Node的指针 .

回到haskell-land,我会用存在量化来解决这个问题:

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!
};

这是一个接口。

让您的树节点实现此接口。nullptr当他们一方或另一方都没有孩子时，他们被允许并鼓励返回。

在基础结构中，将根节点作为模板参数。使用模板 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成员是您的根管理结构的成员。

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

您可以将更多的保证信息泄漏到我上面编写的界面中，但这会使界面变得混乱，超出了读者通常需要了解的范围。（例如，具有不同的Red接口Black节点类型）。

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

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 >. 无法在该共享指针中存储类型，该类型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{};

这是只有 s 才能通过的要求BlackNode。

所以 arestricted_shared_ptr< IsBlackNode, NodeView<K, T> const >是一个共享指针，指向通过测试IsBlackNode并实现接口的东西NodeView<K,T>。