高级程序设计

22 - STL

2020-04-23 14:00 CST
2020-04-23 14:48 CST
CC BY-NC 4.0

什么是STL

除了从C标准库保留下来的一些功能以外,C++还提供了一个基于模板实现的标准模板库(Standard Template Library,简称STL)。

STL基于模板实现了一些面向序列数据的表示以及常用的操作。

STL只吃了一种抽象的编程模式,隐藏了一些低级的程序元素,如数组、链表、循环等。

STL包含什么

  • 容器类模板:容器用于存储序列化的数据,如向量、队列、栈、集合等;
  • 算法函数模板:算法用于对容器中的数据元素进行一些常用操作,如排序、统计等;
  • 迭代器类模板:
    • 迭代器实现了抽象的指针功能,它们指向容器中的数据元素,用于对容器中的数据元素进行遍历和访问。
    • 迭代器是容器和算法之间的桥梁:传给算法的不是容器,而是指向容器中元素的迭代器。算法通过迭代器实现对容器中数据元素的访问,这样使得算法与容器保持独立,提高算法的通用性。

STL的主要容器

  • vector:用于需要快速定位(访问)任意位置上的元素以及在元素序列的尾部增加/删除元素的场合,内部使用动态数组实现。
  • list:用于经常在元素序列中任意位置上插入/删除元素的场合,使用双向链表实现。
  • deque:用于主要在元素序列的两端增加/删除元素以及需要快速定位(访问)任意位置上的元素的场合,使用分段的连续空间结构实现。
  • stack:用于仅在元素序列的尾部增加/删除元素的场合,可基于dequelistvector来实现。
  • queue:用于仅在元素序列的尾部增加、头部删除元素的场合,可基于dequelist来实现。
  • priority_queue:与queue的操作相似,但每次增加/删除元素后对元素位置进行调整,使得头部元素总是最大(优先级最高)的。可基于dequevector来实现。
  • mapmultimap:用于需要根据关键字来访问元素的场合。容器中每个元素是一个pair元素类型,第一个成员为关键字,第二个成员为值。对于map,不同元素的关键字不能相同;而对于multimap不同元素的关键字可以相同。通常使用二叉树结构(红黑树)实现。
  • setmultiset:分别是mapmultimap的特例,每个元素只有关键字而没有值(或者说关键字和值合一)。
  • basic_string:元素为字符类型的vector,提供了一系列与字符串相关的操作。stringwstring分别是它的两个特例。

C++11提供了unordered_前缀的容器。

容器的基本操作

容器类模板提供了一些成员函数来实现容器的基本操作,包括

  • 往容器中增加元素
  • 从容器中删除元素
  • 获取容器中指定位置的元素
  • 在容器中查找元素
  • 获取容器首/尾元素的迭代器等等

这些成员函数往往具有通用性。

  • push_frontpop_front:在容器头部增加/删除元素,适用于listdeque
  • push_backpop_back:在容器尾部增加/删除元素,适用于vectorlistdeque
  • pushpop:在容器尾部/头部增加/删除元素,适用于stackqueuepriority_queue
  • frontback:获取容器中第一个和最后一个元素,适用于vectorlistdequequeue
  • top:获取容器头部/尾部元素,适用于stackpriority_queue
  • at:获取容器中某个位置上的元素(会进行越界检查),适用于vectordequebasic_string
  • operator[]:获取容器中某个位置上的元素,适用范围同上;或获取某个关键字所关联的值,适用于map
  • beginend:获取指向容器第一个元素位置/最后一个元素的下一个位置的迭代器,适用于除queuestackpriority_queue以外的所有容器
  • insert:在指定位置之前插入一个或多个元素,返回插入的第一个元素的迭代器,适用于vectorlistdeque
  • erase:删除指定位置的一个或多个元素,返回删除后下一个元素的迭代器,适用于vectorlistmapsetbasic_string
  • find:根据关键字在容器中查找元素,返回指向元素的迭代器或最后一个元素的下一个位置(未找到),适用于mapset
  • size:获取容器中元素的个数
  • max_size:获取容器中所允许元素的最大个数,适用于除stackqueuepriority_queue以外的所有容器

