std::unordered_multiset 的用例

Question

我想知道为什么有人会使用

std::unordered_multiset

。我的猜测是它与插入/擦除后迭代器的失效或非失效有关，但也许它有更深层次的东西？非常相似的问题在这里：std::multimap的用例，但更多的是关于地图的讨论。

Answer 1

关于你的问题，

unordered_multiset

容器最重要的特点是：

• 它们是关联容器，因此与（未排序的）向量相比，它们允许快速数据查找和检索。
• 它们通常比多重集快得多，无论是插入还是查找，有时甚至删除（参见例如此基准）。

因此，

unordered_multiset

的典型用例是当您需要快速查找并且不关心数据是否无序时：

• 如果您根本不进行任何数据查找，向量可能是更好的解决方案；
• 如果您需要对数据进行排序，则可能应该使用多重集。

请注意，在其他情况下不能或不应使用无序容器。

• 首先，如果散列的成本非常高，则无序容器实际上可能会比有序容器慢。
• 其次，无序容器的最坏情况插入复杂度是线性的，而不是像有序容器的情况那样是对数的。实际上，这意味着插入几乎总是非常快，除非有时容器大小超过某个容量阈值并且整个容器需要重新散列。因此，如果您对插入时间有严格的计时要求或者重新散列非常慢，则可能无法使用无序容器。
• 第三，在某些情况下，unordered_multiset 的内存消耗可能会高得令人无法接受（但有时可以通过微调容器参数来解决）。

关于有序容器优于无序容器的用例，您可能需要阅读这个答案。有关容器选择的一般准则，您可能需要阅读如何在 C++11 中有效地选择标准库容器？。

编辑

考虑到无序多重集和向量通常可以做非常相似的事情，那么始终使用向量不是更好吗？向量不会自动优于无序多重集吗？

下面转载的是一个非常简单的基准测试的结果（完整的代码在本文末尾提供）：

• 我们创建一个容器，它可以是无序多重集、原始向量或排序向量；
• 我们交替插入一些随机元素，然后计算一些随机密钥；
• 插入+计数操作重复10万次；
• 测量并显示这 100 000 次插入+计数操作所需的总持续时间。

以下是整数容器获得的结果：

环境 编译器	Windows 7 VS Express 2013	CygWin 64 位 gcc 4.9.3
unordered_multiset<int>	0.75秒	0.8秒
vector<int> ，未排序	7.9秒	11.0秒
vector<int> ，已排序	1.0秒	0.6秒

在上面的示例中，无序多重集对于 Windows 基准测试稍好一些，而排序向量对于 CygWin 基准测试稍好一些。对于多目标开发，这里没有明显的选择。

以下是使用字符串容器进行类似测试的结果：

环境 编译器	Windows 7 VS Express 2013	CygWin 64 位 gcc 4.9.3
unordered_multiset<string>	1 秒	1 秒
vector<string> ，未排序	30秒	65 秒
vector<string> ，已排序	130秒	32秒

在此示例中，无序多重集的性能远远优于向量。

确切的数字在这里并不重要，因为它们特定于执行这些基准测试的特定条件（硬件、操作系统、编译器、编译器选项等）。重要的是向量有时优于无序多重集，但有时却不然。确定是否应将无序多重集或向量用于给定应用程序的唯一方法是尽可能实际地进行基准测试。

下面包含整数容器基准测试的代码。由于它是即时开发的，欢迎所有更正和改进！

#include "stdafx.h"
#include <iostream>
#include <array>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <unordered_map>
#include <string>

using namespace std;

const unsigned N = 100000;      // Number of test iterations (= insertions + lookups)
typedef string Element;         // Type of data stored into the container to be tested
array<Element, N> testData;     // Pseudo-random input sequence
array<Element, N> lookupKeys;   // Pseudo-random lookup keys

// Test action for an unordered_multiset (insert some random data then count some random key)
struct unordered_multiset_action
{
    typedef unordered_multiset<Element> Container;
    int operator()(Container& container, unsigned k)
    {
        container.insert(testData[k]);
        return container.count(lookupKeys[k]);
    }
};

// Test action for an unsorted vector (insert some random data then count some random key)
struct unsorted_vector_action
{
    typedef vector<Element> Container;
    int operator()(Container& container, unsigned k)
    {
        container.push_back(testData[k]);               
        return count(testData.cbegin(), testData.cend(), lookupKeys[k]);
    }
};

// Test action for a sorted vector (insert some random data then count some random key)
struct sorted_vector_action
{
    typedef vector<Element> Container;
    int operator()(Container& container, unsigned k)
    {
        container.insert(upper_bound(container.begin(), container.end(), testData[k]), testData[k]);
        auto range = equal_range(container.cbegin(), container.cend(), lookupKeys[k]);
        return range.second - range.first;
    }
};

// Builds an empty container to be tested
// Then invokes N times the test action (insert some random key then count some other random key)
template<class Action>
long long container_test(Action action)
{
    using Container = typename Action::Container;
    Container container;
    long long keyCount = 0;
    for (unsigned k = 0; k<N; ++k)
        keyCount += action(container, k);
    return keyCount;
}

int main(int nargs, char *args[])
{
    using namespace chrono;

    // Parse user input to select which container should be tested
    enum SelectedContainer { UNORDERED_MULTISET, UNSORTED_VECTOR, SORTED_VECTOR };
    unordered_map<string, SelectedContainer> decoder{ { "unordered_multiset", UNORDERED_MULTISET },
                                                      { "unsorted_vector",    UNSORTED_VECTOR },
                                                      { "sorted_vector",      SORTED_VECTOR } };
    if ( nargs < 2 )
    {
        cerr << "Please provde an argument among those keywords: unordered_multiset, unsorted_vector, sorted_vector" << endl;
        return (-1);
    }
    auto it = decoder.find(args[1]);
    if (it == decoder.cend())
    {
        cerr << "Please enter one of the following arguments: unordered_multiset, unsorted_vector, sorted_vector" << endl;
        return (-1);
    }
    SelectedContainer selectedContainer = it->second;

    // Generate pseudo-random input data and input keys (no seeding for reproducibility)
    generate(testData.begin(),   testData.end(), []()   { return rand() % 256; });
    generate(lookupKeys.begin(), lookupKeys.end(), []() { return rand() % 256; });

    // Run test on container to be tested and measure elapsed time
    auto startTime = high_resolution_clock::now();
    long long keyCount;
    switch (selectedContainer)
    {
    case UNORDERED_MULTISET: 
        keyCount = container_test(unordered_multiset_action());
        break;
    case UNSORTED_VECTOR:
        keyCount = container_test(unsorted_vector_action());
        break;
    case SORTED_VECTOR:
        keyCount = container_test(sorted_vector_action());
        break;
    };
    
    auto endTime = high_resolution_clock::now();

    // Summarize test results
    duration<float> elaspedTime = endTime - startTime;
    cout << "Performed " << N << " insertions interleaved with " << N << " data lookups" << endl;
    cout << "Total key count = " << keyCount << endl;
    cout << "Elapsed time: " << duration_cast<milliseconds>(elaspedTime).count() << " milliseconds" << endl;
}