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使用,单独使用仿函数的情况比较少。