春暖花开

C++中的关联容器

关联容器(Associative containers)支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map, set。

本文主要是对 C++ 中基本的关联容器 map, set 中的类型和支持的操作进行总结。

关联容器支持很多顺序容器也提供的相同操作,此外,还提供管理或使用键的特殊操作。

关联容器类型

pair 类型

在头文件 utility 中定义。


pair 类型提供的操作, T1, T2, 为类型,如 pair<string, vector<int> > line;

pair 类型的使用相当繁琐,因此,如果需要定义多个相同的 pair 类型对象,可考虑利用 typedef 简化其声明。

与其他标准库类型不同,对于 pair 类,可以直接访问其数据成员:其成员都是仅有的,分别命名为 first 和 second。只需使用普通的点操作符——成员访问标志即可访问其成员。

关联容器

关联容器共享大部分——但并非全部——的顺序容器操作。关联容器不提供front、 push_front、 pop_front、back、push_back 以及 pop_back 操作。

map 容器

map 类型通常可理解为关联数组。同样,要使用 map 类型,也需要包含相应的头文件。

map 的构造函数:

对于键类型,唯一的约束就是必须支持 < 操作符,至于是否支持其他的关系或相等运算,则不作要求。

map 类定义的类型

对 map 类型迭代器解引用,会得到一个 pair 类型。

给 map 添加元素

  • 通过下标:下标为键,如果没找到,则添加键值对。使用下标访问 map 与使用下标访问数组或 vector 的行为截然不同:用下标访问不存在的元素将导致在 map 容器中添加一个新元素,它的键即为该下标值。

在 map 中,迭代器返回 value_type 类型的值——包含 const key_type 和mapped_type 类型成员的 pair 对象;下标操作符则返回一个 mapped_type 类型的值。

对于 map 容器,如果下标所表示的键在容器中不存在,则添加新元素,而值进行默认初始化。

例如,利用 map 来统计输入单词数的简单方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
map<string, int> words;
string word;
while (cin >> word){
++words[word];
}
for (map<string, int>::iterator iter = words.begin(); iter != words.end(); ++iter){
cout << iter->first <<"\t" << iter->second <<endl;
}
return 0;
}

map 的 insert 操作

不修改map对象的查询操作

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

map 的删除操作

map对象的遍历

同样提供 begin, end 运算,以生成用于遍历整个容器的迭代器。

set 容器

set 是键的集合,支持大部分前面的操作,但不支持下标操作。set 支持的操作基本与 map 相同。set 中的键和 map 中的一样,只能做读操作,不能做写操作。

multimap 和 multiset 类型

multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同,只有一个例外:multimap 不支持下标运算。

返回迭代器的关联容器操作

0%