Doglog.net

距离上一篇教程足有半个多月了。关于STL其实需要讲的很多，连我自己也不能说是精通，但作为基础教程，我想并不需要讲太多理论上的东西；STL的存在更多的是为了方便编码的。

STL可以讲得很结构化的，因为它只是一个规划比较完善的库而已，具有程序的结构化特征。这篇教程大致摘取了这里（C++ Reference）的一些用法并做了一些调整，如果希望继续深入学习，这个链接是个很好的去处。另外也可以阅读《The C++ Standard Library》一书。

STL是Standard Template Library的缩写，意为标准模板库。首先我们需要清楚C++强大的核心力量，那就是模板。模板允许我们在C++中进行泛型编程，它规定了一种统一的格式，然后在编译时（而不是运行时）自动产生所需代码。先看一个例子：

template <class T>
inline const T& max(const T& a, const T& b)
{
    // if a < b then use b else use a
    return a < b ? b : a;
}
// ...
// we use it here
int x = 2, y = 3;
int z = max<int>(x, y);
// ...

例子很短，注释得很清楚，主要就是看那个template。很容易看明白，使用模板就好像把东西“嵌”进去了一样，而声明的时候我们就抽象出来一个T来泛指所有类型了（也就是泛型）。

上面的代码使用模板的部分，在编译时（重新强调，不是运行时）会产生类似下面的代码：

inline const int& max(const int& a, const int& b)
{
    // if a < b then use b else use a
    return a < b ? b : a;
}

我想这下你应该大概理解模板了。

下面我们来说STL。

STL里都有什么？STL提供了对常用数据结构、常用算法、迭代器、函数对象、内存管理以及一些实用方法的支持。其中数据结构占了主体部分，因为操作都是对于数据的。STL提供的数据结构可以分为三类：序列、容器适配器、关联容器。序列包括了向量、列表、双端队列；容器适配器包括了栈、队列、优先队列；关联容器包括了位集、映射、集合。

需要提到的是我们用的string也是STL的一部分。但你可以就把它当作一个已有的类型，跟int一样。

下面我们对常用数据结构、常用算法、迭代器分别举例介绍，而函数对象、内存管理的内容不在基础范围内，如有需要请自行查阅相关资料。

1. 向量

我们使用向量最多的地方就是作为一个可变长度的数组使用。C++中的数组大小可以动态分配，但是分配完后不能动态改变，如果重新分配，原来的数据就没有了（因为换了一块内存）。而STL中的vector则提供了这一有用的特性。

// 不断读取输入，如果是零就结束程序，
// 否则把读入的数字添加到向量末尾
// 程序结束之前打印向量的内容

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;
    int n;

    cin >> n;
    while (n)
    {
        v.push_back(n);
        cin >> n;
    }

    for (int i = 0; i < v.size(); ++ i)
        cout << v[i] << endl;

    return 0;
}

2. 栈

栈是一种非常实用的数据结构，保持有先进后出（First In, Last Out）特性。

// 类似上面的例子，不过把输入的数字逆序输出（FILO）

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<int> s;
    int n;

    cin >> n;
    while (n)
    {
        s.push(n);
        cin >> n;
    }

    while (! s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }

    return 0;
}

3. 映射

目前标准的STL还没有Hash（但已经可以找到很多编译器厂商自己的版本），而STL中的map使用最多的也能也是作为哈希表使用（至少我是这样的~）。

// 读取5行数据，每行一个字符串和一个整数
// 再读取一个字符串，输出对应的整数
// 如果没有，报错……key not found!

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
    string s;
    int n;
    map<string, int> m;

    for (int i = 0; i < 5; ++ i)
    {
        cin >> s >> n;
        m[s] = n;
    }

    cin >> s;
    if (m.count(s))
        cout << m[s] << endl;
    else
        cerr << "key not found!" << endl;

    return 0;
}

4. 排序算法

C标准库有个函数叫qsort，C++的STL则提供了更加一般化的算法sort。它们两个都是基于快速排序的实现，sort的速度要比qsort快，据我所知仅慢于手写的尾递归快排（我试验过而且写出了比sort快5倍左右的QuickSort~），能满足于99%以上情况下的需要。

// 读取一个n，再读取n个整数，从小到大排序后输出

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int *a = new int[n];

    for (int i = 0; i < n; ++ i)
        cin >> a[i];

    sort(a, a + n);

    for (int i = 0; i < n; ++ i)
        cout << a[i] << endl;

    delete[] a;

    return 0;
}

5. 迭代器的使用

我们习惯了在for循环中用一个i来表示index（索引），迭代器把我们从具体的i中解放出来，提供更直接的接口便于我们操作。在多数情况下，迭代器对于降低编程复杂度是很有效的。

// 用一种很麻烦的方法计算数字0~9的和
// （只是为了演示迭代器的使用）

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> the_vector;
    vector<int>::iterator the_iterator;

    for (int i = 0; i < 10; ++ i)
        the_vector.push_back(i);

    int total = 0;
    the_iterator = the_vector.begin();
    while (the_iterator != the_vector.end())
    {
        total += *the_iterator;
        ++ the_iterator;
    }

    cout << "Total=" << total << endl;

    return 0;
}

关于STL的例子举这么多就差不多了，STL的初步学习是可以一通百通的。当然这也只是会用一些现成的东西而已，那些更高级的C++话题可都是关于STL的。

（本篇完；做人要厚道，转载请注明出处）

这是本篇的第三部分。第一部分是代码在这里，第二部分是测试用例在这里，这里是代码的解释部分。

首先从直观上看代码，每个字符都是等宽的，字体是Courier New，打代码要习惯这种字体。颜色上，有三种，黑色、绿色、蓝色。黑色的包含了很多内容，但都不特殊。绿色的是注释（Comment），没有实际执行意义，是给人看的不是给机器看的。蓝色的一些是预编译命令，另一些是关键字（Keyword），也是保留字（ReservedWord），就是保留有固定的意义，不能用作其它用途。

C++中的注释有两种，你也看到了，两个斜线（“//”）表示从这里开始到这行末尾所有文字都是注释，而另一种是以“/*”开始以“*/”结束，表示它们中间的文字都是注释。后者来源于C语言。

预编译命令是辅助代码编译的前期阶段处理代码的命令。代码编译成可执行程序经过三个阶段，第一阶段经过预处理器（Preprocessor）初步处理代码，第二阶段将每个源文件独立编译（Compile）成对象（Object）文件，第三阶段将对象文件链接（Link）到一起构成可执行程序。预编译命令就是用作第一阶段的。

#include命令是C++中最常用也几乎是唯一能用到的预编译命令，它表示将某个头文件（Header）包含进来，从而使包含它的代码可以使用头文件提供的各种东西。<iostream>头文件提供了C++的输入输出流机制。流（Stream）是C++抽象出来的一种机制，可以把它想象成一个“槽”，扔到“槽”里的东西会输出，同样也可以从“槽”里获取输入。

C++提供了三个标准的流：cin、cout和cerr，它们分别代表标准输入流、标准输出流、标准错误输出流。对流进行操作的时候，我们一般使用“>>”和“<<”两个操作符（Operator），前者代表从流中获取数据，后者代表将数据输出到流。可以通过箭头的方向来判断数据的流向，从而理解它们的意义。

标准输入输出流是针对用户的命令行窗口的，<fstream>则提供了针对文件的流操作。输入文件流用ifstream声明，输出文件流用ofstream声明。类似地，可以把一个字符串当作一个流，<sstream>提供了这种支持，我们在代码中只用到了istringstream，还有ostringstream是向字符串做流输出用的。流跟其他的量一样使用前都需要声明（Declaration）。

这里不妨说明一下“using namespace std;”，这一行表示的是引用命名空间std。命名空间机制可以解决同一个域（Scope）内名称重复的问题，具体的设计思想不在“基础”范围内。这里只是需要说明像cin、cout这些流以及ifstream、ofstream这些流的类型都是包含在std这个命名空间里的，所以要使用它们必须要using这个std。如果不using的话，cin就应当写成“std::cin”来表明我们用的是这个cin而不是某个别的什么甚至没有定义的东西。

代码中出现了C++中常用的也是很基础的关键字，包括class public protected private virtual const inline void bool char int if else while for break return true false。下面分组简要说明，更详细的需要通过阅读代码（不止是这个代码，还有本系列以后的代码）来自己体会理解。

