C++ STL简单入门
C++标准程序库（The C++ Standard Library）
标准程序库提供：
[1] 基本的运行期之语言支持（run-time language support）（比如运行期内存分配、运行期型别识别等）；
[2] C语言标准程序库（为了使其与类型系统的冲突降到最低，进行了一些微小的修改）；
[3] strings和输入输出流（附带对国际字符集和本地化的支持）；
[4] 一个container framework（比如vector，list和map等）以及使用这些container的算法（比如通用的遍历、排序以及合并算法）；
[5] 对数值计算的支持（复数以及向量的算术运算；类BLAS的、通用的slices；有利于优化处理的语意设计）。
将一个类包含在程序库里的主要原则有：这个类应该可能被几乎所有的C++程序员（不管是新手还是专家）使用；这个类应该以一种通用的形式被提供，但与实现相同功用的、更简单的形式相比，又不会带来明显的负荷；其基本用法很容易学会。总的来说，C++标准库提供了最常用的基本数据结构以及使用这些数据结构的基本算法。
由container、iterator和算法形成的framework通常被称为STL。STL基本上是Alexander Stepanov的研究成果[Stepanov,1994]。
6．1 string和I/O（输入/输出）
在C++中，string和I/O操作并不是直接由某种特殊的语言结构提供的。标准程序库提供了string和一些I/O型别。例如：
#include <string> // 使标准string设施成为可用的
#include <iostream> // 使标准I/O设施成为可用的
int main()
{
using namespace std;
string name;
cout << “Please enter your name: “; // 提示用户
cin >> name; // 读取一个名称
cout << “Hello, “ << name << ‘\n’; // 输出名称，后跟一个“新行符”
return 0;
}
这个例子使用了标准输入流cin、标准输出流cout，以及它们所需要的>>运算符（意即“取自某处”）和<<运算符（意即“放到某处”）。
I/O流支持多种格式化和缓冲设施；string支持诸如联结、插入、从串中取字符之类的常用操作。流和string可以用于任何字符集。
标准程序库的设施可以（也经常就是）只利用面向用户的设施来实现。因此即使标准设施有时还不够用，用户也可以自己提供同样优雅的替代方案。
6．2 Container
标准程序库提供了一些最有用也最通用的container型别，从而使程序员能够从中选择最能满足应用需要的container：
[标准container概要]
l lvector<T> 大小可变的向量
l llist<T> 双向链表
l lqueue<T> 队列
l lstack<T> 栈
l ldeque<T> 双端队列
l lpriority_queue<T> 按值排序的队列
l lset<T> 集合
l lmultiset<T> 允许出现重复元素的集合
l lmap<key,val> 关联数组
l lmultimap<key,val> 允许出现重复key值的关联数组
这些container不但被设计得具有高效性，而且还提供了接口，使我们可以在任何适当的地方交替的使用它们。例如，list、vector等就提供了把元素追加到末尾的高效操作。这使得那些需要高效的经由下标对其进行访问的数据可以按照“增量”的方式被构造。举个例子：
vector<Point> cities;
void add_points(Point sentinel)
{
Point buf;
While (cin >> buf) { // 从输入端读取结点信息
If (buf == sentinel) return;
//
cities.push_back(buf); // 把结点加入vecotr（的末尾）
}
}
container对元素没有什么强制性的限制；这即是说，所有的型别从本质上而言都可以被作为container中元素的型别。特别的是，像int和char*这样的内建型别以及C语言风格的数据结构（即结构体struct）也可以被作为container中元素的型别。
6．3 算法（Algorithms）
标准程序库提供了成打的算法。这些算法在namespace std的范围内定义，可以通过#include <algorithm>来获得使用权。下面列出我认为特别有用的部分算法：
[标准算法摘录]
l lfor_each() 对每一个元素都唤起（调用）一个函数
l lfind() 查找第一个能与引数匹配的元素
l lfind_if() 查找第一个能与谓词（predicate）匹配的元素
l lcount() 计算元素出现的次数
l lcount_if() 计算能与谓词匹配的元素个数
l lreplace() 用新的值替换元素
l lreplace_if() 用新的值替换能与谓词匹配的元素
l lcopy() 复制（拷贝）元素
l lunique_copy() 复制（拷贝）不是邻近副本的元素
l lsort() 对元素排序
l lequal_range() 查找所有元素值相等的元素
l lmerge() 合并有序的序列
上述这些算法以及标准程序库中其它算法都可以应用于标准container、string和内建数组。实际上，所有算法都可以应用于§4.5.1中描述的任何一种序列（如下图）：
如前文所述，*运算符意即“经由一个iterator访问元素”；++运算符意即“使iterator指向下一个元素”。例如，我们可以实现一个通用的算法，其任务是从一个序列中找到第一个能匹配谓词的元素：
template<class In, class Predicate> In find if(In first, In last, Predicate pred)
{
while (first != last && !pred(*first)) ++first;
return first;
}
这些通用且普适的算法从三个方面说明了它们比大多数相应的传统算法要优秀：简单的定义；能根据输入序列的型别在编译期间选择合适的算法；能对简单的操作（比如==、<和简单的用户自定义谓词）施行内联处理。
6．4 数字（Numerics）
与C一样，C++并不是意欲面向数字计算的语言。然而，C++还是拥有许多面向数字计算的部分——标准程序库就很好的反映了这一点。
6．4．1 复数（Complex Numbers）
依照§4.1中描述的complex类，标准程序库支持一系列的复数型别。为了使复数中分量的型别可以是单精度浮点数（float）、双精度浮点数（double）以及其它各种型别，标准程序库中的complex以模板实现：
template<class scalar> class complex {
public:
complex(scalar re, scalar im);
// …
};
这个复数模板支持常见的算术操作以及最常用的一些数学函数。例如：
template<class C> complex<C> pow(const complex<C>&, int);//
void f(complex<float> fl, complex<double> db)
{
complex<long double> ld = fl + sqrt(db);
db += fl * 3;
fl = pow(1 / fl, 2);
// …
}
由此可知，C++对复数型别的支持程度形同对浮点数型别的支持。
6．4．2 向量计算（Vector Arithmetic）
我们在§6.2中讲到过标准vector，其设计目标就是使其成为一个具有可适应性的、通用的机制，专门用来存放各种数据值，并且能很好的配嵌于由container、iterator和算法组成的体系结构中。然而标准vector并不支持向量的算术操作。为vector增加这样的操作其实并不难，但如果使然，那么“让这些操作具有通用性和可适应性”的努力则会使对其进行优化处理的效果变得微乎其微——而对于严格的数学计算而言，通过优化处理以提高效率往往是最重要的。因此，标准程序库提供了一个名为valarray的vector，它的通用性不够强，但为面向数字计算的优化留出了很大的余地：
template<class T>class valarray {
// …
T& operator[](size_t);
// …
};
型别size_t是无符号整型（unsigned integer），valarray将其用于数组的下标操作。
valarray能用于一般的算术操作以及一些最常用的数学函数。例如：
template<class T>valarray<T>abs(const valarray<T>&); // 取绝对值的函数
void f(const valarray<double>& a1, const valarray<double>& a2)
{
valarray<double> a = a1 * 3.14 + a2 / a1;
a += a2 * 3.14;
valarray<double> aa = abs(a);
double d = a2[7];
// …
}
valarray型别还支持BLAS-style、generalized slicing。更多复杂的数学型别——比如Matrix——可以基于valarray来构造。
