string

string 类型支持长度可变的字符串,C++ 标准库将负责管理与存储字符相关的内存,以及提供各种有用的操作。标准库 string 类型的目的就是满足对字符串的一般应用。

1
2
#include <string>
using std::string;

定义和初始化

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 数据类型的使用,这很重要。

读写

使用标准输入输出操作符来读写 string 对象:

1
2
3
4
5
6
7
8
// Note: #include and using declarations must be added to compile this code
int main()
{
string s; // empty string
cin >> s; // read whitespace-separated string into s
cout << s << endl; // write s to the output
return 0;
}

从标准输入读取 string 并将读入的串存储在 s 中。string 类型的输入操作符:

  • 读取并忽略开头所有的空白字符(如空格,换行符,制表符)。
  • 读取字符直至再次遇到空白字符,读取终止。

读入未知数目的 string 对象

和内置类型的输入操作一样, string 的输入操作符也会返回所读的数据流

因此,可以把输入操作作为判断条件,下面的程序将从标准输入读取一组 string 对象,然后在标准输出上逐行输出:

1
2
3
4
5
6
7
8
int main()
{
string word;
// read until end-of-file, writing each word to a new line
while (cin >> word)
cout << word << endl;
return 0;
}

上例中,用输入操作符来读取 string 对象。该操作符返回所读的 istream 对象,并在读取结束后,作为 while 的判断条件。如果输入流是有效的,即还未到达文件尾且未遇到无效输入,则执行 while 循环体,并将读取到的字符串输出到标准输出。如果到达了文件尾,则跳出 while 循环。

使用 getline 读取整行文本

另外还有一个有用的 string IO 操作:getline。这个函数接受两个参数:一个输入流对象和一个 string 对象。getline 函数从输入流的下一行读取,并保存读取的内容到不包括换行符。和输入操作符不一样的是,getline 并不忽略行开头的换行符。只要 getline 遇到换行符,即便它是输入的第一个字符,getline 也将停止读入并返回。如果第一个字符就是换行符,则 string 参数将被置为空 string。

getline 函数将 istream 参数作为返回值,和输入操作符一样也把它用作判断条件。例如,重写前面那段程序,把每行输出一个单词改为每次输出一行文本:

1
2
3
4
5
6
7
8
int main()
{
string line;
// read line at time until end-of-file
while (getline(cin, line))
cout << line << endl;
return 0;
}

由于 line 不含换行符,若要逐行输出需要自行添加。照常,我们用 endl 来输出一个换行符并刷新输出缓冲区。

操作


s.empty() 如果 s 为空串,则返回 true,否则返回 false。 s.size() 返回 s 中字符的个数 s[n] 返回 s 中位置为 n 的字符,位置从 0 开始计数 s1 + s2 把 s1 和 s2 连接成一个新字符串,返回新生成的字符串 s1 = s2 把 s1 内容替换为 s2 的副本 v1 == v2 比较 v1 与 v2 的内容,相等则返回 true,否则返回 false !=, <, <=, >, >= 保持这些操作符惯有的含义 substr 函数 返回当前 string 对象的子串 appendreplace 函数 用于修改 string 对象 一系列 find 函数 用于查找 string 对象


:表2 string标准库支持的操作

任何存储 string 的 size 操作结果的变量必须为 string::size_type 类型,以做到机器无关。特别重要的是,还要把 size 的返回值赋给一个 int 变量。

string 类型还支持大多数顺序容器操作

关系操作符

string 类定义了几种关系操作符用来比较两个 string 值的大小。

string 对象比较操作是区分大小写的,即同一个字符的大小写形式被认为是两个不同的字符。在多数计算机上,大写的字母位于小写之前:任何一个大写之母都小于任意的小写字母。

  • 如果两个 string 对象长度不同,且短的 string 对象与长的 string 对象的前面部分相匹配,则短的 string 对象小于长的 string 对象。
  • 如果 string 对象的字符不同,则比较第一个不匹配的字符。

连接操作

当进行 string 对象和字符串字面值混合连接操作时, +操作符的左右操作数必须至少有一个是 string 类型的

1
2
3
4
5
6
string s1 = "hello"; // no punctuation
string s2 = "world";
string s3 = s1 + ", "; // ok: adding a string and a literal
string s4 = "hello" + ", "; // error: no string operand
string s5 = s1 + ", " + "world"; // ok: each + has string operand
string s6 = "hello" + ", " + s2; // error: can't add string literals

s3 和 s4 的初始化只用了一个单独的操作。在这些例子中,很容易判断 s3 的初始化是合法的:把一个 string 对象和一个字符串字面值连接起来。

而 s4 的初始化试图将两个字符串字面值相加,因此是非法的。 s5 的初始化方法显得有点不可思议,但这种用法和标准输入输出的串联效果是一样的(1.2 节)。本例中,string 标准库定义加操作返回一个 string 对象。这样,在对 s5 进行初始化时,子表达式 s1 + ", " 将返回一个新 string 对象,后者再和字面值 "world\n"连接。整个初始化过程可以改写为:

1
2
string tmp = s1 + ", "; // ok: + has a string operand
s5 = tmp + "world"; // ok: + has a string operand

而 s6 的初始化是非法的。依次来看每个子表达式,则第一个子表达式试图把两个字符串字面值连接起来。这是不允许的,因此这个语句是错误的。

substr 操作

使用 substr 操作可在指定 string 对象中检索需要的子串。

