C++ Primer Plus 学习笔记第十六章关联容器

- 日理万妓 2022-01-11 05:19 324阅读 0赞

字典

数据结构为树

元素查找比链表快

4种关联容器

set, multiset, <set>

map, multimap, <map>

set:

键就是值 唯一

multiset 不唯一。可以有多个重复的键值

可翻转，可排序

格式： set<string> A;

可以显示的指定排序的函数或对象 默认用less<> :

set<string, less<string>> A;

set有将迭代器区间作为参数的构造函数

![20190619172801939.png][]

只有1个for会写到A中

然后自动排序

可用于数学的集合运算（并集，交集，差集等）

在做这些运算前必须先将容器元素进行排序

set\_union()

![2019061917325154.png][]

![20190619173255969.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70][]

set\_intersection():交集

set\_difference()差集

lower\_bound() 传入的1个参数，查找容器中第一个不小于该参数的键的成员

upper\_bound()传入的1个参数，查找容器中第一个大于该参数的键的成员

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 1][]

set程序示例

#include <iostream>
    #include <string>
    #include <set>
    #include <algorithm>
    #include <iterator>
    
    int main()
    {
      using namespace std;
      const int N = 6;
      string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};
      string s2[N] = {"metal", "any", "food", "elegant", "deliver", "for"};
    
      set<string> A(s1, s1 + N);
      set<string> B(s2, s2 + N);
    
      ostream_iterator<string, char> out(cout, " ");
      cout << "Set A: ";
      copy(A.begin(), A.end(), out);
      cout << endl;
      cout << "Set B: ";
      copy(B.begin(), B.end(), out);
      cout <<endl;
      cout << "Union of A and B:\n";
    // 合并输出 并集
      set_union(A.begin(), A.end(), B.begin(), B.end(), out);
      cout << endl;
    
      cout << "Intersection of A and B:\n";
    // 交集输出
      set_intersection(A.begin(), A.end(), B.begin(), B.end(), out);
      cout << endl;
      
      cout << "Difference of A and B:\n";
    // 差集输出
      set_difference(A.begin(), A.end(), B.begin(), B.end(), out);
      cout << endl;
    
      set<string> C;
      cout << "Set C:\n";
    // 并集输出到C容器中 利用插入迭代器
      set_union(A.begin(), A.end(), B.begin(), B.end(), 
          insert_iterator<set<string>> (C, C.begin()));
      copy(C.begin(), C.end(), out);
      cout << endl;
    
      string s3("grungy");
    // 插入并自动排序
      C.insert(s3);
      cout << "Set C after insertion:\n";
      copy(C.begin(), C.end(), out);
      cout << endl;
    
      cout << "Showing a range:\n";
    //string区间输出
      copy(C.lower_bound("ghost"), C.upper_bound("soppk"), out);
      cout << endl;
    
      return 0;
    }

程序结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 2][]

map:

键与值不同，键唯一 一对一

multimap是一对多

元素也是一个STL模板

数据是按键排序

对于元素。可以使用first和second成员来访问键和值

count()传入键，获取键对应的值得数目

lower\_bound() ,upper\_bound() 使用与set一致

qual\_range() 用键作为参数 返回符合该键的元素的两个迭代器区间，这个迭代器的类型就是multimap模板的类型

程序示例

#include <iostream>
    #include <string>
    #include <map>
    #include <algorithm>
    
    typedef int KeyType;
    typedef std::pair<const KeyType, std::string> Pair;
    typedef std::multimap<KeyType, std::string> MapCode;
    
    int main()
    {
      using namespace std;
      MapCode codes;
    
      codes.insert(Pair(415, "San Franciso"));
      codes.insert(Pair(510, "Oakland"));
      codes.insert(Pair(718, "Brooklyn"));
      codes.insert(Pair(718, "Staten Island"));
      codes.insert(Pair(718, "Staten Island"));
      codes.insert(Pair(718, "Staten Island"));
      codes.insert(Pair(415, "San Rafael"));
      codes.insert(Pair(450, "Berkeley"));
    
      cout << "Number of cities with area code 415: "
    // 计数 键为415的元素数量
          << codes.count(415) << endl;
      cout << "Number of cities with area code 718: "
          << codes.count(415) << endl;
      cout << "Number of cities with area code 510: "
          << codes.count(415) << endl;
      cout << "Area Code  City\n";
      MapCode::iterator it;
    
      for (it=codes.begin(); it != codes.end(); ++it)
        cout <<"   " << (*it).first << "    "
             << (*it).second << endl;
      
    取得键为718的multimap类型迭代器区间。（queal_range会将该迭代器区间包裹成pair类型模板）
    // 第一个迭代器表示起始位, 第二个迭代器表示超尾 
      pair<MapCode::iterator, MapCode::iterator> range 
          = codes.equal_range(718);
      cout << "Cities with area code 718:\n";
      for (it = range.first; it != range.second; ++it)
      {
          cout << (*it).second   << endl;
      }
    
      return 0;
    
    }

无序关联容器 底层是用哈希表

unordered\_set, unordered\_multiset, unordered\_map unordered\_multimap

书上不说了 直接让我去看附录= =那我最后再去看吧

泛型编程部分 完结

[20190619172801939.png]: /images/20220111/6e2643bc43244238885f5014aa708fd0.png
[2019061917325154.png]: /images/20220111/94c644c17a2549aaa9e73e157ff5529b.png
[20190619173255969.png]: /images/20220111/c2d755b584f34d70b411d97a4305fdb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70]: /images/20220111/26c39241543c4c56adeef40e2841637b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 1]: /images/20220111/9a88065b504e48b1b36c00b9739e8e96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvdWx3eWI_size_16_color_FFFFFF_t_70 2]: /images/20220111/dcc8e549d386423d95a080288cb31722.png