兵王小站

large picture of the cover

24. 泛型程序设计

引言

模板编程提供的几大功能：

  1. 传递类型参数：模板允许程序员传递类型作为参数，从而提高程序的通用性，使得代码可以适应不同类型的数据。
  2. 类型检查和推断：编译时进行类型检查，避免不同类型间的不兼容错误。
  3. 编译时多态：在编译期确定多态性，而不是在运行期，提高程序的执行效率。

模板的首要用途，也是它最常见的用途，是支持泛型程序设计（generic programming），即关注通用算法设计、实现和使用的程序设计。在这里，“通用”的含义是算法可以接受各种各样的实参类型，只要这些类型满足算法对实参的要求即可。模板是 C++​ 支持泛型程序设计的主要特性。它提供了（编译时）参数化多态。

更多地关注代码生成技术（将模板看作类型和函数的生成器），并依赖类型函数表示编译时计算的编程方式被称为模板元程序设计（template metaprogramming） 。

模板程序设计很像在用动态类型语言编程，但它并没有运行时开销，而且在动态类型语言中呈现为运行时异常的错误在 C++​ 中变成了编译时错误。

具体化概念

在 C++ 中，并没有直接的语言特性来表达概念（concept），需要通过编译期模板参数检查的方式实现。具体化概念在泛型编程中主要用于定义类型的约束条件。

  • 概念定义为一个谓词函数，返回 true​ 表示类型符合要求，返回 false​ 则表示不符合。
  • 利用 constexpr​ 和 static_assert​ 在编译期进行概念检查。

例如，为了确保字符串类 String​ 的字符类型满足 Ordered​ 概念，可以使用以下代码：

template<typename C>
class String {
    static_assert(Ordered<C>(), "String's character type is not ordered");
};

当实例化 String<X>​ 时，如果 Ordered<X>​ 为 true​，则编译成功；否则，会显示错误消息。谓词的定义如下：

template<typename T>
constexpr bool Ordered() {
    return Regular<T>() && Totally_ordered<T>();
}

template<typename T>
constexpr bool Totally_ordered() {
    return Equality_comparable<T>() // 有 == 和 !=
        && Has_less<T>() && Boolean<Less_result<T>>()
        && Has_greater<T>() && Boolean<Greater_result<T>>()
        && Has_less_equal<T>() && Boolean<Less_equal_result<T>>()
        && Has_greater_equal<T>() && Boolean<Greater_equal_result<T>>();
}

template<typename T>
constexpr bool Equality_comparable() {
    return Has_equal<T>() && Boolean<Equal_result<T>>()
        && Has_not_equal<T>() && Boolean<Not_equal_result<T>>();
}

template<typename T>
constexpr bool Regular() {
    return Semiregular<T>() && Equality_comparable<T>();
}

template<typename T>
constexpr bool Semiregular() {
    return Destructible<T>()
        && Default_constructible<T>()
        && Move_constructible<T>()
        && Move_assignable<T>()
        && Copy_constructible<T>()
        && Copy_assignable<T>();
}

此外，约束检查也可用在函数中：

template<typename C>
ostream& operator<<(ostream& out, String<C>& s) {
    static_assert(Streamable<C>(), "String's character not streamable");
    out << "\"";
    for (int i = 0; i != s.size(); ++i) out << s[i];
    out << "\"";
    return out;
}

template<typename T>
constexpr bool Streamable() {
    return Input_streamable<T>() && Output_streamable<T>();
}

公理

公理是一种我们认为正确但无法证明的特性，通常用于表示某些类型或算法的预期行为。

公理允许我们在定义模板时做出某些假设，这些假设不需要通过代码来验证，但假设的存在可以简化设计。

C++ 目前没有直接的语法支持公理，但可以通过代码或注释来表达这些假设。以下是一些关键的公理表达方式：

  1. Copy_equality 公理：用于表示赋值操作后的值相等性

    template<typename T>
bool Copy_equality(T x) {
    return T(x) == x;
}

  2. Copy_assign_equality 公理：表示拷贝赋值操作后两个对象的值相等

    template<typename T>
bool Copy_assign_equality(T x, T& y) {
    return (y = x) == x;
}

  3. Move_effect 公理：表示移动操作后生成的新值与源值相等，同时源值可以被销毁

    template<typename T>