s.substr(pos, n) 返回一个 string 类型的字符串,它包含 s 中从下标 pos 开始的 n 个字符
s.substr(pos) 返回一个 string 类型的字符串,它包含从下标 pos 开始到 s 末尾的所有字符
s.substr() 返回 s 的副本

:表3 substr操作

示例:

1
2
3
4
string s("hello world");
// return substring of 5 characters starting at position 6
string s2 = s.substr(6, 5);
// s2 = world

append 和 replace 操作

string 类型提供了 6 个 append 重载函数版本和 10 个 replace 版本。

s.append(args) 将 args 串接在 s 后面。返回 s 引用
s.replace(pos, len, args) 删除 s 中从下标 pos 开始的 len 个字符,用 args 指定的字符替换之。返回 s 的引用。** 在这个版本中,args 不能为 b2,e2**
s.replace(b, e, args) 删除迭代器 b 和 e 标记范围内所有的字符,用 args 替换之。返回 s 的引用。在这个版本中,args 不能为 s2,pos2,len2

:表4 append 和 replace 函数的所有重载版本

append 和 replace 函数使用了相同的参数集合实现重载:

s2 string 类型的字符串 s2
s2, pos2, len2 字符串 s2 中从下标 pos2 开始的 len2 个字符
cp 指针 cp 指向的以空字符结束的数组
cp, len2 cp 指向的以空字符结束的数组中前 len2 个字符
n, c 字符 c 的 n 个副本
b2, e2 迭代器 b2 和 e2 标记的范围内所有字符

:表5 append 和 replace 函数的参数集合

查找操作

string 类提供了 6 种查找函数,每种函数以不同形式的 find 命名。这些操作全都返回 string::size_type 类型的值,以下标形式标记查找匹配所发生的位置;或者返回一个名为 string::npos 的特殊值,说明查找没有匹配。string 类将 npos 定义为保证大于任何有效下标的值。

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 的字符

:表6 string 查找函数

每种查找操作都有 4 个重载版本,每个版本使用不同的参数集合。

c, pos 在 s 中,从下标 pos 标记的位置开始,查找字符 c。pos 的默认值为 0
s2, pos 在 s 中,从下标 pos 标记的位置开始,查找 string 对象 s2。pos 的默认值为 0
cp, pos 在 s 中,从下标 pos 标记的位置形参,查找指针 cp 所指向的 C 风格的以空字符结束的字符串。pos 的默认值为 0
cp, pos, n 在 s 中,从下标 pos 标记的位置开始,查找指针 cp 所指向数组的前 n 个字符。pos 和 n 都没有默认值

:表7 string 查找函数的参数集合

基本上,这些操作的不同之处在于查找的到底是单个字符、另一个 string 字符串、C 风格的以空字符结束的字符串,还是用字符数组给出的特定数目的字符集合。

示例

1
2
3
4
string name("AnnaBelle");
string::size_type pos1 = name.find("Anna"); // pos1 == 0
string lowercase("annabelle");
pos1 = lowercase.find("Anna"); // pos1 == npos

find 操作的返回类型是 string::size_type,请使用该类型的对象存储 find 的返回值。

compare 操作

除了关系操作符,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 函数返回下面列出的三种可能值之一:

  1. 正数,此时 s1 大于 args 所代表的 string 对象。
  2. 负数,此时 s1 小于 args 所代表的 string 对象。
  3. 0,此时 s1 恰好等于 args 所代表的 string 对象。

字符处理

下表列出了各种字符操作函数,适用于 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
2
3
4
5
6
7
8
string s("Hello World!!!");
string::size_type punct_cnt = 0;
// count number of punctuation characters in s
for (string::size_type index = 0; index != s.size(); ++index)
if (ispunct(s[index]))
++punct_cnt;
cout << punct_cnt
<< " punctuation characters in " << s << endl;

这个程序的输出结果是:

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++ 所特有的。

bitset

有些程序要处理二进制位的有序集,每个位可能包含 0(关)1(开)值。位是用来保存一组项或条件的 yes/no 信息(有时也称标志)的简洁方法。标准库提供的 bitset 类简化了位集的处理。要使用 bitset 类就必须包含相关的头文件。

1
2
#include <bitset>
using std::bitset;

定义和初始化


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 值初始化 bitset 对象

当用 unsigned long 值作为 bitset 对象的初始值时,该值将转化为二进制的位模式。而 bitset 对象中的位集作为这种位模式的副本。如果 bitset 类型长度大于 unsigned long 值的二进制位数,则其余的高阶位将置为 0;如果 bitset 类型长度小于 unsigned long 值的二进制位数,则只使用 unsigned 值中的低阶位,超过 bitset 类型长度的高阶位将被丢弃。

在 32 位 unsigned long 的机器上,十六进制值 0xffff 表示为二进制位就是十六个 1 和十六个 0(每个 0xf 可表示为 1111)。可以用 0xffff 初始化 bitset 对象:

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <bitset>
using namespace std;
int main(void)
{
unsigned int a = 0xffff;
bitset<16> bitvec1(a);
bitset<32> bitvec2(a);
bitset<128> bitvec3(a);
cout << "bitvec1: " << bitvec1 << endl;
cout << "bitvec2: " << bitvec2 << endl;
cout << "bitvec3: " << bitvec3 << endl;
return 0;
}

输出

1
2
3
bitvec1: 1111111111111111
bitvec2: 00000000000000001111111111111111
bitvec3: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111

