C++ Primer(三)_标准库_关联容器

目录

• 关联容器
  • 有序关联容器——map, set, multimap, multiset
  • 无序关联容器——unordered_map, unordered_set, unordered_multimap, unordered_multiset

关联容器

选择什么容器根据业务需求, 研读STL剖析了解底层数据结构, 更加清楚各种优势劣势

有序关联容器——map, set, multimap, multiset

map, multimap:

set, multiset:

pair:

有序依赖

• 元素的<运算符 > <运算符足以推断==和!=，交换执行即可

pair

• make_pair(t1, t2) —— 自动推断类型

• pair的比较

  先比较前者-first；再比较后者-second；依赖于元素的<或==

容器内部类型别名

key_type 关键字类型 mapped_type set没有，关键字的关联类型 value_tyep 容器元素类型，对于set为key_type；对于map为pair<const key_type, mapped_type>

set的iterator和const_iterator都是const的，即begin()和cbegin()得到的都是const迭代器

容器操作

• 增

  注意检查插入单独的元素时返回值，ret.second

操作 map和set multi版 .insert(v) 不存在时才插入或构造 .emplace(args) 返回值：pair<iterator， bool>——bool判断成功与否，迭代器为插入元素 返回插入元素的迭代器 .insert(p, v) 迭代器p为指示器，指示从哪里开始找插入点，即使从.end()开始的，也能找到前面的插入点 .emplace(p, args) 返回插入元素的迭代器 .insert(b, e) 插入范围或列表内元素，返回void .insert(il) 只插入不存在的

• 删

.erace(k) 返回size_type值，删除的数量 .erace(p) 若p不存在，未定义，若p == .end()，返回.end() .erace(b, e) 返回e

• 访问

map和unordered_map的特定操作 [] 存在返回；不存在，添加并值初始化 .at() 不存在，out_of_range

通用操作

.find(k) 返回第一个找到的迭代器，不存在.end() .count(k) 数量 .lower_bound(k) 第一个>=k的迭代器 .upper_bound(k) 第一个>k的迭代器，和lower_bound得到一个范围 .equal_range(k) 返回迭代器pair<b, e>，k不存在，两个都为.end()

• 根据通用操作得到的三种访问multi容器的方法

  • auto it = container.find(k);
    auto cnt = container.count(k);
    while (cnt)
    {
        *it ++;
        -- cnt;
    }

  • auto begin = container.lower_bound(k);
    auto end = container.upper_bound(k);
    while (begin != end)
    {
        *begin ++;
    }

  • auto ret = container.equal_range(k);
    auto begin = ret.first;
    while (begin != ret.second)
    {
        *begin ++;
    }

无序关联容器——unordered_map, unordered_set, unordered_multimap, unordered_multiset

unordered_map, unordered_multimap：

unordered_set, unordered_multiset：

桶

无序容器存储上组织为一组桶，每个桶保存零个或多个元素

桶管理

• 桶接口

  .bucket_count() 当前桶个数 .max_bucket_size() 容器最大桶个数 .bucket_size(n) 第n个桶的元素个数 .bucket(k) k在哪个桶，返回整型

• 桶迭代

  local_iterator 迭代器类型 const_local_iterator .begin(n), .end(n) 桶n的迭代器 .cbegin(n), .cend(n)

• 哈希策略

  负载因子 .load_factor() float，每个桶的平均元素个数 .max_load_factor() 试图维护的平均个数，需要时会加桶保持max_load_factor() > load_factor() .rehash(n) 重组存储，使桶个数>=n的同时，bucket_coun(实际有的) > size / max_load_factor(理论上维护factor需要的) .reserve(n) 重组存储，可以保存n个而不必rehash

无序容器对关键字的要求

默认情况用==比较

• 内置类型，一些标准库设施如：string，智能指针，其他容器等等都哈希特例化，直接用

• 自定义类类型——自己提供==和哈希函数

  size_t hasher(const MyClass &mc)  // 这个用来找桶的
  {
      return hash<string>()(mc.str());  // str()的到MyClass里的成员，能用来标识 
                                        // hash<string>()得到一个临时可调用类对象
  }
  bool eqOp(const MyClass &mc1, const MyClass &mc2) // 这个用来找桶里元素的
  {
      return mc1.str() == mc2.str();
  }
  unordered_map<MyClass, decltype(hasher)*, decltype(eqOp)*>    store;