C++ Primer - 顺序容器

《C++ Primer》第五版引入了11标准相关内容,我早年在初学C++时还只有第四版,近来想对C++做一个整体的复习+版本升级,借此机会过一遍第五版。本文是阅读第九章“顺序容器”时所做的笔记。

C++ Primer - 顺序容器

所谓容器就是一些特定类型对象的集合。容器分为顺序容器和关联容器。

##顺序容器概览

顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值,而是与元素加入容器时的位置相对应。

- -
vector 可变尺寸数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快
list 双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快
forward_list 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快
array 固定大小数组。支持快速随机访问。不能添加或删除元素
string 与vector相似的容器,但专门用于保存字符。随机访问快。在尾部插入/删除速度快

forward_list和array是C++11标准扩展内容。array相比内值数组更安全易用。array大小是固定的,它无法添加或删除元素。forward_list的设计目标是达到与最好的手写的单链表相当的性能。因此,forward_list没有size操作,因为保存或计算其大小就会比手写链表多出额外的开销。

程序员自己的写的容器往往劣于标准库所提供的版本。所以,请使用标准库容器。

使用哪种容器要根据具体场景需求去确定。

每个容器都定义在一个头文件中,文件名与类型名相同。

容器都是模板类,所以需要定义时提供额外信息来生成特定的容器类型。比如list<Sales_data>deque<double>

顺序容器几乎可以保存任意类型的元素,且容器可以嵌套。vector<vector<string>>

C++11以前,连续的两个>>之间要有空格。写成vector<vector<string> >

容器操作一览
类型别名
iterator 此容器类型的迭代器类型
const_iterator 可以读取元素,但不能修改元素的迭代器类型
size_type 无符号整数类型,足够保存此种容器类型最大可能容器的大小
difference_type 带符号整型,足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值类型;与value_type&含义相同
const_reference 元素的const左值类型(const value_type&)
构造函数
C c; 默认构造函数,构造空容器
C c1(c2); 构造c2的拷贝c1
C c(b, e); 构造c,将迭代器b和e指定的范围内的元素拷贝到c
C c{a, b, c…}; 列表初始化c
赋值与swap
c1 = c2 将c1中的元素替换为c2中元素
c1 = {a, b, c…} 将c1中的元素替换为列表中元素(不适用于array)
a.swap(b) 交换a和b的元素
swap(a, b) 与a.swap(b)等价
大小
c.size() c中元素的数目(不支持forward_list)
c.max_size() c可保存的最大元素数目
c.empty() 若c中存储了元素,返回false,否则返回true
添加/删除元素 (不适用于array) 注:不同容器中,这些操作的接口都不同
c.insert(args) 将args中元素拷贝到c
c.emplace(inits) 使用inits构造c中的一个元素
c.erase(args) 删除args指定的元素
c.clear() 删除c中的所有元素,返回void
关系运算符
==, != 所有容器都支持相等(不等)运算符
<, <=, >, >= 关系运算符(无序关联容器不支持)
获取迭代器
c.begin(), c.end() 返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(). c.cend() 返回const_iterator
反向容器的额外成员(不支持forward_list)
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 不能修改元素的逆序迭代器
c.rbegin(), c.rend() 返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend() 返回const_reverse_iterator

迭代器

forward_list类型不支持递减运算符--

一个迭代器范围(iterator range)由一对迭代器表示。这两个迭代器通常被称为begin和end,分别指向同一个容器中的元素或尾后地址。end迭代器不会指向范围中的最后一个元素,而是指向尾元素之后的位置。这种元素范围被称为左闭合区间(left-inclusive interval),其标准数学描述为[begin,end)。迭代器begin和end必须指向相同的容器,end可以与begin指向相同的位置,但不能指向begin之前的位置(由程序员确保)。

1
2
3
4
5
while (begin != end)
{
*begin = val;
++begin;
}

容器定义和初始化

每个容器类型都定义了一个默认构造函数。除array以外,其他容器的默认构造函数都会创建一个指定类型的空容器,且都可以接受指定容器大小和元素初始值的参数。

容器定义和初始化
C c; 默认构造函数。如果C是一个array,则c中元素按默认方式初始化;否则c为空
C c1(c2) c1初始化为c2的拷贝。c1和c2必须是相同类型。array类型还需要两者大小相等
C c{a, b, c…}; C c= {a, b, c…} c初始化为初始化列表中元素的拷贝。列表中元素类型必须与C的元素类型相容。对array类型来说,列表中元素数目必须小于等于array的大小,任何遗漏的元素都进行值初始化
C c(b,e) c初始化为迭代器b和e指定范围中的元素拷贝。
C seq(n) seq包含n个元素,这些元素进行了值初始化,该构造函数是explicit的
C seq(n,t) seq包含n个初始化为值t的元素

