C++容器之无序集(std::unordered_set)

目录

• 1 概述
• 2 使用实例
• 3 接口使用
• • 3.1 construct
  • 3.2 assigns
  • 3.3 iterators
  • 3.4 capacity
  • 3.5 find
  • 3.6 count
  • 3.7 equal_range
  • 3.8 emplace
  • 3.9 emplace_hint
  • 3.10 insert
  • 3.11 erase
  • 3.12 clear
  • 3.13 swap
  • 3.14 bucket_count
  • 3.15 max_bucket_count
  • 3.16 bucket_size
  • 3.17 bucket
  • 3.18 load_factor
  • 3.19 max_load_factor
  • 3.20 rehash
  • 3.21 reserve
  • 3.22 hash_function
  • 3.23 key_eq
  • 3.24 get_allocator

1 概述

  无序集是不按特定顺序存储唯一元素的容器，允许根据单个元素的值快速检索这些元素。
  在一个无序集合中，元素的值同时也是唯一标识它的键。键是不可变的，因此，不能在容器中修改无序集中的元素，但它们可以插入和移除。
  在内部，无序集中的元素不按任何特定顺序排序，而是根据其哈希值组织到桶中，以允许直接根据其值快速访问各个元素（平均具有恒定的平均时间复杂度）。
  无序集合容器比集合容器更快地通过关键字访问单个元素，尽管它们通常在通过元素子集进行范围迭代时效率较低。
  容器中的迭代器至少是前向迭代器。

容器特性：

• 关联性 关联容器中的元素由它们的键(Key)引用，而不是由它们在容器中的绝对位置引用。
• 无序性 无序容器使用哈希表来组织其元素，哈希表允许通过其键快速访问元素。
• 集合 元素的值也是用来识别它的键(Key)。
• 唯一性 容器中没有两个元素可以具有等效的键。
• 分配器感知 容器使用分配器对象来动态处理其存储需求。
• 其类图如下:
  

2 使用实例

void UnorderedSetSuite::rehash()
{
   
    std::unordered_set<std::string> a;

    a.rehash(12);
    TEST_ASSERT_EQUALS(true, a.bucket_count() > 12)

    a.insert("James");
    a.insert("Tom");
    a.insert("Jim");
    a.insert("Rose");
    a.insert("Geore");

    uint32_t bucket_count = a.bucket_count();
    a.rehash(11);
    TEST_ASSERT_EQUALS(bucket_count, a.bucket_count())

    a.rehash(5);
    TEST_ASSERT_EQUALS(true, a.bucket_count() < bucket_count)
}

3 接口使用

3.1 construct

template<class T>
T merge_set(T const & a, T const& b)
{
   
    T t(a);
    t.insert(b.begin(), b.end());
    return t;
}

void UnorderedSetSuite::construct()
{
   
    std::unordered_set<int> a;
    std::unordered_set<int> b({
    1, 2, 3, 3 });
    std::unordered_set<int> c({
    4, 5, 6, 6 });
    std::unordered_set<int> d(b);
    std::unordered_set<int> e(merge_set(b, c));
    std::unordered_set<int> f(e.begin(), e.end());

    TEST_ASSERT_EQUALS(true, a.empty())
    TEST_ASSERT_EQUALS(3, b.size())
    TEST_ASSERT_EQUALS(3, c.size())
    TEST_ASSERT_EQUALS(3, d.size())
    TEST_ASSERT_EQUALS(6, e.size())
    TEST_ASSERT_EQUALS(6, f.size())
}

3.2 assigns

void UnorderedSetSuite::assigns()
{
   
    std::unordered_set<int> a;
    std::unordered_set<int> b;
    std::unordered_set<int> c;
    std::unordered_set<int> d;
    a = {
    1, 2, 3, 3 };
    b = {
    4, 5, 6, 6 };
    c = merge_set(a, b);
    d = c;
    
    TEST_ASSERT_EQUALS(3, a.size())
    TEST_ASSERT_EQUALS(3, b.size())
    TEST_ASSERT_EQUALS(6, c.size())
    TEST_ASSERT_EQUALS(6, d.size())
}

3.3 iterators

void UnorderedSetSuite::iterators()
{
   
    std::unordered_set<std::string> names = 
    {
    "James", "Tom",