【C++ Primer】【学习笔记】【第十章】关联容器之：multimap和multiset类型

一时失言乱红尘 2022-08-06 21:28 155阅读 0赞

**一、基本概念**

map和set容器，一个键只能对应一个实例；而multimap和multiset容器则允许一个键对应多个实例。

multimap类型使用的头文件与map类型一样，均为map；同样地，multiset类型使用的头文件与set类型一样，均为set。

**二、在multimap和multiset容器中添加和删除元素**

添加元素：与map和set的insert操作相同，唯一区别是可以增加具有相同键值的元素；

删除元素：与map和set的erase操作相同，区别是：带有一个键参数的erase版本将删除拥有该键的所有元素，并返回删除元素的个数；而带有一个或一对迭代器参数的版本只删除指定的元素，并返回void类型。

**三、在multimap和multiset容器中查找元素**

注1：在multimap和multiset容器中，所有元素键值是按照字母表顺序存放的；

注2：在multimap和multiset容器中，对于同一个键对应的多个实例，这些实例在容器中是相邻存放的。

1、使用find和count操作进行同一个键对应的多个实例的遍历。

注：find函数返回的迭代器，指向第一个含有查找的键的实例。

string search\_item("Alain de Botton");

typedef multimap<string, string>::size\_type sz\_type;

sz\_type entries = authors.count(search\_item);

multimap<string, string>::iterator iter = authors.find(search\_item);

for (sz\_type cnt = 0; cnt != entries; ++cnt, ++iter)

cout << iter->second << endl;

2、与众不同的面向迭代器的解决方法。

注：如果k键没有关联的元素，则lower\_bound和upper\_bound返回相同的迭代器：都指向同一个元素或者都指向multimap/multiset的超出末端位置。

<table style="font-size:undefined; border-collapse:collapse; margin-top:10px; margin-bottom:10px; background-color:inherit; width:628px"> 
 <tbody style="background-color:inherit"> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:200px"> 返回迭代器的关联容器操作</td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:386px"> 
    <div style="min-width:2px; background-color:inherit">
      说明 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:28px; background-color:inherit; width:200px"> 
    <div style="min-width:2px; background-color:inherit">
      m.lower_bound(k) 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:28px; background-color:inherit; width:386px"> 
    <div style="min-width:2px; background-color:inherit">
      返回一个迭代器，指向键大于或等于k的第一个元素； 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:200px"> 
    <div style="min-width:2px; background-color:inherit">
      m.upper_bound(k) 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:386px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="font-family:微软雅黑; font-size:14px">返回一个迭代器，指向键大于k的第一个元素；亦即：迭代器指向该键应该插入的位置；</span> 
     <br style="background-color:inherit"> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:200px"> 
    <div style="min-width:2px; background-color:inherit">
      m.equal_range(k) 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 16px 5px 12px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:386px"> 
    <div style="min-width:2px; background-color:inherit">
      返回一个迭代器的pair对象；它的first成员等价于m.lower_bound(k)，而second成员等价于m.upper_bound(k)； 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

string search\_item("Alain de Botton");

typedef multimap<string, string>::iterator authors\_it;

authors\_it beg = authors.lower\_bound(search\_item);

authors\_it end = authors.upper\_bound(search\_item);

while (beg != end)

cout << iter->second << endl;

\++beg;

3、方法2的升级版：equal\_range函数

string search\_item("Alain de Botton");

typedef multimap<string, string>::iterator authors\_it;

pair<authors\_it, authors\_it> pos = authors.equal\_range(search\_item);

while (pos.first != pos.second)

cout << pos.first->second << endl;

\++pos.first;

**习题10.26：在multimap容器中查找并删除元素（find函数）**

#include <iostream>
    #include <string>
    #include <map>
    using namespace std;
    
    int main()
    {
        // 建立multimap容器，存储作者及其作品
        multimap<string, string> authors;
        string author, work, searchItem;
    
        do
        {
            cout << "Enter author's name(Ctrl + D or Ctrl + Z to end): " << endl;
            cin >> author;
    
            if (!cin) break;
    
            cout << "Enter author's works(Ctrl + D or Ctrl + Z to end): " << endl;
            while (cin >> work)
            {
                authors.insert(make_pair(author, work));
            }
            cin.clear();
        }
        while (cin);
    
        cin.clear();
    
        // 使用find函数在容器中查找元素，并调用erase将其删除
        // 查找的元素不存在时，确保程序的正确运行
        cout << "Enter the author's name that you want erase: " << endl;
        cin >> searchItem;
    
        multimap<string, string>::iterator iter = authors.find(searchItem);
        if (iter != authors.end())
        {
            authors.erase(searchItem);
        }
        else
        {
            cout << "Can't find the author " << searchItem << "." << endl;
        }
    
        // 输出multimap对象
        cout << "author\t\twork" << endl;
        for (iter = authors.begin(); iter != authors.end(); ++iter)
        {
            cout << iter->first << "\t\t" << iter->second << endl;
        }
    
        return 0;
    }