上面的三个例子中,0 到 15 位都置为 1。由于 bitvec1 位数少于 unsigned long 的位数,因此 bitvec1 的初始值的高阶被丢弃。bitvec2 和 unsigned long 长度相同,因此所有位正好放置了初始值。bitvec3 长度大于 32,31 位以上的高阶位就被置为 0。

用 string 对象初始化 bitset 对象

当用 string 对象初始化 bitset 对象时,string 对象直接表示为位模式。从 string 对象读入位集的顺序是从右向左(from right to left):

1
2
string strval("1100");
bitset<32> bitvec4(strval);

bitvec4 的位模式中第 2 和 3 的位置为 1,其余位置都为 0。如果 string 对象的字符个数小于 bitset 类型的长度,则高阶位置为 0。

string 对象和 bitsets 对象之间是反向转化的:string 对象的最右边字符(即下标最大的那个字符)用来初始化 bitset 对象的低阶位(即下标为 0 的位)。当用 string 对象初始化 bitset 对象时,记住这一差别很重要。

不一定要把整个 string 对象都作为 bitset 对象的初始值。相反,可以只用某个子串作为初始值:

1
2
3
string str("1111111000000011001101");
bitset<32> bitvec5(str, 5, 4); // 4 bits starting at str[5], 1100
bitset<32> bitvec6(str, str.size() - 4); // use last 4 characters

操作

多种 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 对象

如果 bitset 对象中有一个或几个二进制位置为 1,则 any 操作返回 true,也就是说,其返回值等于 1;相反,如果 bitset 对象中二进制位全为 0,则 none 操作返回 true。

1
2
3
bitset<32> bitvec; // 32 bits, all zero
bool is_set = bitvec.any(); // false, all bits are zero
bool is_not_set = bitvec.none(); // true, all bits are 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

示例:访问 bitset 对象中的位

可以用下标操作符来读或写某个索引位置的二进制位,同样地,也可以用下标操作符测试给定二进制位的值或设置某个二进制们的值:

1
2
3
// assign 1 to even numbered bits
for (int index = 0; index != 32; index += 2)
bitvec[index] = 1;

上面的循环把 bitvec 中的偶数下标的位都置为 1。 除了用下标操作符,还可以用 set;、test 和 reset 操作来测试或设置给定二进制位的值:

1
2
3
// equivalent loop using set operation
for (int index = 0; index != 32; index += 2)
bitvec.set(index);

为了测试某个二进制位是否为 1,可以用 test 操作或者测试下标操作符的返回值:

1
2
3
4
5
if (bitvec.test(i))
// bitvec[i] is on
// equivalent test using subscript
if (bitvec[i])
// bitvec[i] is on

如果下标操作符测试的二进制位为 1,则返回的测试值的结果为 true,否则返回 false。

示例:对整个 bitset 对象进行设置

set 和 reset 操作分别用来对整个 bitset 对象的所有二进制位全置 1 和全置 0:

1
2
bitvec.reset(); // set all the bits to 0.
bitvec.set(); // set all the bits to 1

flip 操作可以对 bitset 对象的所有位或个别位取反:

1
2
3
bitvec.flip(0); // reverses value of first bit
bitvec[0].flip(); // also reverses the first bit
bitvec.flip(); // reverses value of all bits

示例:获取 bitset 对象的值

to_ulong 操作返回一个 unsigned long 值,该值与 bitset 对象的位模式存储值相同。仅当 bitset 类型的长度小于或等于 unsigned long 的长度时,才可以使用 to_ulong 操作:

1
2
unsigned long ulong = bitvec3.to_ulong();
cout << "ulong = " << ulong << endl;

to_ulong 操作主要用于把 bitset 对象转到 C 风格或标准 C++ 之前风格的程序上。如果 bitset 对象包含的二进制位数超过 unsigned long 长度,将会产生运行时异常。

示例:输出

可以用输出操作符输出 bitset 对象中的位模式:

1
2
bitset<32> bitvec2(0xffff); // bits 0 ... 15 are set to 1; 16 ... 31 are 0
cout << "bitvec2: " << bitvec2 << endl;

输出结果为:

1
bitvec2: 00000000000000001111111111111111

pair 类型

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
2
3
#include <vector>
#include <list>
#include <deque>

C<T> c; 默认构造函数。创建一个名为 c 的空容器。C 是容器类型名,如 vector,T 是元素类型,如 int 或 string 适用于所有容器。
C c(c2); 复制构造函数。创建容器 c2 的副本 c;c 和 c2 必须具有相同的容器类型,并存放相同类型的元素。适用于所有容器。
C c(b,e); 创建 c,其元素是迭代器 b 和 e 标示的范围内元素的副本。适用于所有容器。
C c(n,t); 用 n 个值为 t 的元素创建容器 c,其中值 t 必须是容器类型 C 的元素类型的值,或者是可转换为该类型的值。只适用于顺序容器
C c(n); 创建有 n 个值初始化(value-initialized)元素的容器 c。只适用于顺序容器

:表13 顺序容器的构造函数

为了使程序更清晰、简短,容器类型最常用的构造函数是默认构造函数。在大多数的程序中,使用默认构造函数能达到最佳运行时性能,并且使容器更容易使用。

容器元素的类型约束

支持复制赋值功能是容器元素类型的最低要求。

C++ 语言中,大多数类型都可用作容器的元素类型。容器元素类型必须满足以下两个约束:

  • 元素类型必须支持赋值运算。
  • 元素类型的对象必须可以复制。

