概念

先了解一下关联容器涉及到的一些概念。
点击查看【processon】
顺序容器：通过元素在容器位置来保存、访问。
关联容器：通过关键字key来保存、访问。
关联容器也是模板。

分类

标准库有8个关联容器。
两大类：

set
- 元素是关键字，适合用于判断是否存在之类的需求，关键字的集合。
map
- 元素是键值对，key起到索引作用。
- 看成数组，下标是key，内置数组下标是整型。

根据key的特性可以再细分：

key是否可重复
- 容器类型名中有multi字眼，则表示容器的key可重复，否则不可重复
- 插入重复key元素，插入失败，什么也不做。
key是否有序
- 无序：通过哈希函数来组织元素。
- 有序：通过key比较运算来组织元素，默认是调用key类型的<运算符。
- 容器类型名中有unordered字眼，则表示容器的key是无序的；否则是有序的。 | 关联容器类型 | key是否可重复 | key是否有序 | | :—-: | :—-: | :—-: | | map | 否 | 是 | | set | 否 | 是 | | multimap | 是 | 是 | | multset | 是 | 是 | | unordered_map | 否 | 否 | | unordered_set | 否 | 否 | | unordered_multimap | 是 | 否 | | unordered_multiset | 是 | 否 |

自定义有序key

自定义的比较必须满足以下：

反对称性
- key1<=key2，则key2不能<=key1
传递性
- key<=key2，key2<=key3，则key1<=key3
等价传递性
- 等价：key1==key2，即key1!<=key2，key2!<=key1
- key1==key2，key2==key3，则key1==key3 ```cpp /**如何自定义有序关联容器*/ bool compare(const int &a, const int &b){ return a < b; }

multiset bookstore(compare);

<a name="xOLLx"></a>
# pair类型
定义utility头文件。<br />保存两个对象，类模板，必须提供两个数据的类型，类型几乎没有限制。<br />成员是public的，分别是first、second。<br />默认构造函数是对数据成员进行值初始化。<br />**pair操作**
```cpp
pair<T1 ,T2> p;                //默认构造，first为T1类型，second为T2类型，进行了值初始化。
pair<Tl,T2> p(v1,v2);         //first=v1，second=v2
pair<T1,T2> p = {v1,v2};     //等价于p(v1,v2)
make_pair(v1,v2);            //返回一个pair，类型自行推断。
                            //代替pair<T1, T2>(v1, v2)，简化操作。
p.first;        //返回first数据
p.second;        //返回second数据
p1 < p2;        //利用first、second的对应运算符来确定
p1 <= p2;        
p1 > p2;        
p1 >= p2;        
p1 == p2;        //p1.first==p2.first && p2.second==p2.second
p1 != p2;        //上面的逻辑反

pair使用例子

pair<string, string> anon;            //默认构造，保存两个string，值为空
pair<string, size_t> word_count;    //默认构造，保存一个string 和一个size_t，值为空和0
pair<string, vector<int>> line;        //默认构造，保存 string 和 vector<int>，值为空和空。
pair<string, string> author{ "James", " Joyce"};
pair<string , int> process(vector<string> &v){
    if (!v.empty())
        return {v.back(), v.back().size()}; //列表初始化
    else
        return pair<string, int>();         //隐式构造返回值
}

迭代器

关联容器迭代器解引用返回元素的引用，即value_type&。
关联容器的key是const，不可修改。
遍历容器和顺序容器的方式一样。
遍历一个有序关联容器时，迭代器按key升序遍历元素，比如字典顺序。

it;        //假设为关联容器迭代器
*it;    //返回元素的引用。
        //set：const key_type&
        //map: pair<const key, value_type>&
/*****************关联容器的key是const类型*********************/
auto map_it = word_count.begin();    //获得指向word_count中一个元素的迭代器
auto elem = *map_it;    //(*map_it)是指向一个pair对象的引用
                        //类型为pair<const string, size_t>
/*****************关联容器的遍历*********************/
cout << map_it->first;        //打印此元素的关键字
cout << map_it->second;        //打印此元素的值
map_it->first = "newkey";    //错误：关联容器的key都是const，也就是不能修改的。
++map_it->second;            //正确：我们可以通过迭代器改变元素
set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end()) {
    *set_it = 42 ;                 //错误： 关键字const
    cout << *set_it << endl;     //正确： 可以读关键字
}
/*****************关联容器的遍历*********************/
auto map_it = wordcount.cbegin();        //得一个指向首元素的迭代器
//因为是有序关联容器，按字典顺序输出。
while(map_it! = word_count.cend()){        //比较当前迭代器和尾后迭代器
    cout << map_it->first << "occurs"     //关键字key
         << map_it->second << "times"     //元素值value
         << endl;
    ++map_it;        //递增迭代器，移动到下一个元素
}

操作

关联容器支持C++_通用容器的全部操作。还有以下特有操作：

类型别名

key_type        //关键字类型
value_type        //元素类型
                //set：key_type == value_type
                //map：pair<const key_type , mapped_type>
mapped_type        //只有map才有：每个关键字关联的类型；


set<string>::value_type v1;    //v1是一个string
set<string>::key_type v2;    //v2是一个string
map<string, int>::value_type v3;    //v3是一个pair<const string,int>
map<string, int>::key_type v4;        //v4是一个string
map<string, int>::mapped_type v5;    //v5是一个int
map<string, size_t> word_count;     //空容器

初始化

//列表初始化
set<string> exclude= {
    "the", "but", "and", "or", "an", "a",
    "The","But", "And", "Or", "An", " A"
    };
//三个元素：authors 将姓映射为名
map<string, string> authors= { 
    {"Joyce", "James"},
    {"Austen", "Jane"},
    {" Dickens", "Charles"}
};
/*****************set和multiset的差别**********************/
//定义一个有20个元素的vector,保存0到9每个整数的两个拷贝
vector<int> ivec;
for(vector<int>::size_type i = O; i != 10 ; ++i) {
    ivec.push_back(i);
    ivec.push_back(i); //每个数重复保存一次
}
//iset包含来自ivec的不重复的元素；miset包含所有20个元素
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl; //打印出 20
cout << iset.size() << endl; //打印出 10
cout << miset.size() << endl; //打印出 20

插入

//插入单个元素
//返回：pair<it, bool>，it指向插入元素，bool表示是否插入成功。
//非multi时，key重复则不会插入。
pair<it, bool> p = c.insert(v);          //v是value_type类型对象
pair<it, bool> p = c.emplace(args);      //args用来构造元素，map的元素是pair，set的元素是key
//插入范围元素，返回void
//非multi时，只插入不重复的元素
void c.insert(b, e);        //是value_type类型的范围。
void c.insert(il);            //初始值列表，值类型是value_type
//类似c.insert(v)、c.emplace(args)
//返回迭代器ti，指向有给定关键字的元素
//迭代器p指出从哪里开始搜索新元素应该存储的位置
it = c.insert(p, v);
it = c.emplace(p, args);

插入元素例子

vector<int> ivec = {2, 4, 6, 8, 2, 4, 6, 8};    //ivec 有 8 个元素
set<int> set2;        //空
set2.insert(ivec.cbegin(), ivec.cend());    //set2有4个元素：key是不可重复的。
set2.insert({1, 3, 5, 7, 1, 3, 5, 7});        //set2现在有8个元素
//map的插入insert的四种方法
word_count.insert({word, 1}) ;
word_count.insert(make_pair(word, 1)) ;
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));
/********************统计单词重复次数例子************************/
map<string, size_t> word_count;    string word;
while( cin >> word){
    //插入单词，成功则表示单词没有重复
    auto ret = word_count.insert({word,l});    //key=word，value=1
    if(!ret.second) ++ret.first->second;    //单词重复一次
}

删除

//n：删除的元素数量。
size_type n = c.erase(key);        //删除指定key的元素
//it：p之后的元素迭代器，可用于循环多次删除。
iterator it = c.erase(p);        //删除指定迭代器的元素
//返回e，即范围之后的元素。
iterator e = c.erase(b, e);    //删除迭代器范围的元素。

访问

通用访问

c.find(k);        //查找第一个key==k的元素，没找到返回end()
                //返回；迭代器
c.count(k);        //返回key==k的元素数量。非multi时，返回1或0。
//不适用于无序容器。
c.lower_bound(k);    //找到第一个key不小于k的元素，左闭右开原则的左闭
                    //返回迭代器
//不适用于无序容器。
c.upper_bound(k);    //找到第一个大于k的元素，左闭右开原则的右开
                    //返回迭代器
c.equal_range(k);    //找到key==k的范围
                    //返回：pair<it1, it2>

例子

set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ;
iset.find(1);     //返回一个迭代器，指向key==1的元素
iset.find(11);     //返回一个迭代器，其值等于iset.end()
iset.count(1);     //返回1
iset.count(ll); //返回0
string search_item("Alain de Botton");        //要查找的作者
auto entries = authors.count(search_item) ;    //元素的数量
auto iter = authors.find(search_item);        //此作者的笫一本书
while(entries) {    //用一个循环查找此作者的所有著作
    cout << iter->second << endl;    //打印每个题目
    ++iter;        //前进到下一本书
    --entries;    //记录已经打印了多少本书
}
string search_item("Alain de Botton");        //要查找的作者
auto begin = authors.lower_bound(search_item);
auto end = authors.upper_bound(search—item) 
for (auto beg = begin, beg != end; ++beg)
    cout << beg->second << endl ;
