关联容器

关联容器主要有两种，一种是map，也就是键值对，一种是set，也就是单纯键的集合。
基于map和set是否有重复数据，扩展有multiset和multimap。
基于是否需要排序，扩展有unordered_map和unordered_set
无序且可以有重复数据，扩展有unordered_multimap和unordered_multiset
因此c++提供了上面8种的关联容器，外加一个pair的数据结构，这就是本章节的所有内容

区别

map和set是最基本的容器，他们要求数据有序且不能存在重复的键
multi(set/map) 要求能够存在重复的键，但是依旧要求有序
unordered_(set/map) 不要求有序，但是不能存在重复的键
unordered_multi(set/map) 不要求有序，且可以存在重复的键

pair

pair是一个很简单的数据结构，他定义了一个集合，集合中就只有两个元素。这就天然的能跟键值对结合起来。

pair定义在utility头文件中

pair支持如下的操作：

pair<T1, T2> p
pair<T1, T2> p(v1, v2)
make_pair(v1, v2)
p.first
p.second
p1 == p2
p1 != p2

实际上pair最主要的作用就是以键值对的形式来初始化map

关联容器的操作

关联容器一般不用泛型算法。

key_type和value_type

key_type       // key的类型
mapped_type    // 仅用于map，value的类型
value_type     // 对于set，与key_type相同
               // 对于map，为pair<key_type, mapped_type>

迭代器

关联容器定义了迭代器的操作，可以通过begin和end来利用迭代器对关联容器进行访问

添加元素

insert/emplace
下标

1
2
3

// v是value_type， args是参数列表，
c.insert(v)
c.emplace(args)

这两者的差别如下所示：

1
2
3

map<string, int> c;
c.insert({"name", 1});
c.empalce("name1" , 1);

1	c.insert(b, e) // 插入迭代器范围内的数据

对于map/set，如果已经存在元素了，那么insert相同的key会失败，对于multi，则可以成功插入。

删除元素

删除元素主要使用erase函数，如下

1
2
3

c.erase(key)   // 删除key的所有元素，返回值为删除的元素的个数，类型为size_type
c.erase(p)     // 删除迭代器指向的元素，返回值为指向下一个元素的迭代器
c.erase(b, e)  // 删除迭代器范围内的所有元素，返回e

下标操作

对于map/set以及multi(set/map)可以使用下标的操作。

下标操作简单清晰，但是有个最大的坑，那就是如果map/set中不存在key，那么就是插入一个默认的值。这一点在有些时候可能会让代码及其精炼，但是很多时候也会是坑，因此不建议轻易使用。

访问元素

访问元素可以有下面的三种方式

find 返回指向key的迭代器
count 返回key的个数
下标

对于multi容器的元素访问

对于无重复键的容器，find和count的实际效果是差不多的，但是如果是multi的容器，find返回的是一个迭代器，指向指定键的初始位置，而count返回的是个数。

因此如果要对multi(set/map)中的键的值进行遍历访问，呢么可以有如下的方式

lower_bound(key) 和 upper_bound(key)
equal_range(key) // 返回一个迭代器的pair，分别为key的初始位置以及终点位置的下一个位置

multimap<string, int>authors;

.......

for (auto beg = authors.lower_bound(key), end = authors.upper_bound(); beg != end; ++beg) {
    cout << beg->second << endl;
}

for (auto iter = authors.equal_range(key); iter.first != iter.second; ++iter.first) {
    cout << iter.second << endl;
}

使用下标进行元素访问

单词转化的示例

出自c++ primer 11.3.6的例子
输入为两个文件，一个文件定义了缩写词与原词的对应关系，一个文件定义了有缩写词的文本，要求还原原词的文本

这个需求比较简单，主要是构建一个map，用来存放缩写词与原词的对应关系，然后遍历缩写词文本，如果是缩写词，那么就从map中读取原词替换即可。

#include "iostream"
#include "fstream"
#include "sstream"
#include "map"

using namespace std;

map<string, string> buildMap(ifstream& mapFile) 
{
    map<string, string> transMap;
    string key, value;
    while (mapFile >> key && getline(mapFile, value)) {
        if (value.size() > 1) {
            transMap[key] = value.substr(1);
        } else {
            throw runtime_error("no rules for ", key);
        }
    }
    return transMap;
}

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

void wordTransform(ifstream& mapFile, ifstream& input) 
{
    auto transMap = buildMap(mapFile);
    string text;
    while (getline(input, text))
    {
        istringstream stream(text);
        string word;
        bool firstWord = true;
        while (stream >> word) {
            if (firstWord) {
                firstWord = false;
            } else {
                cout << " " << transform(word, transMap);
            }
            cout << endl;
        }
    }
}