第2章 类模板 Stack 的实现

2.1 类模板 Stack 的实现 (Implementation of Class Template Stack)

正如函数模板，类模板可以在一个头文件中声明和定义。以下是一个简单的 Stack 类模板的实现示例：

// basics/stack1.hpp#include <vector>
#include <cassert>template <typename T>
class Stack {
private:std::vector<T> elems;  // 元素存储在向量中public:void push(T const& elem);  // 压入元素void pop();  // 弹出元素T const& top() const;  // 返回栈顶元素bool empty() const {  // 检查栈是否为空return elems.empty();}
};template <typename T>
void Stack<T>::push(T const& elem) {elems.push_back(elem);  // 将元素添加到向量末尾
}template <typename T>
void Stack<T>::pop() {assert(!elems.empty());elems.pop_back();  // 移除向量中的最后一个元素
}template <typename T>
T const& Stack<T>::top() const {assert(!elems.empty());return elems.back();  // 返回向量中的最后一个元素
}

该类模板使用C++标准库中的 std::vector 来管理元素，从而避免了手动处理内存管理和拷贝控制等复杂问题，使我们可以专注于类模板接口的设计。

2.1.1 声明类模板 (Declaration of Class Templates)

声明类模板与声明函数模板类似：在声明之前，必须声明一个或多个类型参数的标识符。常见的标识符是 T：

template <typename T>
class Stack {...
};

关键字 typename 也可以用 class 替代：

template <class T>
class Stack {...
};

在类模板中，T 可以像其他任何类型一样用于声明成员变量和成员函数。在这个例子中，T 被用于声明一个 std::vector<T> 成员变量 elems，并在成员函数 push() 中作为参数类型，在 top() 函数中作为返回类型。

template <typename T>
class Stack {
private:std::vector<T> elems;  // 元素public:void push(T const& elem);  // 压入元素void pop();  // 弹出元素T const& top() const;  // 返回栈顶元素bool empty() const {  // 检查栈是否为空return elems.empty();}
};

在类模板内部，直接使用类名（如 Stack）表示带有当前模板参数的类。例如，如果需要声明构造函数和赋值运算符，通常会这样写：

template <typename T>
class Stack {...Stack(Stack const&);  // 拷贝构造函数Stack& operator=(Stack const&);  // 赋值运算符
};

这与显式指定模板参数的形式等价：

template <typename T>
class Stack {...Stack(Stack<T> const&);  // 拷贝构造函数Stack<T>& operator=(Stack<T> const&);  // 赋值运算符
};

但在类模板内部，第一种形式更为简洁且常用。

然而，在类模板外部定义成员函数时，必须明确指定模板参数：

template <typename T>
bool operator==(Stack<T> const& lhs, Stack<T> const& rhs);

在需要类名而不是具体类型的地方，可以直接使用 Stack。特别是在构造函数和析构函数名称的情况下。

与非模板类不同，类模板不能在函数内部或块作用域内声明。它们通常只能定义在全局作用域、命名空间作用域或类声明内。

2.1.2 成员函数实现 (Implementation of Member Functions)

定义类模板的成员函数时，必须指定这是一个模板，并且必须使用类模板的完整类型限定。例如，Stack 类的 push() 成员函数的实现如下：

template <typename T>
void Stack<T>::push(T const& elem) {elems.push_back(elem);  // 将元素添加到向量末尾
}

在这种情况下，elems 是一个 std::vector<T> 对象，push_back() 方法将元素添加到向量的末尾。

需要注意的是，std::vector 的 pop_back() 方法移除最后一个元素但不返回它，这是为了保证异常安全性。完全异常安全的 pop() 版本无法同时返回被移除的元素。然而，如果我们忽略这一限制，可以实现一个返回被移除元素的 pop() 函数：

template <typename T>
T Stack<T>::pop() {assert(!elems.empty());T elem = elems.back();  // 保存最后一个元素elems.pop_back();  // 移除最后一个元素return elem;  // 返回保存的元素
}

由于 back() 和 pop_back() 在空向量上调用会导致未定义行为，因此需要检查栈是否为空。如果为空，则触发断言，因为在空栈上调用 pop() 是错误的。同样的检查也适用于 top() 函数，它返回栈顶元素但不移除它：

template <typename T>
T const& Stack<T>::top() const {assert(!elems.empty());return elems.back();  // 返回最后一个元素
}

当然，对于任何成员函数，也可以在类声明中以内联方式实现：