bool Move_effect(T x, T& y) {
    return (x == y ? T(std::move(x)) == y : true) && can_destroy(y);
}

  4. Move_assign_effect 公理：表示移动赋值操作后新值相等，源值可销毁

    template<typename T>
bool Move_assign_effect(T x, T& y, T& z) {
    return (y == z ? (x = std::move(y), x == z) : true) && can_destroy(y);
}

这些公理定义了操作后的预期行为，尤其在赋值、拷贝和移动操作中，确保行为符合预期。虽然 C++ 无法直接验证这些公理，但它们对模板编程的正确性提供了理论支持。

多实参概念

当我们考虑一个单实参概念并应用于一个类型时，概念的作用看起来类似传统的类型检查。多实参概念扩展了这一思路，允许我们对多个类型参数之间的关系进行定义和约束。这在模板编程中非常重要，因为我们经常需要确保不同类型之间的关系，例如相等性和排序。

例如，考虑标准库中的 find()​ 算法，需要一个迭代器 Iter​ 和一个值类型 Val​。为了让 find()​ 正确工作，要求 Val​ 类型的值能够与迭代器指向的元素类型进行比较。

template<typename Iter, typename Val>
Iter find(Iter b, Iter e, Val x);

以下定义了一个双实参版本的 Equality_comparable​，用于检查两个类型之间是否可以相互比较：

template<typename A, typename B>
constexpr bool Equality_comparable(A a, B b)
{
    return Common<T, U>()
        && Totally_ordered<T>()
        && Totally_ordered<U>()
        && Totally_ordered<Common_type<T, U>>()
        && Has_less<T, U>() && Boolean<Less_result<T, U>>()
        && Has_less<U, T>() && Boolean<Less_result<U, T>>()
        && Has_greater<T, U>() && Boolean<Greater_result<T, U>>()
        && Has_greater<U, T>() && Boolean<Greater_result<U, T>>()
        && Has_less_equal<T, U>() && Boolean<Less_equal_result<T, U>>()
        && Has_less_equal<U, T>() && Boolean<Less_equal_result<U, T>>()
        && Has_greater_equal<T, U>() && Boolean<Greater_equal_result<T, U>>()
        && Has_greater_equal<U, T>() && Boolean<Greater_equal_result<U, T>>();
}

这段代码使用了各种布尔表达式来检查 A​ 和 B​ 是否具有通用类型，并且支持 <​、>​ 等比较运算符，确保两者可比较。

在确保了类型约束之后，可以安全地定义 find()​ 函数：

template<typename Iter, typename Val>
Iter find(Iter b, Iter e, Val x) {
    static_assert(Input_iterator<Iter>(), "find() requires an input iterator");
    static_assert(Equality_comparable<Value_type<Iter>, Val>(), 
                  "find()'s iterator and value arguments must match");

    while (b != e) {
        if (*b == x) return b;
        ++b;
    }
    return b;
}

值概念

概念可以对模板参数的值进行约束，而不仅仅局限于类型。

例如，定义了一个更复杂的值概念 Stackable​，用于检查一个对象是否可以适合在栈中：

constexpr int stack_limit = 2048;

template<typename T, int N>
constexpr bool Stackable() {
    return Regular<T>() && sizeof(T) * N <= stack_limit;
}
  • ​Stackable​ 概念对类型 T​ 和整数 N​ 进行约束，确保类型 T​ 是规则的类型（满足 Regular​ 概念）且 T​ 的总大小（sizeof(T) * N​）小于栈限制 stack_limit​。
  • ​stack_limit​ 是栈大小的限制，设定为 2048 字节。

使用 Stackable​ 概念来限制 Buffer​ 类模板实例化的条件：

template<typename T, int N>
struct Buffer {
    // 实现内容
};

template<typename T, int N>
void fct() {
    static_assert(Stackable<T, N>(), "fct() buffer won't fit on stack");
    Buffer<T, N> buf;
    // 其他实现
}

在 fct​ 函数中，static_assert​ 使用 Stackable​ 概念来检查 Buffer​ 的大小是否适合栈，如果不符合条件则会在编译期报错。

