Что-то среднее между std :: multimap и std :: vector?

Question

Я ищу контейнер STL, который работает как std :: multimap, но имеет постоянное время доступа к случайному n-му элементу. Я нуждаюсь в этом, потому что у меня есть такая структура в памяти, которая по многим причинам является std :: multimap, но элементы, хранящиеся в ней, должны быть представлены пользователю в списке. Поскольку объем данных огромен, я использую поле списка с виртуальными элементами (то есть опросы списка управления для значения в строке X).

В качестве обходного пути я в настоящее время использую дополнительный std :: vector для хранения «индексов» в std :: map и заполняю его так:

std::vector<MMap::data_type&> vec;
for (MMap::iterator it = mmap.begin(); it != mmap.end(); ++it)
    vec.push_back((*it).second);

Но это не очень элегантное решение.

Есть ли такой контейнер?

Answer 1

Что вам нужно, это: Повышение мультииндекса

Answer 2

Сколько элементов в этом списке, какого типа элементы, и как часто вы должны вставлять или удалять в середине этого списка? В зависимости от этого, вы можете использовать отсортированный std::vector<std::pair<key,value>> и std::binary_search с предикатом поиска, сравнивающим только ключи.

Answer 3

Помимо ваших требований, из ваших комментариев видно, что вы также планируете вставлять / удалять элементы. Я должен признать, что 20 миллионов, кажется, довольно много.

Теперь я понимаю идею опроса, но вы рассматривали что-то вроде unordered_multimap? Вместо опроса по позиции вы можете опрашивать по клавише в O (1), хотя с немного большими накладными расходами в зависимости от типа клавиши.

Основное преимущество заключается в том, что не нужно синхронизировать содержимое 2. Конечно, это не работает, если вы хотите отсортировать контент.

Таким образом, если вы хотите, чтобы контент сортировался плюс быстрый (не O (1)) доступ к произвольной позиции, вы можете рассмотреть B + Tree или Radix Tree. Их идея состоит в том, чтобы хранить предметы в смежных зонах памяти по несколько сотен за раз.

Это только макушка моей головы. Подумайте об автозаполненном ответе, если хотите запекать в растворе:)

Answer 4

Попробуйте hash_multimap. Хеши предлагают примерно постоянное время. Hash_multimap - это расширение в Visual Studio, и я вполне уверен, что GCC также предлагает аналогичное расширение. В Boost есть кое-что, если вы в отчаянии.