c++11 - std::unordered_multiset 的用例

Question

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

Answer 1

关于您的问题，unordered_multiset 容器最重要的功能是:

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

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

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

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

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

关于有序容器优于无序容器的用例，您可能需要阅读 this answer 。有关容器选择的一般准则，您可能需要阅读 How can I efficiently select a Standard Library container in C++11? .

编辑

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

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

• 我们创建一个容器，它可以是无序多重集、原始向量或排序向量；
• 我们交替插入一些随机元素，然后计算一些随 secret 钥；
• 插入+计数操作重复100 000次；
• 测量并显示这 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      | |---------------------------------------------|----------------|

In the example above, the unordered multiset is slightly better for the Windows benchmark, whereas the sorted vector is slightly better for the CygWin benchmark. For a multi-target development, there is no obvious choice here.

Below are the results of a similar test with containers of strings:

|-----------------------------------------------|----------------|| 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      | |-----------------------------------------------|----------------|

In this example, the unordered multisets outperforms by far the vectors.

The exact figures don't matter much here, as they are specific to the specific conditions (hardware, OS, compiler, compiler options and so on) where these benchmarks were performed. What matters is that vectors sometimes outperform unordered multisets, but sometimes they don't. The only way to be sure whether unordered multisets or vectors should be used for a given application is to benchmark as realistically as feasible.

Below is included the code for the integer container benchmark. As it was developed on the fly, all corrections and improvements are welcome!

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