在链表中实现中性元素

Question

我做了一个双向二维链表。我的节点称为 chunks，它们包含指向其左侧、右侧、底部和顶部的 chunks 的指针。

class chunk;
typedef std::shared_ptr<chunk> chunk_ptr;
typedef std::weak_ptr<chunk> chunk_wptr;

class chunk
{
public:
    chunk(wanted_id) : id(wanted_id) {}

    chunk_ptr left() const { return _left.lock(); }
    chunk_ptr right() const { return _right.lock(); }
    chunk_ptr top() const { return _top.lock(); }
    chunk_ptr bottom() const { return _bottom.lock(); }

    void left(const chunk_ptr set) { _left = set; }
    void right(const chunk_ptr set) { _right = set; }
    void top(const chunk_ptr set) { _top = set; }
    void bottom(const chunk_ptr set) { _bottom = set; }

    int id() const { return _id; }

private:
    chunk_wptr _left, _right, _top, _bottom;
    int _id;
    void id(const int id) { _id = id; }
};

现在，假设我构建了以下结构：

如果我想从 1 导航到 4，我可以使用以下代码行：

id4 = id1->right()->right()->bottom();

现在假设块 3 已被删除，例如id2->right == id4->top == nullptr:

如果我想访问id4然后对其执行一些操作，将会出现运行时间错误。为了避免在每一步都执行检查，我想引入一个中性的块元素：

auto null_chunk = std::make_shared<chunk>(-1); // Let's define its id as -1
null_chunk->left(null_chunk);
null_chunk->right(null_chunk);
null_chunk->top(null_chunk);
null_chunk->bottom(null_chunk);

因此，下面的语句会运行成功：

id4 = id1->right()->right()->bottom();

然后是id4 == null_chunk.

但是，我不太确定如何在我的代码中集成这样的元素。

我可以使用静态变量:

// This is a public static method
chunk_ptr chunk::null_chunk()
{
    static auto ptr = instanciate_null_chunk();
    return ptr;
}
// This is a private static method
chunk_ptr chunk::instanciate_null_chunk()
{
    auto ptr = std::make_shared<chunk>(-1);
    ptr->left(ptr);
    ptr->right(ptr);
    ptr->top(ptr);
    ptr->bottom(ptr);
    return ptr;
}

现在，我想在我的构造函数中通过 null_chunk 初始化左、右、上和下：

chunk(wanted_id) : id(wanted_id) 
{
    this->left(null_chunk());
    this->right(null_chunk());
    this->top(null_chunk());
    this->bottom(null_chunk());
}

这会导致递归堆栈溢出（null_chunk 调用构造函数调用 null_chunk 等...）。

这迫使我为 null_chunk() 定义一个特定的私有构造函数，但是因为我使用的是共享指针，我的构造函数必须是 public 才能使用 make_shared...

于是就有了设计流程。 实现此类功能的最佳方式是什么？

Answer 1

实现空节点的一种可能解决方案是使用静态成员。此成员使用另一个静态函数初始化一次，该函数使用空块创建共享指针并将所有传出连接重定向到块本身。

在构建任何其他块时，所有传出连接也指向空块。

如上评论所述，请确保不要因循环引用而泄漏任何内存。

您必须像您提到的那样创建第二个构造函数。但是，使用私有结构作为参数可防止从 class.

外部调用此构造函数

class chunk { 
public: 
  using chunk_ptr = std::shared_ptr<chunk>; 
  using chunk_wptr = std::weak_ptr<chunk>;

private:
  int _id; 
  chunk_wptr _left, _right, _top, _bottom; 
  static chunk_ptr nullchunk;
  struct pctor {};

  static chunk_ptr gennull() {
    chunk_ptr pnullchunk {std::make_shared<chunk>(pctor{})};
    pnullchunk->_left = pnullchunk;
    pnullchunk->_right = pnullchunk;
    pnullchunk->_top = pnullchunk;
    pnullchunk->_bottom = pnullchunk;
    return pnullchunk;
  }

public:
  chunk(pctor) : _id(-1) {}
  chunk(int id) :   _id(id), 
                    _left(chunk::nullchunk),
                    _right(chunk::nullchunk),
                    _top(chunk::nullchunk),
                    _bottom(chunk::nullchunk) {}

  bool isNullNode() const 
  { return this == chunk::nullchunk.get(); } 

  //
  // Further functions omitted
  //
}; 

chunk::chunk_ptr chunk::nullchunk {chunk::gennull()};

在链表中实现中性元素

Implement a neutral element in a linked list

c++

null

linked-list

shared-ptr