std :: unordered_multiset的用例

Question

我想知道为什么会用std::unordered_multiset。我的猜测是它与插入/擦除后迭代器的无效或非无效有关，但也许更深层吗？非常相似的问题在这里：std :: multimap的用例，但更多是关于地图的讨论。

Answer 1

关于您的问题，unordered_multiset容器的最重要特征是：

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

因此，一种典型的用例unordered_multiset是当您需要快速查找并且不关心数据是无序的时：

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

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

• 首先，如果散列非常昂贵，那么无序容器实际上可能会比有序容器变慢。
• 其次，无序容器的最坏情况插入复杂度是线性的，而不是有序容器的对数。在实践中，这意味着插入几乎总是非常快，除了有时容器大小超过某个容量阈值并且需要重新包装整个容器时。因此，如果对插入时间有严格的时序要求或重新哈希处理非常缓慢，则可能无法使用无序容器。
• 第三，在某些情况下，unordered_multiset的内存消耗过高（但是有时可以通过微调容器参数来解决）。

关于应优先使用有序容器而不是无序容器的用例，您可能需要阅读此答案。有关容器选择的一般准则，您可能需要阅读如何在C ++ 11中有效选择标准库容器？。

编辑

考虑到无序多重集和向量通常可以做非常相似的事情，总是使用向量不是更好吗？向量不自动胜过无序多重集吗？

以下是一个非常简单的基准测试的结果（本文结尾提供了完整的代码）：

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

这是从整数容器获得的结果：

| --------------------------------------------- | --- ------------- |
| 环境| Windows 7 | CygWin 64位|
| 编译器 VS Express 2013 | 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 | CygWin 64位|
| 编译器 VS Express 2013 | gcc 4.9.3 |
| ----------------------------------------------- |- --------------- |
| unordered_multiset <字符串> | 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;
}