林和小站
Essay Theory TechMisc CodingTrick
林和小站

Contents

C++ Policy Based Design

   3895 words   8 minutes 

策略模式（Strategy Pattern）允许我们使用统一的策略接口来抽象一些行为，利用不同的策略来表示相似但不同的操作，并通过切换策略来方便地切换对象的行为。一般而言这种模式都是运行时的，通过多态的接口来实现。此外，C++ 还支持一种基于策略的设计（Policy Based Design/Policy Based Class）来通过指定策略来在编译器控制或切换类的定义。严格来说这二者没有明确的边界。

这篇文章讲讲 policy based design 方面的技巧。本文出现的例子都是我胡诌的，是因为我不想在写笔记时照抄别人的例子，同时也给自己一次练手的机会。

策略设计的实现方案

基于组合的策略设计

利用组合与委托来实现策略设计，可以写出这样一个简单的例子。

template <class MessagePolicy, class OutputPolicy>
class Greeter {
 public:
  void Greet() { out_d_.WriteLine(msg_d_.Message()); }

 private:
  // 2 delegates.
  MessagePolicy msg_d_;
  OutputPolicy out_d_;
};

class EnglishMessagePolicy {
 public:
  std::string Message() { return "Hello world!"; }
};

class ChineseMessagePolicy {
 public:
  std::string Message() { return u8"你好世界！"; }
};

class StdoutPolicy {
 public:
  template <class T>
  void WriteLine(T&& msg) {
    std::cout << msg << std::endl;
  }
};

int main() {
  auto ga = Greeter<EnglishMessagePolicy, StdoutPolicy>();
  auto gb = Greeter<ChineseMessagePolicy, StdoutPolicy>();
  ga.Greet();
  gb.Greet();
  return 0;
}

上面这种写法，和普通的运行时的策略模式的边界非常模糊。只需要在 Greeter 构造函数处传入委托，然后把所有的 Policy 类都做成多态类，就变成了运行时分发的策略模式。换言之，基于对象实例的策略设计，很容易从编译期分派改造为运行时分派。有些时候，运行时的策略选择是不可避免的，比方说要在上面的代码中再加一个写文件的 OutPolicy，目标文件名运行时指定，那么就必须使用运行时的分派了。

C++ 空类也占一个字节，从而保证不同对象的地址不同，可以通过指针字面值判断对象是否是同一个。上面的例子是基于组合的写法，存储了一个策略实例在类内部，虽然每个委托都是空类，但是需要额外占用一个字节，因此 ga 和 gb 的 size 都是 2。这样，每使用一个策略，就浪费了一个字节。如果策略类完全是空类，也可以把方法写成静态方法，然后直接通过类名调用，这样倒是也可以省下这几个字节，不过失去了很多灵活性。更好的方案是下面的这个例子。

基于继承的策略设计

虽然我们常常说组合优于继承，但是在这个场景下可能反了过来。由于 C++ 规定了 空基类优化（EBO），所以当基类是空类时，并不占用额外的一个字节。

template <class MessagePolicy, class OutputPolicy>
class Greeter : private MessagePolicy, private OutputPolicy {
 public:
  void Greet() { WriteLine(Message()); }

 private:
  using MessagePolicy::Message;
  using OutputPolicy::WriteLine;
};

class EnglishMessagePolicy {
 protected:
  std::string Message() { return "Hello world!"; }
};

class ChineseMessagePolicy {
 protected:
  std::string Message() { return u8"你好世界！"; }
};

class StdoutPolicy {
 protected:
  template <class T>
  void WriteLine(T&& msg) {
    std::cout << msg << std::endl;
  }
};

int main() {
  auto ga = Greeter<EnglishMessagePolicy, StdoutPolicy>();
  auto gb = Greeter<ChineseMessagePolicy, StdoutPolicy>();
  ga.Greet();
  gb.Greet();
  return 0;
}

这种写法，可以省下空基类的一个字节，达到零开销的抽象。

接下来，作为例子，我们使用基于策略的设计实现一个有界环形缓冲区。在后文中，我们都使用基于继承的实现方案。

不带策略的简单实现

从 Circular buffer - Wikipedia 抄一个实现，简单改改，变成模板版本的。

// naive.cc

#include <iostream>
#include <stdexcept>

template <typename T>
class CircularBuffer {
 public:
  CircularBuffer(size_t capacity)
      : begin_(0),
        end_(0),
        cap_(capacity + 1),
        buf_(reinterpret_cast<T*>(new char[sizeof(T) * (capacity + 1)])) {}

  ~CircularBuffer() {
    if (buf_) delete[] buf_;
  }

