下载掌阅APP，畅读海量书库
立即打开
标 准模板库（Standard Template Library，STL）是当今每个从事C++编程的人需要掌握的一项有用的技术。最近各种外企的面试题中，它的比例逐渐增大。想学习STL的人应该花费一段时间来熟悉它，有一些命名是不太容易凭直觉就能够记住的。然而如果一旦你掌握了STL，就不会觉得头痛了。和MFC相比，STL更加复杂和强大。
STL有以下优点：
● 可以方便、容易地实现搜索数据或对数据排序等一系列的算法。
● 调试程序时更加安全和方便。
● 即使是人们用STL在UNIX平台下写的代码，也可以很容易地理解（因为STL是跨平台的）。
STL中一些基础概念的定义如下。
●....模板（Template）：类（及结构等各种数据类型和函数）的宏（macro）。有时叫作甜饼切割机（cookie cutter），正规的名称应叫作泛型（generic）。一个类的模板叫作泛型类（generic class），而一个函数的模板也自然而然地被叫作泛型函数（generic function）。
●....STL标准模板库：一些聪明人写的一些模板，现在已成为每个人所使用的标准C++语言中的一部分。
●....容器（Container）：可容纳一些数据的模板类。STL中有vector、set、map、multimap和deque等容器。
●....向量（Vector）：基本数组模板，这是一个容器。
●....游标（Iterator）：这是一个奇特的东西，它是一个指针，用来指向STL容器中的元素，也可以指向其他的元素。
面试例题1： 介绍一下STL和包容器，如何实现？举例实现vector。[美国某著名移动通信企业面试题]
答案 ：C++的一个新特性就是采用了标准模板库（STL）。所有主要编译器销售商现在都把标准模板库作为编译器的一部分进行提供。标准模板库是一个基于模板的容器类库，包括链表、列表、队列和堆栈。标准模板库还包含许多常用的算法，包括排序和查找。
标准模板库的目的是提供对常用需求重新开发的一种替代方法。标准模板库已经经过测试和调试，具有很高的性能并且是免费的。最重要的是，标准模板库是可重用的。当你知道如何使用一个标准模板库的容器以后，就可以在所有的程序中使用它而不需要重新开发了。
容器是包容其他对象的对象。标准C++库提供了一系列的容器类，它们都是强有力的工具，可以帮助C++开发人员处理一些常见的编程任务。标准模板库容器类有两种类型，分别为顺序和关联。顺序容器可以提供对其成员的顺序访问和随机访问。关联容器则经过优化关键值访问它们的元素。标准模板库在不同操作系统间是可移植的。所有标准模板库容器类都在namespace std中定义。
举例实现vector如下：
或者是：
面试例题2： Find the defects in each of the following programs，and explain why it is incorrect.（找出下面程序的错误，并解释它为什么是错的。）[中国台湾某著名杀毒软件公司2010年面试题]
解析 ：这个程序在退出时会出问题。重复delete同一片内存，程序崩溃。如果把析构函数改为如下，可以更清楚地看到这一点：
运行时发现打印如下信息：
也就是说，发生了CDemo类的两次析构，两次析构str所指向的同一内存地址空间（两次str值相同=0x3d3d28）。
有人认为，vector对象指针能够自动析构，所以不需要调用delete a1，否则会造成两次析构对象，这样理解是不准确的。任何对象如果是通过new操作符申请了空间，必须显示的调用delete来销毁这个对象。所以“delete a1；”这条语句是没有错误的。
“vector<CDemo>*a1=new vector<CDemo>（）；”指定一个指针，指向vector<CDemo>，并用new操作符进行了初始化，所以必须在适当的时候释放a1所占的内存空间，因此，“delete a1；”这句话是没有错误的。但必须明白一点，释放vector对象，vector所包含的元素也同时被释放。
那到底哪里有错误？
这句a1的声明和初始化语句“vector<CDemo>*a1=new vector<CDemo>（）；”说明a1所含元素是“CDemo”类型的，在执行“a1->push_back（d1）；”这条语句时，会调用CDemo的复制构造函数，虽然CDemo类中没有定义复制构造函数，但是编译器会为CDemo类构建一个默认的复制构造函数（浅复制），这就好像任何对象如果没有定义构造函数，编译器会构建一个默认的构造函数一样。正是这里出了问题。a1中的所有CDemo元素的str成员变量没有初始化，只有一个四字节（32位机）指针空间。
“a1->push_back（d1）；”这句话执行完后，a1里的CDemo元素与d1是不同的对象，但是a1里的CDemo元素的str与 d1.str指向的是同一块内存。
我们知道，局部变量，如“CDemo d1；”在main函数退出时，自动释放所占内存空间，那么会自动调用CDemo的析构函数“～CDeme”，问题就出在这里。
前面的“delete a1；”已经把 d1.str 释放了（因为a1里的CDemo元素的str与d1.str指向的是同一块内存），main函数退出时，又要释放已经释放掉的d1.str内存空间，所以程序最后崩溃。
答案 ：本题问题归根结底就是浅复制和深复制的问题。如果CDemo类添加一个这样的复制构造函数就可以解决问题：
添加深复制后可有效解决问题。
面试例题3： 以下代码有什么问题？如何修改？[中国某著名综合软件公司2005年面试题]
解析：
这是迭代器问题，只能删除第一个6，以后迭代器就失效了，不能删除之后的元素。
itor2=itor；这句说明两个迭代器是一样的。array.erase（itor2）；等于array.erase（itor）；，这时指针已经指向下一个元素6了。itor++；又自增了，指向了下一个元素3，略过了第二个6。
答案：
修改方法1：使用vector模板里面的remove函数进行修改，代码如下：
修改方法2：为了让其不略过第二个“6”，可以使“itor-；”，再回到原来的位置上。具体代码如下：
面试例题1 ：解释一下什么是泛型编程，泛型编程和C++及STL的关系是什么？并且，你是怎么在C++环境里进行泛型编程的？[美国某著名CPU生产公司面试题]
答案 ：泛型编程是一种基于发现高效算法的最抽象表示的编程方法。也就是说，以算法为起点并寻找能使其工作且有效率工作的最一般的必要条件集。令人惊讶的是，很多不同的算法都需要相同的必要条件集，并且这些必要条件有多种不同的实现方式。类似的事实在数学里也可以看到。大多数不同的定理都依赖于同一套公理，并且对于同样的公理存在多种不同的模型。泛型编程假定有某些基本的法则在支配软件组件的行为，并且基于这些法则有可能设计可互操作的模块，甚至还有可以使用此法则去指导我们的软件设计。STL就是一个泛型编程的例子。C++是我可以实现令人信服的例子的语言。
面试例题2： Below is usual way we find one element in an array：In this case we have to bear the knowledge of value type“int”，the size of array，even the existence of an array.Would you re-write it using template to eliminate all these dependencies?（我们通常求解一个数在一个数列里的方法是这样的：在这个例子中，我们得先知道int类型的知识，知道队列的大小，甚至要建立一个队列。你能否用泛型编程模拟这个队列，做到不知道上面的附加知识仍然能得出结果？）[德国某著名软件咨询企业2004年面试题]
解析 ：这是一个把普通函数改成泛型函数的问题，在这里公司考的是如何将普通函数转换成泛型函数。
答案 ：
修改代码如下：
或者：
面试例题1： Please write a program to realize the model described int the figure.You should design your program as generic as possible so that we can enhance the model in the future easily without making too much change in your program.（写一个程序来实现下图的模型中整型变量的问题。你必须尽可能地将程序设计为一类（同类），以便于我们今后在不做大量更改的情况下对它进行升级。）[德国某著名软件咨询企业2005年11月面试题]
解析 ：这是一道考函数指针的面试例题，当然也可以用模板来做。
如题目所示：要求A与B之和、C与D之积，以及由于E的情况不同而得出的结果。我们当然可以单独为A和B设置一个求和函数，为C和D设置一个求积函数。但是一旦功能改变，比如说我们不得不求A与B之差或C/D的情况该怎么做？第三次也许是最小值和两数之积……如果不用函数指针，我们需要写多少个这样的test（）函数？显然，函数指针为我们的编程提供了灵活性。
一个函数在编译时被分配给一个入口地址，这个入口地址就称为函数的指针，正如同指针是一个变量的地址一样。函数指针的用途很多，最常用的用途之一是把指针作为参数传递到其他函数。
答案： 程序源代码与解释如下：
另外，有些地方必须使用函数指针才能完成给定的任务，特别是异步操作的回调和其他需要匿名回调的结构。另外，像线程的执行和事件的处理，如果缺少了函数指针的支持也是很难完成的。当然，该程序也可以用静态模板类来实现，解决方法是一致的，代码如下：
扩展知识（模板与容器）
数据结构本身十分重要。当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。
经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码。这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所不同。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构。通过设置一些模板类，STL容器对最常用的数据结构提供了支持。这些模板的参数允许我们指定容器中元素的数据类型，可以将许多重复而乏味的工作简化。
容器部分主要由头文件<vector>、<list>、<deque>、<set>、<map>、<stack>和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其他容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。
面试例题2： 试用多态实现线性表（队列、串、堆栈），要求具备线性表的基本操作：插入、删除、测长等。[美国著名软件企业GS公司2007年11月面试题]
解析 ：队列、串、堆栈都可以实现push、pop、测长等操作。现在要求用多态去实现，就要建立一个线性表的共性模板，来实现以上的功能。
答案： 程序源代码与解释如下：
面试例题2： 1～9的9个数字，每个数字只能出现一次，要求这样一个9位的整数：其第一位能被1整除，前两位能被2整除，前三位能被3整除……依此类推，前9位能被9整除。[中国著名互联网企业B公司2013年11月面试题]
解析 ：可以采用枚举实现以上的功能。
答案： 程序源代码下：
