C++标准模板库:容器

本文是《C++ Primer Plus(第6版)中文版》的笔记。

标准模板库 STL

STL提供了一组表示容器、迭代器、函数对象和算法的模板,容器是一个与数组类似的单元,可以存储若干个值。STL容器是同质的,即存储的值的类型相同;算法是完成特定任务(如对数组进行排序或在链表中查找特定值)的处方;迭代器能够用来遍历容器的对象,与能够遍历数组的指针类似,是广义指针;函数对象是类似于函数的对象,可以是类对象或函数指针(包括函数名,因为函数名被用作指针),STL使得能够构造各种容器(包括数组、队列和链表)和执行各种操作(包括搜索、排序和随机排列)。

泛型编程

C++中的STL就是一种泛型编程,面向对象编程关注的是编程的数据方面,而泛型编程关注的是算法。泛型编程旨在编写独立于数据类型的代码,模板就是C++中编写通用程序的工具。

为何使用迭代器

模板使得算法独立于存储的数据类型,而在STL中迭代器(iterator)使算法独立于使用的容器类型。

为达到上述目的,必须对迭代器和容器进行设计,如迭代器需要重载*++等运算符,容器中增加了可用end()获取的超尾元素等。

迭代器类型

为满足不同算法的要求,STL中定义了5中类型的迭代器,并根据所需的迭代器类型对算法进行描述。5种迭代器为输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器。5种迭代器有一些共同点,如都可以执行解除引用操作,即都定义了*运算符,也都可以使用==!=比较相等或不等(但可能被重载)。5种迭代器详细说明如下:

输入迭代器

这里“输入”是从程序的角度说的,即来自容器的信息被视为输入。

输入迭代器的解引用操作可以读取容器中的值,但不一定能让程序修改其值。需要输入迭代器的算法将不会修改容器中的值。输入迭代器支持前缀和后缀的++运算符,以能够遍历容器中的所有值。输入迭代器是单向迭代器,可以递增,不能倒退。

输出迭代器

“输出”也是从程序的角度说的,程序的输出即是容器的输入。其解除引用操作可以写但不能读。如果是单通行只写算法,则可以使用输出迭代器。

正向迭代器

正向迭代器只使用++运算符来遍历容器。与输入和输出迭代器不同的是,它总是按照相同的顺序遍历一系列值。将正向迭代器递增后,仍然可以对前边的迭代器解除引用(如果保存了它),并可以得到相同的值。因此正向迭代器可用于多次通行算法。正向迭代器可读可写,如果用const修饰则使得只能读取。

双向迭代器

双向迭代器支持所有正向迭代器的特性,并且还支持前缀和后缀的--运算。

随机访问迭代器

随机访问迭代器具有双向迭代器的所有特性,同时添加了支持随机访问的操作(如指针增加运算)和用于对元素进行排序的关系运算符。

迭代器层次结构

迭代器的类型形成了一个层次结构。如正向迭代器具有输入迭代器和输出迭代器的全部功能,同时还有自己的功能;双向迭代器具有正向迭代器的全部功能,同时还有自己的功能;随机访问迭代器具有正向迭代器的全部功能,同时还有自己的功能等。

下表总结了5种迭代器的功能,其中i表示迭代器,n表示整数:

迭代器功能 输入 输出 正向 双向 随机访问
解除引用读取 Y N Y Y Y
解除引用写入 N Y Y Y Y
固定和可重复排序 N N Y Y Y
++i, i++ Y Y Y Y Y
--i, i-- N N N Y Y
i[n] N N N N Y
i+n N N N N Y
i-n N N N N Y
i+=n N N N N Y
i-=n N N N N Y

在编写算法时,应尽可能使用要求最低的迭代器,并让其适用于容器的最大区间。

概念、改进和模型

  • 概念(concept):用于描述算法对于迭代器实现的一系列要求,如输入迭代器概念、正向迭代器概念等等
  • 改进(refinement):用于表示概念之间的继承关系,如双向迭代器是对正向迭代器概念的一种改进
  • 模型(model):概念的具体实现被称为模型,如指向int的常规指针是一个随机访问迭代器模型,也是一个正向迭代器模型,因为它满足该概念的所有要求