反例:引用类型、输入输出(IO)标准库类型、auto_ptr类型,这些类型不能作为容器元素。

特别的,容器本身也可以作为容器元素,因此,可以定义元素本身就是容器类型的容器。例如,可以定义 vector 类型的容器 lines,其元素为 string 类型的 vector 对象:

1
2
// note spacing: use ">>" not ">>" when specifying a container
vector< vector <string> > lines; // vector of vectors

注意,必须用空格隔开两个相邻的 > 符号,以示这是两个分开的符号,否则,系统会认为 >> 是单个符号,为右移操作符,并导致编译时错误。

1
2
vector< vector<string> > lines; // ok: space required between close >
vector< vector<string>> lines; // error: >> treated as shift operator

顺序容器的操作

每种顺序容器都提供了一组有用的类型定义以及以下操作:

  • 在容器中添加元素。
  • 在容器中删除元素。
  • 设置容器大小。
  • (如果有的话)获取容器内的第一个和最后一个元素。

容器定义的类型别名:

size_type 无符号整型,足以存储此容器类型的最大可能容器长度
iterator 此容器类型的迭代器类型
const_iterator 元素的只读迭代器类型
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 元素的只读(不能写)逆序迭代器
difference_type 足够存储两个迭代器差值的有符号整型,可为负数
value_type 元素类型
reference 元素的左值类型,是 value_type& 的同义词
const_reference 元素的常量左值类型,等效于 const value_type&

:表14 顺序容器定义的类型别名

begin 和 end 操作

begin 和 end 操作产生指向容器内第一个元素和最后一个元素的下一位置的迭代器。这两个迭代器通常用于标记包含容器中所有元素的迭代器范围。

c.begin() 返回一个迭代器,它指向容器 c 的第一个元素
c.end() 返回一个迭代器,它指向容器 c 的最后一个元素的下一位置
c.rbegin() 返回一个逆序迭代器,它指向容器 c 的最后一个元素
c.rend() 返回一个逆序迭代器,它指向容器 c 的第一个元素前面的位置

:表15 begin和end操作

由 end 操作返回的迭代器指向 vector 的末端元素的下一个 。“超出末端迭代器”(off-the-end iterator)。表明它指向了一个不存在的元素。

如果 vector 为空,begin 返回的迭代器与 end 返回的迭代器相同。

在顺序容器中添加元素

c.push_back(t) 在容器 c 的前端添加值为 t 的元素。返回 void 类型
c.push_front(t) 在容器 c 的尾部添加值为 t 的元素。返回 void 类型。只适用于 list 和 deque 容器类型
c.insert(p,t) 在迭代器 p 所指向的元素前面插入值为 t 的新元素。返回指向新添加元素的迭代器
c.insert(p,n,t) 在迭代器 p 所指向的元素前面插入 n 个值为 t 的新元素。返回 void 类型
c.insert(p,b,e) 在迭代器 p 所指向的元素前面插入由迭代器 b 和 e 标记的范围内的元素。返回 void 类型

:表16 顺序容器添加元素操作

在 vector 容器中添加元素可能会导致整个容器的重新加载,这样的话,该容器涉及的所有迭代器都会失效。即使需要重新加载整个容器,指向新插入元素后面的那个元素的迭代器也会失效。

关系操作符

所有的容器类型都支持用关系操作符来实现两个容器的比较。但比较的容器必须具有相同的容器类型,而且其元素类型也必须相同

容器的比较是基于容器内元素的比较。容器的比较使用了元素类型定义的同一个关系操作符:两个容器做 != 比较使用了其元素类型定义的 != 操作符。如果容器的元素类型不支持某种操作符,则该容器就不能做这种比较运算。

  • 如果两个容器具有相同的长度而且所有元素都相等,那么这两个容器就相等;否则,它们就不相等。
  • 如果两个容器的长度不相同,但较短的容器中所有元素都等于较长容器中对应的元素,则称较短的容器小于另一个容器。
  • 如果两个容器都不是对方的初始子序列,则它们的比较结果取决于所比较的第一个不相等的元素。

C++ 语言只允许两个容器做其元素类型定义的关系运算。

容器大小的操作

c.size() 返回容器 c 中的元素个数。返回类型为 c::size_type
c.max_size() 返回容器 c 可容纳的最多元素个数,返回类型为 c::size_type
c.empty() 返回标记容器大小是否为 0 的布尔值
c.resize(n) 调整容器 c 的长度大小,使其能容纳 n 个元素,如果 n < c.size(),则删除多出来的元素;否则,添加采用值初始化的新元素
c.resize(n,t) 调整容器 c 的长度大小,使其能容纳 n 个元素。所有新添加的元素值都为 t

:表17 顺序容器大小相关操作

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 顺序容器删除元素操作

删除元素会使对应的迭代器失效。

赋值与 swap

c1 = c2 删除容器 c1 的所有元素,然后将 c2 的元素复制给 c1。c1 和 c2 的类型(包括容器类型和元素类型)必须相同
c1.swap(c2) 交换内容:调用完该函数后,c1 中存放的是 c2 原来的元素, c2 中存放的则是 c1 原来的元素。c1 和 c2 的类型必须相同。该函数的执行速度通常要比将 c2 复制到 c1 的操作快
c.assign(b,e) 重新设置 c 的元素:将迭代器 b 和 e 标记的范围内所有的元素复制到 c 中。b 和 e 必须不是指向 c 中元素的迭代器
c.assign(n,t) 将容器 c 重新设置为存储 n 个值为 t 的元素