string search_item("Alain de Botton");        //要查找的作者
auto range = authors.equal_range(search_item)
for(auto begin = range; begin.first != begin.second; ++begin.first)
    cout << begin.first->second << endl;

map特有：下标操作

两种下标操作方式：

c[key]
- key存在，返回mapped_type对象。注意不是元素（pair对象）
- key不存在，会创建一个元素，返回mapped_type对象
c.at[key]函数
- key存在，返回mapped_type对象
- key不存在，抛出一个out_of_range异常 ```cpp //返回k关联的mapped_type对象，注意不是元素，map的元素是pair对象， //返回左值，可以修改mapped_type对象。 c[k]; //k不存在，则创建元素，并对其值初始化 c.at(k); //带参数检查；若k不在c中，抛出一个out_of_range异常

//下标和at操作只适用于非const的map和unordered_map,

**为什么是下标操作，不是下标访问****？**
   - 第一，不是返回元素，而是返回mapped_type对象。
   - 第二，操作可能会创建元素。
总之，map的下标操作有访问的作用，但是不能看成是访问。
<a name="6NMNl"></a>
# 无序关联容器
标准定义了4个无序关联容器（ unordered associative container），通过一个哈希函数 ( hash function ) 和key的==运算符来组织元素。<br />采用[桶式散列](https://www.yuque.com/tvvhealth/cs/ucqi75#KaZbJ)来存储元素，每个桶对应一个哈希值，相同key的哈希值一样，不同key的哈希值可能一样。性能取决于哈希质量和桶的大小。
<a name="TqueJ"></a>
## 操作
<a name="QEmz8"></a>
### 管理桶
```cpp
c.bucket_count();        //当前桶数量
c.max_bucket_count();    //容器能容纳的最大桶数量
c.bucket_size(n);        //第n个桶有多少元素
c.bucket_(k);            //k在哪个桶。
local_iterator;                //访问桶中元素的迭代器
const_local_iterator;        //同上，const版
c.begin(n), c.end(n);        //桶n的首尾迭代器
c.cbegin(n), c.cend(n);        //同上，const版

管理哈希

c.load_factor();            //每个桶的平均元素数量，float
c.max_load_factor();        //试图维护桶平均大小，返回float，可能添加新桶来维持
                            //load_factor <= max_load_factor
c.rehash(n);                //重组，使用了一段时间后，可以考虑重组一下，减少哈希冲突提高性能。
                            //当前桶数量：bucket_count
                            //使bucket_count >= n
                            //bucket_count > size/max_load_factor
c.reserve(n);                //重组，使得c保存n个元素不会发生rehash
                            //使得在创建map的时候hash好，在使用的时候可以快速访问。

关键字类型要求

一句话，无序容器的key默认支持内置类型，key是自定义类型的话，需要自定义哈希函数和==。
因为无序容器时根据key来生成哈希值的，所以哈希函数必须支持key的类型对象。
标准库已经为内置数据类型定义了hash模板，也就是说有支持内置类型的哈希函数，所以我们可以直接使用key为内置类型的无序容器。
标准库还定义了部分标准库类型的hash模板，如string、智能指针。

我们不能直接定义key是自定义类型的无序容器，因为标准库肯定不能提前帮你设计好你的自定义类型的哈希函数。所以我们必须自己设计好哈希函数和==函数。下面是定义一个key是自定义类型无序容器的例子。

size_t hasher(const Fucker &sd){
    return hash<int>()(sd.isbn());
}
bool eqOp(const Fucker &lhs, const Fucker &rhs){
    return lhs.isbn() == rhs.isbn();
}
using Fucker_multiset = unordered_multiset<Fucker, decltype(hasher)*, decltype(eqOp)*>;
//42：桶大小
//hasher：哈希函数指针
//eqOp==：相等性判断函数指针
Fucker_multiset obj(42 , hasher, eqOp);

泛型算法不适用

关联容器一般不用泛型算法，而是用自己的。
写、重排算法是肯定不能使用，因为key是const的。
读算法一般是查找，但是泛型find是顺序查找，关联容器是通过key来获取，不适用，所以有关联容器专门的find算法。

计算机科学

C _关联容器

概念

分类