首先是void bool char int，先不看void，后三个都是数据类型，分别表示布尔型、单字符型、整型。C++中常用的还有short（短整数） long（长整数） float（单精度浮点数） double（双精度浮点数）以及unsigned short、unsigned int、unsigned long，它们是short、int、long三种整数类型所对应的无符号（unsigned）类型，也就是占用同样大的存储空间，但是只表示非负数。数据类型可以作为函数的返回值，而void表示函数没有返回值。这里所说的函数，跟数学意义上的函数是一样的，就是给它一些参数作为输入，它就返回数据作为输出（返回值）。而返回值用到另一个关键字就是return。

函数的一般声明格式是“数据类型 函数名 参数列表”。所以像“int main(int argc, char** argv)”就是一个相当标准的函数声明的例子，其中main是函数的名字，argc和argv是两个参数的名字。main函数也是C++程序一个很特殊的函数，因为它是整个程序执行的入口，也就是程序最开始运行的地方就是main。main函数的参数列表也是约定好的，argc表示从命令行运行该程序所提供的参数个数，argv则是一个字符串的数组，数组的每一项是对应的参数。比如我们的代码保存为cpptut3.cpp，编译后生成cpptut3.exe文件，命令行下进行测试时我们输入的是“cpptut3 tc1”，这里cpptut3就是第一个参数，tc2就是第二个参数。注意，第一个参数一般都是程序本身的名字，所以虽然我们只需要输入文件名tc1，但还是会有两个参数传进来。

从这里接着说下去，我想你应该就明白 if 这个关键字的作用了。顾名思义，它用来判断某件事情是否成立，然后决定做什么。else 关键字配合 if 使用，它说明了如果表达式（Expression）的值为假（false），也就是不成立，程序应该做什么。而到底做什么，则是另一些语句（Statement）组合起来形成的一个块（Block）。C++中用一对花括号（{}）来标明一个块，一个块等价地构成一个域（Scope）。另外，C++中的语句末尾都有一个分号“;”。

if条件语句用来判断真假并执行一次块的内容，while则不断地根据条件真假循环地执行块的内容。如果不想循环了，还可以用break语句跳出循环，执行while以后的东西。另外还可以用continue语句结束本轮循环（这个代码里没用到）。if和while很相似，它们都有相同的语义结构：“if(…){…}else{…}”表示“如果…的值是真（true）就执行…否则执行…”，而“while(…){…}”表示“当/只要…的值是真就执行…”。else子句加了斜体，因为它并不是必须的。

除了最原始的while循环语句，C++中还有一个很强大的for循环语句。for语句的结构是“for(初始化; 循环条件; 增量){执行体}”。比如我们想输出100以内的所有偶数，我们可以从0开始每次递增2并输出这个值，用for语句就写成“for(int i = 0; i <= 100; i += 2) { cout << i << endl; }”。其中i是for语句域内的变量，所以声明int i放在for语句的初始化部分；循环条件是i<=100；增量部分我们用到了C++的简化操作符“+=”，相当于写成“i = i + 2”；循环体我们向cout流输出i的值，同时还用endl输出一个换行符。代码中的for语句例子更加复杂，需要好好体会，弄清楚循环的真正含义。

下面我们来看class 以及 public protected private这四个关键字，它们都是类定义中很常用的关键字。所谓的类，就是某些具有相同特征的东西抽象出来的一个统一类型。代码例子中我们写了一个类App，用来对我们需要实现的程序进行包装。我们会在以后的篇目里进一步讨论这个类本身，这里只是关注形式上的东西。

首先，类声明是一个语句，所以最后的}还要跟一个;才对。写一个类与写一个函数一样分为声明和定义两部分，声明的大体框架是“class 类名{类声明体};”。类声明体中我们声明类的方法（Method）和成员（Member）。方法就是写在类里面的函数， 比如App::App App::~App App::run App::process App::print App::log。成员就是写在类里面的变量或者常量，比如in_ out_ data_。无论方法还是成员，都需要限定谁能访问它，于是我们用到了public protected private三个访问限定符（Access Specifer）。用public限定的东西，在类的内外都可以用；用protected限定的东西，类里面可以用，从类派生的子类（SubClass）也可以用；用private限定的东西，只能在类本身里使用。关于子类，以后的篇目会详细说明；virtual关键字也与此有关，暂略。而const则表示方法不会改变类成员的值；需要注意const书写的位置。