将指针用作迭代器

迭代器是广义的指针,指针满足所有迭代器要求。迭代器是STL算法的接口,而指针是迭代器,因此STL算法可以使用指针来对基于指针的非STL容器进行操作。

概念、改进和模型

例如可以对数组调用STL的排序算法:

1
2
3
4
const int SIZE = 100;
double arr[SIZE];
// ...
sort(arr , arr + SIZE);

又例如,STL的copy()操作也可以将一个数组复制到一个矢量中:

1
2
3
int cast[10] = {1,2,3,4,5,6,7,8,9,0};
vector<int> dice(10);
copy(casts , casts+10 , dice.begin());

STL中有ostream_iterator迭代器模板,它是输出迭代器概念的一个模型, 也是一个适配器,可以将一些其他接口转换为STL使用的接口,创建方法如下:

1
2
#include <iterator>
ostream_iterator<int,char> out_iter(cout," ");

上述定义的输出流迭代器中,两个迭代器参数中,第一个int表示发送给输出流的数据类型,char表示输出流使用的字符类型(另一个可能的值为wchar_t)。构造函数的第一个参数cout指定了要使用的输出流(也可以是用于文件的输出流),第二个参数字符串是发送给输出流的每个数据项后显示的分隔符。

1
*out_iter++ = 15;

表示将15和空格发送给cout管理的输出流中,并且为下一个输出操作做好准备。所以也可以有以下的用法:

1
copy(dice.begin(), dice.end(), out_iter); //将矢量dice中的内容发送至输出流

ostream_iterator类似,STL中还有istream_iterator,是一个输入迭代器概念的模型。

其他有用的迭代器

反向迭代器reverse_iterator,对reverse_iterator执行递加操作将会导致其递减,这是为了简化对已有函数的使用。

插入迭代器back_insert_iteratorfront_insert_iteratorinsert_iterator也是为了提高STL算法通用性而设计,back_insert_iterator将元素插入到容器的尾部,而front_insert_iterator将元素插入到容器的前端。insert_iterator将元素插入到其构造时构造参数指定的位置前边。插入迭代器的使用有一些限制,如back_insert_iterator可用于vector这样的允许在尾部增加元素的容器,但front_insert_iterator却不可以。front_insert_iterator可用于queue,允许在前段插入。insert_iterator不受插入位置的限制,可以用在vector中在最前端插入。这些迭代器在声明时需要将容器作为模板参数,将实际的容器标识符作为构造函数的参数,例如:

1
back_insert_iterator<vector<int> > back_iter(dice);

front_insert_iterator的声明方式与上边类似。在声明insert_iterator时需要额外指定插入位置作为构造参数:

1
insert_iterator<vector<int> > insert_iter(dice, dice.begin());

容器

容器种类

STL中有容器概念和容器类型,概念是具有名称(如容器、序列容器、关联容器等)的通用类别;容器类型是可用于创建具体容器对象的模板。

容器概念

容器概念指定了所有STL容器类都必须满足的一系列要求:

  • 容器是存储其它对象的对象,被存储的对象必须是同一类型的(可以是对象或内置类型值);

  • 当容器过期时(销毁),存储在其中的数据也会过期(如果存储的是指针,则其指向的数据不一定过期);

  • 只有可复制构造和可赋值的类型才可以存储在容器中(C++11中又增加了复制插入CopyInsertable和移动插入MoveInsertable);

  • 下表是所有的容器都提供的特征和操作:

表达式 返回类型 说明 复杂度
X::iterator 指向T的迭代器类型 满足正向迭代器要求的任何迭代器 编译时间
X::value_type T T的类型 编译时间
X u 创建一个名为u的空容器 固定
X() 创建一个匿名空容器 固定
X u(a) 调用复制构造函数后u==a 线性
X u = a 作用同X u(a) 线性
r = a X& 调用赋值运算后r==a 线性
(&a)->~X() void 对容器中每个元素应用析构函数 线性
a.begin() 迭代器 返回指向容器第一个元素的迭代器 固定
a.end() 迭代器 返回超尾元素迭代器 固定
a.size() 无符号整型 返回元素的个数,等价于a.end() - a.begin() 固定
a.swap(b) void 交换a和b的内容 固定
a==b 可转换为bool 如果a和b的长度相同,且a中每个元素都等于(==)b中相应元素,则为真 线性
a!=b 可转换为bool 返回!(a==b) 线性

