Skip to content

Latest commit

 

History

History
163 lines (130 loc) · 8.89 KB

ch11.md

File metadata and controls

163 lines (130 loc) · 8.89 KB
Raw

第十一章 关联容器

  • 关联容器主要用于高效的关键字查找和访问操作，基本的关联容器类型是 map和 set。
  • 关联容器基于关键字访问元素，顺序容器基于位置访问元素

关联容器类型：

容器类型 解释
按顺序存储
map 关键数组：保存关键字-值对，头文件map
set 关键字即值，即只保存关键字的容器（或者说每个元素只包含一个关键字），头文件set
multimap 支持同一个键多次出现的map，头文件map
multiset 支持同一个键多次出现的set，头文件set
无序集合
unordered_map 用哈希函数组织的map，头文件unordered_map
unordered_set 用哈希函数组织的set，头文件unordered_set
unordered_multimap 哈希组织的map，关键字可以重复出现，头文件unordered_map
unordered_multiset 哈希组织的set，关键字可以重复出现，头文件unordered_set

关联容器概述

  • map类型通常被称为关联数组

  • 对于有序容器，关键字类型必须定义元素比较的方法（即<），严格弱序

  • map中的每个元素都是一个pair类型的对象，pair是一个模板类型，保存两个名为first和second的共有数据成员，first保存关键字，second保存值

    • pair在utility头文件中定义。

      操作 解释
      pair<T1, T2> p; p是一个pair，两个类型分别是T1和T2的成员都进行了值初始化。
      pair<T1, T2> p(v1, v2); first和second分别用v1和v2进行初始化。
      pair<T1, T2>p = {v1, v2}; 等价于`p(v1, v2)
      make_pair(v1, v2); pair的类型从v1和v2的类型推断出来。
      p.first 返回p的名为first的数据成员。
      p.second 返回p的名为second的数据成员。
      p1 relop p2 relop(relational operations,<,>,<=,>=)，运算关系符按字典序定义。
      p1 == p2 必须两对元素两两相等
      p1 != p2 同上

  • 例子：

    // 定义一个重载键类型的类，重载()操作符
class MyCmp{
public:
    // 比较键类型
    bool operator() (const string &a, const string &b) {return a.size() < b.size();}    
};
map<string, int, MyCmp> mp{{"a", 1}, {"ab", 2}, {"b", 3}}; // 每个键值对用花括号包围
set<string> exclude = {"the", "a"};

bool cmp(const string &a, const string &b) {return a.size() < b.size();}
map<string, int, bool(*)(const string&, const string&)> mp2({{"a", 1}, {"b", 2}}, cmp); // 模板中传入函数类型，构造函数中传入函数指针

using CMP = bool(*)(const string&, const string&); // 函数类型的别名
map<string, int, CMP> mp3({{"a", 1}, {"b", 2}}, cmp); // 或者模板中传入函数类型的别名，构造函数中同样传入函数指针

// 遍历
for(map<string, int, CMP>::iterator iter = mp3.begin(); iter != mp3.end(); ++iter) // 或者使用map<string, int>::iterator iter也可以
  cout << iter->first >> " " >> iter->second >>endl;

关联容器操作

  • 关联容器额外的类型别名：

    类型别名 解释
    key_type 此容器类型的关键字类型
    mapped_type 每个关键字关联的类型，只适用于map系列
    value_type 对于map，是pair<const key_type, mapped_type>（注意关键字部分有const）; 对于set，和key_type相同。

  • 解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。

    • map而言，value_type是pair类型（pair<const key_type, mapped_type>）
    • set而言，value_type是const key_type，普通迭代器和const迭代器都是只读的，不能修改值

  • 通常不对关联容器使用泛型算法

添加元素：insert

insert操作 关联容器
c.insert(v) c.emplace(args) v是value_type类型的对象；args用来构造一个元素。 对于map和set，只有元素的关键字不存在c中才插入或构造元素。函数返回一个pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否成功的bool值。对于multimap和multiset则会插入范围中的每个元素。
c.insert(b, e) c.insert(il) b和e是迭代器，表示一个c::value_type类型值的范围；il是这种值的花括号列表（类似列表初始化进行insert）。函数返回void。对于 map和set，只插入关键字不在c中的元素。
c.insert(p, v) c.emplace(p, args) 类似insert(v)，但将迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素。
  • 向map添加元素（在参数列表中构建pair），例子： 
    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));
  • insert返回值：
    • 对于不包含重复关键字的关联容器：返回一个pair<iterator, bool>
    • 对于包含重复关键字的关联容器：返回一个指向新元素的迭代器
  • 相对于下标操作，多使用insert（因为有返回值）
    • 例子：练习11.21 
        map<string, size_t> word_count;
  string word;
  while(cin >> word)
    ++word_count.insert({word, 0}).first->second;

删除元素：erase

操作 解释
c.erase(k) 从c中删除每个关键字为k的元素。返回一个size_type值，指出删除的元素的数量。（顺序容器没有该操作）
c.erase(p) 从c中删除迭代器p指定的元素。p必须指向c中一个真实元素，不能等于c.end()。返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回c.end()
c.erase(b, e) 删除迭代器对b和e所表示范围中的元素。返回e。

下标操作

操作 解释
c[k] 返回关键字为k的元素；如果k不在c中，添加一个关键字为k的元素，对其值初始化。
c.at(k) 访问关键字为k的元素，带参数检查；若k不存在在c中，抛出一个out_of_range异常。
  • 下标和at操作只适用于非const的map和unordered_map，即使访问操作也不行

查找元素

在一个关联容器中查找元素:

操作 解释
c.find(k) 返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器
c.count(k) 返回关键字等于k的元素的数量。对于不允许重复关键字的容器，返回值永远是0或1。
c.lower_bound(k) 返回一个迭代器，指向第一个关键字不小于k的元素。
c.upper_bound(k) 返回一个迭代器，指向第一个关键字大于k的元素。
c.equal_range(k) 返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end()。
  • lower_bound和upper_bound不适用于无序容器。
  • 如果multimap或multiset中有多个元素有相同关键字，则这些元素在容器中会相邻存储

无序容器

  • 有序容器使用比较运算符来组织元素；无序容器使用哈希函数和关键字类型的==运算符。
  • 理论上哈希技术可以获得更好的性能。
  • 无序容器在存储上组织为一组桶(bucket)，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。无序容器首先计算元素的哈希值，找到应该搜索哪个桶（相同哈希值的元素保存到相同的桶中），再搜索桶。

无序容器管理操作：

操作 解释
桶接口
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_local_iterator。
哈希策略
c.load_factor() 每个桶的平均元素数量，返回float值。
c.max_load_factor() c试图维护的平均比桶大小，返回float值。c会在需要时添加新的桶，以使得load_factor<=max_load_factor
c.rehash(n) 重组存储，使得bucket_count>=n，且bucket_count>size/max_load_factor
c.reverse(n) 重组存储，使得c可以保存n个元素且不必rehash。