|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.01.2018, 17:42 | #1 |
Новичок
Джуниор
Регистрация: 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) надо будет гонять итератор вхолостую много тактов, пока доберёмся до нужного индекса. Есть у кого опыт решения подобных задач? |
09.01.2018, 17:48 | #2 | |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,760
|
Цитата:
|
|
09.01.2018, 18:46 | #3 | |
Старожил
Регистрация: 16.12.2011
Сообщений: 2,329
|
Цитата:
при удалении - свап с последним. и удаление последнего. при добавлении - всегда добавлять в конец. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Контейнер 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 |