如果容器的元素类型是一个类,则针对该类可能需要:

  • 自定义拷贝构造函数和赋值操作符重构函数,因为对容器进行的一些操作中可能会创建新的元素或进行元素间的赋值。
  • 重载小雨运算符,因为对容器进行的一些操作中可能需要进行元素比较运算。

迭代器

迭代器(iterator)实现了抽象的指针(智能指针)功能,它们用于指向容器中的元素,对容器中的元素进行访问和遍历。

在STL中,迭代器是作为类模板来实现的,分为以下类型:

  • 输出迭代器OutIt
    • 可以修改它所指向的容器元素
    • 间接访问操作*
    • ++操作
  • 输入迭代器InIt
    • 只能读取它所指向的容器元素
    • 间接访问操作*和元素成员间接访问->
    • ++==!=操作
  • 前向迭代器FwdIt
    • 可以读取/修改它所指向的容器元素
    • 间接访问操作*和元素成员间接访问->
    • ++==!=操作
  • 双向迭代器BidIt
    • 可以读取/修改它所指向的容器元素
    • 间接访问操作*和元素成员间接访问->
    • ++--==!=操作
  • 随机访问迭代器RanIt
    • 可以读取/修改它所指向的容器元素
    • 间接访问操作*、元素成员间接访问->和下标访问元素操作[]
    • ++--+-+=-===!=<><=>=操作

对于vectordequebasic_string容器类,与它们关联的迭代器类型为随机访问迭代器。

对于listmapset容器类,与它们关联的迭代器类型为双向迭代器。

queuepriority_queuestack容器类不支持迭代器。

迭代器之间的相容关系:左边的迭代器可以用右边的迭代器去替代:

InIt/OutIt <- FwdIt <- BidIt <- RanIt

算法

STL提供了一系列通用的对容器中元素进行操作的函数模板,称为算法(algorithm)。

STL算法实现了对序列元素的一些常规操作,主要包括:

  • 调序算法
  • 编辑算法
  • 查找算法
  • 算数算法
  • 集合算法
  • 堆算法
  • 元素遍历算法

大部分STL算法都是遍历指定容器中某范围内的元素,对满足条件的元素执行某项操作。算法的内部实现往往隐含着循环操作,但对于使用者是隐藏的。使用者只需要提供容器(迭代器)、操作条件以及可能的自定义操作,而算法的控制逻辑则由算法内部实现,体现了一种抽象的编程模式。

算法与容器之间的关系

在STL中,不是把容器传给算法,而是把容器的某些迭代器传给他们,在算法中通过迭代器来访问和遍历相应容器中的元素。

这样做的好处是:使得算法不依赖于具体的容器,提高了算法的通用性。

算法的操作范围

用算法对容器中的元素进行操作时,大部分需要用两个迭代器来指出要操作的元素的范围。如

void sort(RanIt first, RanIt last);

其中last是最后一个元素的下一个位置。

有些算法有多个操作范围,此时除了第一个范围外,其他的范围可以不指定最后一个元素位置。如

OutIt copy(InIt src_first, InIt src_last, OutIt dst_first);

一个操作范围的两个迭代器必须属于同一个容器,但不同操作范围的迭代器可以属于不同的容器。

算法的自定义操作条件

有些算法可以让使用者提供一个函数或函数对象来作为自定义操作条件(或称为谓词),其参数类型为对应容器的元素类型,返回值类型为bool

自定义操作条件可分为:

  • Pred:一元谓词,需要一个元素作为参数;
  • BinPred:二元谓词,需要两个元素作为参数。

例如:

size_t count_if(InIt first, InIt last, Pred cond);
void sort(RanIt first, RanIt last, BinPred comp);

算法的自定义操作

有些算法可以让使用者提供一个函数或函数对象作为自定义操作,其参数和返回值类型由相应的算法决定。

自定义操作可分为:

  • OpFun:一元操作,需要一个参数
  • BinOpBinFun:二元操作,需要两个参数

例如:

Fun for_each(InIt first, InIt last, Fun f);

T accumulate(InIt first, InIt last, T val);  // 默认为operator+累积
T accumulate(InIt first, InIt last, T val, BinOp op);  // op决定累积的含义

OutIt transform(InIt src_first, InIt src_last, OutIt dst_first, Op f);  // 一元变换
OutIt transform(InIt1 src_first1, InIt1 src_last1, InIt2 src_first2, OutIt dst_first, BinOp f);  // 二元变换