template <typename T>
class Stack {...void push(T const& elem) {elems.push_back(elem);  // 将元素添加到向量末尾}
};

通过这种方式，我们可以在类声明中直接实现简单的成员函数，从而使代码更加紧凑和易读。

2.2 使用类模板 Stack

在C++17之前，使用类模板时必须显式指定模板实参。以下是一个展示如何使用 Stack<> 类模板的示例：

// basics/stack1test.cpp#include "stack1.hpp"
#include <iostream>
#include <string>int main() {// 创建一个 int 类型的栈Stack<int> intStack;// 创建一个 std::string 类型的栈Stack<std::string> stringStack;// 操作 int 类型的栈intStack.push(7);std::cout << intStack.top() << '\n';  // 输出: 7// 操作 std::string 类型的栈stringStack.push("hello");std::cout << stringStack.top() << '\n';  // 输出: hellostringStack.pop();
}

通过声明 Stack<int>，我们将 int 类型作为类模板中 T 的类型参数。因此，intStack 是一个使用 std::vector<int> 存储元素的对象。任何被调用的成员函数将根据该类型进行实例化。

类似地，通过声明 Stack<std::string>，我们创建了一个使用 std::vector<std::string> 存储元素的对象。任何被调用的成员函数也将根据该类型进行实例化。

关键点：

• 实例化时机：只有当成员函数被实际调用时，它们才会被实例化。这不仅节省了编译时间和空间，还允许类模板的部分使用。

• 实例化示例：在这个例子中，int 类型和 std::string 类型的默认构造函数、push() 函数和 top() 函数都将被实例化。然而，pop() 函数仅对 std::string 类型进行了实例化。如果类模板有静态成员，这些静态成员也只会在特定类型的实例化过程中被实例化一次。

实例化后的类模板类型可以像其他类型一样使用，可以用 const 或 volatile 进行限定，或者基于它衍生出数组和引用。也可以将其作为 typedef 或 using 进行类型定义的一部分（更多类型定义的内容详见第2.8节），或者在构建其他模板类型时作为类型参数。例如：

void foo(Stack<int> const& s) {  // 参数 s 是 int 类型的 Stackusing IntStack = Stack<int>;  // IntStack 是 Stack<int> 的别名Stack<int> istack[10];        // istack 是长度为 10 的 Stack<int> 数组IntStack istack2[10];         // istack2 也是长度为 10 的 Stack<int> 数组
}Stack<float*> floatPtrStack;      // float 指针的 Stack
Stack<Stack<int>> intStackStack;  // int 类型的 Stack 的 Stack

模板实参可以是任何类型，唯一的要求是任何被调用的操作对该类型都是可行的。

需要注意的是，在C++11之前，必须在两个闭合模板括号之间放置空格，以避免语法错误。例如：

Stack<Stack<int> > intStackStack;  // 在 C++11 之前的正确写法

如果不这样做而使用符号 >>，会导致语法错误：

Stack<Stack<int>> intStackStack;  // 在 C++11 之前会引发错误

旧版本的这种行为的原因是为了帮助C++编译器在词法分析阶段将源代码分割成独立的语义片段（tokenize the source code）。然而，由于缺少空格是个常见的bug，C++11移除了“在两个闭合模板括号中间必须加入空格”的规则，这一改变被称为“角括号hack”。

脚注

C++17引入了类模板实参推断（Class Template Argument Deduction, CTAD），使得在某些情况下可以跳过显式指定模板实参，只要可以从构造函数推断出模板实参。这将在第2.9节中详细讨论。

---

改进后的叙述总结

在C++17之前，使用类模板时需要显式指定模板实参。以下是使用 Stack<> 类模板的一个示例：

#include "stack1.hpp"
#include <iostream>
#include <string>int main() {// 创建 int 类型的栈Stack<int> intStack;// 创建 std::string 类型的栈Stack<std::string> stringStack;// 操作 int 类型的栈intStack.push(7);std::cout << intStack.top() << '\n';  // 输出: 7// 操作 std::string 类型的栈stringStack.push("hello");std::cout << stringStack.top() << '\n';  // 输出: hellostringStack.pop();
}

通过声明 Stack<int> 和 Stack<std::string>，我们分别创建了存储 int 和 std::string 类型元素的栈。只有在调用成员函数时，这些函数才会根据具体类型进行实例化。

实例化后的类模板类型可以像其他类型一样使用，可以通过 const 或 volatile 进行限定，或者基于它衍生出数组和引用。也可以将其作为 typedef 或 using 进行类型定义的一部分，或者在构建其他模板类型时作为类型参数。例如：