:表20 顺序容器赋值与swap操作

与赋值相关的操作符都作用于整个容器。除 swap 操作外,其他操作都可以用 erase 和 insert 操作实现。赋值操作符首先 erases 其左操作数容器中的所有元素,然后将右操作数容器的所有元素 inserts 到左边容器中:

1
2
3
4
c1 = c2; // replace contents of c1 with a copy of elements in c2
// equivalent operation using erase and insert
c1.erase(c1.begin(), c1.end()); // delete all elements in c1
c1.insert(c1.begin(), c2.begin(), c2.end()); // insert c2

赋值后,左右两边的容器相等:尽管赋值前两个容器的长度可能不相等,但赋值后两个容器都具有右操作数的长度。

赋值和 assign 操作使左操作数容器的所有迭代器失效。swap 操作则不会使迭代器失效。完成 swap 操作后,尽管被交换的元素已经存放在另一容器中,但迭代器仍然指向相同的元素。

vector 的空间分配

为了支持快速的随机访问,vector 容器的元素以连续的方式存放——每一个元素都紧挨着前一个元素存储。

已知元素是连续存储的,当我们在容器内添加一个元素时,想想会发生什么事情:如果容器中已经没有空间容纳新的元素,此时,由于元素必须连续存储以便索引访问,所以不能在内存中随便找个地方存储这个新元素。于是,vector 必须重新分配存储空间,用来存放原来的元素以及新添加的元素:存放在旧存储空间中的元素被复制到新存储空间里,接着插入新元素,最后撤销旧的存储空间。如果 vector 容器在在每次添加新元素时,都要这么分配和撤销内存空间,其性能将会非常慢,简直无法接受。

但是,通常出现的反而是以下情况:对于大部分应用,使用 vector 容器是最好的。原因在于,标准库的实现者使用这样内存分配策略:以最小的代价连续存储元素。由此而带来的访问元素的便利弥补了其存储代价。

为了使 vector 容器实现快速的内存分配,其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区,用于存放新添加的元素。于是,不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器,这个分配策略带来显著的效率。事实上,其性能非常好,因此在实际应用中,比起 list 和 deque 容器,vector 的增长效率通常会更高。

capacity 和 reserve 成员

vector 类提供了两个成员函数:capacity 和 reserve 使程序员可与 vector 容器内存分配的实现部分交互工作。

  • capacity 操作获取在容器需要分配更多的存储空间之前能够存储的元素总数;
  • reserve 操作则告诉 vector 容器应该预留多少个元素的存储空间。

  • 弄清楚容器的 capacity(容量)与 size(长度)的区别非常重要。size 指容器当前拥有的元素个数;而 capacity 则指容器在必须分配新存储空间之前可以存储的元素总数。
  • 每当 vector 容器不得不分配新的存储空间时,以加倍当前容量的分配策略实现重新分配。

容器的选用

通常来说,除非找到选择使用其他容器的更好理由,否则 vector 容器都是最佳选择。

容器 插入、删除性能 访问元素性能
vector 慢。除了容器尾部外,其他任何位置上的插入(或删除)操作都要求移动被插入(或删除)元素右边所有的元素。 快。支持随机访问。
list 快。在任何位置都可高效地 insert 或 erase 一个元素。 慢,不支持随机访问。
deque 慢。从 deque 队列的首部和尾部插入和删除元素都非常快。在容器中间插入或删除付出的代价将更高。 快。支持随机访问。

:表21 三种顺序容器的性能比较

在 deque 容器首部或尾部插入元素不会使任何迭代器失效,而首部或尾部删除元素则只会使指向被删除元素的迭代器失效。在 deque 容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器都失效。

下面列举了一些选择容器类型的法则:

  1. 如果程序要求随机访问元素,则应使用 vector 或 deque 容器。
  2. 如果程序必须在容器的中间位置插入或删除元素,则应采用 list 容器。如果程序不是在容器的中间位置,而是在容器首部或尾部插入或删除元素,则应采用 deque 容器。
  3. 如果只需在读取输入时在容器的中间位置插入元素,然后需要随机访问元素,则可考虑在输入时将元素读入到一个 list 容器,接着对此容器重新排序,使其适合顺序访问,然后将排序后的 list 容器复制到一个 vector 容器。

容器适配器

除了顺序容器,标准库还提供了三种顺序容器适配器:queue、priority_queue 和 stack。

适配器(adaptor)是标准库中通用的概念,包括容器适配器、迭代器适配器和函数适配器。本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如,stack(栈)适配器可使任何一种顺序容器以栈的方式工作。

size_type 一种类型,足以存储此适配器类型最大对象的长度
value_type 元素类型
container_type 基础容器的类型,适配器在此容器类型上实现
A a; 创建一个新空适配器,命名为 a
A a(c); 创建一个名为 a 的新适配器,初始化为容器 c 的副本
关系操作符 所有适配器都支持全部关系操作符: ==!=<<=>>=

:表22 适配器通用的操作和类型

使用适配器时,必须包含相关的头文件:

1
2
3
4
#include <stack>
// stack adaptor
#include <queue>
// both queue and priority_queue adaptors

适配器的初始化

