C++ STL 概念笔记

本文介绍了有关 C++ 的 STL 相关概念。

写在前面

0xfaner 一直号称自己是队内的数据结构选手,但是某天他发现自己其实连 STL 都一知半解。于是他决定做一个围绕 STL 展开的专题笔记。

本文将随着 0xfaner 对 STL 概念理解的加深而不断更新,敬请期待。

STL 简介

STL 是 Standard Template Library 的缩写,意为标准模板库。是一个具有工业强度的,高效的 C++ 程序库。它被容纳于 C++ 标准程序库 C++ Standard Library 中,是 ANSI/ISO C++ 标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法,在算法竞赛中具有十分广泛的应用。

STL 包括六个部分,分别是

  • 容器 containers:一种可以持有其他对象或指向其他对象的指针的对象类型。

  • 迭代器 iterators:能够用来遍历 STL 容器中的部分或全部元素的一种对象,每个迭代器对象代表容器中的确定的地址。

  • 算法 algorithms:具有特定功能的一类函数模板。

  • 空间配置器 allocator:用于管理动态空间的分配与释放的组件。

  • 配接器 adapters:用于提供接口映射的一个模板类。

  • 仿函数 functors:通过重载 operator() 运算符来行使函数功能的类。

STL 将 在数据上执行的操作要执行操作的数据 分开,分别以如下概念指代:

  • 容器 containers:包含、放置数据的地方。

  • 迭代器 iterators:在容器中指出一个位置、或成对使用以划定一个区域,用来限定操作所涉及到的数据范围。

  • 算法 algorithms:要执行的操作。

容器 Containers

容器是一种可以持有其他对象或指向其他对象的指针的对象类型。

容器分为两种

  • 序列式容器(有序集)sequence containers

    • 向量 vector:动态数组,兼容 C 语言数组,支持下标访问。

    • 列表 list:可以理解为双向链表。

    • 单向列表 forward_list:可以理解为单向链表。

    • 双端队列 deque:可以看作能在两端插入或删除元素的 vector

    • 数组 array:可视为内置数组的封装。

  • 关系式容器(无序集)associative containers

    • 集合 set:不重复元素的集合

    • 多重集合 multiset:与 set 类似,不过允许重复元素。

    • 映射 map:关联数组,元素为键值对 pair,表示键和值的映射。

    • 多重映射 multimap:与 map 类似,不过允许重复键值。

    • 键值对 pair:表示键和值的映射。

迭代器 Iterators

迭代器是能够用来遍历 STL 容器中的部分或全部元素的一种对象,每个迭代器对象代表容器中的确定的地址。

迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素。从这一点上看,迭代器和指针类似。

C++更趋向于使用迭代器而不是下标操作,因为标准库为每一种标准容器定义了一种迭代器类型,而只有少数容器支持下标操作访问容器元素。

迭代器分为五种:

  • 输入迭代器 Input iterator:只读,只支持自增运算

  • 输出迭代器 Output iterator:只写,只支持自增运算

  • 前向迭代器 Forward iterator:读和写,只支持自增运算

  • 双向迭代器 Bidirectional iterator:读和写,支持自增和自减运算

  • 随机访问迭代器 Random access iterator:读和写,支持完整的迭代器算术运算

算法 Algorithm

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。

