C++ 11 特性：关联容器map、set的使用

悠悠 2022-06-01 22:46 237阅读 0赞

参考文献《C++ Primer》

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

一、关联容器概述  
  
**1.1 关联容器的概念**  
  
关联容器支持高效的查找与访问，主要的关联容器为map与set这两个。其中map主要提供的是键-值的操作，比如字典；set主要提供的是集合的操作，比如去重。标准库总计提供了8个关联容器。  
  
按关键字有序保存元素

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">map</td> 
   <td align="left">关联数组，保存&lt;关键字，键&gt;对</td> 
  </tr> 
  <tr> 
   <td align="left">set</td> 
   <td align="left">只保存关键字的容器</td> 
  </tr> 
  <tr> 
   <td align="left">multimap</td> 
   <td align="left">关键字可以重复出现的map</td> 
  </tr> 
  <tr> 
   <td align="left">multiset</td> 
   <td align="left">关键字可以重复出现的set</td> 
  </tr> 
 </tbody> 
</table>

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

无序集合

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">unordered_map</td> 
   <td align="left">使用哈希函数组织的map</td> 
  </tr> 
  <tr> 
   <td align="left">unordered_set</td> 
   <td align="left">使用哈希函数组织的set</td> 
  </tr> 
  <tr> 
   <td align="left">unordered_multimap</td> 
   <td align="left">使用哈希函数组织的map,关键字可以重复出现</td> 
  </tr> 
  <tr> 
   <td align="left">unordered_multiset</td> 
   <td align="left">使用哈希函数组织的set,关键字可以重复出现</td> 
  </tr> 
 </tbody> 
</table>

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

8中关联容器中，map与multimap定义在头文件`<map>` 中；set与multiset定义在头文件`<set>` 中；无序容器则分别定义在头文件`<unordered_map>` 与`<unordered_set>`中。

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

**1.2 pair类型**

在介绍关联容器的操作前，需要掌握pair类型的操作，它定义在头文件`<utility>`中。  
pair通常用来生成一个特定类型的模板，保存两个数据成员。例如

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

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

**1.3 pair类型的操作**

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">pair &lt; T1 , T2 &gt; p</td> 
   <td align="left">p中第一个成员的类型为T1，第二个成员的类型为T2</td> 
  </tr> 
  <tr> 
   <td align="left">pair &lt; T1 , T2 &gt; p(v1,v2)</td> 
   <td align="left">p中第一个成员初始化为v1，第二个成员初始化为v2</td> 
  </tr> 
  <tr> 
   <td align="left">pair &lt; T1 , T2 &gt; p = {v1,v2}</td> 
   <td align="left">等价p(v1,v2)</td> 
  </tr> 
  <tr> 
   <td align="left">make_pair(v1,v2)</td> 
   <td align="left">返回一个用v1,v2初始化的pair类型</td> 
  </tr> 
  <tr> 
   <td align="left">p.first</td> 
   <td align="left">返回p的第一个数据成员</td> 
  </tr> 
  <tr> 
   <td align="left">p.second</td> 
   <td align="left">返回p的第二个数据成员</td> 
  </tr> 
  <tr> 
   <td align="left">p1 == p2</td> 
   <td align="left">当第一个与第二个成员分别相等时，两个pair相等</td> 
  </tr> 
 </tbody> 
</table>

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

二、关联容器操作  
  
**2.1 关联容器的定义**  
  
关联容器set与map的定义如下

map<string, size_t> word_count; //空容器
    //每个<键，值>对在一个花括号中
    map<string, string> name = { {
       "Joce","James"},{
       "Aust","Jane"}};
    set<string> exclude = { "the","a","but","or" };

**2.2 关联容器的基本操作**  
  
**2.2.1 关联容器的相关类型**  
  
除了容器的基本类型外，关联容器还具备如下类型。

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">key_type</td> 
   <td align="left">此容器类型的关键字类型</td> 
  </tr> 
  <tr> 
   <td align="left">mapped_type</td> 
   <td align="left">仅适用于map，关键字对应的值的类型</td> 
  </tr> 
  <tr> 
   <td align="left">value_type</td> 
   <td align="left">对于set与key_type相同<br><br>对于map为<code>pair&lt;const key_type,mapped_type&gt;</code> 类型</td> 
  </tr> 
 </tbody> 
</table>

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

**2.2.1 关联容器与迭代器**  
  
map

map<string, string> word_count{ {
       "1.1","1.2"},{
       "2.1","2.2"} };
    //迭代器指向map的首元素，这里的map_iter指针指向的是pair<const string,string>类型
    auto map_iter = word_count.begin(); 
    //首元素的第一个成员，运行结果为1.1    
    cout << map_iter->first << endl;
    //第二个元素的第二个成员，运行结果为2.2      
    cout << (++map_iter)->second << endl;
    //错误，因为是pair<const string,string>类型，所以无法通过指针修改关键字
    map_iter->first = "修改1.1";      
    //正确，但是可以通过指针修改值。
    map_iter->second = "修改2.2";     
    //运行结果为：
    //2.1 
    //修改2.2 
    cout << map_iter->first << endl;
    cout << map_iter->second << endl;

map的value\_type是`pair<const T1,T2>` 类型的，我们可以修改pair的值，但是不能修改其关键字。

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

set

//定义一个集合
    set<int> s = { 1,2,3,4,5 }; 
    //迭代器set_iter指向集合首元素            
    set<int>::iterator set_iter = s.begin();
    while (set_iter != s.end())
    {
        //正确，set_iter只读
        cout << *set_iter << ends;          
        //错误，不能通过指针修改关键字
        (*set_iter) += 1;
    
        set_iter++;
    }

虽然set中同时定义了iterator与const\_iterator，但它们都是只读的。

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

**2.2.2 关联容器的插入操作**  
  
map  
首先我们要明确，插入map中的应该是一个键值对，也就是一个初始化了的pair类型的变量。下面给出了4中方法可以初始化pair类型，并插入到map中去。

map<string, string> word_count{
       { "1.1","1.2" },{ "2.1","2.2" }};
    //使用花括号初始化pair，然后插入到word_count中。
    word_count.insert({ "3.1","3.2" });
    //使用make_pair返回一个初始化了的pair。
    word_count.insert(make_pair("4.1", "4.2"));
    //直接定义一个初始化了的pair。
    word_count.insert(pair<string, string>("5.1", "5.2"));
    //直接定义一个map::value_type的pair类型。
    word_count.insert(map<string, string>::value_type("6.1", "6.2"));
    
    for (auto i : word_count)
        cout << i.first << ends << i.second << endl;
    //运行结果：
    //  1.1 1.2
    //  2.1 2.2
    //  3.1 3.2
    //  4.1 4.2
    //  5.1 5.2
    //  6.1 6.2

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

set

//定义一个vector容器，包含重复数据。
    vector<int> ivec = { 1,2,3,4,4,5,5 };
    //遍历结果1 2 3 4 4 5 5
    for (auto i : ivec)
        cout << i << ends;
    cout << endl;
    //定义一个set关联容器
    set<int> set_ivec;
    //使用insert插入操作，使用初始化列表
    //set的特性去重。
    set_ivec.insert({
       6,6,7,8});
    //遍历结果6 7 8
    for (auto i : set_ivec)
        cout << i << ends;
    cout << endl;
    //使用insert插入操作的另一个版本，使用一对迭代器插入
    //set的特性排序。
    set_ivec.insert(ivec.begin(), ivec.end());
    //遍历结果1 2 3 4 5 6 7 8
    for (auto i : set_ivec)
        cout << i << ends;
    cout << endl;

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

insert的返回的值依赖于容器的类型和参数。对于map和set，添加单一元素的时候，返回的结果是一个pair，其第一个数据成员是一个迭代器，根据关键字，指向一个键值对；第二个数据成员是一个bool值，如果添加成功则为true，如果该关键字已经在容器中了则返回false。

经典单词计数程序