只有顺序容器(不包括array)的构造函数才能接受大小参数。

定义和使用array类型时,需要同时指定元素类型和容器大小。

1
2
array<int, 42>      // 保存42个int的数组
array<string, 10> // 保存10个string的数组

赋值和swap

容器赋值运算
c1 = c2 c1中元素替换为c2中元素的拷贝。c1和c2必须类型相同
c = {a,b,c…} c1中元素替换为初始化列表中元素的拷贝(array不适用)
swap(c1,c2) c1.swap(c2) 交换c1和c2中的元素。c1和c2必须具有相同类型。swap通常比从c2向c1拷贝元素快得多
seq.assign(b,e) 将seq中元素替换为迭代器b和e所表示的范围中的元素。b和e不能指向seq中的元素
seq.assign(il) 将seq中元素替换为初始化列表il中的元素
seq.assign(n, t) 将seq中元素替换为n个值为t的元素

赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap操作交换容器内容,不会导致迭代器、引用和指针失效(array和string除外)。而对于array,swap会真正交换它们的元素。因此在swap操作后,指针、引用和迭代器所绑定的元素不变,但元素值已经被交换。

array不支持assign,也不允许用花括号列表进行赋值。

新标准库同时提供了成员和非成员函数版本的swap。非成员版本的swap在泛型编程中非常重要,建议统一使用非成员版本的swap。

容器大小操作

size成员返回容器中元素的数量;empty当size为0时返回true,否则返回false;max_size返回一个大于或等于该类型容器所能容纳的最大元素数量的值。forward_list支持max_size和empty,但不支持size。

关系运算符

两个容器的比较实际上是元素的逐对比较,其工作方式与string的关系运算符类似:

  • 如果两个容器大小相同且所有元素对应相等,则这两个容器相等。
  • 如果两个容器大小不同,但较小容器中的每个元素都等于较大容器中的对应元素,则较小容器小于较大容器。
  • 如果两个容器都不是对方的前缀子序列,则两个容器的比较结果取决于第一个不等元素的比较结果。

容器的相等运算符实际上是使用元素的==运算符实现的,而其他关系运算符则是使用元素的<运算符。如果元素类型不支持所需运算符,则保存该元素的容器就不能使用相应的关系运算。

这就意味着如果想要使用容器承载自己定义的类类型,且希望可以进行该种容器的关系运算符操作,那么就要自己去重载自定义类类型的==和<运算符。

顺序容器操作

添加元素

顺序容器添加元素的操作 array不支持
c.push_back(t) c.emplace_back(args) 在c的尾部创建一个值为t或由args创建的元素。返回void
c.push_front(t) c.emplace_front(args) 在c的头部创建一个值为t或由args创建的元素。返回void
c.insert(p,t) c.emplace(p, args) 在迭代器p指向的元素之前创建一个值为t或由args创建的元素。返回指向新添加的元素的迭代器
c.insert(p, n, t) 在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器;若n为0,则返回p
c.insert(p,b,e) 将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素。返回指向新添加的第一个元素的迭代器;若范围为空,则返回p
c.insert(p,il) il是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器;若列表尾空,则返回p

新标准库增加了三个直接构造而不是拷贝元素的操作:emplace_frontemplace_backemplace,其分别对应push_front、push_back和insert。当调用push或insert时,元素对象被拷贝到容器中。而调用emplace时,则是将参数传递给元素类型的构造函数,直接在容器的内存空间中构造元素。传递给emplace的参数必须与元素类型的构造函数相匹配。

forward_list有特殊版本的insert和emplace操作,且不支持push_back和emplace_back。vector和string不支持push_front和emplace_front。

访问元素

顺序容器中访问元素
c.back() 返回c中尾元素的引用。若c为空,函数行为未定义
c.front() 返回c中首元素的引用。若c为空,函数行为未定义
c[n] 返回c中下标为n的元素的引用,n是一个无符号整数。若n>=c.size(),则函数行为未定义
c.at(n) 返回下标为n的元素的引用。如果下标越界,则抛出out_of_range异常

at和下标操作只适用于string/vector/deque和array。

back不适用于forward_list。

删除元素