(表中X表示容器类型,T表示存储的对象类型,ab表示类型为X的值,r表示类型为X&的值,u表示类型为X标识符。)

C++11新增的容器要求

C++11中增加了右值引用的概念,及移动构造、移动赋值操作,也增加了对通用容器的要求:

表达式 返回类型 说明 复杂度
X u(rv) 调用移动构造函数后,u的值与rv的原始值相同 线性
X u = rv 同X u(rv) 线性
a = rv X& 调用移动赋值运算符后,u的值与rv的原始值相同 线性
a.cbegin() const_iterator 返回指向容器第一个元素的const迭代器 固定
a.cend() const_iterator 返回指向容器超尾元素的const迭代器 固定

(表中rv表示类型为X的非常量右值,X::iterator需要满足正向迭代器的要求。)

序列

序列(sequence)是对通用容器概念的一种重要改进。STL中有7种序列:deque、forward_list(C++11)、list、queue、priority_queue、stack和vector。序列概念要求迭代器至少是正向迭代器,以保证元素按照特定顺序排列,不会在两次迭代之间发生变化。array也被归类到序列容器,虽然它并不满足序列的所有要求。

序列要求其元素按照严格的线形顺序排列。数组和链表都是序列,但分支结构不是。序列中的元素可以执行诸如将值插入到特定位置、删除特定区间等操作,参见下表:

表达式 返回类型 说明
X a(n,t) 声明一个名为a的由n个t值组成的序列
X(n,t) 创建一个由n个t值组成的匿名序列
X a(i,j) 声明一个名为a的序列,并将其初始化为区间[i,j)的内容
X(i,j) 创建一个匿名序列,并将其初始化为区间[i,j)的内容
a.insert(p,t) 迭代器 将t插入到p的前面
a.insert(p,n,t) void 将n个t插入到p的前面
a.insert(p,i,j) void 将区间[i,j)中的元素插入到p的前面
a.erase(p) 迭代器 删除p指向的元素
a.erase(p.q) 迭代器 删除区间[p,q)中的元素
a.clear() void 等价于erase(begin(),end())

(表中X表示容器类型,a表示类型为X的值,t表示存储的对象类型T的值,n表示整数,pqij表示迭代器。)

序列概念的模型deque,list,queue,priority_queue,stack和vector支持上表中的所有操作。除此之外,还有一些其他操作,见下表,下表中的所有操作的时间复杂度均为固定时间:

表达式 返回类型 含义 容器
a.front() T& *a.begin() vector、list、deque
a.back() T& *–a.end() vector、list、 deque
a.push_front(t) void a.insert(a.begin(), t) list、deque
a.push_back(t) void a.insert(a.end(), t) vector、 list、deque
a.pop_front(t) void a.erase(a.begin()) list、deque
a.pop_back(t) void a.erase(–a.end()) vector、list、deque
a[n] T& *(a.begin() + n) vector、deque
a.at(n) T& *(a.begin() + n) vector、deque

在上表中,a[n]a.at(n)的差异在于当n查出容器有效区间时,a.at(n)会检查边界并抛出异常 out_of_rangevector不支持push_front()pop_front()是因为在vector的头部插入或删除新元素会引发复杂度为线性时间而非固定时间的操作。

具体说明几种序列容器类型:

vector

vector是数组的一种类表示,可以自动内存管理,动态改变vector对象的长度。可对元素随机访问,在尾部添加或删除元素为固定时间复杂度,但在头部添加或删除元素是线性时间复杂度。

vector还是可反转容器(reversible container)概念的模型,可使用反向迭代器逆序迭代:

1
for_each(dice.rbegin(), dice.rend(), Show);  // display in reversed order
deque

deque是双端队列(double-ended queue),在STL中其实现类似于vector,主要区别在于deque对象在其头部插入和删除元素的时间是固定的。为实现这一目的,deque对象设计比vector对象更为复杂,因此在对元素的随机访问和在序列中部执行限行时间的插入和删除操作,vector容器的执行速度会更快些。

