泛型编程是c++不同于面向对象的又一特性,它不要求通过额外的间接层来调用函数,而是让程序员撰写完全一般化并可以重复运用的算法,其效率和“针对特定数据类型而设计”的算法旗鼓相当。每一个算法、每一个容器的操作行为,其复杂度都有明确规范,通常是最佳效率或极佳效率。
What's STL?
STL是描述软件组件抽象需求条件的一个正规而有条理的阶层架构(formal hierarchy), 是一种高效,泛型,可交互操作的软件组件,巨大且可扩充。它包含许多基本算法和数据结构,但把二者完全分离开来,互不耦合。
STL不只是一个容器类程序库,更是一个泛型算法(Generic Algorithms)库:容器的存在使这些算法有东西可以操作。
STL的效率
人们对STL效率的误解,大部分是因为把编译时期的效率和运行时期的效率混为一谈了。大量嵌套地运用Template会导致编译器在进行Template引数推导(Argument deduction)及实例化(Instantiation)时耗用大量时间,但并不影响运行效率。
STL的严重缺点在于,它尚未支持persistence(对象持久性)
What's Concepts?
所谓Concept,是一组“描述某个类型(Type)”的条件(Requirements)。当某个类型满足所有这样的条件,我们便说它是该Concept的一个model。但concept并不是c++语言的成分。
它是Algorithm和Data Type的接口,当定义新的组件时,对于新的Iterator,代表应提供的机能,对于新算法而言则表示假设已经存在的机能。
What's Concept Requirements?
requirements != member functions,所谓条件是一组valid expressions. e.g. if Iterator is a model of Input Iterator, i is an object of Iterator type, then *i is a valid expression.
The semantic or performance requirements has not been supported yet.
What's Iterators?
Iterator是指针的概括物,它们是“用来指向其他对象”的一种对象,是算法与数据结构之间的接口。
Iterator的抽象化过程让我们可以将算法与其所操作的元素分离,解除耦合关系,使我们得以撰写“能操作于任意线性序列之上”的算法 。大多数算法自身并不直接操作于Container之上,而是操作于Iterators所形成的Ranges上。
About Refinement
若Concept C2提供Concept C1的所有功能,再加上其他可能的额外功能,便说C2是C1的Refinement。
Modeling与Refinement满足:
1)自反性——每个Concept C都是其自身的一个Refinement;
2)涵盖性——若类型X是Concept C2的一个Model,而C2是Concept C1的一个Refinement,则X是C1的一个Model;
3)传递性——若C3是C2的一个Refinement,C2是C1的一个Refinement,则C3是C1的一个Refinement。
Modeling是Type与Concept间的关系,Refinement是两个Concepts之间的关系。
定义新算法时的建议:
- 尽可能做最少的假设——使得你的算法可以有最大弹性地与不同种类的Iterators搭配使用;
- 不应该在效率与通用性之间做选择,因为二者都很重要,遇到需要做选择的场合应用该书3.1.4节所描述的分派(dispatching)技术来解决该问题。参见OOPSLA'06 Concepts: Linguistic Support for Generic Programming in C++ Section 2.2.