何为STL

标准模板库(Standard Template Library),缩写为STL,是一个C++软件库。然而它却经常被人认为是包含在C++标准里的,尤其是在算法竞赛领域。其实STL和Boost等软件库一样,是独立的存在。

至于为什么很多人会混淆这个概念呢,主要是因为C++标准库大量借鉴了STL的有关内容,其C++的标准库有很深的影响。更多有关C++的发展历史,可以参考https://zh.cppreference.com/w/cpp/language/history

当然,本文讨论的重点并不在于概念的辨识。相反,由于STL经常的概念被误解,不妨我们就将被放进C++标准中的那部分STL内容称作STL。同样,不同的编译器对标准的实现不同,我们这里按竞赛中最常用的gcc编译器来讨论。

如何看待STL在算法竞赛上的使用

用的好,那是省时省力;用的不好,那是浪费青春。用还是不用,很大程度上取决于竞赛是否开启O2优化。由于O2优化中inline的存在,STL在效率上有着天与地的差别。而抛开竞赛本身,STL在算法学习上也有值得我们思考的东西。

从时间资源消耗上来看

  • 随机生成1000000个正整数,大小均在32位整型范围内。我们对这组数据进行排序,结果如下:
项目时间
手写快排(递归法,用首位数据做key)133472ms
启用O2优化的情况下使用sort函数63794ms
未启用O2优化的情况下使用sort函数204090ms
  • 对12个英文字母进行全排列,结果如下:
项目时间
手写递归12374408ms
启用O2优化的情况下使用next_permutation函数1177013ms
未启用O2优化的情况下使用next_permutation函数48354277ms

在忽略一定量的误差的情况下,我们还是可以很清楚的看到手写、使用STL以及在开启O2优化的情况下使用STL的差距。

从空间资源消耗上来看

很多人第一次接触vector的时候,大多数人都只记住了它的内存是动态分配的,却少有人关注它的内存是如何分配的。我们不妨做一个小实验:

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;

int main() {
    cout<<v.capacity()<<" ";

    for(int i=0;i<10;++i) {
        v.push_back(10);
        cout<<v.capacity()<<" ";
    }

    return 0;
}

运行结果:

0 1 2 4 4 8 8 8 8 16 16

这和一部分人心里期待的0 1 2 3 4...10 有所不同。事实上,每一次vector容器空间不足的时候,它会多申请和自身大小一致的内存空间以形成效率上的优势。但这会造成在某个节点上插入操作耗时比其他任何节点大的多的情况,也会出现为了存下某个数据而不得不让内存占用翻倍的情况。无论是那种情况,都是我们不曾希望出现的。

从算法学习本身上来看

问大家一个问题:

在学会用sort之后,你还能熟练快速的打出快排吗?

在NOIP 2016初赛上有一道完善程序题,考点就是快速排序,然而在STL的带动下,不少人都已经忘却了手写快排的技能。更有初学者连快排都没有打几遍就直接用上了sort,从实用主义上来说这确实没有什么错,但是就算法学习上本身上来说,这是一个错误。

当然,在打好了坚实基础之后,用好STL反倒成为了一个很重要的事情。毕竟与其自己实现一个快速排序还不如调用STL里面的sort来的简单,来的效率。

小结

在算法竞赛中,程序语言终归是用于表达自己算法思想的工具,用得好事半功倍,而滥用则会搬起石头砸自己的脚。对于初学者,还是要把基础打牢,不能用STL来偷懒。在掌握了应该掌握的知识之后,STL才会成为一个A题好工具。

同样,使用STL也需要看场合。在NOI、ACM-ICPC、蓝桥杯等比赛上启用了O2优化,那么对于大家使用STL就给出了有利条件。而NOIP这类的比赛就没有,所以需要在考虑的时候要慎重。


参考资料

Last modification:February 24, 2019
博客维护不易,如果你觉得我的文章有用,请随意赞赏