标准容器和泛型算法

string

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

1
2

#include <string> 
using std::string;

定义和初始化

string 标准库支持几个构造函数。

:表1 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 对象的子串 append 和 replace 函数 用于修改 string 对象 一系列 find 函数 用于查找 string 对象

:表2 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 对象中检索需要的子串。

:表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 版本。

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

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

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

查找操作

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

:表6 string 查找函数

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

:表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

compare 操作

除了关系操作符，string 类型还提供了一组 compare 操作，用于实现字典顺序的比较。这些操作的结果类似于 C 语言中的库函数 strcmp

:表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!!!

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 头文件中定义。

操作

顺序容器

标准库定义了三种顺序容器类型：vector、list 和 deque，以及三种容器适配器（adaptors）。

:表12 顺序容器

:表12 顺序容器适配器

实际上，适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。

定义

为了定义一个容器类型的对象，必须先包含相关的头文件,即下列头文件之一：

1
2
3

#include <vector>
#include <list>
#include <deque>

:表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

顺序容器的操作

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

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

容器定义的类型别名：

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

begin 和 end 操作

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

:表15 begin和end操作

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

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

在顺序容器中添加元素

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

关系操作符

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

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

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

容器大小的操作

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

访问元素

:表18 顺序容器访问元素操作

删除元素

:表19 顺序容器删除元素操作

赋值与 swap

:表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

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

vector 的空间分配

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

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

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

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

capacity 和 reserve 成员

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

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

容器的选用

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

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

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

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

容器适配器

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

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

:表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);

适配器的运算

:表23 栈容器适配器支持的操作

:表24 队列和优先级队列支持的操作

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 仅包含一个键，并有效地支持关于某个键是否存在的查询。

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

解引用

对迭代器进行解引用时，将获得一个引用，指向容器中一个 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 版本的返回类型。

示例

下面是使用 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 对象的查询操作

示例

使用 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 删除元素操作

遍历元素

在使用迭代器遍历 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 类型与相应的单元素版本具有相同的头文件定义：分别是 map 和 set 头文件。

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 返回迭代器的关联容器操作

迭代器

标准库为每一种标准容器定义了一种迭代器类型。迭代器类型提供了比下标操作更通用化的方法。所有的标准库容器都定义了相应的迭代器类型，而只有少数的容器支持下标操作。

一个迭代器的典型用法是编写循环：

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 常用的迭代器运算

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

C++ 定义的容器类型中，只有 vector 和 deque 容器提供下面两种重要的运算集合：迭代器算术运算，以及使用除了 == 和 != 之外的关系操作符来比较两个迭代器(== 和 != 这两种关系运算适用于所有容器)。

:表30 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 类型时，我们可以得到一个迭代器，它自身的值可以改变，但不能用来改变其所指向的元素的值。可以对迭代器进行自增以及使用解引用操作符来读取值，但不能对该元素赋值。

小结：五种迭代器

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

泛型算法

使用泛型算法必须包含 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)”版本。这些算法对输入序列的元素做出处理，但不修改原来的元素，而是创建一个新序列存储元素的处理结果。但不修改原来的元素，而是创建一个新序列存储元素的处理结果。

举例：

• replace_copy ： replace 的 _copy 版本。

泛型算法的结构

深入阅读

1. STL Algorithm 库
2. STL Numeric 库