list

list模板类表示双向链表,除了第一个和最后一个元素外,每个元素都与前后的元素相链接。list在链表中任意位置插入和删除元素都是固定时间的复杂度,但不支持随机访问。在list中插入或删除元素后链表迭代器指向的元素不变。list也是可反转容器。

除序列和可反转容器的函数外,list还有一些链表专用成员函数,见下表(Alloc参数通常有默认值):

函数 说明 复杂度
void merge(list& x) 将链表x与调用链表合并,两个链表必须是经过排序的。合并之后,调用链表中保存合并的链表,x为空。 线性
void remove(const T & val) 从链表中删除val的所有实例 线性
void sort() 使用运算符<对链表进行排序 NlogN
void splice(iterator pos,list x) 将链表x的内容插入到pos的前面,完成后x为空。 固定
void unique() 将连续的相同元素压缩为单个元素 线性

补充:

方法insert()splice()的区别在于,前者将原始区间的副本插入到目标地址,而后者会将原始区间移到目标地址。list只能使用其成员函数sort(),而非成员函数sort()不能作用于list。

sort()merge()unique()还有各自拥有接受另一个参数的版本,该参数用于指定用来比较元素的函数。remove()也有一个接受另一个参数的版本,该参数用于指定一个用来确定是否删除元素的函数。

forward_list

C++11中的容器,实现了单链表。这种链表中每个节点都只链接到下一个节点,而没有链接到前一个节点。因此forward_list只需要正向迭代器。forward_list是不可反转容器,比list更简单、更紧凑,但功能更少。

queue

queue模板是一个适配器类,让底层类展示典型的队列接口。queue不仅不允许随机访问元素,甚至不允许遍历队列。可以进行队列的操作如在队尾添加元素、从队首删除元素、查看队首和队尾的值、检查元素数目和测试队列是否为空等:

方法 说明
bool empty() 返回队列是否为空
size_type size() 返回队列中元素数目
T& front() 返回指向队首元素的引用
T& back() 返回指向队尾元素的引用
void push(const T& x) 在队尾插入元素x
void pop() 删除队首元素
priority_queue

priority_queue模板类是一个适配器类,与queue支持的操作相同。但在priority_queue中最大的元素总是被移到队首,其默认的底层类是vector。有两种构造函数,在构造时可以指定用于确定哪个元素放到队首的比较方式:

1
2
priority_queue<int> pq1;  // default version
priority_queue<int> pq2(greater<int>); // use greater<int> to order
stack

与队列相似,stack是一个适配器类,给底层的类(默认是vector)提供了典型的栈接口。stack不允许随机访问栈元素,甚至不允许遍历栈。可以将元素推到栈顶、从栈顶弹出元素、查看栈顶的值、检查元素数目和测试栈是否为空:

方法 说明
bool empty() 返回栈是否为空
size_type size() 返回栈中元素数目
T& top() 返回栈顶元素的引用
void push(const T& x) 在栈顶部插入x
void pop() 删除栈顶元素
array

C++11的array并非STL容器,因为其长度是固定的。array没有可以调整大小的操作如push_back()insert(), 但有operator[]()at()。STL中的很多标准算法如copy()for_each()等可用于array对象。

关联容器

关联容器(associative containers) 是对容器概念的另一个改进。关联容器将值与键关联在一起,并使用键来查找值。对于容器X,表达式X::value_type通常指出了存储在容器中的值类型,在关联容器中,表达式X::key_type指出了键的类型。

关联容器的优点在于对元素的快速访问,允许插入新元素但不能指定元素的插入位置,关联容器的底层通常有用于确定数据存放位置的算法,以便能够快速检索信息,关联容器通常使用树来实现。

STL中有4中关联容器:set、multiset、map和multimap。set是最简单的关联容器,对于set来说,值的类型与键相同(值就是键),键是唯一的,所以集合中不会有多个相同的键。multiset与set相似,只是可能有多个值的键相同。

map中值与键的类型不同,键是唯一的,每个键只对应一个值。multimap中一个键可以与多个值相关联。

关联容器的成员变量和方法详见下边的两个表格:

