11.关联容器 | associative container

关联容器和顺序容器根本的不同：

关联容器中的元素是按关键字保存和访问的；顺序容器中的元素是按在容器中的位置顺序保存和访问的。

关联容器支持高效的关键字查找和访问。两个主要的关联容器（associative container）类型是map和set。map中的元素是一些关键字-值（ket-value）对：关键字起到索引作用，值表示与索引相关联的数据。

set中每个元素只包含一个关键字；set支持高校的关键字查询操作：检查一个给定关键字是否在set中。例如某些文本处理过程中可以用set保存要忽略的单词。

字典是一个很好的使用map的例子：可以将单词作为关键字，将单词释义作为值。

标准库提供8个关联容器。这8个容器间的不同体现在3个维度上：每个容器：

1. 或者是一个set，或者是一个map；
2. 或者要求不重复的关键字，或者允许重复关键字
3. 按顺序保存元素，或无序保存

允许重复关键字的容器的名字中都有multi；不保持关键字按顺序存储的容器名字都以unordered开头。

例如：一个unordered_multi_set是一个允许重复关键字，元素无序保存的集合。一个set是一个不允许重复关键字，有序存储的集合。

无序容器使用哈希函数来组织元素。

类型map和multimap定义在头文件<map>中，set和multiset定义在头文件<set>中；无序容器则定义在unordered_map和unordered_set中。

八种关联容器

使用关联容器

map类型通常称为：关联数组（associative array）。关联数组类似正常数组，但其下标不必是正数，可以是一个关键字；set就是关键字的简单集合。

使用map

从文件读取单词并计数程序

int main(){
    std::map<std::string, size_t> word_count;
    std::string ifile = "words.txt";
    std::ifstream ifs(ifile, std::ios_base::in);
    std::istream_iterator<std::string> it(ifs), eof;
    std::vector<std::string> v(it, eof);
    for(auto i: v) ++word_count[i];
    for (const auto& w: word_count){
        std::cout<<w.first<<'\t'<<w.second<<std::endl;
    }
}

map也是一个模板，因此需要指定key和value的类型，如本例中的string和size_t。其中string可以作为下标。
当从map中提取一个元素时会得到一个pair类型的对象。pair也是一个模板类型，保存两个数据成员first和second。

使用set

使用set设置一个忽略关键词的列表，并且在上面程序中进行判断，可以使用set自带的find成员，若返回尾后迭代器则代表未找到，未出现在排除列表中：

int main(){
    //设置除外列表
    std::set<std::string> exclude = {"and", "or", "the", "a", "with"};
    std::map<std::string, size_t> word_count;
    std::string ifile = "words.txt";
    std::ifstream ifs(ifile, std::ios_base::in);
    std::istream_iterator<std::string> it(ifs), eof;
    std::vector<std::string> v(it, eof);
    for(auto i: v) 
        if (exclude.find(i) == exclude.end()) //判断是否不在除外列表中
            ++word_count[i];
    for (const auto& w: word_count){
        std::cout<<w.first<<'\t'<<w.second<<std::endl;
    }
}

关联容器概述

关联容器都支持普通的容器操作，但不支持顺序容器的位置相关的操作，如push_back等。
同时，也不支持构造函数或插入操作等接受一个元素值和一个数量值的操作。
关联容器支持一些顺序容器不支持的操作、类型别名。
此外，无序容器还提供一些调整哈希性能的操作。
关联容器的迭代器都是双向的。

定义关联容器

定义一个map需要指明k和v的类型，set只需要指名k的类型。可以默认初始化为空容器，map也可以使用初始化列表进行值初始化。

int main(){
    std::map<std::string, int> m1;
    std::set<std::string> s1 = {"a", "b", "c"};
    std::map<std::string, int> m2 = {{"a", 0}, {"b", 1}, {"c", 2}};
}

初始化multimap或multiset

可以使用一个顺序容器的一对迭代器对一个set进行初始化：

int main(){
    std::vector<int> v;
    auto it = std::back_inserter(v);
    for(int i = 0; i<10; i++) {it = i;  it = i;}

    for(auto j: v) std::cout<<j;  //00112233445566778899
    std::cout<<std::endl;

    std::set<int> s(v.begin(), v.end());
    std::multiset<int> ms(v.begin(), v.end());

    for(auto k: s) std::cout<<k;  //0123456789
    std::cout<<std::endl;          

    for(auto k: ms) std::cout<<k; //00112233445566778899
    std::cout<<std::endl;         
}

关键字类型的要求

对于有序容器map、multimap、set、multiset，关键字类型必须定义元素比较的方法。默认情况下是使用了关键字类型的operator<进行比较。
set类型中，关键字类型就是元素类型；映射类型中关键字类型是元素第一部分(first)的类型。

有序容器的关键字类型

