第11章 关联容器

1.概述

关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是map和set。

标准库提供 8 个关联容器，如表 11.1 所示。这 8 个容器间的不同体现在三个维度上：（1）或者是一个 set, 或者是一个 map；（2）或者要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存。

2. 操作

当定义一个 map 时，必须既指明关键字类型又指明值类型；而定义一个set 时，只需指明关键字类型，因为 set 中没有值 。

// 列表初始化
set<string> exclude = {"the", "and", "an"};
map<string, string> authors = { {"Joyce", "James"}, {"Austen", "Jane"}, {"Dickens", "Charles"} };

map和set类型都支持begin和end操作，可以使用这些函数获取迭代器。

map和set的关键字是const的，不可以修改。

关联容器基于pair的标准库类型，一个 pair 保存两个数据成员。类似容器，pair 是一个用来生成特定类型的模板。

添加元素

对一个 map 进行 insert 操作时，必须记住元素类型是 pair 。

删除元素

关联容器定义了三个版本的 erase, 如表 11.5 所示。

map的下标操作

对一个 map 使用下标操作，其行为与数组或 vector 上的下标操作很不相同：使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到map 中。

访问元素

示例程序

功能：给定一个 string, 将它转换为另一个 string。程序的输入是两个文件。第一个文件保存的是一些规则，用来转换第二个文件中的文本。每条规则由两部分组成：一个可能出现在输入文件中的单词和一个用来替换它的短语。

函数 word_transform 管理整个过程。它接受两个ifstream 参数：第一个参数应绑定到单词转属文件，第二个参数应绑定到我们要转换的文本文件。函数 buildMap 会读取转换规则文件，并创建一个 map, 用于保存每个单词到其转换内容的映射。函数 transform 接受一个 string, 如果存在转换规则，返回转换后的内容。

void word_transform(ifstream &map_file, ifstream &input) {
    auto trans_map = buildMap(map_file); // 保存转换规则
    string text;
    while (getline(input,text)) { // 读取一行输入
        istringstream stream(text); // 读取每个单词
        string word;
    	bool firstword = true; // 控制是否打印空格
    	while (stream >> word) {
        	if (firstword)
                firstword = false;
            else
                cout<<" ";  // 在单词间打印一个空格
            // transform返回它的第一个参数或其转换之后的形式
            cout << transform(word, trans_map);
        }
        cout << endl; // 完成一行的转换
    }
}

函数首先调用 buildMap 来生成单词转换 map, 我们将它保存在 trans_map 中。函数的剩余部分处理输入文件。while 循环用 getline一行一行地读取输入文件。这样做的目的是使得输出中的换行位置能和输入文件中一样。

建立转换映射

map<string, string> buildMap(ifstream &map_file) {
    map<string, string> trans_map; 
    string key;
    string value;
    // 读取第一个单词存入key中，行中剩余内容存入value
    while (map_file >> key && getline(map_file, value))
        if (value.size() > 1) // 检查是否有转换规则
            trans_map[key] = value.substr(1); // 跳过前导空格
    	else
            throw runtime_error("no rule for " + key);
    return trans_map;
}

生成转换文本

const string & transform(const string &s, const map<string, string> &m) {
    auto map_it = m.find(s);
    if (map_it != m.cend())
        return map_it->second;
    else
        return s;
}