如何在给定的自引用模板实现中去掉抽象类?
我刚刚尝试实现一个跳表数据结构。 所以我想创建模板节点,这样我就可以为不同的节点类实例化下一个链接的类,以避免类转换。 发现了这些问题:
Self-referencing Template in Template Argument
How to properly declare a self-referencing template type?
但他们都没有解决方案。然后我根据两行继承制定了自己的解决方案。一个是“抽象”模板序列(用于 Next 参数传播)。另一种是实例化具体类。但是感觉可以改进它来处理没有冗余抽象模板(NodeAbstract、NodeWithKeyAbstract 等)的情况。经过几次自己的尝试,我想请你帮助我:
template <class Value, class Next >
class NodeAbstract
{
public:
Value m_value;
Next * next;
NodeAbstract () : next(0) {}
Next * getNext() {return next;}
};
template <class Value, class Key, class Next >
class NodeWithKeyAbstract : public NodeAbstract <Value, Next >
{
public:
Key m_key;
};
template <class Value, class Key>
class NodeWithKey : public NodeWithKeyAbstract <Value, Key, NodeWithKey<Value,Key> >
{
};
template <class Value, class Key, int maxlevel, class Next>
class NodeSkipListAbstract : public NodeWithKeyAbstract<Value, Key, Next >
{
public:
Next * nextjump[maxlevel-1];
};
template <class Value, class Key, int maxlevel>
class NodeSkipList : public NodeSkipListAbstract<Value, Key, maxlevel, NodeSkipList<Value, Key, maxlevel> >
{
};
最佳答案
如果我理解正确,你的问题基本上是不同的 maxlevel
值会产生不同的类,所以你不能使用一个数组来存储它们(如果我是,请纠正我错误)。
您不能完全摆脱抽象类 - 如果您想要将具有不同最大级别的节点作为不同的类(不同的模板特化),您必须为它们提供一些共同点。
好消息是你可以摆脱 Curiously Recurring Template Pattern 相反 - 因为你使用指针你不必引用确切的实现类型(例如知道确切的模板特化)如果你抽象让你访问所有你需要的信息。您的代码也可以稍微简化。
考虑这段代码:
template <class Key, class Value>
class Node {
public:
virtual ~Node() = default;
virtual std::size_t MaxLevel() const = 0;
virtual Node* Skip(size_t level) const = 0;
// add setter as well
Key key;
Value value;
};
template <class Key, class Value, std::size_t max_level>
class NodeImpl : public Node<Key, Value> {
public:
typedef Node<Key, Value> node_type;
NodeImpl() : skips() {}
size_t MaxLevel() const { return max_level; }
node_type* Skip(std::size_t level) const {
return level < max_level ? skips[level] : nullptr;
}
// add setter as well
private:
node_type* skips[max_level];
};
template <class Key, class Value>
class SkipList {
public:
typedef Node<Key, Value> node_type;
node_type* head;
};
此处 Node
为您提供了“跳过”行为的抽象。 NodeImpl
将用于生成具有不同最大级别的 Node
,但最终使用的实现对您来说是透明的 - 您将只使用 Node
的界面。同样在语法级别上,您将只使用 Node*
类型,因此实现的多样性不会成为问题。虚拟析构函数将确保 delete
释放所有内存,并且 key
和 value
将始终作为公共(public)字段访问。
这段代码当然可以改进。原始数组可以替换为 std::array
。如果您决定使用 std::vector
并在构造函数中设置大小而不是数组(那么您将只有Node
和 SkipList
)。作为奖励,创建新节点会更容易,因为现在您必须编写一些工厂,其中包含从 1 到某个值的所有 NodeImpl
的特化。此外,指针可以替换为一些智能指针以避免内存泄漏。
关于c++ - 如何改进自引用模板的实现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29376183/