可以向一个算法提供自己定义的比较操作，或者比较操作符。

所提供的操作必须在关键词类型上定义一个严格弱序（strict weak ordering），可将其视为“小于等于”。

定义的比较函数需要具备如下基本性质：

• 两关键字不能同时“小于等于”对方
• 小于等于必须具有传递性
• 若存在两个关键字任何一个都不小于等于第三个，则这来给你个等价，视为相等。

使用关键字类型的比较函数

用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟元素类型给出。

尖括号中出现的每个类型仅仅是一个类型。当创建了一个容器对象时，才会以构造函数参数的形式提供真正的比较操作。

为了使用自定义的操作，在定义multiset时必须提供两个类型：关键字类型以及比较操作类型（一种函数指针类型）。

pair类型

标准库类型pair定义在头文件utility中。

一个pair保存两个数据成员。类似容器，pair是一个用于生成特定类型的模板。创建一个pair时，必须提供两个类型名，pair的数据成员将具有对应的类型，两个类型可以不一样。

using std::pair, std::string, std::vector;
pair<string, size_t> p1;
pair<string, string> p2;
pair<string, vector<string>> p3;

pair的默认构造函数会对数据成员进行值初始化。也可以为每个成员提供初始化器。

pair<string, string> p4 = {"s1", "s2"};

pair的数据成员是public的。分别名为first和second，可以使用普通的成员访问符号进行访问。

创建pair对象的函数

将pair作为函数返回值，可以直接使用初始化列表进行列表初始化：

std::pair<std::string, int> foo(std::vector<std::string> v, const int& cond){
    switch (cond) {
        defalult:
            //默认初始化方式
            return std::pair<std::string, int>();
        case 1:    
            //make_pair方式
            return std::make_pair(v.front(), v.front().size()); 
        case 2:
            //初始化列表方式
            return {v.back(), v.back().size()};  
        case 3:
            //较早版本方式
            return std::pair<std::string, int>(v.back(), v.back().size());
    }
}

关联容器操作

关联容器还定义了以下类型：

关联容器迭代器

解引用一个关联容器迭代器，会得到一个类型为容器value_type的值的引用。对map而言为一个pair，first保存const的关键字（无法修改），second保存值；对set就是key_type本身。

int main(){
    std::map<std::string, size_t> mp = {{"A", 1},{"b", 2},{"C", 3},{"D", 4}};
    auto it = mp.begin();
    std::cout<<it->first<<std::endl;  //A
    std::cout<<it->second<<std::endl; //1

    ++(it->second);  //second成员值+1
    std::cout<<it->first<<std::endl;  //A
    std::cout<<it->second<<std::endl; //2

    ++it->second;  //等价于++(it->second)
    std::cout<<it->first<<std::endl;  //A
    std::cout<<it->second<<std::endl; //3

    (++it)->second; //未赋值，仅后移迭代器
    std::cout<<it->first<<std::endl;  //B
    std::cout<<it->second<<std::endl; //2

    //it->first = "X"; //错误：该值为const
}

set的迭代器是const的

只包含keys的迭代器，和map迭代器指向pair的first成员一样，是const的。

遍历关联容器

map和set都支持begin和end操作，并使用迭代器遍历内容。

关联容器和算法

通常不对关联容器使用泛型算法。原因是const特性使得一些会修改和重排容器的算法无法使用。

对于只读类型的算法如find等，可以用在关联容器上，但是由于储存和寻址方式不同，速度较慢。建议使用关联容器自身的find成员进行类似操作。

通常使用关联容器的成员比使用类似的泛型算法快得多

此外，可以使用泛型copy将关联容器当作一个源序列；或者使用inserter绑定一个关联容器，使用inserter将关联容器作为插入的目的位置。

添加元素

可以使用关联容器自身的insert成员进行元素的添加。
map和set包含不重复的关键字，因此插入一个已存在的元素没有任何影响，也没有任何作用。

int main(){
    std::map<std::string, size_t> mp = {{"A", 1},{"B", 2},{"C", 3},{"D", 4}};
    auto it = mp.begin();
    mp.insert({"A", 5});
    std::cout<<it->first<<std::endl;   //A
    std::cout<<it->second<<std::endl;  //1
}

向map添加元素

必须记住，向map添加的元素类型是pair。添加的四种方法(以及decltype)：

mp.insert({"A", 1});
mp.insert(std::make_pair("A", 1));
mp.insert(std::pair<std::string, size_t>("A", 1));
mp.insert(std::map<std::string, size_t>::value_type("A", 1));

insert的返回值

对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair：

• first成员是一个迭代器，指向具有指定关键字的元素；
• second成员是一个bool值，指出插入成功还是已在容器。

展开递增语句

若ret是insert的返回值，则：

++ret.first->second

按优先级写为：

++((ret.first)->second);

ret的first成员是一个迭代器，其second值即指向插入后位置的value。该语句为将其递增的操作。

向multiset或multimap添加元素

由于插入总是成功，不必返回一个bool值，因此返回的不是pair而直接是指向新元素的迭代器。

删除元素

关联容器定义了三个版本的erase。

• 可以传递一个或一对迭代器来删除指定元素或范围。和顺序容器操作类似，指定的元素被删除，返回void。
• 第三个版本接受一个key_type参数，删除所有匹配给定关键字的元素，返回实际删除元素的数量。可以使用该版本在打印结果之前删除特定key的pair。
• • 非multi容器，返回值总是0或1；为0表示要删除的元素不在容器中。
• • 对于multi容器，返回值可能大于1：可能删除多个元素。

map的下标操作

非multi的map类型存在下标运算符和对应的at函数；set由于只有关键字而没有相关值而不能进行下标操作。multi类型由于一对多，同样无法使用下标操作。

下标操作返回值

解引用迭代器返回的类型和下标运算符返回的类型通常一样。

对于map则不同：下标操作会获得一个mapped_type对象；但解引用时，会得到一个value_type对象。（value_type包含mapped_type和key_type）

std::cout<<mp.begin()->second; //value_type
std::cout<<mp["A"];  //mapped_type

访问元素

是否在：find，返回迭代器
有几个：count，返回数目

lower_bound和upper_bound不适用于无序容器

在map中用find代替下标操作！

map中使用下标若关键字不存在，会插入一个被值初始化的未知值，后续再插入可能出问题，因此首先使用find判断是更好的方法。

在multimap或multiset查找元素

如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中相邻存储。

要找到所有key等于特定值的元素，首先需要进行count操作返回一个数目，该数目就是find返回迭代器需要的前进次数。

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto cnt = mp.count("A");
    //利用了同关键字元素连续存储的特性
    auto it = mp.find("A");
    std::vector<size_t> v;
    while (cnt){
        v.push_back(it++->second);
        cnt--;
    }
    for(auto i: v) std::cout<<i<<" ";
}

find只有接受一个参数的版本，因此不能指定开始位置，无法使用多次find进行循环，另一种方式是面向迭代器的方法：lower_bound, upper_bound, equal_range。

使用equal_range返回的两个迭代器创建一个新的map：

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto ir = mp.equal_range("A");
    decltype(mp) mp2(ir.first, ir.second); 
    //mp2: {{"A", 1},{"A", 2},{"A", 3}}
    for(auto i: mp2) std::cout<<i.first<<'\t'<<i.second<<'\n';
}

使用lower_bound和upper_bound:

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto beg = mp.lower_bound("A");
    auto end = mp.upper_bound("A");
    for (; beg != end; beg++) 
        std::cout<<beg->first<<'\t'<<beg->second<<'\n';
}

实质：

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto beg = mp.lower_bound("A");
    auto end = mp.upper_bound("A");
    auto rng = mp.equal_range("A");
    std::cout<<(rng.first==beg);  //1
    std::cout<<(rng.second==end); //1
}

无序容器

4个无序关联容器（unordered associative container）不是使用比较运算符组织元素，而是使用哈希函数（hash function）和关键字类型的==运算符。

使用无序容器

除了哈希管理操作，无序容器还提供了与有序容器相同的操作(find、insert等)。即曾用于map和set的操作也能用于unordered_map和unordered_set。无序容器也允许重复关键字的版本。

因此通常可以用一个无序容器替换对应的有序容器，反之亦然。但是由于元素未按顺序存储，使用无序容器程序的输出通常与有序容器版本不同。

管理桶

无序容器在存储组织上为一组桶，每个桶保存零个或者多个元素。无序容器使用一个哈希函数将元素映射到桶。

为了访问一个元素，容器首先计算元素的哈希值，指出要搜索的桶。容器将具有一个特定哈希值的所有元素保存在相同的桶中。如果容器允许重复关键字，所有具有相同关键字的元素也会在同一个桶中。

因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

对于相同的参数，哈希函数必须总是产生相同的结果。理想情况下哈希函数还能将每个特定的值映射到唯一的桶。但是，将不同关键字的元素映射到相同的桶也是允许的。当一个桶保存多个元素时，需要顺序搜索这些元素来检查我们想要的那个。计算一个元素的哈希值在桶中搜索通常很快。但是如果一个桶中保存了很多元素，那查找一个特定元素需要大量比较操作。

无序容器提供的一组管理桶的函数：

无序容器对关键字类型的要求

默认情况下，无序容器使用关键字类型的==运算符比较元素。还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。

标准库为内置类型提供了hash模板，还为string和智能指针等标准库类型定义了hash。因此，可以直接定义关键字是内置类型（含指针类型）、string还是智能指针类型的无序容器。

但是不能直接定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供自己的hash模板版本。