  // allow move
  CircularBuffer(CircularBuffer&& other) { *this = other; }
  CircularBuffer& operator=(CircularBuffer&& other) {
    begin_ = other.begin_;
    end_ = other.end_;
    cap_ = other.cap_;
    buf_ = other.cap_;
    other.begin_ = other.end_ = other.cap_ = 0;
    other.buf_ = nullptr;
    return *this;
  }
  // disable copy
  CircularBuffer(const CircularBuffer&& other) = delete;
  CircularBuffer& operator=(const CircularBuffer& other) = delete;

  void Push(T item) {
    size_t next = Next(end_);
    if (next == begin_) {
      throw std::out_of_range("buffer overflow!");
    }
    buf_[end_] = std::move(item);
    end_ = next;
  }

  void Pop(T& item) {
    if (begin_ == end_) {
      throw std::out_of_range("buffer underflow!");
    }
    item = std::move(buf_[begin_]);
    begin_ = Next(begin_);
  }

 private:
  size_t Next(size_t cur) {
    size_t n = cur + 1;
    if (n >= cap_) n -= cap_;
    return n;
  }

  size_t begin_;
  size_t end_;
  size_t cap_;
  T* buf_;
};

int main() {
  int n = 10;
  auto buf = CircularBuffer<int>(n);
  for (int i = 0; i < n; ++i) {
    std::cout << "pushing " << i << std::endl;
    buf.Push(i);
  }
  try {
    buf.Push(0);
  } catch (const std::out_of_range& e) {
    std::cout << e.what() << std::endl;
  };
  int value;
  for (int i = 0; i < n; ++i) {
    buf.Pop(value);
    std::cout << value << (i < n - 1 ? ", " : "");
  }
  std::cout << std::endl;
  try {
    buf.Pop(value);
  } catch (const std::out_of_range& e) {
    std::cout << e.what() << std::endl;
  }
  return 0;
}

其中 Push 方法偷懒了，利用了传值来优化 move 语义。这种写法能消除使用 move 传参时的额外 copy，比只写 copy 版本性能要好，但是会比拆开写 copy/move 两个版本性能略差。更好的选择是利用完美转发，只写一个函数解决两种参数，详见 c++ - Advantages of pass-by-value and std::move over pass-by-reference - Stack Overflow。

接下来我们从简单到复杂，逐渐加上各种策略来控制派生类。

调试打印

现在我们想调试一下这个程序，我们给派生类添加模板参数 DebugPolicy。当需要调试时，替换这个策略的参数，就能在每次 Push/Pop 操作成功后打印相应的数值。再实现一个相同接口的类，每个函数都是空函数，这样在不需要调试时编译期会自动优化。给模板添加默认参数，使得默认情况下不会有调试输出。真棒！再也不用到处写 printf 然后再注释掉了！

// debug_print.cc

#include <iostream>
#include <stdexcept>

struct Debug {
  template <typename T>
  void OnPush(const T& value) {
    std::cout << "pushed " << value << std::endl;
  }

  template <typename T>
  void OnPop(const T& value) {
    std::cout << "popped " << value << std::endl;
  }
};

struct NoDebug {
  template <typename T>
  void OnPush(const T& value) {}

  template <typename T>
  void OnPop(const T& value) {}
};

template <typename T, typename DebugPolicy = NoDebug>
class CircularBuffer : private DebugPolicy {
 public:
  CircularBuffer(size_t capacity)
      : begin_(0),
        end_(0),
        cap_(capacity + 1),
        buf_(reinterpret_cast<T*>(new char[sizeof(T) * (capacity + 1)])) {}

  ~CircularBuffer() {
    if (buf_) delete[] buf_;
  }

  // allow move
  CircularBuffer(CircularBuffer&& other) { *this = other; }
  CircularBuffer& operator=(CircularBuffer&& other) {
    begin_ = other.begin_;
    end_ = other.end_;
    cap_ = other.cap_;
    buf_ = other.cap_;
    other.begin_ = other.end_ = other.cap_ = 0;
    other.buf_ = nullptr;
    return *this;
  }
  // disable copy
  CircularBuffer(const CircularBuffer&& other) = delete;
  CircularBuffer& operator=(const CircularBuffer& other) = delete;

  void Push(T item) {
    size_t next = Next(end_);
    if (next == begin_) {
      throw std::out_of_range("buffer overflow!");
    }
    buf_[end_] = std::move(item);
    DebugPolicy::OnPush(buf_[end_]);
    end_ = next;
  }

  void Pop(T& item) {
    if (begin_ == end_) {
      throw std::out_of_range("buffer underflow!");
    }
    item = std::move(buf_[begin_]);
    begin_ = Next(begin_);
    DebugPolicy::OnPop(item);
  }