类型
X::key_type 键的类型
X::key_compare key_type的比较函数,默认less\
X::value_compare 在set和multiset中等同于key_compare,在map或multimap中为pair\值提供了排序功能。
X::mapped_type T,关联数据的类型(map和multimap中)
操作 描述
X(i,j,c) 创建一个空容器,插入区间[i,j)的元素,并将c作为比较对象
X a(i,j,c) 创建一个名为a的空容器,插入区间[i,j)的元素,并将c作为比较对象
X(i,j) 创建一个空容器,插入区间[i,j)的元素,使用Compare()作为比较对象
X a(i,j) 创建一个名为a的空容器,插入区间[i,j)的元素,使用Compare()作为比较对象
X(il); 等价于X(il.begin(), il.end())
a = il 将[il.begin(), il.end())的内容赋给a
a.key_comp() 返回构造a时使用的比较对象
a.value_comp() 返回a的value_compare对象
a_uniq.insert(t) a中不包含相同键的值时,将t插入容器a。该方法返回一个pair\值。其中bool的值为是否成功进行了插入,iterator指向与t相同的元素
a_eq.insert(t) 插入t并返回一个指向其位置的迭代器
a.insert(p,t) 将p作为insert()开始搜索的位置,将t插入。如果a是a_uniq则当且仅当a中没有与t的键相同的值时才插入;如果a是a_eq则直接插入。无论是否进行插入该方法都会返回一个指向拥有相同键的位置的迭代器
a.insert(i,j) 将区间[i, j)的元素插入a
a.insert(il) 将初始化列表il中的元素插入a
a_uniq.emplace(args) 与a_uniq.insert(t)相似,但使用参数列表与参数包args的内容匹配的构造函数
a_eq.emplace(args) 与a_eq.insert(t)相似,但使用参数列表与参数包args的内容匹配的构造函数
a.emplace_hint(args) 与a.insert(p,t)相似,但使用参数列表与参数包args的内容匹配的构造函数
a.erase(k) 删除a中键与k相同的所有元素,并返回删除元素的数目
a.erase(q) 删除q指向的元素
a.erase(q1,q2) 删除区间[q1, q2)中的元素
a.clear() 等价于erase(a.begin(), a.end())
a.find(k) 返回一个迭代器,该迭代器指向键与k相同的元素;如果没有找到这样的元素则返回a.end
a.count(k) 返回键与k相同的元素的数量
a.lower_bound(k) 返回一个迭代器,该迭代器指向第一个键不小于k的元素
a.upper_bound(k) 返回一个迭代器,该迭代器指向第一个键大于k的元素
a.equal_range(k) 返回一个pair,第一值为a.lower_bound(k),第二值为a.upper_bound(k)
a.operator[](k) 返回一个引用,该引用指向与键k关联的值(仅限于map容器)

通常,比较对象不要求键相同时值是相同的,等价键(equivalent key)意味着两个值(相同或不同)的键相同。上表中X是容器类,a是类型为X的对象。如果X使用唯一键(即set或map)则a_uniq将是类型为X的对象。如果X允许一键多值(multiset或multimap)则a_eq是类型为X的对象。ij是指向value_type元素的输入迭代器,[i,j]是一个有效的区间,pq2是指向a的迭代器,qq1是指向a的可解除引用的迭代器,[q1,q2]是有效区间,tX::value_type值,kX::key_type值,ilinitializer<value_type>对象。

无序关联容器

无序关联容器是对容器概念的另一种改进。与关联容器一样,无序关联容器也将值与键关联起来,并用键来查找值。但底层的差别在于,关联容器是基于树结构的,而无序关联容器是基于数据结构哈希表,旨在提高添加和删除元素的速度以及提高查找算法的效率。STL中的四种无序关联容器是unordered_set、unordered_multiset、 unordered_map 和unordered_multimap。

哈希函数(hash function)将键转换为索引值。哈希函数中有桶(bucket)的概念,不同的key得到不同的索引值(如使用数字编码等)后,将这些索引值根据桶的个数求余,求余得到的是与桶的数量相同的一组不同索引值,根据索引值将key放于桶中。如需在容器中搜索键,则对键执行哈希函数,进而只在索引对应的桶中搜索,理想情况下应有足够多的桶,每个桶只包含为数不多的key。C++11库中提供了模板hash<key>,无序关联容器默认使用该模板,为各种整型、浮点型、指针及一些模板类(如string)定义了改模板的具体化。

