【头歌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};则调用getIndexchar, 4(ac, u)的返回值为1。开始你的任务吧祝你成功#include iostream using namespace std; template typename T, int n int getIndex(T a[], T x){ /******* begin ******/ for(int i0;in;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 getIndexchar,4(ac, c)endl; break; case 1: int i; cin i; cout getIndexint, 5(ai, i) endl; break; case 2: bool b; cin b; cout getIndexbool, 4(ab, b) endl; break; default: cout -1endl; 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 getIndexchar,4(ac, c)endl; break; case 1: int i; cin i; cout getIndexint, 5(ai, i) endl; break; case 2: bool b; cin b; cout getIndexbool, 4(ab, b) endl; break; default: cout -1endl; break; } }用于根据情况对 getIndex 进行调用。然而这个函数不具备任何灵活性并且包含了非常多的“冗余”成分。任务目标将上述函数改造为模板化的版本template typename T, int nN 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 i0; in; i) if (a[i] x) return i; return -1; } template typename T, int nN void output(){ T aT[N]; for(int i0; in; i) cin aT[i]; T x; cin x; /***** begin ***/ cout getIndexT, n(aT, x) endl; /**** end *****/ } int main(int argc, char** argv){ outputint(); 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 *******/ 之间书写 StackT 的类定义在 /****** body begin ******/ 和 /****** body end *******/ 之间书写其对应的方法实现。开始你的任务吧祝你成功#include iostream using namespace std; /****** header begin *****/ template typename T class Stack { public: Stack(); Stack(unsigned int); Stack(const StackT); ~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 *******/ templatetypename T unsigned int StackT::objNum 0; templatetypename T unsigned int StackT::defSize 20; /****** body begin ******/ template typename T StackT::Stack() { size defSize; data new T[size]; top 0; objNum; } template typename T StackT::Stack(unsigned int s) { size s; data new T[size]; top 0; objNum; } template typename T StackT::Stack(const StackT 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 StackT::~Stack() { delete[] data; objNum--; } template typename T bool StackT::pop() { if (isEmpty()) { return false; // 栈为空弹栈失败 } top--; return true; } template typename T bool StackT::push(T val) { if (top size) { return false; // 栈已满压栈失败 } data[top] val; top; return true; } template typename T T StackT::readTop() const { // 假设调用时栈不为空返回栈顶元素 return data[top - 1]; } template typename T bool StackT::isEmpty() const { return top 0; } /****** body end *******/ int main(int argc, char** argv){ Stackint s; for(int i0; i5; i){ int n; cin n; s.push(n); } for(int i0; i5; i){ couts.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 作为友元函数置于类声明中。这是一个非常复杂的问题 —— 建议大家查阅关于模板类与友元的相关知识这里不做过多介绍 —— 如果一定要将其声明为友元函数那么建议将该函数的定义写在类声明的内部以保证编译通过。这里有一个需要大家特别注意的地方实现 DynArrayT::position(int) const 方法时其正确的语法是什么呢嗯有些复杂其函数定义为template typename T typename DynArrayT::ArrayEle* DynArrayT::position(int pos) const { ... }因为我们需要显式的告诉编译器DynArrayT::ArrayEle 一定是一个嵌套类的名字。你的任务给出DynArrayT所有方法请在/******** begin **********/和/******** end **********/之间完成以及template typename T ostream operator(ostream os, const DynArrayT 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 DynArrayT::DynArray() : m_head(nullptr), m_tail(nullptr) {} // 析构函数清空内存 template typename T DynArrayT::~DynArray() { clear(); } // 定位函数返回指定位置的节点指针核心嵌套类型必须加typename template typename T typename DynArrayT::ArrayEle* DynArrayT::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 DynArrayT::count() const { int num 0; ArrayEle* p m_head; while (p ! nullptr) { num; p p-next; } return num; } // 尾部添加元素 template typename T void DynArrayT::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 DynArrayT::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 DynArrayT::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 DynArrayT::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 DynArrayT::operator[](int pos) { return position(pos)-val; } // const下标运算符返回值只读 template typename T T DynArrayT::operator[](int pos) const { return position(pos)-val; } /******** end **********/ template typename T ostream operator(ostream os, const DynArrayT 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; DynArrayint da; for(int i0; i6; i){ cin v; da.add(v); } cin v; da.insert(2,v); da.remove(3); cout daendl; return 0; }第5关模板的特化与偏特化任务描述本关任务掌握模板的特化与偏特化。相关知识“凡事都有特例”程序设计中的普遍规律。对于某些模板类存在“过于宽泛”的问题 —— 某些方法针对一般模板参数如T的实现未必适用于某些特定的参数类型。考虑下面的例子假设有按照如下方式声明的类templatetypename T class Spec{ private: T value; public: Spec(const T ); ~Spec(); public: bool operator(const Spec) const; };它对算符 进行了重载 —— 只有两个 SpecT 对象的 value 成员相同时才返回真1。然而这对于T为char*的情况是不适用的因为我们希望当两个Specchar* 对象的value指向字符串内容相同时即返回真而无需要求value对应的地址相同。此时需要对 SpecT 类进行特化即对 Specchar* 进行特殊处理。特化时需要按如下方式进行类声明template // 取消模板参数 class Specchar*{ private: char* value; public: Spec(char *); ~Spec(); public: bool operator(const Specchar*); };接下来你需要实现Specchar*类的各个方法请在/**********begin ********/ 和 /********** end ********/之间完成。此外模板参数还存在“偏特化”也成为“部分特化”的概念。偏特化分为两种情况第一类模板中含有多个类型参数将某些类型参数固定为特定类型第二将类模板中的类型参数限制为某种特定形式如指针等。 关于模板类的偏特化问题感兴趣的同学可以进一步查阅相关资料。开始你的任务吧祝你成功#include iostream using namespace std; templatetypename T class Spec{ private: T value; public: Spec(const T ); ~Spec(); public: bool operator(const Spec) const; }; templatetypename T SpecT::Spec(const T t){ this-value t; } templatetypename T SpecT::~Spec(){ } templatetypename T bool SpecT::operator (const Spec s) const { return this-value s.value; } #includestring.h template class Specchar*{ private: char* value; public: Spec(char *); ~Spec(); public: bool operator(const Specchar*); }; /**********begin ********/ Specchar*::Spec(char * str) { value new char[strlen(str) 1]; strcpy(value, str); } Specchar*::~Spec() { delete[] value; } bool Specchar*::operator(const Specchar* s) { return strcmp(value, s.value) 0; } /********** end ********/ #define LEN 10 int main(int argc, char** argv) { int u, v; cin u; cinv; Specint spec1(u); Specint spec2(v); char s[LEN]; char t[LEN]; cin s; cint; Specchar* s1(s); Specchar*s2(t); cout (spec1 spec2)endl; cout (s1s2)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 可以自定义优先级。标准容器存在一些通用的操作如元素的插入与删除、元素的查找与遍历等。一般采用与容器类型兼容的迭代器对其中元素进行遍历。如 vectorT::iterator 就是vectorT类对应的迭代器类型。在 STL 中可以使用容器的begin() end() rbegin() rend()四个成员函数获得指向起始、结尾、逆向起始、逆向结尾处的迭代器。在 C17 之后的标准中上述四个方法被提升为 std 名字空间的函数将其作用在容器上可直接获得相应的迭代器。迭代器都重载了 * 或者 - 算符因此可以当作指针使用。比如下面的代码就可完成 vector 容器的遍历vectorint vec; ... for(vectorint::iterator it vec.begin(); it !vec.end(); it) { cout *itendl; }或者在支持 C17 标准及以上的编译器中可简化为for(auto it std::begin(vec); it!std::end(vec); it){ cout *itendl; }对于 map 的迭代器可以用 -first 和 -second 指向序偶的 key 与 value。事实上还可以避开迭代器进一步简化为for(auto i: vec) // 或 for(int i: vec) cout i endl;具体任务今天的任务比较简单计算一个二元关系的对称闭包。在数学上一个二元关系是一个二元序偶的集合而在 C 中专门为序偶设置了pair 和 tuple 容器。比如pairint, char(3,a); pairint, int(3,5);就构造了两个匿名的二元偶也可以用make_pair这个泛型函数构造二元偶。如果 R 是一个二元关系则其对称闭包 s(R) 定义为其余的我想就不需要作额外介绍了。请在 /****************** begin *******************/和/****************** end *******************/之间补全代码。开始你的任务吧祝你成功#include iostream #include map #include set using namespace std; template typename T setpairT,T sym_closure(const setpairT, T s){ /****************** begin *******************/ setpairT, T res; for (const auto p : s) { res.insert(p); } for (const auto p : s) { res.insert({p.second, p.first}); } return res; /****************** end *******************/ } templatetypename T void output(const setpairint, int s){ for(auto p: s){ cout (p.first,p.second)endl; } } int main(int argc, char** argv){ int n; setpairint, int r; for(cinn; n; n--){ int u, v; cin u v; r.insert(make_pair(u,v)); } auto sr sym_closure(r); outputpairint,int(sr); return 0; }第7关STL 算法与函数对象任务目的本关目的掌握 STL 的算法与函数对象相关知识STL 中除包含了若干模板化的容器、迭代器、适配器等还内置了若干通用模板算法—— 使用这些算法时需要引入头文件 algorithm。下面罗列了一些常用算法accumulate()返回某范围内元素之和这些元素对应的类必须重载 算符copy()对元素进行复制count()对某范围内元素进行统计返回其数目count_if()是 count 的带条件版本返回某些元素中满足特定条件的数目find()在特定范围内对元素进行查找find_if()是 find() 的带条件版本只在特定范围内满足特定条件的元素中进行查找binary_search()顾名思义二分查找sort()对某范围内的元素进行排序...在上面的介绍中多次提到“某范围”三个字具体是什么呢答案就是大部分 STL算法的前两个参数都是两个相同类型的迭代器这个“范围”就由这两个迭代器确定。看下面这个例子vectorint v {12, 34, 22, 18, 6}; sort(v.begin(), v.end()); for(int i0; i5; i) coutv[i]endl;则其依次输出 6、12、18、22、34 —— 我们发现在缺省的情况下它会按照“从小到大”的顺序对v中的元素进行排序。大家可能会有这样的问题如果需要将 v 中的元素按照“从大到小”的顺序派列应当如何做更一般的情况假设 v 中的元素不是整数无法比较大小那 sort() 的结果是什么样的呢这两个都是非常好的问题 —— 它引出了我们下面一个知识点。事实上 sort() 的一般形式形如sort(iter_beg, iter_end, pred)这第三个参数 pred 可以视为一个“二元谓词”—— sort(begin(v), end(v), pred) 调用完成后会使得 pred(v[i],v[i1]) 均成立。那么这个 pred 是什么呢它一般是一个“函数对象”functional object—— 一个函数对象就是某个重载了 ()函数调用算子的对象。比如如果有下面的类声明templatetypename T class Comparator{ public: bool operator() (const T ,const T); };那么每个 Comparator 类的实例都可以看作是一个二元函数对象 —— 换言之每个 Comparator 的实例都可以充当前面的 pred 参数。任务描述完善 Comparator 类使得将 Comparatordouble 的对象作为 sort() 的第三个参数传入时能够将容器假设模板参数为double中的元素按绝对值从大到小排序。请在 /**************begin***********/ 和 /**************end***********/两处之间完成代码。开始你的任务吧祝你成功#includeiostream #include vector #includealgorithm #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){ vectordouble 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(), Comparatordouble()); /**************end***********/ for(double d: vd) cout d endl; return 0; }