在没有 const cast 的情况下在链表中实现 advance 方法

Question

我正在制作一个相当简单的链表版本，它可以通过 Link class 访问。这里的目标是制作一个 advance() 方法，用于遍历列表。但是，我拥有的最轻量级解决方案涉及使用 const_cast ，这是不受欢迎的。有没有我没有考虑过的解决方案？

Link* Link::advance(int n) const
{
    if(!this) return nullptr;

    Link* it = const_cast<Link*>(this);
    if(n > 0) {
        while(n--) {
            it = it->next(); //the next link in the list
        }
    }
    else if(n < 0) {
        while(n++) {
            it = it->previous(); //the previous link in the list
        }
    }
    return it;
}

Answer 1

这比看起来更像是一个语义问题。

通过签名：Link* Link::advance(int n) const

这意味着给定您的 linked 列表的节点实例，您希望它提供对其前面或后面的兄弟节点之一的访问。

有趣的部分如下：一个节点不拥有它的兄弟。

它们都存在于同一级别。鉴于来自不同其他节点实例的 next 和 previous 指针同时指向同一节点，这一点更加明显。

你的节点之所以可以提供对它不拥有的其他节点的访问，是因为他有一个 link 到它们的非 const 实例（一个 next和一个 previous 指针）。这是唯一的原因。这与当前节点实例本身无关，因此证明 advance 成员函数的 const 是合理的。

现在唯一真正的问题来自于一个节点没有 link 自身的事实，因此不能像它可以提供对其兄弟之一的访问一样提供对自身的访问。

有两种方法可以基于此采取行动：

1) 要么改变这种情况的基本事实，即改变 Link* Link::advance(int n) const，有多种方法可以做到这一点，例如删除 const、添加迭代器概念和其他方法，返回 const 个实例等。每个实例采用不同的接近角度。

2) 或者你继续走这条路，这意味着你自己也需要有一个 link 才能完全尊重你赋予函数的语义：

class Link
{
public:
  Link()
    :
    previous_(nullptr),
    current_(this),
    next_(nullptr)
  {}

  // ...

  Link* advance(int n) const;

  // ...

  Link* previous() const { return previous_; }
  Link* next() const { return next_; }

  // ...

private:
  Link *previous_;
  Link * const current_;
  Link *next_;
};

Link* Link::advance(int n) const
{
  //if(!this) return nullptr;

  Link* it = current_;
  if(n > 0) {
    while(n--) {
      it = it->next(); //the next link in the list
    }
  }
  else if(n < 0) {
    while(n++) {
      it = it->previous(); //the previous link in the list
    }
  }
  return it;
}

在没有 const cast 的情况下在链表中实现 advance 方法

Implement an advance method in a linked list without const cast

c++

linked-list

this

const-cast