 private:
  size_t Next(size_t cur) {
    size_t n = cur + 1;
    if (n >= cap_) n -= cap_;
    return n;
  }

  size_t begin_;
  size_t end_;
  size_t cap_;
  T* buf_;
};

int main() {
  int n = 10;
  // auto buf = CircularBuffer<int>(n);
  auto buf = CircularBuffer<int, Debug>(n);
  for (int i = 0; i < n; ++i) {
    buf.Push(i);
  }
  std::cout << std::endl;
  int value;
  for (int i = 0; i < n; ++i) {
    buf.Pop(value);
  }
  return 0;
}

如果在 CircularBuffer 的 private 域写上 using DebugPolicy::OnPush，上面的 DebugPolicy::OnPush 也可以简写成 OnPush。

更好的调试打印（友元）

上面的例子中，调试打印只是能打印操作数。如果我们希望打印更多的信息，例如当前缓冲区容量，就需要修改函数接口参数。每新增一个策略，就可能需要设计一个更抽象的接口。比起不断地修改函数参数，直接传递 this 指针给调试类，让它决定要访问哪些元素即可。由于涉及到私有成员的访问，所以需要声明友元。

// better_debug_print.cc

#include <iostream>
#include <stdexcept>

struct Debug {
  template <typename P>
  void OnPush(P self) {
    auto [occ, cap] = GetOccCap(self);
    size_t pos = self->end_ == 0 ? self->cap_ - 1 : self->end_ - 1;
    std::cout << "pushed " << self->buf_[pos] << " [" << occ << '/' << cap
              << ']' << std::endl;
  }

  template <typename P>
  void OnPop(P self) {
    auto [occ, cap] = GetOccCap(self);
    size_t pos = self->begin_ == 0 ? self->cap_ - 1 : self->begin_ - 1;
    std::cout << "popped " << self->buf_[pos] << " [" << occ << '/' << cap
              << ']' << std::endl;
  }

 private:
  template <typename P>
  std::pair<int, int> GetOccCap(P self) {
    size_t cap = self->cap_ - 1;
    size_t occ;
    if (self->begin_ <= self->end_) {
      occ = self->end_ - self->begin_;
    } else {
      occ = self->cap_ - self->end_ + self->begin_;
    }
    return {occ, cap};
  }
};

/* ... */

template <typename T, typename DebugPolicy = NoDebug>
class CircularBuffer : private DebugPolicy {
 public:
  /* ... */

  void Push(T item) {
    size_t next = Next(end_);
    if (next == begin_) {
      throw std::out_of_range("buffer overflow!");
    }
    buf_[end_] = std::move(item);
    end_ = next;
    DebugPolicy::OnPush(this);
  }

  void Pop(T& item) {
    if (begin_ == end_) {
      throw std::out_of_range("buffer underflow!");
    }
    item = std::move(buf_[begin_]);
    begin_ = Next(begin_);
    DebugPolicy::OnPop(this);
  }
  /* ... */
  friend DebugPolicy;
  /* ... */
};

/* ... */

这两个例子把策略类的成员函数设置成模板函数，避免了把策略类本身设置成模板。接下来我们看一个策略类本身就是模板的例子。

缓冲区越界行为（友元 + CRTP）

在我们默认的实现中，当缓冲区发生越界（上溢或下溢）时，程序直接抛出异常。有时候，我们想要在发上溢时自动丢弃最老的元素，实现一个自动滑动的缓冲区。那么我们可以使用策略来控制派生类的行为。

/* ... */

template <typename P>
struct OverflowPop {
  void OnOverflow() { static_cast<P*>(this)->Pop(); }
};

template <typename P>
struct OverflowException {
  void OnOverflow() {
    std::string msg = "no more space!";
    throw std::out_of_range(msg);
  }
};

template <typename T, template <typename> class OverflowPolicy = OverflowPop,
          typename DebugPolicy = NoDebug>
class CircularBuffer
    : private OverflowPolicy<CircularBuffer<T, OverflowPolicy, DebugPolicy>>,
      private DebugPolicy {
 public:
  /* ... */

  void Push(T item) {
    size_t next = Next(end_);
    if (next == begin_) {
      OverflowPolicy<CircularBuffer>::OnOverflow();
      next = Next(end_);
    }
    buf_[end_] = std::move(item);
    end_ = next;
    DebugPolicy::OnPush(this);
  }

 private:
  /* ... */
  friend OverflowPolicy<CircularBuffer>;
  /* ... */
};