在 STL 中,算法表现为具有特定功能的一类函数模板。根据这些算法各自的功能可以分为九类:

  • 查找算法:判断容器中是否包含某个值

    • adjacent_find:在 iterator 对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的 ForwardIterator。否则返回 last。重载版本使用输入的二元操作符代替相等的判断。

    • binary_search:在有序序列中查找 value,找到返回 true。重载的版本实用指定的比较函数对象或函数指针来判断相等。

    • count:利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数。

    • count_if:利用输入的操作符,对标志范围内的元素进行操作,返回结果为 true 的个数。

    • equal_range:功能类似 equal,返回一对 iterator,第一个表示 lower_bound,第二个表示 upper_bound

    • find:利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较。当匹配时,结束搜索,返回该元素的一个 InputIterator

    • find_end: 在指定范围内查找”由输入的另外一对 iterator 标志的第二个序列”的最后一次出现。找到则返回最后一对的第一个 ForwardIterator,否则返回输入的”另外一对”的第一个 ForwardIterator。重载版本使用用户输入的操作符代替等于操作。

    • find_first_of:在指定范围内查找”由输入的另外一对 iterator 标志的第二个序列”中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。

    • find_if:使用输入的函数代替等于操作符执行 find

    • lower_bound:返回一个 ForwardIterator,指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。

    • upper_bound:返回一个 ForwardIterator,指向在有序序列范围内插入 value 而不破坏容器顺序的最后一个位置,该位置标志一个大于 value 的值。重载函数使用自定义比较操作。

    • search:给出两个范围,返回一个 ForwardIterator,查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置,查找失败指向 last1。重载版本使用自定义的比较操作。

    • search_n:在指定范围内查找 val 出现 n 次的子序列。重载版本使用自定义的比较操作。

  • 排序与通用算法:提供元素排序策略

    • inplace_merge:合并两个有序序列,结果序列覆盖两端范围。重载版本使用输入的操作进行排序。

    • merge:合并两个有序序列,存放到另一个序列。重载版本使用自定义的比较操作。

    • nth_element:将范围内的序列重新排序,使所有小于第 n 个元素的元素都出现在它前面,而大于它的都出现在后面。重载版本使用自定义的比较操作。

    • partial_sort:对序列做部分排序,被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。

    • partial_sort_copy:与 partial_sort 类似,不过将经过排序的序列复制到另一个容器。

    • partition:对指定范围内元素重新排序,使用输入的函数,把结果为 true 的元素放在结果为 false 的元素之前。

    • random_shuffle:对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。

    • reverse:将指定范围内元素重新反序排序。

    • reverse_copy:与 reverse 类似,不过将结果写入另一个容器。

    • rotate:将指定范围内元素移到容器末尾,由 middle 指向的元素成为容器第一个元素。

    • rotate_copy:与 rotate 类似,不过将结果写入另一个容器。

    • sort:以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。

    • stable_sort:与 sort 类似,不过保留相等元素之间的顺序关系。

    • stable_partition:与 partition 类似,不过保留容器中的相对顺序。

  • 删除和替换算法:

    • copy:复制序列

    • copy_backward:与 copy 相同,不过元素是以相反顺序被拷贝。

    • iter_swap:交换两个 ForwardIterator 的值。

    • remove:删除指定范围内所有等于指定元素的元素。注意,该函数不是真正删除函数。内置函数不适合使用 removeremove_if 函数。

    • remove_copy:将所有不匹配元素复制到一个制定容器,返回 OutputIterator 指向被拷贝的末元素的下一个位置。

    • remove_if:删除指定范围内输入操作结果为 true 的所有元素。

    • remove_copy_if:将所有不匹配元素拷贝到一个指定容器。

    • replace:将指定范围内所有等于 vold 的元素都用 vnew 代替。

    • replace_copy:与 replace 类似,不过将结果写入另一个容器。

    • replace_if:将指定范围内所有操作结果为 true 的元素用新值代替。

    • replace_copy_if:与 replace_if 类似,不过将结果写入另一个容器。

    • swap:交换存储在两个对象中的值。

    • swap_range:将指定范围内的元素与另一个序列元素值进行交换。

    • unique:清除序列中重复元素,和 remove 类似,它也不能真正删除元素。重载版本使用自定义比较操作。

    • unique_copy:与 unique 类似,不过把结果输出到另一个容器。

  • 排列组合算法:提供计算给定集合按一定顺序的所有可能排列组合

    • next_permutation:取出当前范围内的排列,并重新排序为下一个排列。重载版本使用自定义的比较操作。

    • prev_permutation:取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回 false。重载版本使用自定义的比较操作。

  • 算术算法:

    • accumulate:iterator 对标识的序列段元素之和,加到一个由 val 指定的初始值上。重载版本不再做加法,而是传进来的二元操作符被应用到元素上。

    • partial_sum:创建一个新序列,其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法。

    • inner_product:对两个序列做内积(对应元素相乘,再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作。

    • adjacent_difference:创建一个新序列,新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。

  • 生成和异变算法:

    • fill:将输入值赋给标志范围内的所有元素。

    • fill_n:将输入值赋给 firstfirst+n 范围内的所有元素。

    • for_each:用指定函数依次对指定范围内所有元素进行迭代访问,返回所指定的函数类型。该函数不得修改序列中的元素。

    • generate:连续调用输入的函数来填充指定的范围。

    • generate_n:与 generate 函数类似,填充从指定 iterator 开始的 n 个元素。

    • transform:将输入的操作作用与指定范围内的每个元素,并产生一个新的序列。重载版本将操作作用在一对元素上,另外一个元素来自输入的另外一个序列。结果输出到指定容器。

  • 关系算法:

    • equal:如果两个序列在标志范围内元素都相等,返回 true。重载版本使用输入的操作符代替默认的等于操作符。

    • includes:判断第一个指定范围内的所有元素是否都被第二个范围包含,使用底层元素的<操作符,成功返回 true。重载版本使用用户输入的函数。

    • lexicographical_compare:比较两个序列。重载版本使用用户自定义比较操作。

    • max:返回两个元素中较大一个。重载版本使用自定义比较操作。

    • max_element:返回一个 ForwardIterator,指出序列中最大的元素。重载版本使用自定义比较操作。

    • min:返回两个元素中较小一个。重载版本使用自定义比较操作。

    • min_element:返回一个 ForwardIterator,指出序列中最小的元素。重载版本使用自定义比较操作。

    • mismatch:并行比较两个序列,指出第一个不匹配的位置,返回一对 iterator,标志第一个不匹配元素位置。如果都匹配,返回每个容器的 last。重载版本使用自定义的比较操作。

  • 集合算法:

    • set_union:构造一个有序序列,包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。

    • set_intersection:构造一个有序序列,其中元素在两个序列中都存在。重载版本使用自定义的比较操作。

    • set_difference:构造一个有序序列,该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。

    • set_symmetric_difference:构造一个有序序列,该序列取两个序列的对称差集。

  • 堆算法:

    • make_heap:把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。

    • pop_heap:并不真正把最大元素从堆中弹出,而是重新排序堆。它把 firstlast-1 交换,然后重新生成一个堆。可使用容器的 back 来访问被”弹出”的元素或者使用 pop_back 进行真正的删除。重载版本使用自定义的比较操作。

    • push_heap:假设 firstlast-1 是一个有效堆,要被加入到堆的元素存放在位置 last-1,重新生成堆。在指向该函数前,必须先把元素插入容器后。重载版本使用指定的比较操作。

    • sort_heap:对指定范围内的序列重新排序,它假设该序列是个有序堆。重载版本使用自定义比较操作。

空间配置器 Allocator

空间配置器 allocator 除了负责空间(包括内存在内的一切能调用的存储介质)的分配和释放,还负责对象的构造和析构,知道类型才能调用对象的构造和析构函数。

STL 所有的容器都需要空间配置器 allocator,一般我们不会接触到,因为容器会选择默认的 allocator

空间配置器分为两类:

  • 一级空间配置器 malloc_alloc_template

  • 二级空间配置器 default_alloc_template

配接器 Adapters

配接器 adapters 是用于提供接口映射的一个模板类。其接受一种已有的类型,使其行为看起来像一种不同的类型。

容器、迭代器和函数都有适配器,分别是

  • 容器适配器 container adapters:

    • stack:使用 deque 作为底层,只允许在一端插入或删除元素,即先进后出 first-in last-out

    • 队列 queue:使用 deque 作为底层,只允许在一端插入元素,在另一端删除元素,即先进先出 first-in first-out

    • 优先队列 priority_queue:使用 vector 作为底层,只允许访问/弹出优先级最高的元素,即最高级先出 first-in largest-out

  • 迭代器适配器 iterator adapters

    • 安插型迭代器 insert iterators:用于安插元素的迭代器。

      • 尾部安插器 back inserters

      • 头部安插器 front inserters

    • 一般性按插器 general inserters

    • 流迭代器 stream iterators:用于读写流 stream 的迭代器。

      • 输入流迭代器 istream_iterator

      • 输入流迭代器 ostream_iterator

    • 逆向迭代器 reverse iterators:即反向迭代器,所有容器都可以通过成员函数 rbegin()rend() 分别产生出 reverse iterator,它们共同定义一个半开区间。

  • 函数适配器 function adapter:用于让一个函数对象表现出另外一种类型的函数对象的特征。通过不同函数适配器 function adapter 的绑定,组合和修饰能力,可以实现强大的功能,配合 STL 泛型算法完成复杂功能。

    • 绑定器 binder:通过把二元函数对象的一个实参绑定到一个特殊的值上,将其转换成一元函数对象。

    • 取反器 negator:是一个将函数对象的值翻转的函数适配器。

仿函数 Functors

仿函数 functor 又称为函数对象 function object,是一种通过重载 operator() 运算符来行使函数功能的类。

需要强调的是,仿函数 functors 是一种类而非函数。

与函数相比它具有三大优势:

  • 仿函数比一般函数更加灵活。

  • 仿函数有类型识别,可以作为模板参数。

  • 仿函数比函数和指针执行效率更高。

仿函数 functors 主要功能是为了搭配 STL 算法 algorithm 使用,单独使用仿函数的情况比较少。