void foo(Stack<int> const& s) {  // 参数 s 是 int 类型的 Stackusing IntStack = Stack<int>;  // IntStack 是 Stack<int> 的别名Stack<int> istack[10];        // istack 是长度为 10 的 Stack<int> 数组IntStack istack2[10];         // istack2 也是长度为 10 的 Stack<int> 数组
}Stack<float*> floatPtrStack;      // float 指针的 Stack
Stack<Stack<int>> intStackStack;  // int 类型的 Stack 的 Stack

在C++11之前，必须在两个闭合模板括号之间放置空格，以避免语法错误：

Stack<Stack<int> > intStackStack;  // 在 C++11 之前的正确写法

不这样做会导致语法错误：

Stack<Stack<int>> intStackStack;  // 在 C++11 之前会引发错误

旧版本的这种行为的原因是为了帮助C++编译器在第一轮中将源代码分成独立语义的片段。然而，由于缺少空格是个典型的bug，C++11移除了“在两个闭合模板括号中间必须加入空格”的规则，称为“角括号hack”。

脚注

C++17引入了类模板实参推断（CTAD），使得可以跳过指定模板实参，只要可以从构造函数推断出模板实参。这将在第2.9节中详细讨论。

2.3 类模板的局部使用 (Partial Usage of Class Templates)

类模板并不强制要求模板实参提供所有可能的操作，而只需要提供必要的操作。以下是一个具体的示例，展示了这一点：

假设 Stack<> 类模板提供了一个成员函数 printOn()，用于打印整个栈的内容，并对每个元素调用 operator<<：

