Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

Есть очень большое количество объектов (сотни тысяч, оперируем указателями на них). И две ключевых особенности:
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, 18:48   #2
p51x
Профессионал
 
Регистрация: 15.02.2010
Сообщений: 11,085
Репутация: 1862

icq: 216409213
По умолчанию

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

Цитата:
Сообщение от 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 вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


16:11.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru