C++ STL 基础及应用

学习参考书

• 书名：《C++ STL 基础及应用》
• 作者：金百东；刘德山
• 出版社：清华大学出版社

资源网站：http://www.tup.tsinghua.edu.cn/ 或 http://www.tup.com.cn/

〇、说明

本文章不是教学文章，只是个人的学习记录，或者说更像是学习笔记，所以它并不适合用来学习。如果你想学好 C++ STL，我不推荐你仅依赖本文章进行学习，希望你可以借助更加专业的学习指导书学习相关知识。

为什么要写这篇文章呢？

准确来说之前学习 C++ STL 主要依赖于实战。说简单点就是遇到了就学一点，更多的时候是借助 C++ references 进行查阅式使用 C++ STL。至于，STL 的一些原理或者重点知识其实并不是很了解。所以，我希望能通过这次系统的学习，加深对 C++ STL 及模板编程的理解。

当然，我也希望这篇文章对你的学习之路有帮助！

一、STL 概述

STL，全称 Standard Template Library，中文名为“标准模板库”。

1.1 STL 历史

20 世纪 70 年代，Alexander Stepanov（标准模板库之父）开始考虑：在保证效率的前提下，将算法从诸多具体应用之中抽象出来的可能性。

1987 年，在贝尔实验室工作的 Alexander Stepanov 开始首次采用 C++ 语言进行泛型软件库的研究（当时 C++ 还没有引入模板语法）。

1988 年，Alexander Stepanov 等人经过长时间的努力，最终完成了一个包含大量数据结构和算法部件的庞大运行库，也就是现在 STL 的雏形。

1994 年，滑铁卢会议上，委员会们最终通过了 Stepanov 等人的提案，决定将 STL 正式纳入 C++ 标准化进程之中。

1998 年，ANSI/ISO C++ 标准正式定案，STL 始终是 C++ 标准中不可或缺的一大部件。

1.2 STL 内容

STL 主要包含三大部分，分别是：容器、算法和迭代器。

STL 容器包含了绝大部分的数据结构，如：数组、链表、队列、堆、栈和树等。值得注意的是，这些容器都是带模板参数的，可以适应很多数据元素类型，功能非常强大。STL 算法包含了诸如增、删、改、查和排序等系统函数，开发者可以直接操作这些函数实现相应的功能。STL 迭代器类似指针，通过它的有序移动把容器中的元素与算法联系起来，它是实现所有 STL 功能的基础所在。

当然，STL 中还包含其他的一些内容，如字符串、输入输出流等内容。

二、STL 的模板思维

本章不是介绍 C++ 的模板语法！！！
本章不是介绍 C++ 的模板语法！！！
本章不是介绍 C++ 的模板语法！！！

2.1 初识 STL 模板思维

首先，我们需要知道的是在 C++ 中预处理器和模板都支持“泛型编程”，都是用于在编译时进行代码生成和转换的工具。但是，二者却有很大的区别，而模板通常被认为比预处理器更安全，因为它们提供了更多的编译时检查和类型安全性。下面是对二者异同点的总结：

共同点：

1. 编译时处理： 预处理器和模板都在编译时期执行，用于生成最终的源代码。
2. 泛型编程： 两者都支持“泛型编程”概念，允许编写与数据类型无关的通用代码。

区别：

1. 处理方式：
   预处理器： 在编译前执行，主要用于文本替换和宏展开。
   模板： 在编译时进行，通过编译器生成针对不同数据类型的代码。
2. 类型安全性：
   预处理器： 不具备类型安全性，因为它只是进行文本替换，不考虑数据类型。
   模板： 具备类型安全性，因为它在编译时进行代码生成，只有在类型匹配时才会生成有效的代码。
3. 代码生成：
   预处理器： 生成文本替换后的源代码，但没有真正的代码生成机制。
   模板： 通过编译器根据模板生成针对具体类型的代码。
4. 功能：
   预处理器： 主要用于条件编译、宏定义、文件包含等简单文本处理。
   模板： 用于实现泛型编程、实现通用数据结构和算法。

安全性：
模板相对于预处理器在安全性方面更具优势。原因如下：

1. 类型检查： 模板提供了强类型检查，编译器在编译时会检查代码是否符合类型规定。这有助于捕捉一些在编译时就可以发现的错误，而不是在运行时才暴露出来。
2. 避免宏副作用： 预处理器宏可能导致一些副作用，因为它们只是简单的文本替换。模板通过在编译时生成类型安全的代码，可以避免一些宏展开引起的问题。
3. 可读性： 模板使得代码更具可读性，因为泛型代码更接近自然语言的表达形式，而不是宏展开的冗长代码。