所有适配器都定义了两个构造函数:默认构造函数用于创建空对象,而带一个容器参数的构造函数将参数容器的副本作为其基础值。例如,假设 deq 是 deque<int> 类型的容器,则可用 deq 初始化一个新的栈,如下所示:

1
stack<int> stk(deq); // copies elements from deq into stk

覆盖基础容器类型

默认的 stack 和 queue 都基于 deque 容器实现,而 priority_queue 则在 vector 容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型实参,可覆盖其关联的基础容器类型:

1
2
3
4
5
// empty stack implemented on top of vector
stack< string, vector<string> > str_stk;
// str_stk2 is implemented on top of vector and holds a copy of svec
stack<string, vector<string> > str_stk2(svec);

使用适配器要注意两点

  1. 对于给定的适配器,其关联的容器必须满足一定的约束条件。stack 适配器所关联的基础容器可以是任意一种顺序容器类型。因此, stack 栈可以建立在 vector、list 或者 deque 容器之上。而 queue 适配器要求其关联的基础容器必须提供 push\_front 运算,因此只能建立在 list 容器上,而不能建立在 vector 容器上。priority_queue 适配器要求提供随机访问功能,因此可建立在 vector 或 deque 容器上,但不能建立在 list 容器上。
  2. 应该选择使用适配器的操作而不是所基础容器的操作。例如,尽管栈是以 deque 容器为基础实现的,但是程序员不能直接访问deque 所提供的操作。如不能在栈上调用 push_back 函数,而是必须使用栈所提供的名为 push 的操作。

适配器的运算

:表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 类型视为字符容器。除了一些特殊操作,string 类型提供与 vector 容器相同的操作。string 类型与 vector 容器不同的是,它不支持以栈方式操纵容器:在 string 类型中不能使用 front、back 和 pop_back 操作。

string支持的容器操作有:

  • 13 列出的容器构造函数,但是不包括只需要一个长度参数的构造函数。
  • 14 列出的 typedef,包括迭代器类型。
  • 15 列出的 begin 和 end 操作。
  • 16 列出的 vector 容器所提供的添加元素的操作。注意:无论 vector 容器还是 string 类型都不支持 push_front 操作。
  • 17 列出的长度操作。
  • 18 列出的下标和 at 操作;但 string 类型不提供该表列出的 back 和 front 操作。
  • 19 列出的 erase 和 clear 操作;但是 string 类型不入提供 pop_back 或 pop_front 操作。
  • 20 列出的赋值操作。

与 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 操作。

顺序容器和关联容器公共的操作包括下面的几种:

  • 13 列出的前三种容器构造函数(关联容器不能通过容器大小来定义,因为这样的话就无法知道键所对应的值是什么);
  • 关系运算
  • 14 列出的类型别名(typedef)。注意,对于 map 容器,value_type并非元素的类型,而是描述键及其关联值类型的 pair 类型。
  • 15 列出的 begin、end、rbegin 和 rend 操作;
  • 17 列出的关于容器大小的操作。但 resize 函数不能用于关联容器。
  • 18 列出的下标和 at 操作;但 string 类型不提供该表列出的 back 和 front 操作。
  • 19 列出的 clear 和 erase 操作,但关联容器的 erase 运算返回 void 类型。
  • 20 swap 和赋值操作。但关联容器不提供 assign 函数。

除了上述列出的操作之外,关联容器还提供了其他的操作。而对于顺序容器也提供的相同操作,关联容器也重新定义了这些操作的含义或返回类型,其中的差别在于关联容器中使用了键。

map

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 定义的类型

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
2
3
4
5
6
7
8
// get an iterator to an element in word_count
map<string, int>::iterator map_it = word_count.begin();
// *map_it is a reference to a pair<const string, int> object
cout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element
map_it->first = "new key"; // error: key is const
++map_it->second; // ok: we can change value through an iterator

对迭代器进行解引用将获得一个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
2
3
4
map <string, int> word_count; // empty map
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;

通常来说,下标操作符返回左值。它返回的左值是特定键所关联的值。可如下读或写元素:

1
2
3
4
cout << word_count["Anna"]; // fetch element indexed by Anna; prints 1
++word_count["Anna"]; // fetch the element and add one to it
cout << word_count["Anna"]; // fetch the element and print it; prints 2

示例:一个单词计数器

对于 map 容器,如果下标所表示的键在容器中不存在,则添加新元素,这一特性可使程序惊人地简练:

1
2
3
4
5
// count number of times each word occurs in the input
map<string, int> word_count; // empty map from string to int
string word;
while (cin >> word)
++word_count[word];

插入元素

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
2
3
4
5
6
7
8
9
10
11
12
// count number of times each word occurs in the input
map<string, int> word_count; // empty map from string to int
string word;
while (cin >> word) {
// inserts element with key equal to word and value 1;
// if word already in word_count, insert does nothing
pair<map<string, int>::iterator, bool> ret =
word_count.insert(make_pair(word, 1));
if (!ret.second)
// word already in word_count
++ret.first->second; // increment counter
}

查找元素

下标操作符给出了读取一个值的最简单方法:

1
2
map<string,int> word_count;
int occurs = word_count["foobar"];

但是,使用下标存在一个很危险的副作用:如果该键不在 map 容器中,那么下标操作会插入一个具有该键的新元素。

map 容器提供了两个操作:count 和 find,用于检查某个键是否存在而不会插入该键。

:表26 不修改 map 对象的查询操作

