1

nilのセンチネルとして機能する静的変数 がありますtemplate <typename Node> Tree。タイプに特化してツリーを増やしています。Nodeただし、nil の作成に問題があります。

Tree の静的メンバーとしての Nil

中身tree.h

template <typename Node>
class Tree {
    using NP = Node*;
    using T = typename Node::key_type;

    NP root {nil};
    // nil sentinel
    static NP nil;

    // core utilities
    const static NP get_nil() {
        return nil;
    }
};

enum class Color : char {BLACK = 0, RED = 1};

template <typename T>
struct Basic_node {
        using key_type = T;
        T key;
        Basic_node *parent, *left, *right;
        Color color;
        Basic_node() : color{Color::BLACK} {}   // sentinel construction
        Basic_node(T val, Color col = Color::RED) : 
            key{val}, 
            parent{Tree<Basic_node>::get_nil()}, 
            left{Tree<Basic_node>::get_nil()}, 
            right{Tree<Basic_node>::get_nil()}, 
            color{col} {}
};

template <typename T>
using Basic_tree = Tree<Basic_node<T>>;

template <typename T>
typename Basic_tree<T>::NP Basic_tree<T>::nil {new Basic_node<T>};
// alternatively
template <typename T>
Basic_node<T>* Basic_tree<T>::nil {new Basic_node{}};

エラー template definition of non-template 'typename sal::Basic_tree<T>::NP sal::Tree<sal::Basic_node<T> >::nil' は最後の 2 行で発生します。

Basic_nodeすべてのT タイプを使用するすべてのツリーに同じ nil を使用したいと考えています。

ノードの静的メンバーとしての Nil

次に、 nil を の静的メンバーにしようとしましたBasic_node。この方法では、ノードはツリーに依存せず (これparent{Tree<Basic_node>::get_nil()}は非常に厄介です)、より自然になります。

template <typename T>
struct Basic_node {
        static Basic_node* nil;

        using key_type = T;
        T key;
        Basic_node *parent, *left, *right;
        Color color;
        Basic_node() : color{Color::BLACK} {}   // sentinel construction
        Basic_node(T val, Color col = Color::RED) : key{val}, parent{nil}, left{nil}, right{nil}, color{col} {}
};
template <typename T>
Basic_node<T>* Basic_node<T>::nil {new Basic_node{}};

// inside Tree
using Node::nil;

新しいエラーは、私が階層を参照していると想定しているため、type 'sal::Basic_node<int>' is not a base type for type 'sal::Tree<sal::Basic_node<int> >'悪用していることを意味しています。usingここで言いたいのは、Tree の残りの部分でNode::nil参照するときに使用することです。nil

(私の最後のアプローチが機能したことに注意してください。毎回 Node::nil を参照する必要があるだけです。また、Node::nil によって導入された余分な間接性があるかどうかも知りたいです)。

4

0 に答える 0