而这也正是 STL 模板思维的优势所在！

2.2 Traits 技术

STL 非常强调“复用”这一概念，而在 C++ 中，Traits 技术是复用技术中非常重要的一部分。

那么，什么是 Traits 技术呢？

在 C++ 中，Traits（特征）是一种，用于通过在编译时查询类型信息来实现泛型编程的编程技术。Traits 允许在不依赖于继承或多态的情况下，对类型进行参数化和操作。

其技术的核心思想是通过定义一系列与类型相关的特征（被称之为 traits），然后通过这些特征来执行不同的代码操作。这种方法能够提高代码的灵活性，使得代码可以适应多种不同的类型，而无需显式地指定类型之间的继承关系。

然而，要想更好的理解 Traits 技术，我觉得还得从具体的例子里学习。下面我给出一段示例代码，帮助理解：

例2.1 初始代码
#include <iostream>
using namespace std;

class CIntArray        // 整型数组
{
private:
    int m_arr[10];

public:
    CIntArray()        // 构造函数——自动赋初值
    {
        for (int i = 0; i < 10; i++)
        {
            m_arr[i] = i;
        }
    }

    int GetSum(int times)    // times：整数倍数
    {
        int sum = 0;
        for (int i = 0; i < 10; i++)
        {
            sum += m_arr[i];
        }
        return sum * times;    // 返回数组元素和 * 倍数
    }
};

class CFloatArray    // 浮点数数组
{
private:
    float m_arr[10];

public:
    CFloatArray()    // 构造函数——自动赋初值
    {
        for (int i = 0; i < 10; i++)
        {
            m_arr[i] = (float)i;
        }
    }

    float GetSum(float times)    // times：浮点数倍数
    {
        float sum = 0.0f;
        for (int i = 0; i < 10; i++)
        {
            sum += m_arr[i];
        }
        return sum * times;        // 返回数组元素和 * 倍数
    }
};

int main(int argc, char* argv[])
{
    CIntArray intArray;
    CFloatArray floatArray;

    cout << "整型数组元素和的 3 倍是：" << intArray.GetSum(3) << "\n";
    cout << "浮点数数组元素和的 3.2 倍是：" << floatArray.GetSum(3.2f) << endl;

    return 0;
}

上述程序实现了个很简单的功能，即把整型或浮点型数组的元素和乘以相应的倍数并输出。其中，不难发现 CIntArray 的定义与 CFloatArray 的定义非常的相似，几乎除了使用的数据类型不一样之外全部一致。这种代码重复率较高的代码是不利于后期维护的，所以有没有什么办法降低这个代码的冗余程度呢？很显然，C++ 的模板语法是个不二选择！那么，我们使用模板对这个程序代码做进一步的改进。

例2.2 使用模板改进代码
// ... ...

// 新增加一个 CApply 类，通过该类调用对应数据类型的对象
template<class T>
class CApply
{
public:
    float GetSum(T& t, float times)
    {
        return t.GetSum(times);
    }
};

// 主函数修改如下
int main(int argc, char* argv[])
{    
    CIntArray intArray;
    CFloatArray floatArray;
    CApply<CIntArray> cInt;
    CApply<CFloatArray> cFloat;

    cout << "整型数组元素和的 3 倍是：" << cInt.GetSum(intArray, 3) << "\n";
    cout << "浮点数数组元素和的 3.2 倍是：" << cFloat.GetSum(floatArray, 3.2f) << endl;

    return 0;
}

看似这以及是个比较完美的代码了，实际不然，它还存在非常多的问题，尤其是对于数据类型的处理方面。在例 2.2 中的 CApply 类中，GetSum 函数的输入输出都被强制定义成了 float 类型。这样做在目前这样的小程序中也许没什么问题，但是当在逻辑更复杂、要求更加严格的业务中，这往往会带来很多很棘手的问题，甚至导致错误的结果。如何解决这种需要针对输入、输出参数类型做出变化的问题呢？Traits 技术一定是个不二之选！

例2.3 Traits 改进
// ... ...（省略相关定义，保持一致）

// 定义基本模板类
template<typename T>
class NumTraits {};