m.count(k) 返回 m 中 k 的出现次数
m.find(k) 如果 m 容器中存在按 k 索引的元素,则返回指向该元素的迭代器。如果不存在,则返回超出末端迭代器
示例

使用 count 检查 map 对象中某键是否存在:

1
2
3
int occurs = 0;
if (word_count.count("foobar"))
occurs = word_count["foobar"];

读取元素而不插入元素:

find 操作返回指向元素的迭代器,如果元素不存在,则返回 end 迭代器:

1
2
3
4
int occurs = 0;
map<string,int>::iterator it = word_count.find("foobar");
if (it != word_count.end())
occurs = it->second;

删除元素

:表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
2
3
4
5
6
7
8
9
10
// get iterator positioned on the first element
map<string, int>::const_iterator
map_it = word_count.begin();
// for each element in the map
while (map_it != word_count.end()) {
// print the element key, value pairs
cout << map_it->first << " occurs "
<< map_it->second << " times" << endl;
++map_it; // increment iterator to denote the next element
}

set

set 容器只是单纯的键的集合。

set 容器支持大部分的 map 操作,除了两种例外情况:

  1. set 不支持下标操作符
  2. set 没有定义 mapped_type 类型。

在 set 容器中,value_type 不是 pair 类型,而是与 key_type 相同的类型。它们指的都是 set 中存储的元素类型。这一差别也体现了 set 存储的元素仅仅是键,而没有所关联的值。与 map 一样,set 容器存储的键也必须唯一,而且不能修改。

multimap 和 multiset

map 和 set 容器中,一个键只能对应一个实例。而 multiset 和 multimap 类型则允许一个键对应多个实例。例如,在电话簿中,每个人可能有多个电话号码。在作者的文章集中,每位作者可能发表了多篇文章。

multimap 和 multiset 类型与相应的单元素版本具有相同的头文件定义:分别是 mapset 头文件。

multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同,只有一个例外:multimap 不支持下标运算。不能对 multimap 对象使用下标操作,因为在这类容器中,某个键可能对应多个值。为了顺应一个键可以对应多个值这一性质,map 和 multimap,或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 时,对于某个键,必须做好处理多个值的准备,而非只有单一的值。

元素的添加和删除

  • 由于键不要求是唯一的,因此每次调用 insert 总会添加一个元素。
  • 带有一个键参数的 erase 版本将删除拥有该键的所有元素,并返回删除元素的个数。而带有一个或一对迭代器参数的版本只删除指定的元素,并返回 void 类型。

遍历元素

迭代遍历 multimap 或 multiset 容器时,可保证依次返回特定键所关联的所有元素。

查找元素

在 map 或 set 容器中查找一个元素很简单——该元素要么在要么不在容器中。但对于 multimap 或 multiset,该过程就复杂多了:某键对应的元素可能出现多次。

上述问题可用三种策略解决:

  1. 使用 find 和 count 操作。count 函数求出某键出现的次数,而 find 操作则返回一个迭代器,指向第一个拥有正在查找的键的实例;
  2. 使用 lower_bound 和 upper_bound 操作。
  3. 直接调用 equal_range 函数。这三个操作都需要传递一个键,并返回一个迭代器。

:表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
2
3
4
// equivalent loop using iterators to reset all the elements in ivec to 0
for (vector<int>::iterator iter = ivec.begin();
iter != ivec.end(); ++iter)
*iter = 0; // set element to which iter refers to 0

容器的 iterator 类型

每种容器类型都定义了自己的迭代器类型,如 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 比较两个迭代器是否相等(或不等)。当两个迭代器指向同一个容器中的同一个元素,或者当它们都指向同一个容器的超出末端的下一位置时,两个迭代器相等

vector 和 deque 容器的迭代器提供额外的运算

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++ 语言还提供了另外三种迭代器,以为泛型算法提供便利:

  1. 插入迭代器:这类迭代器与容器绑定在一起,实现在容器中插入元素的功能。
  2. iostream 迭代器:这类迭代器可与输入或输出流绑定在一起,用于迭代遍历所关联的 IO 流。
  3. 反向迭代器:这类迭代器实现向后遍历,而不是向前遍历。所有容器类型都定义了自己的 reverse_iterator 类型,由 rbegin 和 rend 成员函数返回。

上述迭代器类型都在 iterator 头文件中定义。

插入迭代器

C++ 语言提供了三种插入器,其差别在于插入元素的位置不同。

  • back_inserter,创建使用 push_back 实现插入的迭代器。
  • front_inserter,使用 push_front 实现插入。
  • inserter,使用 insert 实现插入操作。除了所关联的容器外,inserter还带有第二实参:指向插入起始位置的迭代器。

示例:

1
2
3
4
5
6
// position an iterator into ilst
list<int>::iterator it =
find (ilst.begin(), ilst.end(), 42);
// insert replaced copies of ivec at that point in ilst
replace_copy (ivec.begin(), ivec.end(),
inserter (ilst, it), 100, 0);

iostream 迭代器

虽然 iostream 类型不是容器,但标准库同样提供了在 iostream 对象上使用的迭代器:istream_iterator 用于读取输入流,而 ostream_iterator 则用于写输出流。

流迭代器有下面几个重要的限制:

  • 不可能从 ostream_iterator 对象读入,也不可能写到 istream_iterator 对象中。
  • 一旦给 ostream_iterator 对象赋了一个值,写入就提交了。赋值后,没有办法再改变这个值。此外,ostream_iterator 对象中每个不同的值都只能正好输出一次。
  • ostream_iterator 没有 -> 操作符。