顺序容器的删除操作 array不适用
c.pop_back() 删除c中尾元素。若c为空,则函数行为未定义。返回void
c.pop_front() 删除c中首元素。若c为空,则函数行为未定义。返回void
c.erase(p) 删除迭代器p所指定的元素,返回一个指向被删除元素之后元素的迭代器,若p指向尾元素,则返回尾后迭代器。若p是尾后迭代器,则函数行为未定义
c.erase(b,e) 删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删元素之后元素的迭代器,若e本身就是尾后迭代器,则函数也返回尾后迭代器。
c.clear() 删除c中所有元素。返回void

forward_list有特殊版本的erase,且不支持pop_back。

vector和string不支持pop_front。

###特殊的forward_list

forward_list插入或删除操作
lst.before_begin() lst.cbefore_begin() 返回指向链表首元素之前不存在的元素的迭代器。此迭代器不能解引用。cbefore_begin()返回一个const_iterator
lst.insert_after(p,t) lst.insert_after(p,n,t) lst.insert_after(p,b,e) lst.insert_after(p,il) 迭代器p之后插入元素。t为对象,n为数量,b和e表示范围的一对迭代器(不能指向自身),il是一个花括号列表。返回一个指向最后一个插入元素的迭代器。
emplace_after(p, args) 使用args在p指定的位置之后创建一个元素,返回一个指向这个新元素的迭代器。若p为尾后迭代器,则函数行为未定义
lst.erase_after(p) lst.erase_after(b,e) 删除p指向的位置之后的元素,或删除b到e之间的元素。返回一个指向被删元素之后元素的迭代器。

resize

1
2
3
4
list<int> ilist(10,42);
ilist.resize(15); //将5个值为0的元素添加到ilist末尾
ilist.resize(25,-1); //再将10个值为-1的元素添加到ilist末尾
ilist.resize(5); //从ilist末尾删除20个元素

显然,array不支持resize。

容器操作可能使迭代器失效

向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素,使用它们是一种严重的程序设计错误。

##扩展的string操作

###构造string的其他方法

n,len2和pos2都是无符号值
string s(cp, n) s是cp指向的数组中前n个字符的拷贝。此数组至少应该包含n个字符
string s(s2, pos2) s是string s2从下标pos2开始的字符的拷贝。若pos2>s2.size(),构造函数的行为未定义
string s(s2, pos2, len2) s是string s2从下标pos2开始len2个字符的拷贝。若pos2>s2.size(),构造函数的行为未定义。不管len2值是多少,构造函数至多拷贝s2.size()-pos2个字符

string的一些操作

子字符串操作
s.substr(pos, n) 返回一个string,包含s中从pos开始的n个字符的拷贝。pos的默认值为0。n的默认值为s.size()-pos,即拷贝从pos开始的所有字符
修改string的操作
s.insert(pos,args) 在pos前插入args指定的字符。pos可以是下标或迭代器。接受下标的版本返回一个指向s的引用,接受迭代器的版本返回指向第一个插入字符的迭代器。
s.erase(pos,len) 删除从位置pos开始的len个字符。如果len被省略,则删除从pos开始到s末尾的所有字符。返回一个指向s的引用
s.assign(args) 将s中的字符替换为args指定的字符。返回一个指向s的引用
s.append(args) 将args追加到s。返回一个指向s的引用
s.replace(range, args) 删除s中范围range内的字符,替换为args指定的字符。range或者是一个下标和一个长度,或者是一对指向s的迭代器。返回一个指向s的引用

args的形式:

  • str:字符串
  • str,pos,len:str中从pos开始最多len个字符
  • cp,len:从cp指向的字符数组的前(最多)len个字符
  • cp:cp指向的以空字符结尾的字符数组
  • n,c:n个字符c
  • b,e:迭代器b和e指定的范围内的字符
  • 初始化列表:花括号包围的,以逗号分隔的字符列表
搜索操作
s.find(args) 查找s中args第一次出现的位置
s.rfind(args) 查找s中args最后一次出现的位置
s.find_first_of(args) 在s中查找args中任何一个字符第一次出现的位置
s.find_last_of(args) 在s中查找args中任何一个字符最后一次出现的位置
s.find_first_not_of(args) 在s中查找第一个不在args中的字符
s.find_last_not_of(args) 在s中查找最后一个不在args中的字符

args形式:

  • c,pos:从s中位置pos开始查找字符c。pos默认为0
  • s2,pos:从s中位置pos开始查找字符串s2。pos默认为0
  • cp,pos:从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串。pos默认为0。
  • cp,pos,n:从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和n无默认值。