// 针对 CIntArray 进行模板特化
template<>
class NumTraits<CIntArray> 
{
public:
    typedef int outputType;       // 定义依赖名
    typedef int inputType;        // 定义依赖名
};

// 针对 CFloatArray 进行模板特化
template<>
class NumTraits<CFloatArray>
{
public:
    typedef float outputType;   // 定义依赖名
    typedef float inputType;    // 定义依赖名
};

template<class T>
class CApply
{
    // 这里的重定义是为了优化 result GetSum(T& t, input times) 函数的可读性，
    // 不然函数就会写成 typename NumTraits<T>::outputType GetSum(T& t, typename NumTraits<T>::inputType times)。
    typedef typename NumTraits<T>::outputType result;    // 使用 typename 来明确告诉编译器 NumTraits<T>::outputType 这是一个类型
    typedef typename NumTraits<T>::inputType input;      // 使用 typename 来明确告诉编译器 NumTraits<T>::inputType 这是一个类型
public:
    result GetSum(T& t, input times)
    {
        return t.GetSum(times);
    }
};

// ... ...(省略 main 函数，保持源代码)

此时，我们就成功应用 Traits 技术对代码中因类型不同而发生变化的片段进行了包装，从而使之随我们的需要而进行不同类型的适配。这也就是 Traits 技术的主要内容。

2.3 操作符重载

操作符重载是 C++ 中一种强大的特性，它允许你重新定义已有的操作符的行为，以适应用户自定义类型。

概述：操作符重载允许你重新定义类对象的基本操作符的行为，比如加法、减法、乘法等。

语法：操作符重载通过在类中定义对应的成员函数或全局函数来实现。

• 对于成员函数的操作符重载，格式为 returnType operator op(parameters);。
• 对于全局函数的操作符重载，格式为 returnType operator op(type1, type2);。

成员函数 vs. 全局函数：

• 你可以选择在类中定义成员函数，或者在类外定义全局函数来重载操作符。
• 对于大多数二元操作符，建议使用全局函数进行重载，因为这样可以保持对称性。

可以重载的内容：

1. 一元操作符重载：
   • 例如 +, -, ++, --。
   • 可以通过成员函数或全局函数进行重载。
2. 二元操作符重载：
   • 例如 +, -, *, /, %, ==, !=, <, >, <=, >=。
   • 对于大多数二元操作符，建议使用全局函数进行重载。
3. 赋值运算符重载：
   • 赋值运算符 = 可以通过成员函数进行重载。
   • 通常返回一个引用，以支持连续赋值。
4. 下标运算符重载：
   • 下标运算符 [] 可以通过成员函数进行重载。
   • 用于使类对象的行为类似于数组。
5. 函数调用运算符重载：
   • 函数调用运算符 () 可以通过成员函数进行重载。
   • 使得对象可以像函数一样被调用。

注意事项：

• 操作符的基本语法和优先级不会改变，只是其含义被重新定义。
• 不要过度使用操作符重载，以免导致代码难以理解。

示例：以下是一个简单的操作符重载示例，重载了 + 和 << 操作符：

class Complex {
private:
    double real;
    double imag;

public:
    Complex(double r, double i) : real(r), imag(i) {}

    Complex operator+(const Complex& other) const {
        return Complex(real + other.real, imag + other.imag);
    }

    friend ostream& operator<<(ostream& out, const Complex& c) {
        out << c.real << " + " << c.imag << "i";
        return out;
    }
};

这些是操作符重载的一些关键知识点，详细知识点请自行学习。由于 STL 中有大量的模板函数，因此很多时候都需要重载与之对应的操作符，所以掌握操作符重载也是掌握 STL 的关键知识点。

三、迭代器

迭代器是 STL 的核心技术，它为访问不同容器的元素提供了统一的方法，是实现通用算法的重要基础。

3.1 什么是迭代器？

迭代器可以理解为“广义指针”，它最大的好处就是成功将容器和算法分离开来。例如，有两个容器类：MyArray 是某数组类型集合；MyLink 是某类型链表集合。他们都有显示、查询和排序等功能，常规思维是每个容器类里都有自己的显示、查询和排序功能函数。

但是，如果你仔细思考这其中的细节，你就会发现：不同容器完成相同功能的基本逻辑都是一样的，那么能不能把它们抽象出来，多个容器对应一个显示、查询和排序函数呢？这就是泛型思维的思考结果，于是就有了迭代器。（具体推演思路代码这里不展示，见书 P19-P24。）