无序关联容器的成员变量及方法见下边的表格:

类型
X::key_type Key键类型
X::key_equal 指向一个二元函数,用于判断两个类型为Key的参数是否相等
X::hasher Hash,散列函数,一个这样的一元函数对象,如果hf类型为Hash,k的类型为Key,则hf(k)的类型为std::size_t
X::local_iterator 一个类型与X::iterator相同的迭代器,但只能用于一个桶(Hash bucket)
X::const_local_iterator 一个类型与X::const_iterator相同的迭代器,但只能用于一个桶(Hash bucket)
X::mapped_type T关联的数据类型(仅限map和multimap)

无序关联列表的方法与关联列表相似,所以上边关联容器列表的大多数方法也适用于无序关联列表,例外是:无序关联列表不存在lower_bound(k)upper_bound(k)以及构造函数X(i,j,c)等涉及到排序或比较大小关系的方法。关联列表中有“大于”或“小于”的概念,但是在无序关联列表中只有“等于”和“不等于”。

操作 描述
X(n,hf,eq) 创建一个空容器,至少包含n个桶,将hf用作哈希函数,将eq用作判断键相等的函数。如果省略了eq,则将key_equal()用作判断键相等的函数;如果省略了hf,则将hasher()用作哈希函数;如果省略了n,则包含的桶数不确定
X a(n,hf,eq) 创建一个名为a的空容器,至少包含n个桶,将hf用作哈希函数,将eq用作判断键相等的函数。如果省略了eq,则将key_equal()用作判断键相等的函数;如果省略了hf,则将hasher()用作哈希函数;如果省略了n,则包含的桶数不确定
X(i,j,n,hf,eq) 创建一个空容器,至少包含n个桶,将hf用作哈希函数,将eq用作判断键相等的函数,向其插入[i,j)中的元素。如果省略了eq,则将key_equal()用作判断键相等的函数;如果省略了hf,则将hasher()用作哈希函数;如果省略了n,则包含的桶数不确定
X a(i,j,n,hf,eq) 创建一个名为a的空容器,至少包含n个桶,将hf用作哈希函数,将eq用作判断键相等的函数,向其插入[i,j)中的元素。如果省略了eq,则将key_equal()用作判断键相等的函数;如果省略了hf,则将hasher()用作哈希函数;如果省略了n,则包含的桶数不确定
b.hash_function() 返回b使用的哈希函数
b.key_eq() 返回创建b时使用的判断键相等的函数
b.bucket_count() 返回b包含的桶数
b.max_bucket_count() 返回b最多可包含的桶的个数的上限值
b.bucket(k) 返回键为k的元素所属的桶的索引
b.bucket_size(n) 返回索引为n的桶可包含的元素个数
b.begin(n) 返回一个迭代器,指向所因为n的桶中的第一个元素
b.end(n) 返回一个迭代器,指向所因为n的桶中的最后一个元素
b.cbegin(n) 返回一个常量迭代器,指向所因为n的桶中的第一个元素
b.cbegin(n) 返回一个常量迭代器,指向所因为n的桶中的最后一个元素
b.load_factor() 返回每个桶包含的平均元素数
b.max_load_factor() 返回负载系数的最大可能取值,超过这个值后,容器将增加桶
b.max_load_factor(z) 可能修改最大负载系数,建议值为z
a.rehash(n) 将桶数调整为不小于n,并确保a.bucket_count() > a.size()/a.max_load.factor()
a.reserve(n) 等价于a.rehash(ceil(n/a.max_load_factor()))

表中X是无序关联容器,a是类型为X的对象,b可能是类型为X的常量对象,hf是类型为hasher的值,eq是类型为key_equal的值,n是类型为size_type的值,z是类型为float的值。ij是指向value_type元素的输入迭代器,[i,j]是一个有效的区间,pq2是指向a的迭代器,qq1是指向a的可解除引用的迭代器,[q1,q2]是有效区间,tX::value_type值,kX::key_type值,ilinitializer<value_type>对象。

REFERENCE

C++ Primer Plus(第6版)中文版