类的定义一般与声明分开，比如App::run App::process等等，都是像一般的函数一样定义。而App::log我们却写在类的声明里面，我们称之为内联（Inline）方法。同时我们还使用了关键字inline说明它是一个内联方法。函数也可以内联，声明的方法跟内联方法相同。内联适合一些很小规模的内容，编译器在编译的时候会把它们展开应用到每个使用到它的地方。但这也是不一定的。关于内联的知识很复杂，不在“基础”范围内，这里用到只是为了指出这个语言现象。

我们眼前的类一定有两个方法让你觉得特别刺眼，那就是App::App和App::~App。因为C++中的名字首先不能重复，其次名字只能是“字母或下划线开头的字母、数字与下划线组合”。但这两个方法确实是合法的，因为它们特殊。App::App叫做构造函数（Constructor），App::~App叫做析构函数（Destructor）。从它们的名字就可以大概理解它们的作用了。

构造函数在用一个类创建一个新的对象时被调用，应用到这个对象，负责对象的初始化构建工作。析构函数则在这个对象超出其作用域时被调用，负责对象的清理工作。现在可以看主函数main中的“App myApp(argv[1]);”这一行，这里我们就用类App创建了一个叫做myApp的对象，另外我们还给构造函数提供了一个参数argv[1]。创建对象后我们就可以使用它了，“myApp.run();”就调用了run函数。而这一切都是在“int main(…){…}”这个域中工作的。

C++中的任何东西都有一个使用范围，这个范围用域来结构化。当前域可以使用域外声明的东西，当前域可以使用域内已经声明的东西，当前域内声明的东西会覆盖掉域外相同名称的东西。理解好这三条，就是一个很好的开始。

回到之前的问题。当超出了main函数定义的域后，对象myApp就超出了它的作用域，此时就会对myApp调用析构函数。为了更好理解构造函数和析构函数，我们不妨看看它们到底都做了些什么：

App::App(const char* inStr) // App类的构造函数
{
    string filename(inStr); // 创建了一个字符串叫做filename 用传进来的参数inStr初始化它
    in_.open(string(filename + ".txt").c_str()); // 打开输入文件流in_ 文件以.txt结尾
    out_.open(string(filename + ".log").c_str()); // 打开输出文件流out_ 文件以.log结尾
}

App::~App() // App类的析构函数
{
    in_.close(); // 关闭输入文件流in_
    out_.close(); // 关闭输出文件流out_
// 文件流使用后一定要关闭！
}

综合上面的代码和注释，一个很显然的执行过程就出现了。而在打开、关闭文件之间，我们的run()函数被调用来进行一些操作。我们把输入文件按行处理，line是一个字符串（String）表示当前读取的行，line_count则是行号计数。我们用getline函数读入一行内容到line中。注意，我们没用“in_ >> line; ”是因为默认情况下这样读取字符串只是到一个空白符为止，而我们需要处理的文件的每一行是有很多空格的，所以这样会导致错误。

process()函数处理一行命令。我们允许的命令格式已经在那个C风格的注释中简要说明了，结合测试用例我想你应该能明白。process()函数的大体框架是好几个互斥的if条件语句，用来区分对不同的命令进行处理。在每次处理的最后，如果发生错误会返回false到run()函数的执行流程里，示意终止对输入文件的处理，如果顺利执行，则调用print()函数打印（指向控制台输出）被操作的数组（Array）的值。

整个程序处理的核心对象是很多个数组，我们允许为每个数组命名，并通过这个名字来对相应的数组进行操作。这听上去是个很强大却又很复杂的东西，但我们只用了不到二百行就实现了。如此高效的原因在于我们使用了STL（Standard Template Library）。关于STL的描述我们将在下一篇中进行。

好了，到此为止对这段代码的说明应该差不多了，具体的执行流程不在语法范围内，需要你好好阅读，仔细思考。

（本篇完；做人要厚道，转载请注明出处）