C++基类自引用指针如何适配派生类？以伸展树可翻转节点实现为例

核心解决方案：使用CRTP（奇异递归模板模式）改造基类 #

通过将派生类类型作为模板参数传递给基类，让基类在编译期感知实际节点类型，直接使用派生类指针，完全消除强制类型转换，且无任何运行时额外开销。

1. 改造节点基类

template <typename Derived>
struct node {
  Derived *f, *c[2];
  int size;
  node() {
    f = c[0] = c[1] = nullptr;
    size = 1;
  }
  void push_down() {}
  void update() {
    size = 1;
    for (int t = 0; t < 2; ++t)
      if (c[t]) size += c[t]->size;
  }
};

2. 改造可翻转派生节点

struct reversable_node : node<reversable_node> {
  int r;
  reversable_node() : node() { r = 0; }
  void push_down() {
    if (r) {
      std::swap(c[0], c[1]);
      // 补全空指针判断，避免访问空指针成员
      if (c[0]) c[0]->r ^= 1;
      if (c[1]) c[1]->r ^= 1;
      r = 0;
    }
  }
};
// 普通无翻转节点定义示例
struct plain_node : node<plain_node> {};

3. 改造树模板

修正原代码中的笔误与潜在空指针问题，将所有节点指针替换为模板参数对应的实际节点类型：

template <typename T = plain_node, int MAXSIZE = 500000>
struct tree {
  T pool[MAXSIZE + 2];
  T *root;
  int size;
  tree() {
    size = 2;
    root = &pool[0], root->c[1] = &pool[1], root->size = 2;
    pool[1].f = root;
  }
  void rotate(T *n) {
    int v = n->f->c[0] == n;
    T *p = n->f, *m = n->c[v];
    p->push_down(), n->push_down();
    n->c[v] = p, p->f = n, p->c[v ^ 1] = m;
    if (m) m->f = p;
    p->update(), n->update();
  }
  void splay(T *n, T *s = nullptr) {
    while (n->f != s) {
      T *m = n->f, *l = m->f;
      if (l == s)
        rotate(n);
      else if ((l->c[0] == m) == (m->c[0] == n))
        rotate(m), rotate(n);
      else
        rotate(n), rotate(n);
    }
    if (!s) root = n;
  }
  T *new_node() { return &pool[size++]; }
  void walk(T *n, int &v, int &pos) {
    n->push_down();
    int s = n->c[0] ? n->c[0]->size : 0;
    v = pos < s;
    if (!v) pos -= s + 1;
  }
  void add_node(T *n, int pos) {
    T *c = root;
    int v;
    ++pos;
    do {
      walk(c, v, pos);
    } while (c->c[v] && (c = c->c[v]));
    // 修正原代码中未定义的cur变量
    c->c[v] = n, n->f = c, splay(n);
  }
  T *find(int pos, bool splay_flag = true) {
    T *c = root;
    int v;
    ++pos;
    while (true) {
      walk(c, v, pos);
      if (pos == 0 || !c->c[v]) break;
      c = c->c[v];
    }
    if (splay_flag) splay(c);
    return c;
  }
  T *find_range(int posl, int posr) {
    T *l = find(posl - 1), *r = find(posr, false);
    splay(r, l);
    if (r->c[0]) r->c[0]->push_down();
    return r->c[0];
  }
};

方案优势

• 完全消除了丑陋的强制类型转换，所有类型检查在编译期完成，无运行时开销
• 兼容原有用例，几乎不需要修改上层调用代码，find_range等接口直接返回对应节点类型指针，无需额外转换
• 修复了原代码中空指针访问、未定义变量等潜在问题

内容的提问来源于stack exchange，提问作者zhtluo