下面这张图可以更形象地阐述三者之间的关系，帮助理解到底什么是迭代器：

每个容器都有自己对应的迭代器，容器通过迭代器共享某一具体的算法，某一具体算法通过迭代器不依附于某一具体容器。迭代器起到了一个中间媒介的作用，通过迭代器就可以把容器和算法联系起来。

3.2 STL 迭代器

按照功能划分，STL 迭代器可以划分为以下 5 类：

• 输入迭代器（Input Iterator） 按顺序只读一次。完成的功能有：能进行构造和默认构造，能被复制或赋值，能进行相等性比较，能进行逐步向前移动，能进行读取值。输入迭代器重载的主要操作符列表请见后面表格。

  STL 提供的主要输入迭代器是 istream_iterator，其构造函数有以下两种形式：

  • istream_iterator()：默认的构造器，创建了一个流结束的迭代器。
  • istream_iterator(istream &)：参数是输入流。含义是从输入流中读取数据，当遇到流结束符时结束。

操作符	说明
operator*	访问迭代元素值
operator==	迭代元素相等比较
operator!=	迭代元素不等比较
operator++()	前置迭代指针++
operator++(int)	后置迭代指针++

例3.2.1 利用 istream_iterator 迭代器迭代标准输入流
#include <iostream>
#include <iterator>
using namespace std;

int main(void)
{
    cout << "请输入数据：";

    istream_iterator<int> a(cin);    // 建立键盘输入流，并利用 istream_iterator 枚举整型数据
    istream_iterator<int> b;         // 建立输入流结束迭代器

    while (true)
    {
        cout << *a << endl;          // 输出整型数据 | 调用 operator*()
        a++;                         // 迭代器指针指向下一个元素 | 调用 operator++()
        if (a == b)                  // 判断当前迭代器是否等于结束迭代器 | 调用 operator==()
        {
            break;                   // 退出 while 循环
        }
    }

    return 0;
}

例 3.2.1 示例程序输入输出结果
请输入数据：111 222 333,
111
222
333

• 输出迭代器（Output Iterator） 只写一次。完成的功能有：能进行构造和默认构造，能被复制或赋值，能进行相等性比较，能进行逐步向前移动，能进行写入值。输出迭代器重载的主要操作符列表请见后面表格。

  STL 提供的主要输入迭代器是 ostream_iterator，其构造函数有以下两种形式：

  • ostream_iterator(ostream & out)：创建了流输出迭代器，用来迭代 out 输出流。
  • ostream_iterator(ostream & out, const char *delim)：创建了流输出迭代器，用来向 out 输出流输出数据，并且输出的数据之间用 delim 字符串进行分隔。

操作符	说明
operator=	写入元素值
operator*	访问迭代元素值
operator++()	前置迭代指针++
operator++(int)	后置迭代指针++

例3.2.2 利用 ostream_iterator 迭代器向屏幕输出数据
#include <iostream>
#include <iterator>
using namespace std;

int main(void)
{
    cout << "输出迭代器演示结果：";

    ostream_iterator<int> myout(cout, ", "); // 创建标准输出迭代器

    *myout = 1;
    myout++;

    *myout = 2;
    myout++;

    *myout = 3;
    myout++;

    return 0;
}

例 3.2.2 示例程序输入输出结果
输出迭代器演示结果：1, 2, 3,

• 向前迭代器（Forward Iterator） 使用输入迭代器和输出迭代器可以基本满足算法和容器的要求，但是还有一些算法需要同时兼备两者的功能。
• 双向迭代器（Bidirectional Iterator） 具有向前迭代器的全部功能，另外它还可以利用自减操作符(operator--)向后一次移动一个位置。
• 随机访问迭代器（Random Access Iterator） 具有双向迭代器的全部功能，再加上一个指针的全部功能。包括使用操作符 operator[] 进行索引、加某个整数值就可以向前或向后移动若干个位置或者使用比较运算符在迭代器之间进行比较。

四、输入输出流

在 C++ STL 中提供了一组模板类来支持面向对象的数据输入输出功能，如标准输入输出流 iostream、文件输入输出流 fstream、字符串输入输出流 sstream等。

4.1 标准输入输出流

4.1.1 cin 与 cout

在 C++ 中 cin 与 cout 可谓是最常见的函数之一了，其本身使用起来也没有太多难度。