string还提供一组compare函数,用于比较,类似C的strcmp。

s.compare的几种参数形式
s2 比较s和s2
pos1, n1, s2 将s中从pos1开始的n1个字符与s2比较
pos1,n1,s2,pos2,n2 将s中pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较
cp 比较s与cp指向的以空字符结尾的字符数组
pos1,n1,cp s中pos1开始的n1个字符与cp指向的空字符结尾的字符数组进行比较
pos1,n1,cp,n2 将s中从pos1开始的n1个字符与指针cp指向的地址开始的n2个字符进行比较

字符串转数值型也是非常常见的场景,字符串往往包含数值的字符。

string和数值间转换
to_string(val) 一组重载函数,返回数值val的string表示。val可以是任何算术类型。对每个浮点类型和int或更大的整型,都有对应版本的to_string。小整型会被提升。
stoi(s, p, b) stol(s, p, b) stoul(s, p, b) stoll(s, p, b) stoull(s, p, b) 返回s的起始子串的数值,返回值类型分别是int、long、unsigned long、long long、unsigned long long。b表示转换所用的基数,默认为10,表示十进制。p是size_t指针,用来保存s中第一个非数值字符的下标,p默认为0,即函数不保存下标。
stof(s, p) stod(s, p) stold(s, p) 返回s的起始子串的数值,返回值类型分别为float、double或long double。参数p的作用域整数转换函数中一样。

适配器

标准库还定义了3个顺序容器适配器:stack, queue和priority_queue。

适配器(Adapter)是标准库中的一个概念,它是一种机制,使某种事物的行为看起来像另一种事物一样。

所有容器适配器都支持的操作和类型
size_type 一种类型,足以保存当前类型的最大对象的大小
value_type 元素类型
container_type 实现适配器的底层容器类型
A a; 创建一个名为a的空适配器
A a(c); 创建一个名为a的适配器,带有容器c的一个拷贝
关系运算符 每个适配器都支持所有关系运算符:==, !=, <, <=, >和>=。
a.empty() 若a中包含任何元素,返回false,否则返回true
a.size() 返回a中的元素数目
swap(a,b) a.swap(b) 交换a和b的内容,a和b必须有相同类型,包括底层容器类型也必须相同

默认情况下,stack和queue是基于deque实现的,priority_queue是基于vector实现的。可以在创建适配器时将一个命名的顺序容器作为第二个类型参数,来重载默认容器类型。

1
2
3
4
// 基于vector实现的空stack
stack<string, vector<string>> str_stk;
// str_stk2基于vector实现,以svec拷贝初始化
stack<string, vector<string>> str_stk2(svec);

所有适配器都要求容器具有添加和删除元素的能力,因此适配器不能构造在array至上。适配器还要求容器具有添加、删除和访问尾元素的能力,因此也不能用forward_list构造适配器。

stack

支持的操作
s.pop() 删除栈顶元素,但不反回该元素值
s.push(item) s.emplace(args) 创建一个新元素压入栈顶,该元素通过拷贝或移动item而来,或者由args构造
s.top() 返回栈顶元素,但不将元素弹出栈

stack默认基于deque实现,也可以在list或vector上实现

queue & priority_queue

支持的操作
q.pop() 返回queue的首元素或priority_queue的最高优先级的元素,但不删除此元素
q.front() q.back() 返回首元素或尾元素,但不删除此元素,只适用于queue
q.top() 返回最高优先级元素,但不删除该元素,只适用于priority_queue
q.push(item) q.emplace(args) 在queue末尾或priority_queue中恰当的位置创建一个元素,值为item或由args构造

queue应用FIFO的访问和存储策略。priority_queue允许我们为队列元素建立优先级。标准库在元素类型上默认使用<运算符来确定相对优先级,这个可以根据具体需求情况而重载。

文章目录
  1. 1. C++ Primer - 顺序容器
    1. 1.0.1. 迭代器
    2. 1.0.2. 容器定义和初始化
    3. 1.0.3. 赋值和swap
    4. 1.0.4. 容器大小操作
    5. 1.0.5. 关系运算符
  2. 1.1. 顺序容器操作
    1. 1.1.1. 添加元素
    2. 1.1.2. 访问元素
    3. 1.1.3. 删除元素
    4. 1.1.4. resize
    5. 1.1.5. 容器操作可能使迭代器失效
  3. 1.2. 适配器
    1. 1.2.1. stack
    2. 1.2.2. queue & priority_queue
,