[技术] OIer的STL入门教程 - rvalue_H5之家 - 中国HTML5教程资源分享第一站

注: 本文主要摘取STL在OI中的常用技巧应用, 所以可能会重点说明容器部分和算法部分, 且不会讨论所有支持的函数/操作并主要讨论 C++11 前支持的特性. 如果需要详细完整的介绍请自行查阅标准文档.

原始资料源于各大C++参考信息网站/C++标准文档和Wikipedia.

(表示打这个好累的说OwO博主表示手打了好几天才码完这么多字)

1.概述

首先, 什么是STL?

STL, 即标准模板库, 全称Standard Template Library , 主要包含4个组件, 即算法, 函数, 容器, 迭代器. 这里的函数似乎主要指函数式编程(FP)中的函数而不是平常概念中的函数...标准模板库具有强大的可扩展性, 包含很多常用算法/数据结构/常用操作, 极大地增加了代码的重用, 几年前在NOI系列赛中解禁后为C++语言选手提供了很多便利.

为了与用户的命名区分, STL中的内容都在 namespace std 中, 可能许多人会偷懒使用 using namespace std; , 但是博主个人不建议大家使用这种做法. 因为这样可能会造成潜在的访问元素歧义. 因为在使用该语句后, 如果在全局也有声明同名变量/函数且调用时未显式指定命名空间为全局或 std 的话就可以同时解释为调用标准库或访问自己定义的标识符. 容易出现欧洲合格认证(CE)的情况w

(顺便说一句其实C++里的模板是图灵完全的, 据说有dalao可以用这个在编译期可以打出表来)

2.内容

STL的逻辑是"将待操作的数据与要进行的操作分开", 于是便有了如下的三个概念:

1.容器: 用于存放数据的

2.迭代器: 用于指出数据的位置, 或成对使用来划定一个区间 (注: STL区间一般都是左闭右开的半开区间.)

3.算法: 要执行的操作.

2.1 容器

STL中, 容器是"包含/放置数据的地方". STL中的容器使用的都是堆内存, 而且大多数情况下支持动态分配(不会写指针和动态内存的选手の福利)所以内存利用率多数都很高.

多说几句, 对于STL容器的对象数组坚决不能memset.....STL 容器所存储的静态内存内部数据都是指针或者其他标志位, memset之后直接乱掉然后没法用了w

容器又分以下几类:

2.1.1 顺序容器

顺序容器中保存的是一个有序的数据集合, 实现能按顺序访问的数据结构.

也就是说你放进顺序容器的数据是保持原来放进去时的顺序的. 关联容器内部实现是平衡树, 只能按元素从大到小访问.(当然也有时候我们确实也希望这么做w所以要分两类嘛(雾))

STL中的顺序容器包含以下5个:

std::vector std::list std::forward_list std::deque std::array

由于 std::list 和 std::forward_list 就是链表平常手写一个也不费事功能过于简单而且时间复杂度常数偏大OI中一般不使用所以略(其实是博主懒癌发作)

然后 std::array 是C++11起支持的特性, 提供一个更加安全的C风格数组(然而这个是定长的...除了比较安全以及可以快速获取长度/剩余空间等等信息之外和普通数组似乎没卵区别)所以也略(逃)

2.1.1.1 std::vector

std::vector 定义于头文件 <vector> , 在OI中一般用于作为变长数组. 元素在其中连续存储, 也就是说不仅按下标随机访问是严格 $O(1)$ 时间复杂度, 而且除了迭代器外, 常规指针也可以用于访问它的内容. 最重要的是在尾部插入/删除元素的均摊时间复杂度为 $O(1)$ ,在OI中无需担心时间复杂度问题(虽然可能有丧病出题人卡你常数233).

其实它也支持在首部和中间插入数据, 但是时间复杂度 $O(n)$ ...

vector似乎是用了一些启发式的奇技淫巧内存管理方式, 每次预分配一定的空间, 当预分配的这部分被用完时开一块新的连续内存并将所有原来的元素copy过去. 当预分配大小经过仔细计算后就可以做到尾部插入元素操作均摊 $O(1)$ 的时间复杂度.

模板参数如下

1 template< 2 class T, 3 class Allocator = std::allocator<T> 4 > class vector;

第一个参数 class T 指定元素类型, 第二个参数 class Allocator 指定内存分配方式(这个参数有默认值所以平常一般不用管, 除非手写了个内存池出来让STL用)

例:声明一个成员为 int , 内存分配方式默认的 std::vector 的代码如下:

std::vector<int> v;

然后是 std::vector 所支持的操作(成员函数):

1. std::vector::operator= $O(n)$

将另一个vector中的所有值copy进该vector(平常似乎没卵用)

2. std::vector::at $O(1)$

这个函数用来按下标访问vector中的值(返回引用), 参数为一个下标. 与用方括号的效果基本上是等价的. 但是用这个函数来访问vector中的值之前会先检查一下下标是否越界, 如果越界则抛出异常 std::out_of_range , 控制台也会输出相关信息比如所在行号所在文件等等. 如果用方括号的话就可能出现各种玄学错误比如修改了其他变量的值或者破坏内存结构影响以后对内存的访问, 再或者直接崩溃RE...

3. std::vector::operator[] $O(1)$

最常用的操作, 按下标访问vector中的值. 当做数组来用233 复杂度$O(1)$

4. std::vector::front $O(1)$

返回vector首部元素的引用. 用于对首部元素进行修改/读取. 注意如果是空vector的话访问结果是未定义行为(也就是天晓得会发生什么, 因平台和编译器而异)

5. std::vector::back $O(1)$

返回vector的尾部元素的引用, 用于对尾部元素进行修改/读取. 注意这次STL没有日常左闭右开.

6. std::vector::data $O(1)$

这个函数返回的是指向vector首部元素的指针(不是迭代器. 不是迭代器. 重要的事情说三遍, 不是迭代器) , 比如vector内部元素的类型为 $T$ , 则此函数的返回值类型为 $T*$.

7. std::vector::begin $O(1)$

返回指向vector首部元素的迭代器. 迭代器类型为随机访问迭代器(具体参见下文).

8. std::vector::end $O(1)$

返回指向vector尾部元素的后一个元素. STL的日常左闭右开区间的结果=w=

9. std::vector::rbegin $O(1)$

返回指向vector尾部元素的反向迭代器. 倒序枚举专用(雾) (其实貌似等于一个自增时实际下标自减的向前迭代器?)

10. std::vector::empty $O(1)$

如果vector为空的话返回true, 否则为false. 常用于各种while循环里 (诶好像stack/queue/priority_queue的empty操作更常用在while里吧)

11. std::vector::size $O(1)$

返回vector中包含的元素个数.

12. std::vector::resize $O(n)$

这个函数参数为一个整数, 可以调整vector的大小使其可以容纳参数指定的元素.

13. std::vector::clear $O(n)$

将vector清空.

14. std::vector::push_back 均摊 $O(1)$

向vector尾部插入一个值. 除了下标访问操作之外最常用的233

15. std::vector::pop_back 均摊 $O(1)$

删除vector尾部的值.

16. std::vector::push_front $O(n)$

向vector首部插入一个值. 因为要移动整个vector中的元素所以复杂度为 $O(n)$. 很少使用. 对应的 std::vector::pop_front 也是同一个时间复杂度, 原因一样.

17.六种大小比较运算符 != == > >= < <= $O(n)$

按字典序比较两个vector中的内容.

2.1.1.2 std::deque