самый быстрый способ получить все уникальные отображаемые значения в std::map

У меня есть такая карта:

std::map<time_t, int>

Существует одно значение (int) в день (time_t). Некоторые дни могут иметь одинаковое значение и, следовательно, не могут быть уникальными. Мне нужно выполнить расчет для каждого уникального значения int из этой карты.

Каков самый быстрый (с наименьшим использованием ЦП) способ их получения?


c++ performance stdmap
person d-_-b    schedule 21.02.2012    source источник
comment
Вы можете изменить std::map на другую структуру данных?   -  person Luchian Grigore    schedule 21.02.2012
comment
@LuchianGrigore, конечно, почему бы и нет. Пока я не теряю данные.   -  person d-_-b    schedule 21.02.2012
comment
Ответ на самый быстрый будет отличаться в зависимости (среди прочего) от того, сколько раз вам нужно получить уникальные целые числа для каждой модификации основного map. Если это число велико, вам следует поддерживать коллекцию значений (либо отдельный multiset, либо отдельный map<int, size_t> для подсчета, либо использование Boost.MultiIndex, и в каждом случае набор/карта может быть упорядочена или неупорядочена). Если число достаточно мало, то будет быстрее избежать накладных расходов при каждой модификации карты и просто копировать значения в новый набор или unordered_set каждый раз, когда они вам понадобятся.   -  person Steve Jessop    schedule 21.02.2012
comment
@SteveJessop, спасибо за советы по производительности. Количество пар относительно невелико ‹ 1000. Так что думаю с набивкой их в комплект.   -  person d-_-b    schedule 21.02.2012

Ответы (1)


arrow_upward
3
arrow_downward

У вас есть ограничения по памяти? Если нет, я бы сохранил std::set (или любой другой hash_set, доступный в вашей среде), в котором перечислены уникальные целые числа.

Если вы абсолютно не можете выделить больше памяти, возможно, вам следует в первую очередь рассмотреть возможность использования другой структуры данных.

person Guy Adini    schedule 21.02.2012
comment
Скажем, память не проблема. Как я буду следить за днями? - person d-_-b; 21.02.2012
comment
Сохраните исходную структуру данных и дополнительную. Есть два варианта для второй структуры данных: (a) сохранить std::set‹int›, который просто перечисляет, какие значения уникальных целых чисел (если это все, что вам нужно). (b) сохранить std::map‹int, list‹time_t›, перечисляющий все дни, в которые появлялось данное значение. - person Guy Adini; 21.02.2012
comment
И всякий раз, когда вы вставляете в исходную карту, также вставляйте в поддерживающую структуру данных. - person Guy Adini; 21.02.2012
comment
Если вы сохраняете set значений, то что вы делаете с ним, когда удаляете элемент из исходного map? - person Steve Jessop; 21.02.2012
comment
Если это когда-либо произойдет, вы должны придерживаться варианта 2 (сохранить двунаправленную карту - чтобы у вас был список/набор дней, сопоставленных для каждого значения, и удалить из него, полностью удалив значение, если все дни, в которые оно появилось, удалены ). - person Guy Adini; 21.02.2012
comment
Вместо двунаправленной карты обратная структура может просто отображать от значения до количества раз, которое оно появляется в прямой карте. Когда счетчик уменьшится до нуля, значение можно будет удалить. - person Toby Speight; 07.06.2019