string 类型支持长度可变的字符串,C++ 标准库将负责管理与存储字符相关的内存,以及提供各种有用的操作。标准库 string 类型的目的就是满足对字符串的一般应用。
1 |
|
string 标准库支持几个构造函数。
string s1; |
默认构造函数 s1 为空串 |
string s2(s1); |
将 s2 初始化为 s1 的一个副本 |
string s3("value"); |
将 s3 初始化为一个字符串字面值副本 |
string s4(n, 'c'); |
将 s4 初始化为字符 ‘c’ 的 n 个副本 |
:表1 string标准库支持的构造函数
因为历史原因以及为了与 C 语言兼容,字符串字面值与标准库 string 类型不是同一种类型。这一点很容易引起混乱,编程时一定要注意区分字符串字面值和 string 数据类型的使用,这很重要。
1 | // Note: #include and using declarations must be added to compile this code |
1 | int main() |
1 | int main() |
任何存储 string 的 size 操作结果的变量必须为 string::size_type
类型,以做到机器无关。特别重要的是,还要把 size 的返回值赋给一个 int 变量。
string 类型还支持大多数顺序容器操作。
string 类定义了几种关系操作符用来比较两个 string 值的大小。
string 对象比较操作是区分大小写的,即同一个字符的大小写形式被认为是两个不同的字符。在多数计算机上,大写的字母位于小写之前:任何一个大写之母都小于任意的小写字母。
1 | string s1 = "hello"; // no punctuation |
1 | string tmp = s1 + ", "; // ok: + has a string operand |
1 | string s("hello world"); |
1 | string name("AnnaBelle"); |
find 操作的返回类型是 string::size_type
,请使用该类型的对象存储 find 的返回值。
除了关系操作符,string 类型还提供了一组 compare 操作,用于实现字典顺序的比较。这些操作的结果类似于 C 语言中的库函数 strcmp
s.compare(s2) | 比较 s 和 s2 |
s.compare(pos1, n1, s2) | 让 s 中从 pos 下标位置开始的 n1 个字符与 s2 做比较 |
s.compare(pos1, n1, s2, pos2, n2) | 让 s 中从 pos1 下标位置开始的 n1 个字符与 s2 中从 pos2 下标位置开始的 n2 个字符做比较 |
s.compare(cp) | 比较 s 和 cp 所指向的以空字符结束的字符串 |
s.compare(pos1, n1, cp) | 让 s 中从 pos1 下标位置开始的 n1 个字符与 cp 所指向的字符串做比较 |
s.compare(pos1, n1, cp, n2) | 让 s 中从 pos1 下标位置开始的 n1 个字符与 cp 所指向的字符串的前 n2 个字符做比较 |
:表8 compare 操作
compare 函数返回下面列出的三种可能值之一:
下表列出了各种字符操作函数,适用于 string 对象的字符(或其他任何 char 值)。这些函数都在 cctype 头文件中定义。
isalnum(c)
如果 c 是字母或数字,则为 True。
isalpha(c)
如果 c 是字母,则为 true。
iscntrl(c)
如果 c 是控制字符,则为 true
isdigit(c)
如果 c 是数字,则为 true。
isgraph(c)
如果 c 不是空格,但可打印,则为 true。
islower(c)
如果 c 是小写字母,则为 true。
isprint(c)
如果 c 是可打印的字符,则为 true。
ispunct(c)
如果 c 是标点符号,则 true。
isspace(c)
如果 c 是空白字符,则为 true。
isupper(c)
如果 c 是大写字母,则 true。
isxdigit(c)
如果 c 是十六进制数,则为 true。
tolower(c)
如果 c 大写字母,返回其小写字母形式,否则直接返回 c。
toupper(c)
如果 c 是小写字母,则返回其大写字母形式,否则直接返回 c。
:表9 字符处理函数
表中的大部分函数是测试一个给定的字符是否符合条件,并返回一个 int 作为真值。如果测试失败,则该函数返回 0 ,否则返回一个(无意义的)非 0 ,表示被测字符符合条件。
表中的这些函数,可打印的字符是指那些可以表示的字符,空白字符则是空格、制表符、垂直制表符、回车符、换行符和进纸符中的任意一种;标点符号则是除了数字、字母或(可打印的)空白字符(如空格)以外的其他可打印字符。
这里给出一个例子,运用这些函数输出一给定 string 对象中标点符号的个数:
1 | string s("Hello World!!!"); |
这个程序的输出结果是:
1 | 3 punctuation characters in Hello World!!! |
建议:采用 C 标准库头文件的 C++ 版本。
C++ 标准库除了定义了一些选定于 C++ 的设施外,还包括 C 标准库。C++中的头文件 cctype 其实就是利用了 C 标准库函数,这些库函数就定义在 C 标准库的 ctype.h 头文件中。
C 标准库头文件命名形式为 name 而 C++ 版本则命名为 cname ,少了后缀,.h 而在头文件名前加了 c 表示这个头文件源自 C 标准库。因此,cctype 与 ctype.h 文件的内容是一样的,只是采用了 更适合 C++程序的形式。特别地,cname 头文件中定义的名字都定义在命名空间 std 内,而 .h 版本中的名字却不是这样。
通常,C++ 程序中应采用 cname 这种头文件的版本,而不采用 name.h 版本,这样,标准库中的名字在命名空间 std 中保持一致。使用 .h 版本会给程序员带来负担,因为他们必须记得哪些标准库名字是从 C 继承来的,而哪些是 C++ 所特有的。
有些程序要处理二进制位的有序集,每个位可能包含 0(关)1(开)值。位是用来保存一组项或条件的 yes/no 信息(有时也称标志)的简洁方法。标准库提供的 bitset 类简化了位集的处理。要使用 bitset 类就必须包含相关的头文件。
1 |
|
bitset<n> b;
b 有 n 位,每位都 0
bitset<n> b(u);
b 是 unsigned long 型 u 的一个副本
bitset<n> b(s);
b 是 string 对象 s 中含有的位串的副本
bitset<n> b(s, pos, n);
b 是 s 中从位置 pos 开始的 n 个位的副本。
:表10 bitset的构造函数
类似于 vector,bitset 类是一种类模板;而与 vector 不一样的是 bitset 类型对象的区别仅在其长度而不在其类型。在定义 bitset 时,要明确 bitset含有多少位,须在尖括号内给出它的长度值:
1 | bitset<32> bitvec; // 32 bits, all zero |
这条语句把 bitvec 定义为含有 32 个位的 bitset 对象。和 vector 的元素一样,bitset 中的位是没有命名的,程序员只能按位置来访问。位集合的位置编号从 0 开始,因此,bitvec 的位序是从 0 到 31。以 0 位开始的位串是低阶位(low-order),以 31 位结束的位串是高阶位(high-order)。
当用 unsigned long 值作为 bitset 对象的初始值时,该值将转化为二进制的位模式。而 bitset 对象中的位集作为这种位模式的副本。如果 bitset 类型长度大于 unsigned long 值的二进制位数,则其余的高阶位将置为 0;如果 bitset 类型长度小于 unsigned long 值的二进制位数,则只使用 unsigned 值中的低阶位,超过 bitset 类型长度的高阶位将被丢弃。
在 32 位 unsigned long 的机器上,十六进制值 0xffff 表示为二进制位就是十六个 1 和十六个 0(每个 0xf 可表示为 1111)。可以用 0xffff 初始化 bitset 对象:
1 |
|
1 | bitvec1: 1111111111111111 |
上面的三个例子中,0 到 15 位都置为 1。由于 bitvec1 位数少于 unsigned long 的位数,因此 bitvec1 的初始值的高阶被丢弃。bitvec2 和 unsigned long 长度相同,因此所有位正好放置了初始值。bitvec3 长度大于 32,31 位以上的高阶位就被置为 0。
当用 string 对象初始化 bitset 对象时,string 对象直接表示为位模式。从 string 对象读入位集的顺序是从右向左(from right to left):
1 | string strval("1100"); |
bitvec4 的位模式中第 2 和 3 的位置为 1,其余位置都为 0。如果 string 对象的字符个数小于 bitset 类型的长度,则高阶位置为 0。
string 对象和 bitsets 对象之间是反向转化的:string 对象的最右边字符(即下标最大的那个字符)用来初始化 bitset 对象的低阶位(即下标为 0 的位)。当用 string 对象初始化 bitset 对象时,记住这一差别很重要。
不一定要把整个 string 对象都作为 bitset 对象的初始值。相反,可以只用某个子串作为初始值:
1 | string str("1111111000000011001101"); |
多种 bitset 操作用来测试或设置 bitset 对象中的单个或多个二进制位。
b.any()
b 中是否存在置为 1 的二进制位?
b.none()
b 中不存在置为 1 的二进制位吗?
b.count()
b 中置为 1 的二进制位的个数
b.size()
b 中二进制位的个数
b[pos]
访问 b 中在 pos 处二进制位
b.test(pos)
b 中在 pos 处的二进制位置为 1 么?
b.set()
把 b 中所有二进制位都置为 1
b.set(pos)
把 b 中在 pos 处的二进制位置为 1
b.reset()
把 b 中所有二进制位都置为 0
b.reset(pos)
把 b 中在 pos 处的二进制位置为 0
b.flip()
把 b 中所有二进制位逐位取反
b.flip(pos)
把 b 中在 pos 处的二进制位取反
b.to_ulong()
用 b 中同样的二进制位返回一个 unsigned long 值
os << b
把 b 中的位集输出到 os 流
:表11 bitset支持的操作
如果 bitset 对象中有一个或几个二进制位置为 1,则 any 操作返回 true,也就是说,其返回值等于 1;相反,如果 bitset 对象中二进制位全为 0,则 none 操作返回 true。
1 | bitset<32> bitvec; // 32 bits, all zero |
如果需要知道置为 1 的二进制位的个数,可以使用 count 操作,该操作返回置为 1 的二进制位的个数:
1 | size_t bits_set = bitvec.count(); // returns number of bits that are on |
count 操作的返回类型是标准库中命名为 size_t
类型。size_t
类型定义在 cstddef 头文件中,该文件是 C 标准库的头文件 stddef.h 的 C++ 版本。
它是一个与机器相关的 unsigned 类型,其大小足以保证存储内在中对象的大小。
与 vector 和 string 中的 size 操作一样,bitset 的 size 操作返回 bitset 对象中二进制位的个数,返回值的类型是 size_t
:
1 | size_t sz = bitvec.size(); // returns 32 |
可以用下标操作符来读或写某个索引位置的二进制位,同样地,也可以用下标操作符测试给定二进制位的值或设置某个二进制们的值:
1 | // assign 1 to even numbered bits |
上面的循环把 bitvec 中的偶数下标的位都置为 1。 除了用下标操作符,还可以用 set;、test 和 reset 操作来测试或设置给定二进制位的值:
1 | // equivalent loop using set operation |
为了测试某个二进制位是否为 1,可以用 test 操作或者测试下标操作符的返回值:
1 | if (bitvec.test(i)) |
如果下标操作符测试的二进制位为 1,则返回的测试值的结果为 true,否则返回 false。
set 和 reset 操作分别用来对整个 bitset 对象的所有二进制位全置 1 和全置 0:
1 | bitvec.reset(); // set all the bits to 0. |
flip 操作可以对 bitset 对象的所有位或个别位取反:
1 | bitvec.flip(0); // reverses value of first bit |
to_ulong
操作返回一个 unsigned long 值,该值与 bitset
对象的位模式存储值相同。仅当 bitset 类型的长度小于或等于 unsigned long
的长度时,才可以使用 to_ulong
操作:
1 | unsigned long ulong = bitvec3.to_ulong(); |
to_ulong
操作主要用于把 bitset 对象转到 C 风格或标准 C++
之前风格的程序上。如果 bitset 对象包含的二进制位数超过 unsigned long
长度,将会产生运行时异常。
可以用输出操作符输出 bitset 对象中的位模式:
1 | bitset<32> bitvec2(0xffff); // bits 0 ... 15 are set to 1; 16 ... 31 are 0 |
输出结果为:
1 | bitvec2: 00000000000000001111111111111111 |
pair 类型是一种简单的模板类型,该类型在 utility
头文件中定义。
pair<T1, T2> p1; |
创建一个空的 pair 对象,它的两个元素分别是 T1 和 T2 类型,采用值初始化 |
pair<T1, T2> p1(v1, v2); |
创建一个 pair 对象,它的两个元素分别是 T1 和 T2 ,其中 first 成员初始化为 v1,而 second 成员初始化为 v2 |
make_pair(v1, v2) |
以 v1 和 v2 值创建一个新 pair 对象,其元素类型分别是 v1 和 v2 的类型 |
p1 < p2 |
两个 pair 对象之间的小于运算,其定义遵循字典次序:如果 p1.first < p2.first 或者 !(p2.first < p1.first) && p1.second < p2.second ,则返回 true |
p1 == p2 |
如果两个 pair 对象的 first 和 second 成员依次相等, 则这两个对象相等。该运算使用其元素的 == 操作符 |
p.first |
返回 p 中名为 first 的(公有)数据成员 |
p.second |
返回 p 的名为 second 的(公有)数据成员 |
标准库定义了三种顺序容器类型:vector、list 和 deque,以及三种容器适配器(adaptors)。
顺序容器 | |
---|---|
vector | 支持快速随机访问 |
list | 支持快速插入/删除 |
deque | 双端队列(“double-ended queue”的简写,发音为“deck”) |
:表12 顺序容器
顺序容器适配器 | |
---|---|
stack | 后进先出(LIFO)栈 |
queue | 先进先出(FIFO)队列 |
priority_queue | 有优先级管理的队列 |
:表12 顺序容器适配器
实际上,适配器是根据原始的容器类型所提供的操作,通过定义新的操作接口,来适应基础的容器类型。
一个容器中的所有对象都必须是同一种类型的。
1 |
为了使程序更清晰、简短,容器类型最常用的构造函数是默认构造函数。在大多数的程序中,使用默认构造函数能达到最佳运行时性能,并且使容器更容易使用。
支持复制和赋值功能是容器元素类型的最低要求。
1 | // note spacing: use ">>" not ">>" when specifying a container |
1 | vector< vector<string> > lines; // ok: space required between close > |
在 vector 容器中添加元素可能会导致整个容器的重新加载,这样的话,该容器涉及的所有迭代器都会失效。即使需要重新加载整个容器,指向新插入元素后面的那个元素的迭代器也会失效。
所有的容器类型都支持用关系操作符来实现两个容器的比较。但比较的容器必须具有相同的容器类型,而且其元素类型也必须相同。
容器的比较是基于容器内元素的比较。容器的比较使用了元素类型定义的同一个关系操作符:两个容器做 != 比较使用了其元素类型定义的 != 操作符。如果容器的元素类型不支持某种操作符,则该容器就不能做这种比较运算。
C++ 语言只允许两个容器做其元素类型定义的关系运算。
resize 操作可能会使迭代器失效。在 vector 或 deque 容器上做 resize 操作有可能会使其所有的迭代器都失效。
c.back() |
返回容器 c 的最后一个元素的引用。如果 c 为空,则该操作未定义 |
c.front() |
返回容器 c 的第一个元素的引用。如果 c 为空,则该操作未定义 |
c[n] |
返回下标为 n 的元素的引用。如果 n < 0 或 n >= c.size(),则该操作未定义。只适用于 vector 和 deque 容器 |
c.at(n) |
返回下标为 n 的元素的引用。如果下标越界,则该操作未定义。只适用于 vector 和 deque 容器 |
:表18 顺序容器访问元素操作
c.erase(p) |
删除迭代器 p 所指向的元素。返回一个迭代器,它指向被删除元素后面的元素。如果 p 指向容器内的最后一个元素,则返回的迭代器指向容器的超出末端的下一位置。如果 p 本身就是指向超出末端的下一位置的迭代器,则该函数未定义。 |
c.erase(b,e) |
删除迭代器 b 和 e 所标记的范围内所有的元素。返回一个迭代器,它指向被删除元素段后面的元素。如果 e 本身就是指向超出末端的下一位置的迭代器,则返回的迭代器也指向容器的超出末端的下一位置。 |
c.clear() |
删除容器 c 内的所有元素。返回 void。 |
c.pop_back() |
删除容器 c 的最后一个元素。返回 void。如果 c 为空容器,则该函数未定义。 |
c.pop_front() |
删除容器 c 的第一个元素。返回 void。如果 c 为空容器,则该函数未定义。只适用于 list 或 deque 容器 |
:表19 顺序容器删除元素操作
删除元素会使对应的迭代器失效。
1 | c1 = c2; // replace contents of c1 with a copy of elements in c2 |
赋值和 assign 操作使左操作数容器的所有迭代器失效。swap 操作则不会使迭代器失效。完成 swap 操作后,尽管被交换的元素已经存放在另一容器中,但迭代器仍然指向相同的元素。
为了支持快速的随机访问,vector 容器的元素以连续的方式存放——每一个元素都紧挨着前一个元素存储。
已知元素是连续存储的,当我们在容器内添加一个元素时,想想会发生什么事情:如果容器中已经没有空间容纳新的元素,此时,由于元素必须连续存储以便索引访问,所以不能在内存中随便找个地方存储这个新元素。于是,vector 必须重新分配存储空间,用来存放原来的元素以及新添加的元素:存放在旧存储空间中的元素被复制到新存储空间里,接着插入新元素,最后撤销旧的存储空间。如果 vector 容器在在每次添加新元素时,都要这么分配和撤销内存空间,其性能将会非常慢,简直无法接受。
但是,通常出现的反而是以下情况:对于大部分应用,使用 vector 容器是最好的。原因在于,标准库的实现者使用这样内存分配策略:以最小的代价连续存储元素。由此而带来的访问元素的便利弥补了其存储代价。
为了使 vector 容器实现快速的内存分配,其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区,用于存放新添加的元素。于是,不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器,这个分配策略带来显著的效率。事实上,其性能非常好,因此在实际应用中,比起 list 和 deque 容器,vector 的增长效率通常会更高。
vector 类提供了两个成员函数:capacity 和 reserve 使程序员可与 vector 容器内存分配的实现部分交互工作。
通常来说,除非找到选择使用其他容器的更好理由,否则 vector 容器都是最佳选择。
1 |
|
1 | stack<int> stk(deq); // copies elements from deq into stk |
1 | // empty stack implemented on top of vector |
使用适配器要注意两点:
:表23 栈容器适配器支持的操作
s.empty() |
如果栈为空,则返回 true,否则返回返回栈中元素的个数 |
s.size() |
返回栈中元素的个数 |
s.pop() |
删除栈顶元素的值,但不返回其值 |
s.top() |
返回栈顶元素的值,但不删除该元素 |
s.push(item) |
在栈顶压入新元素 |
:表24 队列和优先级队列支持的操作
q.empty() |
如果队列为空,则返回 true,否则返回 false |
q.size() |
返回队列中元素的个数 |
q.pop() |
删除队首元素,但不返回其值 |
q.front() |
返回队首元素的值,但不删除该元素该操作只适用于队列 |
q.back() |
返回队尾元素的值,但不删除该元素该操作只适用于队列 |
q.top() |
返回具有最高优先级的元素值,但不删除该元素该操作只适用于优先级队列 |
q.push(item) |
对于 queue,在队尾压入一个新元素,对于 priority_quue,在基于优先级的适当位置插入新元素 |
在某些方面,可将 string 类型视为字符容器。除了一些特殊操作,string 类型提供与 vector 容器相同的操作。string 类型与 vector 容器不同的是,它不支持以栈方式操纵容器:在 string 类型中不能使用 front、back 和 pop_back 操作。
string支持的容器操作有:
与 vector 容器的元素一样,string 的字符也是连续存储的。因此,string 类型也支持 capacity 和 reserve 操作。
关联容器(Associative containers)支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map 和 set。map 的元素以键-值(key-value)对的形式组织:键用作元素在 map 中的索引,而值则表示所存储和读取的数据。set 仅包含一个键,并有效地支持关于某个键是否存在的查询。
map | 关联数组:元素通过键来存储和读取 |
set | 大小可变的集合,支持通过键实现的快速读取 |
multimap | 支持同一个键多次出现的 map 类型 |
multiset | 支持同一个键多次出现的 set 类型 |
:表25 关联容器类型
一般来说,如果希望有效地存储不同值的集合,那么使用 set 容器比较合适,而 map 容器则更适用于需要存储(乃至修改)每个键所关联的值的情况。在做某种文本处理时,可使用 set 保存要忽略的单词。而字典则是 map 的一种很好的应用:单词本身是键,而它的解释说明则是值。
关联容器共享大部分——但并非全部——的顺序容器操作。关联容器不提供 front、 push_front、 pop_front、back、push_back 以及 pop_back 操作。
顺序容器和关联容器公共的操作包括下面的几种:
除了上述列出的操作之外,关联容器还提供了其他的操作。而对于顺序容器也提供的相同操作,关联容器也重新定义了这些操作的含义或返回类型,其中的差别在于关联容器中使用了键。
map 是键-值对的集合。map 类型通常可理解为关联数组(associative array):可使用键作为下标来获取一个值,正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联,而并非通过元素在数组中的位置来获取。
map<k, v> m; |
创建一个名为 m 的空 map 对象,其键和值的类型分别为 k 和 v |
map<k, v> m(m2); |
创建 m2 的副本 m,m 与 m2 必须有相同的键类型和值类型 |
map<k, v> |
创建 map 类型的对象 m,存储迭代器 b 和 e 标记的范围内所有 |
m(b, e); |
元素的副本。元素的类型必须能转换为 pair<const k, v> |
在实际应用中,键类型必须定义 <
操作符,而且该操作符应能“正确地工作”,这一点很重要。
map<K, V>::key_type |
在 map 容器中,用做索引的键的类型 |
map<K, V>::mapped_type |
在 map 容器中,键所关联的值的类型 |
map<K, V>::value_type |
一个 pair 类型,它的 first 元素具有 const map<K, V>::key_type 类型,而 second 元素则为 map<K, V>::mapped_type 类型 |
对迭代器进行解引用时,将获得一个引用,指向容器中一个 value_type 类型的值。对于 map 容器,其 value_type 是 pair 类型:
1 | // get an iterator to an element in word_count |
对迭代器进行解引用将获得一个pair 对象,它的 first 成员存放键,为 const,而 second 成员则存放值。
map 类额外定义了两种类型:key_type 和 mapped_type,以获得键或值的类型。对于 word_count,其 key_type 是 string 类型,而 mapped_type 则是 int 型。如同顺序容器一样,可使用作用域操作符(scope operator)来获取类型成员,如 map<string, int>::key_type
。
使用下标访问 map 与使用下标访问数组或 vector 的行为截然不同:用下标访问不存在的元素将导致在 map 容器中添加一个新元素,它的键即为该下标值:
1 | map <string, int> word_count; // empty map |
通常来说,下标操作符返回左值。它返回的左值是特定键所关联的值。可如下读或写元素:
1 | cout << word_count["Anna"]; // fetch element indexed by Anna; prints 1 |
对于 map 容器,如果下标所表示的键在容器中不存在,则添加新元素,这一特性可使程序惊人地简练:
1 | // count number of times each word occurs in the input |
map 容器的 insert 成员与顺序容器的类似,但有一点要注意:必须考虑键的作用。键影响了实参的类型:插入单个元素的 insert 版本使用键-值 pair 类型的参数。类似地,对于参数为一对迭代器的版本,迭代器必须指向键-值 pair 类型的元素。另一个差别则是:map 容器的接受单个值的 insert 版本的返回类型。
m.insert(e) |
e 是一个用在 m 上的 value_type 类型的值。如果键 (e.first) 不在 m 中,则插入一个值为 e.second 的新元素; 如果该键在 m 中已存在,则保持 m 不变。该函数返回一个 pair 类型对象,包含指向键为 e.first 的元素的 map 迭代器,以及一个 bool 类型的对象,表示是否插入了该元素 |
m.insert(beg, end) |
beg 和 end 是标记元素范围的迭代器,其中的元素必须为m.value_type 类型的键-值对。对于该范围内的所有元素,如果它的键在 m 中不存在,则将该键及其关联的值插入到 m。返回 void 类型 |
m.insert(iter,e) |
e 是一个用在 m 上的 value_type 类型的值。如果键(e.first)不在 m 中,则创建新元素,并以迭代器 iter 为起点搜索新元素存储的位置。返回一个迭代器,指向 m 中具有给定键的元素 |
下面是使用 insert 重写的单词统计程序:
1 | // count number of times each word occurs in the input |
下标操作符给出了读取一个值的最简单方法:
1 | map<string,int> word_count; |
但是,使用下标存在一个很危险的副作用:如果该键不在 map 容器中,那么下标操作会插入一个具有该键的新元素。
map 容器提供了两个操作:count 和 find,用于检查某个键是否存在而不会插入该键。
:表26 不修改 map 对象的查询操作
m.count(k) | 返回 m 中 k 的出现次数 |
m.find(k) | 如果 m 容器中存在按 k 索引的元素,则返回指向该元素的迭代器。如果不存在,则返回超出末端迭代器 |
使用 count 检查 map 对象中某键是否存在:
1 | int occurs = 0; |
读取元素而不插入元素:
find 操作返回指向元素的迭代器,如果元素不存在,则返回 end 迭代器:
1 | int occurs = 0; |
:表27 map 删除元素操作
m.erase(k) | 删除 m 中键为 k 的元素。返回 size_type 类型的值,表示删除的元素个数 |
m.erase§ | 从 m 中删除迭代器 p 所指向的元素。p 必须指向 m 中确实存在的元素,而且不能等于 m.end()。返回 void |
m.erase(b, e) | 从 m 中删除一段范围内的元素,该范围由迭代器对 b 和 e 标记。b 和 e 必须标记 m 中的一段有效范围:即 b 和 e 都必须指向 m 中的元素或最后一个元素的下一个位置。而且,b 和 e 要么相等(此时删除的范围为空),要么 b 所指向的元素必须出现在 e 所指向的元素之前。返回 void 类型 |
在使用迭代器遍历 map 容器时,迭代器指向的元素按键的升序排列。
1 | // get iterator positioned on the first element |
set 容器只是单纯的键的集合。
set 容器支持大部分的 map 操作,除了两种例外情况:
在 set 容器中,value_type 不是 pair 类型,而是与 key_type 相同的类型。它们指的都是 set 中存储的元素类型。这一差别也体现了 set 存储的元素仅仅是键,而没有所关联的值。与 map 一样,set 容器存储的键也必须唯一,而且不能修改。
map 和 set 容器中,一个键只能对应一个实例。而 multiset 和 multimap 类型则允许一个键对应多个实例。例如,在电话簿中,每个人可能有多个电话号码。在作者的文章集中,每位作者可能发表了多篇文章。
multimap 和 multiset 类型与相应的单元素版本具有相同的头文件定义:分别是 map
和 set
头文件。
multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同,只有一个例外:multimap 不支持下标运算。不能对 multimap 对象使用下标操作,因为在这类容器中,某个键可能对应多个值。为了顺应一个键可以对应多个值这一性质,map 和 multimap,或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 时,对于某个键,必须做好处理多个值的准备,而非只有单一的值。
迭代遍历 multimap 或 multiset 容器时,可保证依次返回特定键所关联的所有元素。
在 map 或 set 容器中查找一个元素很简单——该元素要么在要么不在容器中。但对于 multimap 或 multiset,该过程就复杂多了:某键对应的元素可能出现多次。
上述问题可用三种策略解决:
:表28 返回迭代器的关联容器操作
m.lower_bound(k) |
返回一个迭代器,指向键不小于 k 的第一个元素 |
m.upper_bound(k) |
返回一个迭代器,指向键大于 k 的第一个元素 |
m.equal_range(k) |
返回一个迭代器的 pair 对象。它的 first 成员等价于 m.lower_bound(k) 。而 second 成员则等价于 m.upper_bound(k) 。 |
标准库为每一种标准容器定义了一种迭代器类型。迭代器类型提供了比下标操作更通用化的方法。所有的标准库容器都定义了相应的迭代器类型,而只有少数的容器支持下标操作。
一个迭代器的典型用法是编写循环:
1 | // equivalent loop using iterators to reset all the elements in ivec to 0 |
每种容器类型都定义了自己的迭代器类型,如 vector:
1 | vector<int>::iterator iter; |
这符语句定义了一个名为 iter 的变量,它的数据类型是 vector<int>
定义的 iterator 类型。每个标准库容器类型都定义了一个名为 iterator 的成员,这里的 iterator 与迭代器实际类型的含义相同。
:表29 常用的迭代器运算
*iter |
返回迭代器 iter 所指向的元素的引用 |
iter->mem |
对 iter 进行解引用,获取指定元素中名为 mem 的成员。等效于(*iter).mem |
++iter iter++ |
给 iter 加 1,使其指向容器里的下一个元素 |
--iter iter-- |
给 iter 减 1,使其指向容器里的前一个元素 |
iter1 == iter2 iter1 != iter2 |
比较两个迭代器是否相等(或不等)。当两个迭代器指向同一个容器中的同一个元素,或者当它们都指向同一个容器的超出末端的下一位置时,两个迭代器相等 |
C++ 定义的容器类型中,只有 vector 和 deque 容器提供下面两种重要的运算集合:迭代器算术运算,以及使用除了 == 和 != 之外的关系操作符来比较两个迭代器(== 和 != 这两种关系运算适用于所有容器)。
:表30 vector 和 deque 容器的迭代器提供额外的运算
iter + n |
在迭代器上加(减)整数值 n,将产生指向容器中前面(后面)第 n 个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置 |
iter - n |
|
iter1 += iter2 |
这是迭代器加减法的复合赋值运算:将 iter1 加上或减去 iter2 的运算结果赋给 iter1 |
iter1 -= iter2 |
|
iter1 - iter2 |
两个迭代器的减法,其运算结果加上右边的迭代器即得左边的迭代器。这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置。只适用于 vector 和 deque 容器 |
> , >= , < , <= |
迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前,则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置。只适用于 vector 和 deque 容器 |
关系操作符只适用于 vector 和 deque 容器,这是因为只有这种两种容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素位置实现的随机访问,因此它们的迭代器可以有效地实现算术和关系运算。
另一方面,。list 容器的迭代器既不支持算术运算(加法或减法),也不支持关系运算(<=, <, >=, >),它只提供前置和后置的自增、自减运算以及相等(不等)运算。
C++ 语言还提供了另外三种迭代器,以为泛型算法提供便利:
上述迭代器类型都在 iterator
头文件中定义。
C++ 语言提供了三种插入器,其差别在于插入元素的位置不同。
示例:
1 | // position an iterator into ilst |
虽然 iostream 类型不是容器,但标准库同样提供了在 iostream 对象上使用的迭代器:istream_iterator 用于读取输入流,而 ostream_iterator 则用于写输出流。
流迭代器有下面几个重要的限制:
->
操作符。考虑下面的例子,从标准输入读取一些数,再将读取的不重复的数写到标准输出:
1 | istream_iterator<int> cin_it(cin); |
反向迭代器是一种反向遍历容器的迭代器。也就是,从最后一个元素到第一个元素遍历容器。反向迭代器将自增(和自减)的含义反过来了:对于反向迭代器,++
运算将访问前一个元素,而 --
运算则访问下一个元素。
示例:逆序输出元素
1 | // reverse iterator of vector from back to front |
每种容器类型还定义了一种名为 const_iterator
的类型,该类型只能用于读取容器内元素,但不能改变其值 。
当我们对普通 iterator 类型解引用时,得到对某个元素的非 const 对象的引用。而如果我们对 const_iterator
类型解引用时,则可以得到一个指向
const 对象的引用,如同任何常量一样,该对象不能进行重写。
例如,如果 text 是 vector<string>
类型,程序员想要遍历它,输出每个元素,可以这样编写程序:
1 | // use const_iterator because we won't change the elements |
使用 const_iterator
类型时,我们可以得到一个迭代器,它自身的值可以改变,但不能用来改变其所指向的元素的值。可以对迭代器进行自增以及使用解引用操作符来读取值,但不能对该元素赋值。
可以将迭代器操作分为五个类别:
Input iterator(输入迭代器) | 读,不能写;只支持自增运算 |
Output iterator(输出迭代器) | 写,不能读;只支持自增运算 |
Forward iterator(前向迭代器) | 读和写;只支持自增运算 |
Bidirectional iterator(双向迭代器) | 读和写;支持自增和自减运算 |
Random access iterator(随机访问迭代器) | 读和写;支持完整的迭代器算术运算 |
关键概念:算法永不执行容器提供的操作
泛型算法本身从不执行容器操作,只是单独依赖迭代器和迭代器操作实现。这个事实也许比较意外,但本质上暗示了:使用“普通”的迭代器时,算法从不修改基础容器的大小。正如我们所看到的,算法也许会改变存储在容器中的元素的值,也许会在容器内移动元素,但是,算法从不直接添加或删除元素。
使用泛型算法必须包含 algorithm 头文件:
1 |
标准库还定义了一组泛化的算术算法(generalized numeric algorithm),其命名习惯与泛型算法相同。使用这些算法则必须包含 numeric 头文件:
1 |
除了少数例外情况,所有算法都在一段范围内的元素上操作,我们将这段范围称为“输出范围(input range)”。带有输入范围参数的算法总是使用头两个形参标记该范围。这两个形参是分别指向要处理的第一个元素和最后一个元素的下一位置的迭代器。
算法最基本的性质是需要使用的迭代器种类。所有算法都指定了它的每个迭代器形参可使用的迭代器类型。
任何其他的算法分类都含有一组形参规范。理解这些形参规范有利于学习新的算法——只要知道形参的含义,就可专注于了解算法实现的操作。大多数算法采用下面四种形式之一:
1 | alg (beg, end, other parms); |
其中,alg 是算法的名字,beg 和 end 指定算法操作的元素范围。我们通常将该范围称为算法的“输入范围”。尽管几乎所有算法都有输入范围,但算法是否使用其他形参取决于它所执行的操作。这里列出了比较常用的其他形参:dest、beg2 和 end2,它们都是迭代器。这些迭代器在使用时,充当类似的角色。除了这些迭代器形参之外,有些算法还带有其他的非迭代器形参,它们是这些算法特有的。
很多算法通过检查其输入范围内的元素实现其功能。这些算法通常要用到标准关系操作符:== 或 <。其中的大部分算法会提供第二个版本的函数,允许程序员提供比较或测试函数取代操作符的使用。
有些算法提供所谓的“复制(copying)”版本。这些算法对输入序列的元素做出处理,但不修改原来的元素,而是创建一个新序列存储元素的处理结果。但不修改原来的元素,而是创建一个新序列存储元素的处理结果。
举例: