c++关联容器总结

小灰灰 2022-06-13 03:07 192阅读 0赞

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。  
关联容器支持高效的关键字查找与访问。两个主要的关联容器类型是map与set。

--------------------

### **map类容器** ###

map容器中的元素是一些关键字-值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。字典则是一个很好的使用map的例子：可以将单词作为关键字，将单词释义作为值。  
map类型通常被成为关联数组。

map关联容器的类型

> map ：关联数组；保存关键字-值对；数据的存放是有序的  
> multimap：关键字可以重复出现的map  
> unordered\_map：用哈希函数组织的map；容器中的数据存放是无序的  
> unordered\_multimap：哈希组织的map；关键字可以重复出现

类型map和multimap定义在头文件map中，unordered\_map定义在头文件unordered\_map中。  
**所有有序关联容器数据是按关键字的字典顺序进行存储存放的。**

#### **一.map容器：** ####

**1.pair类型：**  
在介绍有关map容器的使用之前，我们需要了解名为pair的标准库类型，它定义在头文件utility中。  
一个pair保存两个数据成员。类似容器，pair是一个用来生成特定类型的模板。当创建一个pair时，我们必须提供两个类型名，pair的数据成员将具有对应的类型。可以这么认为，一个pair类型的对象，其实存储的是一个键值对（key-value）。

pair<string,string>anon;    //保存两个string
    pair<string,size_t> word_count;   //保存一个string和一个size_t
    pair<string,vector<int>> line;     //保存string和vector<int>

当我们没有对pair类型的对象进行初始化时，pair的默认构造函数对数据成员进行值初始化。我们也可以为每个成员提供初始化器：

//创建一个名为author的pair，两个成员被初始化为"James"和"Joyce"
    pair<string,string> author{
       "James","Joyce"};
    //等价于：
    pair<string,string>  author("James","Joyce");

pair的数据成员是public的，两个成员分别命名为first和second。我们用普通的成员访问符号来访问它们，比如：

//w为pair类型的对象
    cout<<w.first<<" "<<w.second<<endl;

同其它类型一样，我们同样可以在函数中返回一个pair类型的对象。  
例如：

pair<string,int>
    process(vector<string> &v)
    {
       //处理V
       if(!v.empty())
          return {v.back(),v.back().size()};   //列表初始化，返回
       else
          return pair<string,int>();  //隐式构造一个空pair，返回
    }

介绍完pair类型后，我们就会对map容器有更深刻的理解，其实map就是存储pair类型对象的容器。  
**2.map容器的定义：**  
类似顺序容器，关联容器也是模板。当定义一个map时，必须指明关键字类型又指明值类型。每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。

map<string,size_t> word_count;  //string到size_t的空map
    map<string,string> authors1={
       {
       "Joyce","James"},{
       "Austen","Jane"}};
    map<string,string>  authors2=authors1;

**3.map容器额外的类型别名：**  
map容器定义了如下列出的类型，这些类型表示容器关键字和值的类型。

key_type        map容器的关键字的类型
    mapped_type     每个关键字对应的值的类型
    value_type      为pair<const key_type,mapped_type>

map<string,int>::value_type v1;   //v1是一个pair<const string,int>
    map<string,int>::key_type v2;     //v2是一个string
    map<string,int>::mapped_type v3;   //v3是一个int

**4.map容器的使用:**  
**向map容器中添加元素：**  
当我们向顺序容器比如vector中插入元素时，我们可以使用push\_back()函数将数据插入到容器尾部。但是关联容器不支持push\_back()和push\_front()的操作，所以我们想要往map中插入数据时，只能使用insert和emplace函数。

相关的插入操作:

c.insert(v)          v是value_type类型的对象
    c.emplace(args)      args用来构造一个value_type类型的对象
    c.insert(b,e)        b,e是迭代器，表示一个c::value_type类型值的范围
    c.insert(il)         il代表花括号列表，花括号里是一个pair
    c.insert(p,v)        类似insert(v)，迭代器p指出从哪里开始搜索新元素应该存储的位置
    c.emplace(p,args)    类似emplace(args)，迭代器p指出从哪里开始搜索新元素应该存储的位置

使用insert()函数向map中添加元素时，传入insert函数中的参数类型必须是pair类型。通常，对于想要插入的数据，并没有一个现成的pair对象，我们可以在insert的参数列表中创建一个pair。而使用emplace函数向map中添加元素时，我们只需要将构造pair类型对象需要的数据传入就可以，emplace函数会自动为我们构造好一个pair类型对象添加到map容器当中。

//向map容器添加一个元素
    map<string,size_t> word_count;
    string word("fengxin");
     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));
       // 等价于 word_count.emplace(word,1);

由于map是不包含重复关键字的，因此重复插入一个已存在的关键字元素并不会添加到map容器中。map容器中存储的关键字对应的值还是第一次添加到容器中关键字对应的值。

**遍历map容器：**  
当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value\_type的值的引用。对map容器而言，它的迭代器其实指向的是一个pair类型的对象。  
我们可以使用迭代器遍历map容器。

//word_count是一个map容器
    //获得一个指向首元素的const迭代器
    auto map_it=word_count.cbegin();
    for(map_it;map_it!=word_count.cend();map_it++)
       cout<<map_it->first<<" "<<map_it->second<<endl;

**使用下标操作：**  
map和unordered\_map容器提供了下标运算符，我们可以通过下标进行访问map中的元素，也可以通过下标向map中添加元素。  
map下标运算符接受一个关键字，获取与此关键字相关联的值。**如果关键字不再map中，会为它创建一个元素并插入到map中。**

map<string,size_t> word_count;   //empty map
    word_count["Anna"]=1;    
    //word_count中并没有关键字为Anna的元素，所以会自动创建一个关键字为Anna，值为1的键值对插入到map中
    cout<<word_count["Anna"]<<endl;     //输出1

**访问元素：**

//c为一个map容器
    c.find(k)         返回一个迭代器，指向关键字为k的元素。若k不在容器中，则返回尾后迭代器
    c.count(k)        返回关键字等于k的元素数量。对于map而言，返回值永远是0或1。

当我们要在map容器中查找一个元素时，我们可以使用find函数查找。

auto it = word_count.find("foobar");
    if(it==word_count.end())
       cout<<"foobar is not in the map"<<endl;
    else
       cout<<it->first<<" "<<it->second<<endl;

**删除元素：**  
同添加元素一样，关联容器并不支持顺序容器的pop\_front()和pop\_back()操作。  
我们可以使用erase()函数删除关联容器中的元素。

c.erase(k)   //从c中删除关键字为k的元素。返回一个size_type的值，指出删除元素数量
    c.erase(p)   //从c中删除迭代器p指定的元素。
    c.erase(b,e) //删除迭代器b和e表示的范围中的元素。返回e

二.**multimap容器：**  
和map容器类似，区别在于map容器中的关键字必须是唯一的，对于一个给定的关键字，只能有一个元素的关键字等于它。而multimap对此没有限制，允许多个元素具有相同的关键字。  
由于map与multimap很多操作都一样。在此，我只说一下multimap与map使用不同的地方。  
**1.添加元素：**  
由于multimap中容器的关键字不必唯一，所以我们可以向multimap中插入多个关键字相同的元素。

multimap<string,string> authors;
    authors.insert({
       "Barth","sot-weed factor"});
    //添加第二个元素，关键字也是Barth
    authors.insert({
       "Barth","Lost in the Funhouse"});

**2.下标访问：**  
map是支持下标访问的，使用起来很方便。但是由于multimap中的一个关键字可能对应多个值，所以multimap并不支持下标操作，这里需要注意。

**3.查找元素：**  
在对于允许重复关键字的容器来说，查找元素的过程稍微复杂些，因为一个关键字可能对应多个值，我们需要把这么对应的值都找出来。  
**如果multimap中有多个元素具有相同的关键字，则这些关键字在容器中会相邻存储。**我们可以通过这一特性，将一个关键字对应的多个值全部找出来。

