Примеры использования для std::unordered_multiset
Я хотел бы знать, почему кто-то будет использовать std::unordered_multiset, Я предполагаю, что это как-то связано с недействительностью или недействительностью итераторов после вставки / стирания, но, может быть, это что-то более глубокое? Очень похожий вопрос здесь: варианты использования std:: multimap, но это больше обсуждение карт.
1 ответ
Что касается вашего вопроса, наиболее важные особенности unordered_multiset контейнеры таковы:
- Это ассоциативные контейнеры, поэтому они обеспечивают быстрый поиск и извлечение данных по сравнению с (несортированными) векторами.
- Они, как правило, намного быстрее, чем мультимножества, как для вставки, так и для поиска, а иногда даже для удаления (см., Например, этот тест).
Таким образом, типичный вариант использования для unordered_multiset было бы, когда вам нужен быстрый поиск и не волнует, что данные неупорядочены:
- Если вы вообще не просматриваете данные, вектор, вероятно, будет лучшим решением;
- Если вам нужно отсортировать данные, вероятно, следует использовать мультимножество.
Обратите внимание, что существуют другие ситуации, когда неупорядоченные контейнеры не могут или не должны использоваться.
- Во-первых, если хеширование очень дорого, неупорядоченный контейнер может на самом деле стать медленнее, чем упорядоченный.
- Во-вторых, сложность вставки в наихудшем случае для неупорядоченного контейнера является линейной, а не логарифмической, как в случае упорядоченного контейнера. На практике это означает, что вставка происходит почти всегда очень быстро, за исключением случаев, когда размер контейнера превышает некоторый порог емкости, и что весь контейнер необходимо перефразировать. Как следствие, может быть невозможно использовать неупорядоченный контейнер, если у вас есть строгие требования к времени для времени вставки или если перефразировка очень медленная.
- В-третьих, могут быть случаи, когда потребление памяти неприемлемо велико для unordered_multiset (но иногда это можно решить путем точной настройки параметров контейнера).
Что касается случаев использования, когда заказанные контейнеры должны быть предпочтительнее неупорядоченных, вы можете прочитать этот ответ. Общие рекомендации по выбору контейнера можно прочитать в разделе Как эффективно выбрать контейнер стандартной библиотеки в C++11?,
РЕДАКТИРОВАТЬ
Учитывая, что неупорядоченный мультимножество и вектор часто могут делать очень похожие вещи, не лучше ли всегда использовать вектор? Разве векторы не превосходят неупорядоченные мультимножества?
Ниже приведены результаты очень простого теста (полный код приведен в конце этого поста):
- Мы создаем контейнер, который может быть неупорядоченным мультимножеством, необработанным вектором или отсортированным вектором;
- Мы поочередно вставляем некоторый случайный элемент, а затем подсчитываем некоторый случайный ключ;
- Операция вставки + счета повторяется 100 000 раз;
- Общая продолжительность, необходимая для этих 100 000 операций вставки + подсчета, измеряется и отображается.
Вот результаты, полученные для контейнеров целых чисел:
| --------------------------------------------- | --- ------------- | | Окружающая среда | Windows 7 | CygWin 64 бит | | Компилятор | VS Express 2013 | gcc 4.9.3 | | --------------------------------------------- | --- ------------- | | unordered_multiset| 0,75 с | 0,8 с | | вектор , несортированный | 7,9 с | 11,0 с | | вектор , отсортировано | 1,0 с | 0,6 с | | --------------------------------------------- | --- ------------- |
В приведенном выше примере неупорядоченный мультимножество немного лучше для эталонного теста Windows, тогда как отсортированный вектор немного лучше для эталонного теста CygWin. Для многоцелевой разработки здесь нет очевидного выбора.
Ниже приведены результаты аналогичного теста с контейнерами строк:
| ----------------------------------------------- | - --------------- | | Окружающая среда | Windows 7 | CygWin 64 бит | | Компилятор | VS Express 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;
}