Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.01.2018, 17:42   #1
ArtHome
Новичок
Джуниор
 
Регистрация: 20.10.2014
Сообщений: 1
По умолчанию Посоветуйте оптимальный контейнер

Есть очень большое количество объектов (сотни тысяч, оперируем указателями на них). И две ключевых особенности:
A1. Количество объектов постоянно меняется - удаляются существующие, добавляются новые. Список неупорядочен, без разницы куда добавлять новые.
A2. Надо делать их обход в случайном порядке.

Мои рассуждения.
Б1. Удаление/добавление быстро будет работать в std::list, но непонятно, как организовать случайный доступ.
Б2. Проблем с произвольным доступом нет у std::vector, но удаление элементов очень дорого.
Б3. Может быть будет эффективно завести рядом std::forward_list, в который помещать индексы освободившихся элементов из std::vector?

Отдельный вопрос - как организовать перебор в случайном порядке.
В1. Вариант с std::random_shuffle() дал бы самое качественное решение - случайный порядок и гарантированный перебор каждого элемента, но на мой взгляд не годится, так как количество элементов очень велико.
В2. В качестве компромисса можно выбирать случайно индекс элемента и повторять эту операцию многократно (недостаток - некоторые элементы поучаствуют несколько раз, некоторые ни разу, но на длительном интервале всё станет равномерно).

Для варианта перебора В2 для вектора (Б2, Б3) легко генерить случайный индекс и получать доступ к элементу. Для списка (Б1) надо будет гонять итератор вхолостую много тактов, пока доберёмся до нужного индекса.

Есть у кого опыт решения подобных задач?
ArtHome вне форума Ответить с цитированием
Старый 09.01.2018, 17:48   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Цитата:
Б2. Проблем с произвольным доступом нет у std::vector, но удаление элементов очень дорого.
Есть небольшой трюк: если порядок не важен, то свопаете удаляемый с последним и удаляете.
p51x вне форума Ответить с цитированием
Старый 09.01.2018, 18:46   #3
_Bers
Старожил
 
Регистрация: 16.12.2011
Сообщений: 2,329
По умолчанию

Цитата:
Сообщение от ArtHome Посмотреть сообщение
Есть очень большое количество объектов (сотни тысяч, оперируем указателями на них). И две ключевых особенности:
A1. Количество объектов постоянно меняется - удаляются существующие, добавляются новые. Список неупорядочен, без разницы куда добавлять новые.
A2. Надо делать их обход в случайном порядке.

Мои рассуждения.
Б1. Удаление/добавление быстро будет работать в std::list, но непонятно, как организовать случайный доступ.
Б2. Проблем с произвольным доступом нет у std::vector, но удаление элементов очень дорого.
Б3. Может быть будет эффективно завести рядом std::forward_list, в который помещать индексы освободившихся элементов из std::vector?

Отдельный вопрос - как организовать перебор в случайном порядке.
В1. Вариант с std::random_shuffle() дал бы самое качественное решение - случайный порядок и гарантированный перебор каждого элемента, но на мой взгляд не годится, так как количество элементов очень велико.
В2. В качестве компромисса можно выбирать случайно индекс элемента и повторять эту операцию многократно (недостаток - некоторые элементы поучаствуют несколько раз, некоторые ни разу, но на длительном интервале всё станет равномерно).

Для варианта перебора В2 для вектора (Б2, Б3) легко генерить случайный индекс и получать доступ к элементу. Для списка (Б1) надо будет гонять итератор вхолостую много тактов, пока доберёмся до нужного индекса.

Есть у кого опыт решения подобных задач?
std::vector.
при удалении - свап с последним. и удаление последнего.
при добавлении - всегда добавлять в конец.
_Bers вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Контейнер STL Noob(c++) Общие вопросы C/C++ 9 25.06.2012 14:11
Посоветуйте ноутбук оптимальный по цене,качеству ALKOrobot Компьютерное железо 10 25.05.2011 17:19
Посоветуйте литературу для начинающего. И вообще что-нибудь толковое посоветуйте ))) Гаур-Мяур SQL, базы данных 5 24.12.2009 00:37
Контейнер ! curtcobain Общие вопросы Delphi 3 04.02.2009 20:27