C++ STL标准模板库

除了运行时库之外，C++ 还提供了一个模板库。标准模板库（STL）包含许多用于实现数据类型和算法的模板。

STL 中最重要的数据结构是容器和迭代器。容器是一种存储数据并以某种方式组织数据的类。迭代器是一个像指针一样工作的对象，允许访问存储在容器中的项目。

顺序容器

STL 中有两种类型的容器类：顺序容器和关联容器。顺序容器以序列的形式存储项目，这意味着按照项目在容器内的位置以自然方式排序项目。数组就是顺序容器的一个示例。

STL提供了如表 1 所示的 3 个顺序容器。 

因为顺序容器按顺序组织它存储的项目，所以可称它有一个头部和一个尾部。如果可以指定容器中某个项目的位置，然后直接跳转到该项目，而不必遍历容器中该项目之前的所有项目，则称该容器提供了对其内容的随机访问方式。

随机访问中使用的位置通常是通过给定一个整数指定的，该整数指定了容器内所需项目的位置。该整数指定的位置可以相对于容器的头部、末尾或相对于其他位置。数组和矢量都是提供随机访问的顺序容器示例。

关联容器

顺序容器使用序列中的项目位置来访问其数据。相反，关联容器将一个键（Key）与存储的每个项目相关联，然后使用该键来检索存储的项目。电话簿是关联容器的一个示例，它存储的值是电话号码，每个电话号码都与一个名称相关联。该名称稍后可以用作查找或 检索电话号码的键。

STL 提供了 4 个关联容器，如表 2 所示。

map 是一个容器，要求每个存储的值都与一个键相关联。每个键可能只与一个值相关 联。一旦使用了键，则不能将具有相同键的其他值添加到 map 中

multimap 和 map 相似，只不过其键则可以关联多个值。

set 和 map 类似，只不过它仅存储键，并不关联值。没有项目能在一个 set 中存储两次，也就是说，不允许重复项目。multiset 很像 set，只不过它允许重复。

迭代器

迭代器是像指针一样的对象。它们可用于访问存储在容器中的项目。典型的迭代器是在容器类中声明的类的对象。迭代器可以重载指针运算符，如递增运算符 ++、递减运算符 -- 和解引用运算符 * 等，以提供类似于指针的行为。

每个 STL 容器对象都提供成员函数 begin() 和 end()，它们返回对象的开始和结束迭代器。如果容器是非空的，则 begin() 迭代器将指向容器开始处的项目，而 end() 迭代器则指向刚刚超过容器尾部的地方。

表 3 显示了可用于各种 STL 容器的不同类型的迭代器。

迭代器的使用

每个STL容器类都定义了一个名为 iterator 的内部类，可用于创建迭代对象。示例如下：

以上示例都是内部类，可以相应为 vector<int> 和 list<string> 类型的容器提供迭代器。以下示例演示了如何为 int 类型的矢量和 string 列表定义迭代器，并将它们初始化为容器的开始位置。

在 C++ 11 中，可以将迭代器的类型声明为 auto，这样编译器将从容器的类型推断出迭代器的正确类型，如下所示：

除此之外，C++ 还提供了 begin(c) 和 end(c) 函数，当它们应用于 STL 容器 c 时，将相应返回 c.begin() 和 c.end() 迭代器。

所以，上面的 2 个示例也可以改写为以下形式：

begin(c) 和 end(c) 函数的好处是可以和数组一起使用。在某些情况下，这允许程序员编写能同时处理 STL 容器和数组的代码。

迭代器可以像指针一样工作，指示容器内的位置。如果 iter 是一个迭代器，则 *iter 就代表了在容器的迭代器位置中存储的元素。此外，编写 iter++ 将导致迭代器向前移动到容器的下一个位置。end() 迭代器始终指示超过容器最后一个元素的位置，所以它绝对不能被解引用。end() 迭代器仅用作标记符号，以防止掉入容器的末尾。

例如，以下代码将打印代码中的所有值：

vector<int> vect { 10, 20, 30, 40, 50};
auto vIter = vect.begin();
while (iter != vect.end())
{
    //打印iter位置的元素并向前迭代
    cout << *iter << " ";
    iter ++;
}

下面的程序演示了如何使用上述概念知识来处理数组和矢量。它的主要思路是编写如下模板函数：

该函数釆用 T 类型形参。作为 T 传递的真实类型需要支持解引用运算符 * 和后缀递增运算符 ++。像这样的类型进入某些 STL 容器中可以作为迭代器，或者进入数组中作为指针。无论哪一种方式，都可以引用 T 作为迭代器类型。

请注意，begin_iter 和 end_iter 指定了某些容器中的开头和末尾位置。递增运算符 ++ 知道如何从容器中的一个位置移动到下一个位置。因此，无须第三个形参即可指定容器本身。在下面程序的代码清单中可以看到 print 函数的代码。

该程序的 main 函数演示了print函数的两种用法，其中一个用于 string 数组，另一个用于 int 类型的数组。

// This program demonstrates how iterators and related concepts can be used to write code that works with arrays and STL containers.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<typename T>

void print(T begin_iter, T end_iter)
{
    auto iter = begin_iter;
    while (iter != end_iter)
    {
        cout << *iter << ";
        iter++;
    }
    cout << endl;
}
int main()
{
    // Print an array of strings
    string names[]{ "Anna", "Bob", "Chuck" };
    print(begin(names), end(names));
    // Print a vector of integers
    vector<int> vec{ 10, 20, 30 };
    print(begin(vec), end(vec));
    return 0;
}

程序输出结果:

vector容器

表 4 列出了矢量类模板的一些成员函数。其中一些接收迭代器作为形参，而另外一些则返回迭代器作为结果。 

算法

STL 提供的算法被实现为函数模板，并可对容器的元素执行各种操作。在 STL 中有很多算法，表 5 仅列出了其中的很少一部分（该表仅给出了一般说明）。 

注意，STL 算法需要包含 algorithm 头文件才能使用。