std::unordered_multiset 的用例

Question

我想知道为什么有人会使用 std::unordered_multiset。我的猜测是它与 insert/erase 之后迭代器的失效或非失效有关，但也许它更深层次？非常相似的问题在这里：Use cases of std::multimap，但更多的是关于地图的讨论。

Answer 1

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

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

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

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

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

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

关于有序容器优于无序容器的用例，您可能需要阅读 this answer. For general guidelines regarding container selection, you may want to read How can I efficiently select a Standard Library container in C++11?。

编辑

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

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

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

以下是整数容器的结果：

|---------------------------------------------|----------------|
| Environment              |     Windows 7    | CygWin 64 bits |
| Compiler                 | VS Express 2013  |   gcc 4.9.3    |
|---------------------------------------------|----------------|
| unordered_multiset<int>  |    0.75 s        |     0.8 s      |
| vector<int>, unsorted    |    7.9  s        |    11.0 s      |
| vector<int>, sorted      |    1.0  s        |     0.6 s      | 
|---------------------------------------------|----------------|

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

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

|-----------------------------------------------|----------------|
| Environment                |     Windows 7    | CygWin 64 bits |
| Compiler                   | VS Express 2013  |   gcc 4.9.3    |
|-----------------------------------------------|----------------|
| unordered_multiset<string> |      1  s        |       1 s      |
| vector<string>, unsorted   |     30  s        |      65 s      |
| vector<string>, sorted     |    130  s        |      32 s      | 
|-----------------------------------------------|----------------|

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

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

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

#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;
}

std::unordered_multiset 的用例

Usecases for std::unordered_multiset

stl

hashset

c++11

unordered-multiset