我想知道为什么有人会使用std::unordered_multiset. 我的猜测是它与插入/擦除后迭代器的失效或非失效有关，但也许它更深层次？非常相似的问题在这里：用例 std::multimap，但更多的是关于地图的讨论。
问问题
2189 次
1 回答
7
关于您的问题，unordered_multiset容器最重要的特点是：
- 它们是关联容器，因此与（未排序的）向量相比，它们允许快速的数据查找和检索。
- 它们通常比多集快得多，无论是插入还是查找，有时甚至是删除（参见例如this benchmark）。
因此，一个典型的用例unordered_multiset是当您需要快速查找并且不关心数据是无序的时：
- 如果您根本不进行任何数据查找，那么向量可能是更好的解决方案；
- 如果您需要对数据进行排序，则可能应该使用多重集。
请注意，在其他情况下，无序容器不能或不应使用。
- 首先，如果散列非常昂贵，那么无序容器实际上可能会比有序容器慢。
- 其次，无序容器的最坏情况插入复杂度是线性的，而不是有序容器的对数。在实践中，这意味着插入几乎总是非常快，除非有时容器大小超过某个容量阈值并且需要重新散列整个容器。因此，如果您对插入时间有严格的时序要求或重新散列非常慢，则可能无法使用无序容器。
- 第三，可能存在 unordered_multiset 的内存消耗高得无法接受的情况（但有时可以通过微调容器参数来解决）。
关于应优先使用有序容器而不是无序容器的用例，您可能需要阅读此答案。有关容器选择的一般指南，您可能需要阅读如何在 C++11 中有效地选择标准库容器？.
编辑
考虑到无序多重集和向量通常可以做非常相似的事情，总是使用向量不是更好吗？向量不会自动优于无序多重集吗？
下面转载的是一个非常简单的基准测试的结果（完整代码在本文末尾提供）：
- 我们创建一个容器，它可以是无序的多重集、原始向量或排序的向量；
- 我们交替插入一些随机元素，然后计算一些随机键；
- 插入+计数操作重复100 000次；
- 测量并显示这 100 000 次插入+计数操作所需的总持续时间。
以下是整数容器的结果：
|----------------------------------------------------------|--- -------------| | 环境 | 视窗 7 | CygWin 64 位 | | 编译器 | VS 快递 2013 | GCC 4.9.3 | |----------------------------------------------------------|--- -------------| | unordered_multiset<int> | 0.75 秒 | 0.8 秒 | | 向量<int>，未排序 | 7.9 秒 | 11.0 秒 | | 向量<int>，已排序 | 1.0 秒 | 0.6 秒 | |----------------------------------------------------------|--- -------------|
在上面的示例中，无序多重集在 Windows 基准测试中稍好一些，而有序向量在 CygWin 基准测试中稍好一些。对于多目标开发，这里没有明显的选择。
以下是使用字符串容器进行的类似测试的结果：
|------------------------------------------------|- ---------------| | 环境 | 视窗 7 | CygWin 64 位 | | 编译器 | VS 快递 2013 | GCC 4.9.3 | |------------------------------------------------|- ---------------| | unordered_multiset<字符串> | 1 秒 | 1 秒 | | 矢量<字符串>，未排序 | 30 秒 | 65 秒 | | 向量<字符串>，已排序 | 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;
}
于 2015-10-26T12:49:35.187 回答