约束检查

约束检查并非 C++ 标准的一部分，而是用于泛型编程的一种约定，可以在单独命名空间（如 Estd​）中定义，以便在未来避免与标准库冲突。

这些约束反映了标准库的概念，可以帮助编译器检查类型是否满足模板的要求。

常见的迭代器约束

  • Input_iterator<X> ：类型 X​ 是一个输入迭代器，支持一次性遍历序列中的元素（前进 ++​），每个元素只读取一次。
  • Output_iterator<X> ：类型 X​ 是一个输出迭代器，支持一次性遍历序列中的元素（前进 ++​），每个元素只写入一次。
  • Forward_iterator<X> ：类型 X​ 是一个前向迭代器，支持多次遍历序列中的元素（前进 ++​）。
  • Bidirectional_iterator<X> ：类型 X​ 是一个双向迭代器，支持向前（++​）和向后（--​）遍历。
  • Random_access_iterator<X> ：类型 X​ 是一个随机访问迭代器，支持任意位置的访问操作（如 +​、-​）。

通用比较与排序约束

  • Equality_comparable<X, Y> ：类型 X​ 和 Y​ 可以使用 ==​ 和 !=​ 进行比较。
  • Totally_ordered<X, Y> ：类型 X​ 和 Y​ 满足完全排序关系，支持 <​、<=​、>​ 和 >=​。

通用类型行为约束

  • Semiregular<X> ：类型 X​ 可以被拷贝、默认构造，没有技术限制。
  • Regular<X> ：类型 X​ 是 Semiregular​ 且可以比较相等。
  • Ordered<X> ：类型 X​ 满足 Regular​ 且支持完全排序。
  • Assignable<X, Y> ：类型 X​ 可以被赋值为 Y​。
  • Predicate<F, X> ：函数对象 F​ 可接受 X​ 参数并返回 bool​ 值。
  • Streamable<X> ：类型 X​ 可以进行 I/O 操作，如使用 <<​ 和 >>​。

移动、拷贝与转换约束

  • Movable<X> ：类型 X​ 支持移动语义（移动构造函数和移动赋值操作）。
  • Copyable<X> ：类型 X​ 满足 Movable​ 且支持拷贝操作。
  • Convertible<X, Y> ：类型 X​ 可以隐式转换为类型 Y​。

其他常用约束

  • Common<X, Y> ：类型 X​ 和 Y​ 可以无损转换为一个公共类型 Common_type<X, Y>​。
  • Range<X> ：类型 X​ 支持范围操作，可用于范围 for​ 循环，要求 X​ 有 begin()​ 和 end()​ 成员函数或等价的非成员函数。

模板定义检查

约束检查只能确保类型满足指定的概念，但不能检测到实际使用中不正确的操作（即使用了概念中未检查的性质）。

template<typename Iter, typename Val>
Iter find(Iter b, Iter e, Val x) {
    static_assert(Input_iterator<Iter>(), "find(): Iter is not a Forward iterator");
    static_assert(Equality_comparable<Value_type<Iter>, Val>(), "find(): value type doesn't match iterator");

    while (b != e) {
        if (*b == x) return b;
        b = b + 1; // 注意：此处使用了 b + 1 而不是 ++b
    }
    return b;
}

这里存在一个错误：b + 1​ 操作仅对随机访问迭代器有效，而不是所有的前向迭代器。这种错误在约束检查中无法检测到。

模板实现不应使用概念未指定的实参性质，因此我们测试实现时使用的实参应该提供了概念所指定的属性，且只使用这类实参。这种类型有时被称为原型（archetype​）。

可以定义一个用于测试的类型 Forward​，其中实现了 find​ 函数所需的基本操作符：

template<typename Val>
struct Forward {
    Forward();
    Forward(const Forward&);
    Forward operator=(const Forward&);
    bool operator==(const Forward&) const;
    void operator++();
    Val& operator*();
};

这样可以用来测试模板定义的概念是否满足 find()​ 的要求：

Forward<int> p = find(Forward<int>{}, Forward<int>{}, 7);

此种测试不需要验证具体的操作逻辑，只需检查类型是否满足模板所需的概念属性。

‍

site logo

Hi,Friend

© 2025 兵王小站