ACM/ICPC竞赛之STL简介

ACM模版

STL简介

关于STL

STL（Standard Template Library,标准模版库）是C++语言标准中的重要组成部分。STL以模板类和模版函数的形式为程序员提供了各种数据结构和算法的实现，程序员吐过能够充分的利用STL，可以在代码空间、执行时间和编码效率上获得极大的好处。

STL大致可以分为三大类：算法（algorithm）、容器（container）、迭代器（iterator）。

STL容器是一些模版类，提供了多种组织数据的常用方法，例如：vector（向量，类似于数组）、list（列表，类似于链表）、deque（双向队列）、set（集合）、map（映像）、stack（栈）、queue（队列）、priority_queue（优先队列）等，通过模版的参数我们可以指定容器中的元素类型。
STL算法是一些模版函数，提供了相当多的有用的算法和操作，从简单的for_each（遍历）到复杂的stable_sort（稳定排序）。
STL迭代器是对C中的指针的一般化，用来将算法和容器联系起来。几乎所有的STL算法都是通过迭代器来存取元素序列进行工作的，而STL中的每一个容器也都定义了其本身所专有的迭代器，用以存取容器中的元素。有趣的是，普通的指针也可以像迭代器一般的工作。

熟悉了STL后，你会发现，很多功能只需要用短短的几行就可以实现了。通过STL，我们可以构造出优雅而且高效的代码，甚至比你自己手工实现的代码效率还要高很多。
STL的另外一个特点是，它是以源码方式免费提供的，程序员不仅可以自由地使用这些代码，也可以学习其源码，甚至可以按照自己的需要去修改它，这一点十分得人性化。

Example:
（STL实现Ugly Numbers）

#include <iostream>
#include <queue>

/* * Ugly Numbers * Ugly numbers are numbers whose only prime factors are 2, 3 or 5. * 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... */

typedef std::pair<unsigned long, int> node_type;

int main(int argc, const char * argv[])
{
    unsigned long result[1502];
    std::priority_queue<node_type, std::vector<node_type>, std::greater<node_type>> Q;
    Q.push(std::make_pair(1, 2));
    for (int i = 0; i < 1500; i++)
    {
        node_type node = Q.top();
        Q.pop();
        switch (node.second)
        {
            case 2:
                Q.push(std::make_pair(node.first * 2, 2));
            case 3:
                Q.push(std::make_pair(node.first * 3, 3));
            case 5:
                Q.push(std::make_pair(node.first * 5, 5));
        }
        result[i] = node.first;
    }

    int n;
    std::cin >> n;
    while (n > 0)
    {
        std::cout << result[n - 1] << '\n';
        std::cin >> n;
    }

    return 0;
}

在ACM竞赛中，熟练掌握和运用STL对快速编写实现代码会有极大的帮助。

使用STL

在C＋＋标准中，STL被组织为以下的一组头文件（注意，是没有.h后缀的！）:
algorithm/deque/functional/iterator/list/map/memory/numeric/queue/set/stack/utility/vector
当我们需要使用STL的某个功能时，需要嵌入相应的头文件。但要注意的是，在C++标准中，STL是被定义在std命名空间中的。如下例所示：

#include <stack>

int main()
{
    std::stack<int> s;
    s.push(0);
    //...
    return 0;
}

如果希望在程序中直接引用STL，也可以在嵌入头文件后，用using namespace 语句将std命名空间导入，如下例：

#include <stack>

using namespace std;

int main()
{
    stack<int> s;
    s.push(0);
    //...
    return 0;
}

但是需要强调的是，在实际的开发中，不建议直接导入std命名空间，而在ACM/ICPC等算法竞赛中，直接导入会有很大的优势，提高编码效率。所以我们要分清楚是竞赛还是实际的开发。

STL是C++语言机制运用的一个典范，通过学习STL可以更深刻的理解C++语言的思想和方法。在本系列的文章中不打算对STL做深入的剖析，而只是想介绍一些STL的基本应用。
有兴趣的同学，建议可以在有了一些STL的使用经验后，认真阅读一下《C++ STL》这本书。