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