[chapter10]$ ./a.out 
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    1
    Enter author's works(Ctrl + D or Ctrl + Z to end): 
    a b c
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    2
    Enter author's works(Ctrl + D or Ctrl + Z to end): 
    d e f
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    3
    Enter author's works(Ctrl + D or Ctrl + Z to end): 
    g h i
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    Enter the author's name that you want erase: 
    2
    author          work
    1               a
    1               b
    1               c
    3               g
    3               h
    3               i

**习题10.27：在multimap容器中查找并删除元素（equal\_range函数）**

#include <iostream>
    #include <string>
    #include <map>
    using namespace std;
    
    int main()
    {
        // 建立multimap容器，存储作者及其作品
        multimap<string, string> authors;
        string author, work, searchItem;
    
        do
        {
            cout << "Enter author's name(Ctrl + D or Ctrl + Z to end): " << endl;
            cin >> author;
    
            if (!cin) break;
    
            cout << "Enter author's works(Ctrl + D or Ctrl + Z to end): " << endl;
            while (cin >> work)
            {
                authors.insert(make_pair(author, work));
            }
            cin.clear();
        }
        while (cin);
    
        cin.clear();
    
        // 使用euqal_range函数在容器中查找元素，并调用erase将其删除
        // 查找的元素不存在时，确保程序的正确运行
        cout << "V2: Enter the author's name that you want erase: " << endl;
        cin >> searchItem;
    
        typedef multimap<string, string>::iterator authors_it;
        pair<authors_it, authors_it> pos = authors.equal_range(searchItem);
       
        if (pos.first != pos.second)
        {
            authors.erase(pos.first, pos.second);
        }
        else
        {
            cout << "Can't find the author " << searchItem << "." << endl;
        }
    
        // 输出multimap对象
        cout << "author\t\twork" << endl;
        for (authors_it iter = authors.begin(); iter != authors.end(); ++iter)
        {
            cout << iter->first << "\t\t" << iter->second << endl;
        }
    
        return 0;
    }

[chapter10]$ ./a.out
    Enter author's name(Ctrl + D or Ctrl + Z to end):
    1
    Enter author's works(Ctrl + D or Ctrl + Z to end):
    a b c
    Enter author's name(Ctrl + D or Ctrl + Z to end):
    2
    Enter author's works(Ctrl + D or Ctrl + Z to end):
    d e f
    Enter author's name(Ctrl + D or Ctrl + Z to end):
    3
    Enter author's works(Ctrl + D or Ctrl + Z to end):
    g h i
    Enter author's name(Ctrl + D or Ctrl + Z to end):
    V2: Enter the author's name that you want erase:
    2
    author          work
    1               a
    1               b
    1               c
    3               g
    3               h
    3               i

**习题10.28：在multimap容器中的元素按字典顺序输出（equal\_range函数）**

#include <iostream>
    #include <string>
    #include <map>
    using namespace std;
    
    int main()
    {
        // 建立multimap容器，存储作者及其作品
        multimap<string, string> authors;
        string author, work, searchItem;
    
        do
        {
            cout << "Enter author's name(Ctrl + D or Ctrl + Z to end): " << endl;
            cin >> author;
    
            if (!cin) break;
    
            cout << "Enter author's works(Ctrl + D or Ctrl + Z to end): " << endl;
            while (cin >> work)
            {
                authors.insert(make_pair(author, work));
            }
            cin.clear();
        }
        while (cin);
    
        cin.clear();
    
        // 按姓名首字母的顺序输出作者及其作品
        // Author Names Beginning with 'A':
        // Author, book, book, ...
        // ...
        // Author Names Beginning whit 'B':
        // ...
    
        if (authors.empty())
        {
            cout << "Empty multimap!" << endl;
            return 0;
        }
    
        string preAuthor, curAuthor;
    
        typedef multimap<string, string>::iterator authors_it;
        authors_it iter = authors.begin();
        while (iter != authors.end())
        {
            curAuthor = iter->first;
            if (preAuthor.empty() || curAuthor[0] != preAuthor[0])
            {
                preAuthor = curAuthor;
                cout << "Author Names Beginning with '" << curAuthor[0] << "': " << endl;
            }
    
            cout << curAuthor;
    
            pair<authors_it, authors_it> pos = authors.equal_range(curAuthor);
            while (pos.first != pos.second)
            {
                cout << ", " << pos.first->second;
                ++pos.first;
            }
            cout << endl;
    
            iter = pos.second;
        }
    
        return 0;
    }

[chapter10]$ ./a.out 
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    B
    Enter author's works(Ctrl + D or Ctrl + Z to end): 
    4 5 6
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    C
    Enter author's works(Ctrl + D or Ctrl + Z to end): 
    7 8 9
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    A
    Enter author's works(Ctrl + D or Ctrl + Z to end): 
    1 2 3
    Enter author's name(Ctrl + D or Ctrl + Z to end): 
    Author Names Beginning with 'A': 
    A, 1, 2, 3
    Author Names Beginning with 'B': 
    B, 4, 5, 6
    Author Names Beginning with 'C': 
    C, 7, 8, 9