值得注意的是 cin 对象使用空白字符（例如空格、制表符、换行符等）作为输入数据的界定符。这意味着它会将输入数据视为由空白字符分隔的标记，并将这些标记作为不同的输入。

还需要注意的是，cin 对于不同类型的数据，比如整数、浮点数、字符串等，会根据类型的不同使用空白字符进行分隔。如果输入的数据类型不匹配，cin 可能会出现问题。在实际使用中，可以根据需要使用其他方法来处理输入，以确保正确性。

4.1.2 get 系列函数

int get();

从输入流中读取并释放一个字符，并返回该字符的 ASCII 值。

istream& get (char& c);

从输入流中读取并释放一个字符，并将该字符存储在变量 c 中。

istream& get (char* s, streamsize n);
istream& get (char* s, streamsize n, char delim);

从输入流中读取并释放一个或多个字符，并将获取到的字符存储在变量 s 中。

第一个参数 char* s 为指向字符缓冲区的指针，用于存储结果。
第二个参数 streamsize n 为字符缓冲区长度。
第三个参数 char delim（默认为 '\n'，可以忽略）为界定符^[1]，根据界定符判断何时停止读取操作。

istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

从输入流中读取并释放一个或多个字符，并将获取到的字符存储在变量 s 中。

第一个参数 char* s 为指向字符缓冲区的指针，用于存储结果。
第一个参数 streamsize n 为字符缓冲区长度。
第一个参数 char delim（默认为 '\n'，可以忽略）为界定符^[2]，根据界定符判断何时停止读取操作。

注意：get 与 geline 的区别

当使用 get 进行字符串读取的时候，get 的功能基本与 getline（注意：这里特指 basic_istream::getline）没有差别。但是，get 不会读取界定符（界定符还留在输入流里），并且会把读取到的多个字符最后位置追加一个 ‘\0’ 字符构成字符串。而 getline 会将界定符连同前面的字符一起读取出来（界定符也被读取，不会保留在流中），然后将界定符替换为 ‘\0’ 构成字符串。

4.1.3 处理流错误

获取输入状态信息的函数如下：

int rdstate();
无参数，返回值即是状态信息的特征值。如果需要清除状态标识位则需要使用 clear() 函数。

使用以下函数来检测相应的输入输出状态：

bool good();：返回 true 代表一切正常，没有错误发生。
bool eof();：返回 true 代表已经抵达流的末尾。
bool fail();：返回 true 代表 I/O 操作失败，主要原因是非法数据的输入输出（例如需要读取数字时遇到字母）。流本身还存在，可以继续使用。
bool bad();：返回 true 代表发生致命的错误（可能是物理上的错误），流将不能继续被使用。

例4.1.3.1 确保输入一个整型变量给变量 a
#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    int a;
    while (true)
    {
        cin >> a;
        if (cin.fail())
        {
            cout << "输入有误！请重新输入！" << "\n";
            cin.clear();    // 清空状态标识位
            cin.get();      // 清空错误输入（一位字符）
                            // 可改成 getline 进行行清除
        }
        else
        {
            cout << "a = " << a << endl;
            break;
        }
    }
    return 0;
}

4.2 文件输入输出流

这都是非常基础的内容，这里不想再过多赘述。

需要的可以自己查看 C++ reference：《C++ reference fstream》

4.3 字符串输入输出流

这都是非常基础的内容，这里不想再过多赘述。

需要的可以自己查看 C++ reference：《C++ reference sstream》

---

1. get 函数的读取界定条件总共有以下几种：
   
   读到 eof：以上所有函数当读到流的结尾触发 end of file 条件时，会执行 setstate(eofbit)。
   
   读到 delim：当将要读取的下一个字符 c == delim 时，get 会将已读取到的字符串存储并从流中释放，但字符 c 并不会被释放。如果继续读取，第一个读取到的字符就是 c。
   
   读满 s：至多读取 count-1 个字符存储至字符串 s 中，因为最后一个字符是 ‘\0’。
   
   没读到：如果没有读出任何字符，会执行 setstate(failbit)。 ↩︎

2. getline 函数的读取界定条件总共有以下几种：
   
   读到 eof：读到流的结尾，会执行 setstate(eofbit)；
   
   读到 delim：下一个字符 c == delim，字符 c 会被读取并释放，但不会被存储；
   
   读满 s：已经读取了 count-1 个字符，会执行 setstate(failbit)；
   
   没读到：如果没有读出任何字符（e.g.count < 1），会执行 setstate(failbit)。 ↩︎