Альтернатива векторам для больших наборов данных? C++

Question

Я ищу структуру данных, которая хранит данные, чтобы их вставленные (как вектор), которые должны содержать миллионы беззнаковых длин. Ключ в том, что он должен иметь поиск, который лучше, чем O (logn), потому что он будет искать по сравнению с аналогичным вектором того же размера. Есть ли что-то такое?

Если я вставляю 10, 20, 30 и затем перебираю множество, мне нужно гарантировать порядок 10, 20, 30. Мои данные - это строка, которую я преобразовал в unsigned long, чтобы уменьшить использование памяти, то есть обратный декодируемый.

EDIT: Поскольку люди спрашивают, я сравниваю два вектора друг с другом (оба очень большие по размеру), чтобы получить разницу.

Небольшой пример:

vector 1: 10 20 30 40 50 60 

vector 2: 11 24 30 40 55 70 90 

result: 30 40 

Answer 1

Хэш карта является одним из способов вы будете иметь более быстрый поиск, чем отсортированный вектор. Для его использования требуется поддержка C++ 11.
http://www.cplusplus.com/reference/unordered_map/unordered_map/
Чтобы сохранить порядок данных единственным способом будет поддерживать вектор рядом с ним, что хранится ИНТ, как хорошо
Прежде чем перейти к его использованию вы должны рассмотреть, как вы собираетесь использовать эту структуру данных (шаблон доступа). Также рассмотрите, какие данные вы будете получать, вероятно, будут.
Вот версия о поднимать торг то же самое http://www.boost.org/doc/libs/1_53_0/doc/html/unordered.html

Answer 2

Я думаю, что вы должны использовать это unordered_map в сочетании с возможно дважды связанный список для заказа.

Итак, каждый раз, когда вы добавляете новый элемент в свою базу данных, вы добавляете его сначала к фронту (или к концу) связанного списка, а затем добавляете его в хэш-карту, где ключ является значением (unsigned int) и «значение» (из пары ключ/значение) является указателем на объект в связанном списке. Итак, если вы хотите быстрый поиск, вы смотрите в хэш-карту, и если вы хотите выполнить итерацию по порядку, вы используете связанный список. Конечно, если вы хотите удалить объект, вы должны удалить их из обоих, но сложность мудрая одинакова (O (1) амортизируется для всего).

Это, конечно, увеличит вашу память на 2 или 3 по сравнению с использованием только хэш-карты.

Answer 3

Я никогда не использовал его сам, и он может быть устаревшим по сравнению с последними версиями C++ (последнее обновление с 2011 года), но STXXL предназначено для набора контейнеров и алгоритмов, построенных для очень большого количества данные. Он может соответствовать вашим потребностям.

Ядро STXXL является реализацией С ++ стандартного шаблона библиотеки STL для внешней памяти (вне ядра) вычислений, я. e., STXXL реализует контейнеры и алгоритмы, которые могут обрабатывать огромные тома данных, которые подходят только для дисков. В то время как близость к STL поддерживает простоту использования и совместимость с существующими приложениями, еще один приоритет разработки - высокая производительность.

Ключевые особенности STXXL являются:

• Прозрачная поддержка параллельных дисков. Библиотека обеспечивает реализацию основных алгоритмов параллельного диска.STXXL - единственная библиотека алгоритмов внешней памяти , поддерживающая параллельные диски.
• Библиотека способна обрабатывать проблемы очень большого размера (проверено до десятков терабайт).
• Улучшенное использование компьютерных ресурсов. В реализациях STXXL алгоритмов внешней памяти и структур данных выигрывает от перекрытия ввода-вывода и вычислений.
• Небольшие постоянные факторы в объеме ввода/вывода. Уникальная функция библиотеки, называемая «конвейерная обработка», может сэкономить более половины количества входов/выходов, на потоковых данных между алгоритмическими компонентами, а не временно , сохраняя их на диске. В ветке разработки поддерживается асинхронное выполнение алгоритмических компонентов, что позволяет выполнить задачу высокого уровня .
• Сокращение времени разработки благодаря известным STL-совместимым интерфейсам для алгоритмов внешней памяти и структур данных.
• Алгоритмы STL могут быть непосредственно применены к контейнерам STXXL; кроме того, сложность ввода-вывода алгоритмов остается оптимальной в большинстве случаев .

Для внутреннего вычисления, параллельные алгоритмы от MCSTL или libstdC++ параллельного режима необязательно используются, что делает алгоритмы по своей сути выгоду от многоядерного параллелизма.