【头歌Educoder】国防科大 模板与 STL

第1关：初识模板函数

任务目的

本关目的：编写你的第一个模板函数。

编程要求

本题的要求为：编写模板函数

template <typename T, int n> int getIndex (T a[], T x)

返回长度为 n 的数组 a 中 x 第一个出现的位置（下标）—— 若 x 在 a 中没有出现，则返回 -1。

测试说明

请在代码的 /******* begin ******/ 和 /******* end ******/ 之间完成getIndex函数。平台会对你编写的代码进行测试。例如：若

char ac[] = {'x', 'u', 'v', 'x'};

则调用

getIndex<char, 4>(ac, 'u')

的返回值为1。
开始你的任务吧，祝你成功！

#include <iostream> using namespace std; template <typename T, int n> int getIndex(T a[], T x){ /******* begin ******/ for(int i=0;i<n;i++){ if(a[i]==x){ return i; } } /******* end ******/ return -1; } void output(){ char ac[] = {'x', 'u', 'v', 'x'}; int ai[] = {35, 12, 26, 11, 38}; bool ab[] = {0, 1, 0, 0}; int id; cin >>id; switch (id){ case 0: char c; cin >>c; cout << getIndex<char,4>(ac, c)<<endl; break; case 1: int i; cin >> i; cout << getIndex<int, 5>(ai, i) <<endl; break; case 2: bool b; cin >> b; cout << getIndex<bool, 4>(ab, b) <<endl; break; default: cout << -1<<endl; break; } } int main(int argc, char** argv){ output(); return 0; }

---

第2关：模板化 output() 函数

任务描述

本关任务：将上一步的 output() 函数模板化。

在上一个关卡中的文件里，函数

void output(){ char ac[] = {'x', 'u', 'v', 'x'}; int ai[] = {35, 12, 26, 11, 38}; bool ab[] = {0, 1, 0, 0}; int id; cin >>id; switch (id){ case 0: char c; cin >>c; cout << getIndex<char,4>(ac, c)<<endl; break; case 1: int i; cin >> i; cout << getIndex<int, 5>(ai, i) <<endl; break; case 2: bool b; cin >> b; cout << getIndex<bool, 4>(ab, b) <<endl; break; default: cout << -1<<endl; break; } }

用于根据情况对 getIndex 进行调用。然而，这个函数不具备任何灵活性，并且包含了非常多的“冗余”成分。

任务目标：将上述函数改造为模板化的版本

template <typename T, int n=N> void output();

其中，N 是预定义的常量。请在/***** begin ***/ 与 /**** end *****/ 之间补全代码，实现对getIndex() 函数的调用。

注意事项

假设测试用例中 T 只会例化为基本数据类型（如 int、char、bool）等。

开始你的任务吧，祝你成功！

#include <iostream> using namespace std; #define N 10 template <typename T, int n> int getIndex(T a[], T x){ for(int i=0; i<n; i++) if (a[i] == x) return i; return -1; } template <typename T, int n=N> void output(){ T aT[N]; for(int i=0; i<n; i++) cin >>aT[i]; T x; cin >> x; /***** begin ***/ cout << getIndex<T, n>(aT, x) << endl; /**** end *****/ } int main(int argc, char** argv){ output<int>(); return 0; }

---

第3关：模板化 Stack 类

任务描述

本关任务：将 Stack 类模板化。

相关知识

在前面单元的实训关卡中，我们曾经实现过堆栈（Stack）类，其声明如下