考虑下面的例子,从标准输入读取一些数,再将读取的不重复的数写到标准输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
istream_iterator<int> cin_it(cin);
// reads ints from cin
istream_iterator<int> end_of_stream; // end iterator value
// initialize vec from the standard input:
vector<int> vec(cin_it, end_of_stream);
sort(vec.begin(), vec.end());
// writes ints to cout using " " as the delimiter
ostream_iterator<int> output(cout, " ");
// write only the unique elements in vec to the standard output
unique_copy(vec.begin(), vec.end(), output);

反向迭代器

反向迭代器是一种反向遍历容器的迭代器。也就是,从最后一个元素到第一个元素遍历容器。反向迭代器将自增(和自减)的含义反过来了:对于反向迭代器,++ 运算将访问前一个元素,而 -- 运算则访问下一个元素。

示例:逆序输出元素

1
2
3
4
5
6
// reverse iterator of vector from back to front
vector<int>::reverse_iterator r_iter;
for (r_iter = vec.rbegin(); // binds r_iter to last element
r_iter != vec.rend(); // rend refers 1 before 1st element
++r_iter) // decrements iterator one element
cout << *r_iter << endl; // prints 9,8,7,...0

const_iterator

每种容器类型还定义了一种名为 const_iterator 的类型,该类型只能用于读取容器内元素,但不能改变其值

当我们对普通 iterator 类型解引用时,得到对某个元素的非 const 对象的引用。而如果我们对 const_iterator 类型解引用时,则可以得到一个指向 const 对象的引用,如同任何常量一样,该对象不能进行重写。

例如,如果 text 是 vector<string> 类型,程序员想要遍历它,输出每个元素,可以这样编写程序:

1
2
3
4
// use const_iterator because we won't change the elements
for (vector<string>::const_iterator iter = text.begin();
iter != text.end(); ++iter)
cout << *iter << endl; // print each element in text

使用 const_iterator 类型时,我们可以得到一个迭代器,它自身的值可以改变,但不能用来改变其所指向的元素的值。可以对迭代器进行自增以及使用解引用操作符来读取值,但不能对该元素赋值。

小结:五种迭代器

可以将迭代器操作分为五个类别:

Input iterator(输入迭代器) 读,不能写;只支持自增运算
Output iterator(输出迭代器) 写,不能读;只支持自增运算
Forward iterator(前向迭代器) 读和写;只支持自增运算
Bidirectional iterator(双向迭代器) 读和写;支持自增和自减运算
Random access iterator(随机访问迭代器) 读和写;支持完整的迭代器算术运算

泛型算法

关键概念:算法永不执行容器提供的操作

泛型算法本身从不执行容器操作,只是单独依赖迭代器和迭代器操作实现。这个事实也许比较意外,但本质上暗示了:使用“普通”的迭代器时,算法从不修改基础容器的大小。正如我们所看到的,算法也许会改变存储在容器中的元素的值,也许会在容器内移动元素,但是,算法从不直接添加或删除元素。

使用泛型算法必须包含 algorithm 头文件:

1
#include <algorithm>

标准库还定义了一组泛化的算术算法(generalized numeric algorithm),其命名习惯与泛型算法相同。使用这些算法则必须包含 numeric 头文件:

1
#include <numeric>

除了少数例外情况,所有算法都在一段范围内的元素上操作,我们将这段范围称为“输出范围(input range)”。带有输入范围参数的算法总是使用头两个形参标记该范围。这两个形参是分别指向要处理的第一个元素和最后一个元素的下一位置的迭代器。

算法最基本的性质是需要使用的迭代器种类。所有算法都指定了它的每个迭代器形参可使用的迭代器类型。

算法分类

  • 只读算法,不改变元素的值顺序;
  • 给指定元素赋新值的算法;
  • 将一个元素的值移给另一个元素的算法。

算法的形参形式

任何其他的算法分类都含有一组形参规范。理解这些形参规范有利于学习新的算法——只要知道形参的含义,就可专注于了解算法实现的操作。大多数算法采用下面四种形式之一:

1
2
3
4
alg (beg, end, other parms);
alg (beg, end, dest, other parms);
alg (beg, end, beg2, other parms);
alg (beg, end, beg2, end2, other parms);

其中,alg 是算法的名字,beg 和 end 指定算法操作的元素范围。我们通常将该范围称为算法的“输入范围”。尽管几乎所有算法都有输入范围,但算法是否使用其他形参取决于它所执行的操作。这里列出了比较常用的其他形参:dest、beg2 和 end2,它们都是迭代器。这些迭代器在使用时,充当类似的角色。除了这些迭代器形参之外,有些算法还带有其他的非迭代器形参,它们是这些算法特有的。

算法的命名规范

区别带有一个值或一个谓词函数参数的算法版本

很多算法通过检查其输入范围内的元素实现其功能。这些算法通常要用到标准关系操作符:== 或 <。其中的大部分算法会提供第二个版本的函数,允许程序员提供比较或测试函数取代操作符的使用。

区别是否实现复制的算法版本

有些算法提供所谓的“复制(copying)”版本。这些算法对输入序列的元素做出处理,但不修改原来的元素,而是创建一个新序列存储元素的处理结果。但不修改原来的元素,而是创建一个新序列存储元素的处理结果。

举例:

泛型算法的结构

深入阅读

  1. STL Algorithm 库
  2. STL Numeric 库