int main() {
  int n = 3;
  // auto buf = CircularBuffer<int, OverflowException>(n);
  auto buf = CircularBuffer<int>(n);
  for (int i = 0; i < n + 2; ++i) {
    buf.Push(i);
  }
  int value;
  for (int i = 0; i < n; ++i) {
    value = buf.Pop();
    std::cout << "popped " << value << std::endl;
  }
  return 0;
}

这里由于需要在基类 OverflowPop 中把 this 指针转化为派生类型，所以需要在派生类中声明友元，否则编译器将报错：cannot cast to private base class。除了友元之外，还有两种方案也能让基类向派生类转型：

  1. 用 C 风格的类型转换，忽略 C++ static_cast 的限制 （但忽略限制容易不安全）
  2. 把 private 继承改成 public 继承 （但会导致派生类泄露不该暴露的接口 OnOverflow ） 更多的讨论见 C++ 继承修饰符

所以，友元就是最合适的方案。

类型别名

有时候我们希望控制内部数据结构抽象向外部的泄露。我们希望调用者使用时，只修改一部分策略，而固定另一部分策略。用上面的环形缓冲区的例子，我们希望固定缓冲区满之后弹出老元素，只允许使用者修改调试策略，那么可以利用类型别名。这样子只用向外部名空间暴露该适配器即可。

template <typename T, typename DebugPolicy = NoDebug>
using CircularBufferAdapter = CircularBuffer<T, OverflowPop, DebugPolicy>;

int main() {
  int n = 3;
  auto buf = CircularBufferAdapter<int, Debug>(n);
  for (int i = 0; i < n + 3; ++i) {
    buf.Push(i);
  }
  int value;
  for (int i = 0; i < n; ++i) {
    value = buf.Pop();
  }
  return 0;
}

类型导出与重绑定

为了方便使用各种 trait，最好是从派生类暴露模板参数的类型。这样在拿到一个类型（或实例）时，可以很方便地通过类内部的类型别名来获取模板参数信息。此外，还提供一个 rebind_type 接口，方便替换主类型 T。在我们这个例子中 rebind_type 看上去很平凡，因为它完全可以通过 overflow_policy 和 debug_policy 这几个类型别名拼凑出来。但是如果我们有更多的模板策略参数，比如说一个依赖主类型 T 的内存分配器策略 Allocator<T>，简单地拼凑暴露出来的类型别名，是难以重新组装一个新类型的。因此才需要 rebind_type 定义。这样可以让使用者无需深挖类的具体实现细节，就能替换主参数 T。

template <typename T, template <typename> class OverflowPolicy = OverflowPop,
          typename DebugPolicy = NoDebug>
class CircularBuffer
    : private OverflowPolicy<CircularBuffer<T, OverflowPolicy, DebugPolicy>>,
      private DebugPolicy {
 public:
  using value_type = T;
  using overflow_policy = OverflowPolicy<CircularBuffer>;
  using debug_policy = DebugPolicy;
  template <typename U>
  using rebind_type = CircularBuffer<U, OverflowPolicy, DebugPolicy>;
  /* ... */
};

int main() {
  int n = 10;
  auto buf = CircularBuffer<int>(n);
  using T = typename decltype(buf)::rebind_type<float>;
  return 0;
}

附录

继承修饰符

大多数资料都会 像这样 告诉你 C++ 的 public、protected 和 private 继承的含义。我一直也这样以为。直到我在写这篇文章的例子时，发现编译器报错 cannot cast to private base class，凭直觉修改 private 继承到 public 继承，竟然能解决？！后来我在 upcast with protected base unaccessible - C++ Forum (cplusplus.com) 查到了一个解释，大义是说 private 继承“隐藏”了继承关系，只有子类能看到继承关系而父类看不到，所以编译器处理不了。这样一来也说得通为什么声明了 friend 就能有用，因为父类能通过友元看到子类，那么这个继承关系就又“成立”了。这完全是我感性的理解，深刻的编译原理我是真的不懂啊 TAT

类型检查与 concept

如果我们想自定义策略类作为参数，传递进入类型模板。如果当我们的自定义策略类实现有错时（函数名 typo、缺某个接口定义、缺某个构造函数等等），编译器会报错。但因为模板参数被实际调用的位置可能已经和传入参数的位置相隔很远，实际上报错信息常常令人感到困惑，不知道该如何解决。因此，如果需要更完善的编译错误信息，一个很好的方案就是在传参后，class 定义的前几行，立刻检查模板参数是否符合约束。可以考虑这些方案：

SFINAE （Until C++17）

把 static_assert 和这两篇文章的内容结合起来：

concept （Since C++20）

Constraints and concepts (since C++20) - cppreference.com 本身就提供了这个能力，写一个 concept 来约束模板参数即可！

Updated on 2024-01-17
Back | Home