当前位置 : 主页 > 编程语言 > c++ >

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

来源:互联网 收集:自由互联 发布时间:2021-06-23
目录 关联容器 有序关联容器——map, set, multimap, multiset 无序关联容器——unordered_map, unordered_set, unordered_multimap, unordered_multiset 关联容器 选择什么容器根据业务需求, 研读STL剖析了解底层

目录

  • 关联容器
    • 有序关联容器——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;
网友评论