c++ - 是否可以组合对称代码段？

Question

我正在为我的学校项目实现 avl 树，发现自己为对称情况编写了两次几乎相同的代码。例如，此函数执行两个节点的旋转以平衡树。 if 子句处理低节点是高节点的左子节点的情况，else 子句处理相反的情况:

void avl<T>::rotate(node<T> *x, node<T> *y)
{
  if (x == y->l)
  {
    x->p = y->p;
    if (y->p != nullptr)
      if(y->p->l == y)
        y->p->l = x;
      else
        y->p->r = x;
    else
      this->setHead(x);
    y->p = x;
    y->l = x->r;
    if(x->r != nullptr)
      x->r->p = y;
    x->r = y;
    y->dl = y->calcd('l');
    x->dr = x->calcd('r');
    if(x->p != nullptr)
      if(x->p->l == x)
        x->p->dl = x->p->calcd('l');
      else
        x->p->dr = x->p->calcd('r');
  }
  else
  {
    x->p = y->p;
    if (y->p != nullptr)
      if(y->p->r == y)
        y->p->r = x;
      else
        y->p->l = x;
    else
      this->setHead(x);
    y->p = x;
    y->r = x->l;
    if(x->l != nullptr)
      x->l->p = y;
    x->l = y;
    y->dl = y->calcd('l');
    x->dr = x->calcd('r');
    if(x->p != nullptr)
      if(x->p->r == x)
        x->p->dr = x->p->calcd('r');
      else
        x->p->dl = x->p->calcd('l');

  }
}

如您所见，else 子句与交换了“l”和“r”的 if 子句完全相似。有没有办法将它们结合起来。我可以做些什么来改进它？我的代码中是否存在设计错误？

Answer 1

使用指向成员的指针。这两个分支之间的唯一区别是您访问的是哪个成员，因此这是将其抽象出来的简单方法:

using Child = node<T> node<T>::*;

void rotate_impl(node<T>* x, node<T>* y, Child* left, Child* right)
{
    x->p = y->p;
    if (y->p != nullptr) {
      if(y->p->*left == y) {
        y->p->*left = x;
      }
      else {
        y->p->*right = x;
      }
    }
    else {
      this->setHead(x);
    }

    y->p = x;
    y->*left = x->*right;

    if(x->*right != nullptr) {
      (x->*right)->p = y;
    }

    x->*right = y;
    y->dl = y->calcd('l');
    x->dr = x->calcd('r');
    if(x->p != nullptr) {
      if(x->p->*left == x) {
        x->p->dl = x->p->calcd('l');
      }
      else {
        x->p->dr = x->p->calcd('r');
      }
   }
}

void avl<T>::rotate(node<T> *x, node<T> *y)
{
  if (x == y->l) {
    rotate_impl(x, y, &node<T>::l, &node<T>::r);
  }
  else {
    rotate_impl(x, y, &node<T>::r, &node<T>::l);
  }
}

我还冒昧地在您的代码中添加了大括号。你可以稍后再感谢我。