C++ STL unordered_set用法整理

1 定义

unordered_set本质是使用hash散列的方式存储数据,是一种使用hash值作为key的容器,所以当有频繁的搜索、插入和移除拥有常数时间。unordered_set存储原理是声明一个有n个桶的数据结构,计算加入到unordered_set的新的值hash,然后计算hash%n后的值x,将新的值加入到桶x中。当桶x中已经有了元素,就直接链接在后边。当数据结构中的元素满足一定数量时需要扩充桶的数量,并重新构建桶结构。它具有以下特点:

  1、unordered_set是一种容器,它以不特定的顺序存储唯一的元素,并允许根据元素的值快速检索单个元素。

  2、在unordered_set中,元素的值同时是唯一标识它的键。键是不可变的,只可增删,不可修改。

  3、在内部,unordered_set中的元素没有按照任何特定的顺序排序,而是根据它们的散列值组织成桶(一个线性链表代表一个桶),从而允许通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。

  4、unordered_set容器比set容器更快地通过它们的键访问单个元素,尽管它们在元素子集的范围迭代中通常效率较低。

  5、容器中的迭代器只能是正向迭代器。

2 基本的函数

2.1 unordered_set构造

  std::unordered_set<std::string> c:初始化容器;

  std::unordered_set<std::string> c{ "aaa", "bbb", "ccc" }:初始化容器,并将"aaa", "bbb", "ccc"加入到容器中;

  std::unordered_set<std::string> c{ 16 }:初始化容器,并设置16个桶;

2.2 添加新的元素

  c.insert("dddd"):向容器添加元素”dddd";

  a.insert({ "aaa","bbbb","cccc" }):向容器添加元素"aaa","bbbb","cccc";

  a.insert(b.begin(), b.end()):b是一个存储着和a相同类型元素的向量,可将b中所有元素添加到a中。

2.3 查找元素

  a.find("eeee"):查找元素"eeee",返回结果为a.end()则表明没有找到,否则返回所对应元素;

  a.count("eeee"):查找元素"eeee"在a中有几个(由于unordered_set中没有相同的元素,所以结果通常为0或1)。

2.4 查找桶接口

  a.bucket_count():返回数据结构中桶的数量;

  a.bucket_size(i):返回桶i中的大小;

  a.bucket(“eeee"):返回元素"eeee"在哪个桶里。

2.5 观察器

  a.hash_function()("aaa"):返回"aaa"所对应的hash值;

  a.key_eq()("aaa","aaaa") :当元素相同时返回true,否则返回false。

2.6 清除元素

  a.clear():清除a中所有元素;

  a.erase("aaa"):清除元素"aaa"。

2.7 统计函数

  a.size():返回a中总的元素个数;

  a.max_size():返回a中最大容纳元素;

  a.empty():判断a中是否为空。

C++ STL unordered_set用法整理

上一篇:C++的两种实例化方式


下一篇:Caused by: java.lang.ClassNotFoundException: io.netty.resolver.AddressResolverGroup