标准容器和泛型算法

1

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

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 库