1 概述

  无序多集是不按特定顺序存储元素的容器，允许根据单个元素的值快速检索这些元素，与无序集容器非常相似，但允许不同的元素具有相同的值。
  在一个无序的多重集合中，一个元素的值同时也是用来识别它的键。键是不可变的，因此，无序的多重集中的元素不能在容器中修改一次，它们可以插入和删除。
  在内部，undered_multiset中的元素没有任何特定的排序，而是根据它们的哈希值组织到桶中，以允许直接根据它们的值快速访问各个元素（平均具有恒定的平均时间复杂度）。
  具有等效值的元素被分组在同一个bucket中，并且迭代器（请参阅equal_range）可以遍历所有元素。
  容器中的迭代器至少是前向迭代器。

容器特性：

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

2 使用实例

void UnorderedMultiSet::rehash()
{
   
    std::unordered_multiset<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");
    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_multiset(T const & a, T const& b)
{
   
    T t(a);
    t.insert(b.begin(), b.end());
    return t;
}

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

    TEST_ASSERT_EQUALS(true, a.empty())
    TEST_ASSERT_EQUALS(4, b.size())
    TEST_ASSERT_EQUALS(4, c.size())
    TEST_ASSERT_EQUALS(4, d.size())
    TEST_ASSERT_EQUALS(8, e.size())
    TEST_ASSERT_EQUALS(8, f.size())
}

3.2 assigns

void UnorderedMultiSet::assigns()
{
   
    std::unordered_multiset<int> a;
    std::unordered_multiset<int> b;
    std::unordered_multiset<int> c;
    std::unordered_multiset<int> d;
    a = {
    1, 2, 3, 3 };
    b = {
    4, 5, 6, 6 };
    c = merge_multiset(a, b);
    d = c;
    
    TEST_ASSERT_EQUALS(4, a.size())
    TEST_ASSERT_EQUALS(4, b.size())
    TEST_ASSERT_EQUALS(8, c.size())
    TEST_ASSERT_EQUALS(8, d.size())
}

3.3 iterators

void UnorderedMultiSet::iterators