class Stack{ public: Stack(); Stack (unsigned int); Stack (const Stack&); ~Stack(); public: bool pop(); // 弹栈操作 bool push(int); // 压栈操作 int readTop() const; // 读栈顶元素 bool isEmpty() const; // 判断栈是否为空 private: int * data; // 存储栈数据的数组 unsigned int top; // 栈顶元素下标 unsigned int size; // 栈的最大容量 public: static unsigned int objNum; static unsigned int defSize; } ;

但是，这个 Stack 类只能以整数为元素。现在，我们需要对其进行“模板化”，让它支持任意的数据类型。

注意事项

请在 /****** header begin *****/ 与 /****** header end *******/ 之间书写 Stack<T> 的类定义；在 /****** body begin ******/ 和 /****** body end *******/ 之间书写其对应的方法实现。

开始你的任务吧，祝你成功！

#include <iostream> using namespace std; /****** header begin *****/ template <typename T> class Stack { public: Stack(); Stack(unsigned int); Stack(const Stack<T>&); ~Stack(); public: bool pop(); // 弹栈操作 bool push(T); // 压栈操作 T readTop() const; // 读栈顶元素 bool isEmpty() const; // 判断栈是否为空 private: T * data; // 存储栈数据的数组 unsigned int top; // 栈顶元素下标 (指向下一个可用位置) unsigned int size; // 栈的最大容量 public: static unsigned int objNum; static unsigned int defSize; }; /****** header end *******/ template<typename T> unsigned int Stack<T>::objNum = 0; template<typename T> unsigned int Stack<T>::defSize = 20; /****** body begin ******/ template <typename T> Stack<T>::Stack() { size = defSize; data = new T[size]; top = 0; objNum++; } template <typename T> Stack<T>::Stack(unsigned int s) { size = s; data = new T[size]; top = 0; objNum++; } template <typename T> Stack<T>::Stack(const Stack<T>& other) { size = other.size; data = new T[size]; top = other.top; for (unsigned int i = 0; i < top; i++) { data[i] = other.data[i]; } objNum++; } template <typename T> Stack<T>::~Stack() { delete[] data; objNum--; } template <typename T> bool Stack<T>::pop() { if (isEmpty()) { return false; // 栈为空，弹栈失败 } top--; return true; } template <typename T> bool Stack<T>::push(T val) { if (top >= size) { return false; // 栈已满，压栈失败 } data[top] = val; top++; return true; } template <typename T> T Stack<T>::readTop() const { // 假设调用时栈不为空，返回栈顶元素 return data[top - 1]; } template <typename T> bool Stack<T>::isEmpty() const { return top == 0; } /****** body end *******/ int main(int argc, char** argv){ Stack<int> s; for(int i=0; i<5; i++){ int n; cin >> n; s.push(n); } for(int i=0; i<5; i++){ cout<<s.readTop()<<endl; s.pop(); } return 0; }

---

第4关：模板化 DynArray 类

任务描述

本关任务：将 DynArray 类模板化。

问题回顾

在之前单元的实训中，曾经将动态数组（DynArray）类改进至如下形式

class DynArray { friend ostream & operator<<(ostream &, const DynArray &); public: DynArray(); virtual ~DynArray(); protected: struct ArrayEle { int val; ArrayEle* next; }; private: ArrayEle * m_head; ArrayEle * m_tail; ArrayEle * position(int) const; public: int count() const; void add(int); void insert(int, int); void remove(int); int & operator[](int); int operator[](int) const; void clear(); };

这个版本的DynArray已经非常完备了，但唯一的缺憾是只能封装以整数为元素的数组。现在，需要对其进行模板提升，使其可以支持任意的元素类型。

相关知识

这个改造还是据有一定难度的。它的类声明是这样的：

template <typename T> class DynArray { public: DynArray(); virtual ~DynArray(); protected: struct ArrayEle { T val; ArrayEle * next; }; private: ArrayEle* m_head; ArrayEle* m_tail; ArrayEle* position(int) const; public: int count() const; void add(const T &); void insert(int, const T &); void remove(int); void clear(); T& operator[](int); T operator[](int) const; };

如大家见到的那样，我们并没有将 operator << 作为友元函数置于类声明中。
这是一个非常复杂的问题 —— 建议大家查阅关于模板类与友元的相关知识，这里不做过多介绍 —— 如果一定要将其声明为友元函数，那么建议将该函数的定义写在类声明的内部，以保证编译通过。

这里，有一个需要大家特别注意的地方：实现 DynArray<T>::position(int) const 方法时，其正确的语法是什么呢？嗯，有些复杂，其函数定义为

template <typename T> typename DynArray<T>::ArrayEle* DynArray<T>::position(int pos) const { ... }

因为我们需要显式的告诉编译器：DynArray<T>::ArrayEle 一定是一个嵌套类的名字。

你的任务

给出DynArray<T>所有方法（请在/******** begin **********/和/******** end **********/之间完成）以及

template <typename T> ostream & operator<<(ostream & os, const DynArray<T> & arr)

函数的实现（请在两个/****************************/之间完成）
—— operator<< 的要求同前：将动态数组的全部元素置于 [ 和 ] 之间输出，且元素之间用 ; 分隔。

开始你的任务吧，祝你成功！

#include <iostream> using namespace std; template <typename T> class DynArray { public: DynArray(); virtual ~DynArray(); protected: struct ArrayEle { T val; ArrayEle * next; }; private: ArrayEle* m_head; ArrayEle* m_tail; ArrayEle* position(int) const; public: int count() const; void add(const T &); void insert(int, const T &); void remove(int); void clear(); T& operator[](int); T operator[](int) const; }; /******** begin **********/ template <typename T> DynArray<T>::DynArray() : m_head(nullptr), m_tail(nullptr) {} // 析构函数：清空内存 template <typename T> DynArray<T>::~DynArray() { clear(); } // 定位函数：返回指定位置的节点指针（核心：嵌套类型必须加typename） template <typename T> typename DynArray<T>::ArrayEle* DynArray<T>::position(int pos) const { // 位置非法返回空 if (pos < 0 || pos >= count()) { return nullptr; } ArrayEle* p = m_head; // 遍历到目标位置 for (int i = 0; i < pos; ++i) { p = p->next; } return p; } // 统计元素个数 template <typename T> int DynArray<T>::count() const { int num = 0; ArrayEle* p = m_head; while (p != nullptr) { num++; p = p->next; } return num; } // 尾部添加元素 template <typename T> void DynArray<T>::add(const T &value) { // 创建新节点 ArrayEle* newNode = new ArrayEle; newNode->val = value; newNode->next = nullptr; // 空链表：头尾都指向新节点 if (m_head == nullptr) { m_head = newNode; m_tail = newNode; } else { // 非空：尾节点后追加，更新尾指针 m_tail->next = newNode; m_tail = newNode; } } // 指定位置插入元素 template <typename T> void DynArray<T>::insert(int pos, const T &value) { int total = count(); // 位置非法直接返回 if (pos < 0 || pos > total) { return; } ArrayEle* newNode = new ArrayEle; newNode->val = value; // 插入头部 if (pos == 0) { newNode->next = m_head; m_head = newNode; // 原链表为空，同步更新尾指针 if (total == 0) { m_tail = newNode; } } else { // 找到前驱节点 ArrayEle* pre = position(pos - 1); newNode->next = pre->next; pre->next = newNode; // 插入尾部，更新尾指针 if (pos == total) { m_tail = newNode; } } } // 删除指定位置元素 template <typename T> void DynArray<T>::remove(int pos) { int total = count(); // 位置非法直接返回 if (pos < 0 || pos >= total) { return; } ArrayEle* delNode = nullptr; // 删除头节点 if (pos == 0) { delNode = m_head; m_head = m_head->next; // 只剩一个节点，清空尾指针 if (total == 1) { m_tail = nullptr; } } else { // 找到前驱节点 ArrayEle* pre = position(pos - 1); delNode = pre->next; pre->next = delNode->next; // 删除尾节点，更新尾指针 if (pos == total - 1) { m_tail = pre; } } // 释放内存 delete delNode; } // 清空所有元素 template <typename T> void DynArray<T>::clear() { ArrayEle* p = m_head; while (p != nullptr) { ArrayEle* temp = p; p = p->next; delete temp; } // 头尾指针置空 m_head = nullptr; m_tail = nullptr; } // 非const下标运算符：返回引用，支持修改 template <typename T> T& DynArray<T>::operator[](int pos) { return position(pos)->val; } // const下标运算符：返回值，只读 template <typename T> T DynArray<T>::operator[](int pos) const { return position(pos)->val; } /******** end **********/ template <typename T> ostream & operator<<(ostream & os, const DynArray<T> & arr){ /****************************/ os << "["; int len = arr.count(); for (int i = 0; i < len; ++i) { if (i != 0) { os << ";"; } os << arr[i]; } os << "]"; /****************************/ } int main(int argc, char** argv){ int v; DynArray<int> da; for(int i=0; i<6; i++){ cin >> v; da.add(v); } cin >> v; da.insert(2,v); da.remove(3); cout <<da<<endl; return 0; }

---

第5关：模板的特化与偏特化

任务描述

本关任务：掌握模板的特化与偏特化。

相关知识

“凡事都有特例”，程序设计中的普遍规律。对于某些模板类，存在“过于宽泛”的问题 —— 某些方法针对一般模板参数（如T）的实现，未必适用于某些特定的参数类型。

考虑下面的例子：假设有按照如下方式声明的类

template<typename T> class Spec{ private: T value; public: Spec(const T &); ~Spec(); public: bool operator==(const Spec&) const; };

它对算符 == 进行了重载 —— 只有两个 Spec<T> 对象的 value 成员相同时，才返回真（1）。然而，这对于T为char*的情况是不适用的，因为我们希望当两个Spec<char*> 对象的value指向字符串内容相同时即返回真（而无需要求value对应的地址相同）。

此时，需要对 Spec<T> 类进行特化，即对 Spec<char*> 进行特殊处理。特化时，需要按如下方式进行类声明

template<> // 取消模板参数 class Spec<char*>{ private: char* value; public: Spec(char *); ~Spec(); public: bool operator==(const Spec<char*>&); };

接下来，你需要实现Spec<char*>类的各个方法（请在/**********begin ********/ 和 /********** end ********/之间完成）。

此外，模板参数还存在“偏特化”（也成为“部分特化”）的概念。偏特化分为两种情况：

• 第一，类模板中含有多个类型参数，将某些类型参数固定为特定类型；
• 第二，将类模板中的类型参数限制为某种特定形式，如指针等。 关于模板类的偏特化问题，感兴趣的同学可以进一步查阅相关资料。

开始你的任务吧，祝你成功！

#include <iostream> using namespace std; template<typename T> class Spec{ private: T value; public: Spec(const T &); ~Spec(); public: bool operator==(const Spec&) const; }; template<typename T> Spec<T>::Spec(const T & t){ this->value = t; } template<typename T> Spec<T>::~Spec(){ } template<typename T> bool Spec<T>::operator== (const Spec& s) const { return this->value == s.value; } #include<string.h> template<> class Spec<char*>{ private: char* value; public: Spec(char *); ~Spec(); public: bool operator==(const Spec<char*>&); }; /**********begin ********/ Spec<char*>::Spec(char * str) { value = new char[strlen(str) + 1]; strcpy(value, str); } Spec<char*>::~Spec() { delete[] value; } bool Spec<char*>::operator==(const Spec<char*>& s) { return strcmp(value, s.value) == 0; } /********** end ********/ #define LEN 10 int main(int argc, char** argv) { int u, v; cin >> u; cin>>v; Spec<int> spec1(u); Spec<int> spec2(v); char s[LEN]; char t[LEN]; cin >> s; cin>>t; Spec<char*> s1(s); Spec<char*>s2(t); cout << (spec1 == spec2)<<endl; cout <<(s1==s2)<<endl; return 0; }

---

第6关：STL 中的容器与迭代器

任务描述

本关任务：掌握 STL 中若干标准容器和迭代器的使用。

相关知识

STL（标准模板库）是 C++ 源码中重要组成部分。它包括一系列模板化的容器（container）、迭代器（iterator）、算法（algorithm）等组件。本关主要关注前两方面。

总体来说，STL 中的容器可以分为两大类型 —— 序列式容器与关联式容器。
序列式容器的元素中存在一个线性序，该线性序由元素插入的顺序决定；
关联式容器的每个元素通过特定的key对其进行索引。STL中的容器主要包括如下几种类型：

• vector（头文件为<vector>），序列式容器，逻辑上表示一个大小可变的数组，支持元素的随机访问与动态增删；
• list（相应头文件为 <list>），序列式容器，也是一个可变长数组，但是其插入/删除元素的操作效率较高，随机访问的效率反而低一些；
• deque（声明于<deque>头文件中），序列式容器，它的逻辑结构与前面两个容器一样，但它却结合了二者的优点；
• set/multiset（头文件为<set>），关联式容器，逻辑结构为一个集合，其中 multiset 允许元素的重复；
• map/multimap（头文件为 <map>），关联式容器，为“名-值（key-value）对”的集合，其中 multimap 允许 key 重复。

事实上，序列式容器可以看作以连续整数值（下表）为 key 的 map，而 set 可以看作 元素的 key 和 value 相同的 map。
除了上述标准容器，还存在如下类型的“适配器”：

• stack（定义于 <stack>中），先进后出的序列式容器，是堆栈的逻辑实现；
• queue/priority_queue（定义于<queue>中），先进先出的序列式容器，表示队列，其中 priority_queue 可以自定义优先级。

标准容器存在一些通用的操作，如元素的插入与删除、元素的查找与遍历等。一般，
采用与容器类型兼容的迭代器对其中元素进行遍历。如 vector<T>::iterator 就是
vector<T>类对应的迭代器类型。在 STL 中，可以使用容器的

begin() end() rbegin() rend()

四个成员函数获得指向起始、结尾、逆向起始、逆向结尾处的迭代器。在 C++17 之后的标准中，上述四个方法被提升为 std 名字空间的函数，将其作用在容器上，可直接获得相应的迭代器。

迭代器都重载了 * 或者 -> 算符，因此可以当作指针使用。比如下面的代码就可完成 vector 容器的遍历

vector<int> vec; ... for(vector<int>::iterator it = vec.begin(); it !=vec.end(); it++) { cout <<*it<<endl; }

或者在支持 C++17 标准及以上的编译器中，可简化为

for(auto it = std::begin(vec); it!=std::end(vec); it++){ cout <<*it<<endl; }

对于 map 的迭代器，可以用 ->first 和 ->second 指向序偶的 key 与 value。

事实上，还可以避开迭代器，进一步简化为

for(auto i: vec) // 或 for(int i: vec) cout << i <<endl;

具体任务

今天的任务比较简单：计算一个二元关系的对称闭包。
在数学上，一个二元关系是一个二元序偶的集合，而在 C++ 中，专门为序偶设置了
pair 和 tuple 容器。比如

pair<int, char>(3,'a'); pair<int, int>(3,5);

就构造了两个匿名的二元偶，也可以用make_pair这个泛型函数构造二元偶。

如果 R 是一个二元关系，则其对称闭包 s(R) 定义为

其余的，我想就不需要作额外介绍了。
请在 /****************** begin *******************/和/****************** end *******************/之间补全代码。

开始你的任务吧，祝你成功！

#include <iostream> #include <map> #include <set> using namespace std; template <typename T> set<pair<T,T>> sym_closure(const set<pair<T, T>> & s){ /****************** begin *******************/ set<pair<T, T>> res; for (const auto& p : s) { res.insert(p); } for (const auto& p : s) { res.insert({p.second, p.first}); } return res; /****************** end *******************/ } template<typename T> void output(const set<pair<int, int>> & s){ for(auto p: s){ cout <<"("<<p.first<<","<<p.second<<")"<<endl; } } int main(int argc, char** argv){ int n; set<pair<int, int>> r; for(cin>>n; n; n--){ int u, v; cin >> u >> v; r.insert(make_pair(u,v)); } auto sr = sym_closure(r); output<pair<int,int>>(sr); return 0; }

---

第7关：STL 算法与函数对象

任务目的

本关目的：掌握 STL 的算法与函数对象

相关知识

STL 中，除包含了若干模板化的容器、迭代器、适配器等，还内置了若干通用模板算法—— 使用这些算法时需要引入头文件 <algorithm>。下面罗列了一些常用算法：

• accumulate()，返回某范围内元素之和，这些元素对应的类必须重载 + 算符；
• copy()，对元素进行复制
• count()，对某范围内元素进行统计，返回其数目；
• count_if()，是 count 的带条件版本，返回某些元素中满足特定条件的数目；
• find()，在特定范围内对元素进行查找；
• find_if()，是 find() 的带条件版本，只在特定范围内满足特定条件的元素中进行查找；
• binary_search()，顾名思义，二分查找；
• sort()，对某范围内的元素进行排序；
• ...

在上面的介绍中，多次提到“某范围”三个字，具体是什么呢？答案就是：大部分 STL算法的前两个参数都是两个（相同类型的）迭代器，这个“范围”就由这两个迭代器确定。

看下面这个例子：

vector<int v> = {12, 34, 22, 18, 6}; sort(v.begin(), v.end()); for(int i=0; i<5; i++) cout<<v[i]<<endl;

则其依次输出 6、12、18、22、34 —— 我们发现，在缺省的情况下，它会按照“从小到大”的顺序对v中的元素进行排序。大家可能会有这样的问题：

1. 如果需要将 v 中的元素按照“从大到小”的顺序派列，应当如何做？
2. 更一般的情况，假设 v 中的元素不是整数，无法比较大小，那 sort() 的结果是什么样的呢？

这两个都是非常好的问题 —— 它引出了我们下面一个知识点。事实上， sort() 的一般形式形如

sort(iter_beg, iter_end, pred)

这第三个参数 pred 可以视为一个“二元谓词”—— sort(begin(v), end(v), pred) 调用完成后，会使得 pred(v[i],v[i+1]) 均成立。

那么，这个 pred 是什么呢？它一般是一个“函数对象”（functional object）—— 一个函数对象就是某个重载了 ()（函数调用）算子的对象。比如，如果有下面的类声明

template<typename T> class Comparator{ public: bool operator() (const T& ,const T&); };

那么每个 Comparator 类的实例都可以看作是一个（二元）函数对象 —— 换言之，每个 Comparator 的实例都可以充当前面的 pred 参数。

任务描述

完善 Comparator 类，使得将 Comparator<double> 的对象作为 sort() 的第三个参数传入时，能够将容器（假设模板参数为double）中的元素按绝对值从大到小排序。
请在 /**************begin***********/ 和 /**************end***********/（两处）之间完成代码。

开始你的任务吧，祝你成功！

#include<iostream> #include <vector> #include<algorithm> #include <cmath> using namespace std; template <typename T> class Comparator { /**************begin***********/ public: bool operator () (const T& a, const T& b){ return fabs(a)>fabs(b); } /**************end***********/ }; int main(int argc, char** argv){ vector<double> vd; int n; // number of elements of vd; for(cin >> n; n; n--){ double d; cin >> d; vd.push_back(d); } /**************begin***********/ // sort vd here sort(vd.begin(), vd.end(), Comparator<double>()); /**************end***********/ for(double d: vd) cout << d << endl; return 0; }