сортированный по значению map

Хранить еще один контейнер для быстрого поиска минимального «значения».

можно пояснить? не понял

Посмотри как Boost.Multi_index устроен.

Идея простая - хранить несколько вариантов индексов через указатели на объекты. В твоем случае, наверное будет верно хранить еще кучу (heap) указателей, где минимальное значение всегда наверху будет.

Например, завести еще multimap где в роли ключа выступает «значение» из предыдущего map.

В соответствие с алгоритмом, значения некоторых пар итеративно меняются. Кроме того, каждую итерацию надо выбирать пару (1 или несколько) по минимальному значению «значения» (прошу прощения за тавтологию). Язык реализации C++

тебе бинарное дерево нужно над списком ИМХО.

Т.е. в списке будут «значения»(в порядке увеличения), а в дереве указатели _перед_ «значением» и ключ.

Тогда вставка/удаление/поиск будет O(ln(n)).

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

Декартово дерево?

да, забыл добавить, что диапозон значений и ключа и значений ограничен одним и тем же N (не больше 100000).

O(ln(n)) - плохо, очень медленно. как и multimap по значению.

Для поиска по ключ-значение быстрее всего (О(1)) будет unordered_map. Но для быстрого поиска значение-ключ нужен еще один контейнер. Т.к. тебе нужно только минимальные значения, то отсортированный список или multimap справятся с этим за О(1).

update: забыл добавить, что диапозон значений и ключа и значений ограничен одним и тем же N (не больше 100000).

— ключ и значение в структуру;
— N таких структур в векторе/массиве, индекс вектора совпадает с ключом;
— еще один вектор из N элементов, где каждый элемент — это счетчик количества «значений», совпадающих с индексом элемента;

выбор минимального «значения» — это поиск первого ненулевого элемента в последнем векторе

1. вектор на 100000 элементов индекс это значение.

в каждом элементе вектора это список ключей.

над вектором дерево-фенвика для быстрого переноса ключей из ставшего пустого списка в пустой до переноса элемент.

Ну для начала очевидная замена map на unordered_map для более быстрого выбора по ключу. С учётом ограничения на N, вообще на вектор значений, позиция в векторе - ключ.

Для быстрого выбора минимального значения - обратный map (я не понял насчёт ограничений неуникальности значений - если одинаковых значений может быть сколько угодно то multi_map значение -> ключ, если только одна пара, то map значение -> std::pair<ключ, ключ>)

O(ln(n)) - плохо, очень медленно.

быстрее не бывает, если требуется

1. вставка

2. доступ по произвольному ключу

3. упорядоченность

массив не даст п1, список не даст п2, хеш не даст п3.

как и multimap по значению.

это и есть дерево, пруфлинк: http://www.cplusplus.com/reference/map/multimap/

Для поиска по ключ-значение быстрее всего (О(1)) будет unordered_map. Но для быстрого поиска значение-ключ нужен еще один контейнер. Т.к. тебе нужно только минимальные значения, то отсортированный список или multimap справятся с этим за О(1).

что-то я не понял, как это реализовать?

А что непонятно? Завести два контейнера, в одном быстро ищется значение по ключу. В другом контейнере элементы отсортированны по значению из первого контейнера, поэтому быстро находятся минимальные элементы. Собственно, все сейчас это и предлагают.

непонятно, как ты в multimap будешь вставлять за O(1)?

Да, со вставкой будет косяк(

Стандартный map для pair ключ-значение - очень медленно

Очень это сколько? Выкатывай бенч.

Даже вектор чисел и стандартный std::min каждый раз и то быстрее.

Быстрее это сколько? Вменяемо реализованный линейный поиск в твоём случае это 100к+рпс на любом говне на ведро, если ты не засрёшь кеш. Засрёшь - из рамы ~50к на «камень».

Тем более линейный поиск, в отличии от всего остального может искать хоть сколько значений сразу. Надо тебе за итерацию искать 20 - будет 2кк+рпс.

Кроме того, каждую итерацию надо выбирать пару (1 или несколько) по минимальному значению «значения» (прошу прощения за тавтологию).

Если выбирать это не «удалять», то вперёд - кеш из сколько там тебе надо елементов и на каждом апдейте значения апдейть кеш.

Какое решение посоветуете?

Понимаешь у всех разное представление о «быстроте». Опиши внятно задачу, напиши бенч и сравни, в чем проблема? Я даже за тебя напишу.

Толку от твоих абстрактных быстро/медленно? Тут у пацанов стловские говнокеши O(1), а у брёвен логарифмы. Хотя скорее всего у тебя так же. Я сомневаюсь, что тебе тут что-то «подскажут». Я уж не говорю о какой-то быстроте.

Ца-а-а-рь вернулся! 😊

Стандартный map для pair ключ-значение - очень медленно (видимо, за счет частых обращений и модификаций перед поиском минимума). Даже вектор чисел и стандартный std::min каждый раз и то быстрее.

Что-то не верится. Только если у тебя количество элементов всегда маленькое.

А сколько пар в мапе ? Если порядка 10000 - то я бы сделал хеш на 100000 элементов (каждый элемент хеша либо NULL либо list/set/vector ключуй у которых значение равно этому индексу).

Если же пар не много и не хочется делать перерасход памяти то как уже писали очень подайдет куча (min-heap) https://ru.wikipedia.org/wiki/Двоичная_куча

см http://www.youtube.com/watch?v=aIHAEYyoTUc#t=1545

так ша vector vector vector