//authors是一个multimap容器
    string search_item("Alain");
    int numbers=authors.count(search_item);
    auto it=authors.find(search_item);
    while(numbers)
    {
       cout<<iter->second<<endl;
       ++it;
       numbers--;
    }

--------------------

### **set类容器** ###

set容器中的每个元素只包含一个关键字，可以这么认为，其实set就是一个集合，用来存储同类型的元素。  
set关联容器的类型

> set : 关键字即值，即只保存关键字的容器  
> multiset : 关键字可重复出现的set  
> unordered\_set: 无序的set  
> unordered\_multiset: 关键字可以重复出现的无序的set

set和multiset定义在头文件set中，unordered\_set定义在头文件unordered\_set中。

#### **一.set容器：** ####

**1.set容器的定义与初始化：**  
同map容器，定义set容器时，我们需要指定关键字的类型，即set集合存储的元素的类型。由于set是有序的关联容器，容器内部会按字典顺序自动为元素进行排序，如果我们需要将数据按顺序存储起来，使用set容器是一个非常不错的选择。数据初始化与map类似。

set<string> a1={
       "fengxin","666"};
    set<string> a2=a1;

**2.添加与删除元素：**  
同map容器类似。

set<string> a;  //empty set
    a.insert("fengxin");  // 插入一个元素
    a.emplace("123");   //插入
    a.erase("123");    //删除关键字为123的元素

**3.遍历元素：**  
同map容器类似。我们使用迭代器进行遍历set容器。需要注意的是，同不能改变一个map的关键字一样，一个set中的关键字也是const的。所以，我们只能用一个set迭代器读取元素的值，但不能修改。

set<int> iset={
       0,1,2,3,4,5,6,7,8,9};
    auto it=iset.begin();
    if(it!=iset.end())
    {
         *it=10;  //错误：set中关键字是只读的
         cout<<*it<<endl;
    }

**4.查找元素：**  
由于set中存储的只有关键字，所以set容器并不支持下标操作。  
set同样可以使用find函数进行对关键字的查找，此时函数返回指向关键字的迭代器。

set<int> iset={
       0,1,2,3,4,5,6,7,8,9};
    auto it=iset.find(6);
    cout<<*it<endl;

#### **二.multiset容器：** ####

set和multiset容器区别同map与multimap容器。在此我们不再介绍multiset的相关操作了。

--------------------

### **无序关联容器** ###

unordered\_map与unordered\_set都是无序的关联容器。在此，我们将它们一起总结。  
有序关联容器中的关键字是有序排列的，所以要求关键字可以进行<运算符比较或满足自定义的比较操作。无序关联容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。  
无序容器可以使用上述所有的与有序容器相同的操作，由于无序容器在存储上组织为桶，每个桶保存零个或多个元素，容器的性能依赖于哈希函数的质量和桶的数量和大小，因此无序容器多了一些哈希函数和桶相关的操作。  
1.桶接口

m.bucket_count()        正在使用的桶的数目
    m.max_bucket_count()    容器能容纳的最多的桶的数量
    m.bucket_size(n)        第n个桶中有多少个元素
    m.bucket(k)             关键字为k的元素在哪个桶

2.桶迭代

local_iterator            可以用来访问桶中元素的迭代器类型
    const_local_iterator      桶迭代器的const版本
    m.begin(n)、m.end(n)      桶n的首元素迭代器和尾后迭代器（n是什么类型？）
    m.cbegin(n)、m.cend(n)    与前两个函数类似，但返回const_local_iterator

3.哈希策略

//每个桶的平均元素数量，返回float值
    m.load_factor() 
    //m试图维护的平均桶大小，返回float值，要求创建的新桶的load_factor<=max_load_factor 
    m.max_load_factor() 
    //重新存储，使得bucket_count>=n，且bucket_count>size/max_load_factor 
    m.rehash(n)  
    //重新存储，使得m可以保存n个元素且不必rehash 
    m.reserve(n)