//统计每个单词在输入中出现的次数。
    map<string, size_t>  word_count;
    string word;
    while (cin >> word)
    {
        //若word已经在word_count中则insert什么也不做
        auto ret = word_count.insert({ word,1 });
        if (!ret.second)
            ++ret.first->second;
            //上句等价于++((ret.first)->second)
    }
    //ret是一个pair
    //ret.first是pair的第一个数据成员，是一个map的迭代器，根据关     键字指向键值对。
    //ret.first->second是指向的那个键值对的第二个数据成员，在程序中是size_t类型，表示计数器。

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

multiset与multimap

对于允许重复关键字的容器，插入操作如下。

multimap<string,string> authors;
    authors.insert({
       "John","Sot-weed"});
    authors.insert({
       "John","Lost"});

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

**2.2.3 关联容器的删除操作**  
  
对于删除操作，关联容器定义了三个版本的erase。

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">c.erase(k)</td> 
   <td align="left">从c中删除关键字为k的元素，返回一个size_type值，指明删除元素的数量</td> 
  </tr> 
  <tr> 
   <td align="left">c.erase(p)</td> 
   <td align="left">从c中删除迭代器p指定的元素，返回一个指向p之后元素的迭代器，若p指向了c中的尾元素则返回c.end()</td> 
  </tr> 
  <tr> 
   <td align="left">c.erase(b,e)</td> 
   <td align="left">删除迭代器从b到e范围内的元素，返回e</td> 
  </tr> 
 </tbody> 
</table>

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

**2.2.4 map的下标操作**  
  
仅map与unordered\_map提供了下标运算以及一个队形的at函数，其他的关联容器没有提供。

map<string, size_t>  word_count;
    //使用下标运算符
    //如果该关键字已经在容器中，则获取关键字对应的值
    //如果该关键字不在容器中，则将一个新的键值对插入到容器，并将值初始化
    word_count["Anna"] = 1;
    //这里提取出新插入的元素，并将值赋值为1

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">c[k]</td> 
   <td align="left">返回关键字为k的值，如果k不在c中，则添加一个关键字为k的键值对，并对其值进行初始化</td> 
  </tr> 
  <tr> 
   <td align="left">c.at(k)</td> 
   <td align="left">访问关键字为k的元素，如果k不在c中，则抛出异常</td> 
  </tr> 
 </tbody> 
</table>

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

**2.2.5 关联容器的访问操作**

<table> 
 <thead> 
  <tr> 
   <th align="left">名称</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">c.find(k)</td> 
   <td align="left">返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回c.end()</td> 
  </tr> 
  <tr> 
   <td align="left">c.count(k)</td> 
   <td align="left">返回关键字为k的元素的数量，对于无重复关键字的容器，返回值永远为0或1</td> 
  </tr> 
  <tr> 
   <td align="left">c.lower_bound(k)</td> 
   <td align="left">返回一个迭代器，指向第一个关键字不小于k的元素</td> 
  </tr> 
  <tr> 
   <td align="left">c.upper_bound(k)</td> 
   <td align="left">返回一个迭代器，指向第一个关键字大于k的元素</td> 
  </tr> 
  <tr> 
   <td align="left">c.equal_range(k)</td> 
   <td align="left">返回一个迭代器pair，表示关键字等于k的元素的范围，如果k不在c中，pair的两个成员都等于c.end()</td> 
  </tr> 
 </tbody> 
</table>

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

在multimap或multiset中查找元素

如果一个multimap或multiset中有多个元素具有相同关键字，这些元素会在容器中相邻存储。解决这种情况下的查找问题可以有三种方法。

*  1. 常用的方法是使用count方法，记录下元素的数量，使用find找到首个值，然后使用迭代器递加遍历。  
    
 *  2. 可以使用lower\_bound与upper\_bound 两种方法，完成相同的工作。  
    
 *  3. 使用equal\_range()函数，此函数接受一个关键字，返回一个迭代器pair，若关键字存在，则pair的第一个数据成员指向第一个与关键字匹配的元素，第二个数据成员指向最后一个和关键字匹配的元素之后的位置。

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

对于无序容器如果有机会在做补充，如有不对的地方欢迎大家指正交流。