Блог

Главная - Вопросы по программированию - Разделить вектор на блоки с постоянной памятью

Разделить вектор на блоки с постоянной памятью

#c #c 11 #vector

#c #c 11 #вектор

Вопрос:

предположим, вам нужно работать с большим количеством элементов (более 1 миллиарда), которые хранятся в vector, и в какой-то момент вы хотели бы взять все эти элементы и разделить их на группы. Чтобы быть конкретным, мы хотели бы сделать следующее:

 std::vector<std::vector<int>> groups(100, std::vector<int>);
for (size_t i = 0; i < 1000000000;   i) {
    groups[i % 100].push_back(big_vector.push_back(i));
}
big_vector.resize(0);
big_vector.shrink_to_fit();

Однако, поскольку big_vector он действительно массивный, довольно неудобно дублировать наши данные в памяти. Однако этого, вероятно, нельзя избежать из-за непрерывного выделения памяти векторами и невозможности изменять размер без копирования всех данных (поправьте меня, если я ошибаюсь).

Тогда возникает вопрос, какую другую структуру использовать для хранения наших больших данных? Я подумал о написании пользовательского контейнера, в котором будут храниться данные внутри std::vector<std::array<SIZE>> , где SIZE достаточно большой, чтобы не иметь слишком много кусков, но не настолько большой, чтобы вызвать проблемы с дублированием накладных расходов на память. Есть ли более стандартный (boost-ish) способ сделать это, или лучше всего написать пользовательский контейнер?

Для дальнейшего уточнения моих ожиданий от контейнера — было бы неплохо, если бы у него был интерфейс, похожий на vector (быстрый произвольный доступ и т.д.). Однако при необходимости я, вероятно, мог бы обойтись без произвольного доступа и только возможностью нажимать и читать вещи. В любом случае это должно быть очень быстро.

Комментарии:

1. » Однако, если необходимо, я бы, вероятно, мог обойтись без произвольного доступа и только возможностью нажимать и читать вещи». Как насчет std::unordered_set<> / std::unordered_multiset<> ? В C 17 они получают extract и merge функции-члены, которые делают то, что вы хотите.

2. Функция, которую вы используете для разделения элементов на группы f:i->(i0) , т.е. с заданным индексом i она перейдет в группу i0 . Итак, вам действительно нужны группы. Вы можете найти группу по запросу. Также vector::push_back() не возвращает никакого значения, так что это неверно groups[i % 100].push_back(big_vector.push_back(i));

3. ах, я должен был быть более конкретным об этом. I в реальном коде они разделены на группы по более сложным правилам, и необходимо, чтобы они были разделены векторами. По теме std::unordered_set — не приведет ли это к большим затратам памяти? Я не очень хорошо знаком с реализацией неупорядоченных множеств.

4. std::unordered_xxx<> основаны на узлах, что имеет накладные расходы; но это также то, что позволяет им передавать элементы без их дублирования. Вам решать, стоит ли идти на компромиссы.

5. Итак, разве у вас нет больших данных, уже отсортированных по группам? Или просто выполнить сортировку (big_data, group_comparator)? Это будет стоить (n * logn) времени, но только дополнительной памяти logn (с большинством std::sort реализаций?).