template <typename T>
class Stack {...void printOn(std::ostream& strm) const {for (T const& elem : elems) {strm << elem << ' ';  // 每个元素调用 operator<<}}
};

尽管如此，你依然可以使用没有定义 operator<< 的类作为该类模板的模板实参：

Stack<std::pair<int, int>> ps;  // 注意：std::pair<> 没有定义 operator<<
ps.push({4, 5});  // OK
ps.push({6, 7});  // OK
std::cout << ps.top().first << '\n';  // OK
std::cout << ps.top().second << '\n';  // OK

只有当调用这样的栈的 printOn() 方法时，代码才会生成错误，因为它不能实例化对该特殊类型的 operator<< 的调用：

ps.printOn(std::cout);  // ERROR: 元素类型不支持 operator<<

2.3.1 Concepts

为了明确哪些操作是模板实例化所需要的，术语 概念（Concept） 被用来指示约束条件的集合，并在模板库中重复使用。例如，C++ 标准库依赖于随机访问迭代器（random access iterator）和默认构造（default constructible）等概念。

截至 C++17，concepts 主要通过文档或代码注释进行表述。这可能导致未遵循约束条件时产生混乱的错误消息（详见第9.4节）。

自 C++11 起，可以通过使用 static_assert 关键字和预定义的类型特性来检查基本的约束条件，例如：

template <typename T>
class C {static_assert(std::is_default_constructible<T>::value, "Class C requires default-constructible elements");...
};

没有该断言，如果需要默认构造函数，编译依然会失败，但错误信息可能包含整个模板实例化的历史，从开始实例化到真实的模板定义（详见第9.4节）。

对于更复杂的约束条件，如类型 T 的对象是否提供某种特定的成员函数或是否可以使用 < 操作符进行比较，则需要更详细的检查。详见第19.6.3节的一个详细代码示例。

参考附件E关于更多的有关C++ Concept的讨论

---

改进后的叙述总结

2.3 类模板的局部使用

类模板不需要模板实参提供所有可能的操作，而只需提供必要的操作。例如：

template <typename T>
class Stack {...void printOn(std::ostream& strm) const {for (T const& elem : elems) {strm << elem << ' ';  // 每个元素调用 operator<<}}
};Stack<std::pair<int, int>> ps;  // std::pair<> 没有定义 operator<<
ps.push({4, 5});  // OK
ps.push({6, 7});  // OK
std::cout << ps.top().first << '\n';  // OK
std::cout << ps.top().second << '\n';  // OK// 仅在调用 printOn() 时会报错
ps.printOn(std::cout);  // ERROR: 元素类型不支持 operator<<

2.3.1 Concepts

概念（Concept） 是一组约束条件，用于确保模板实参满足特定要求。例如，C++ 标准库依赖于诸如随机访问迭代器和默认构造等概念。

截至 C++17，这些概念主要通过文档或代码注释描述。自 C++11 起，可以使用 static_assert 和类型特性来检查基本约束条件：

template <typename T>
class C {static_assert(std::is_default_constructible<T>::value, "Class C requires default-constructible elements");...
};

对于更复杂的约束条件，如特定成员函数的存在或 < 操作符的支持，需进一步的检查方法。详见第19.6.3节的详细代码示例。

2.4 友元 (Friends)

除了使用 printOn() 方法来打印栈的内容，使用操作符 << 将是更好的选择。然而，通常操作符 << 都实现为非成员函数，这可以通过内联方式调用 printOn() 方法：

template <typename T>
class Stack {...void printOn(std::ostream& strm) const { ... }friend std::ostream& operator<< (std::ostream& strm, Stack<T> const& s) {s.printOn(strm);return strm;}
};

注意，这意味着类 Stack<> 的操作符 << 不是一个函数模板，而是在必要时由类模板实例化的一个普通函数。

然而，当尝试声明友元函数并在之后定义时，事情会变得复杂。我们有两种主要的选择：

选项1：隐式地定义一个新的函数模板

这需要使用一个不同的模板参数，比如 U：

template <typename T>
class Stack {...template <typename U>friend class std::ostream& operator<< (std::ostream&, Stack<U> const&);
};

无论再次使用 T 还是跳过模板参数声明都无法工作（无论是内层 T 屏蔽外层 T 还是在命名空间范围内声明非模板参数）。

选项2：前向声明 Stack<T> 的输出操作为模板

这需要先进行 Stack<T> 的前向声明：

template <typename T>
class Stack;template <typename T>
std::ostream& operator<< (std::ostream&, Stack<T> const&);template <typename T>
class Stack {...friend std::ostream& operator<< <T> (std::ostream&, Stack<T> const&);
};

注意“函数名”即 << 操作后面的 <T>。因此，我们声明了一个非成员函数模板的特化版本作为友元。没有 <T>，我们将声明一个新的非模板函数，详见第12.5.2节。

在任何情形下，依然可以使用没有定义 << 操作的类作为成员。只有调用该 Stack 的 << 操作才会引发错误：

Stack<std::pair<int, int>> ps;  // std::pair<> 没有定义 << 操作
ps.push({4, 5});  // OK
ps.push({6, 7});  // OK
std::cout << ps.top().first << '\n';  // OK
std::cout << ps.top().second << '\n';  // OK
std::cout << ps << '\n';  // 错误： 元素类型不支持 << 操作

改进后的叙述总结

2.4 友元 (Friends)

为了更好地打印栈的内容，使用操作符 << 是一个更好的选择。通常情况下，操作符 << 实现为非成员函数，并通过内联方式调用 printOn() 方法：

template <typename T>
class Stack {...void printOn(std::ostream& strm) const { ... }friend std::ostream& operator<< (std::ostream& strm, Stack<T> const& s) {s.printOn(strm);return strm;}
};

需要注意的是，这里的 operator<< 不是一个函数模板，而是由类模板实例化生成的一个普通函数。

然而，在声明和定义友元函数时可能会遇到一些复杂性。以下是两种处理方法：

选项1：隐式定义新的函数模板

这种方式需要引入一个新的模板参数，例如 U：

template <typename T>
class Stack {...template <typename U>friend class std::ostream& operator<< (std::ostream&, Stack<U> const&);
};

这种方法存在一些问题，例如重新使用 T 或跳过模板参数声明都会导致编译错误。

选项2：前向声明输出操作符为模板

首先进行 Stack<T> 的前向声明：

template <typename T>
class Stack;template <typename T>
std::ostream& operator<< (std::ostream&, Stack<T> const&);template <typename T>
class Stack {...friend std::ostream& operator<< <T> (std::ostream&, Stack<T> const&);
};

注意在 operator<< 后面加上 <T>，这表明我们声明的是一个非成员函数模板的特化版本作为友元。如果省略 <T>，则会声明一个新的非模板函数，详见第12.5.2节。

即使如此，你仍然可以使用没有定义 << 操作的类作为成员。只有在调用 Stack 的 << 操作时才会引发错误：

Stack<std::pair<int, int>> ps;  // std::pair<> 没有定义 << 操作
ps.push({4, 5});  // OK
ps.push({6, 7});  // OK
std::cout << ps.top().first << '\n';  // OK
std::cout << ps.top().second << '\n';  // OK
std::cout << ps << '\n';  // 错误： 元素类型不支持 << 操作

脚注

这是个模板化实体（templated entity），详见第12.1节。