Есть ли такая структура данных?

Батчить удаления,+ хранить в узлах информацию о минимальном и максимальном элементе например, это если ничего хитрого не искать. В мутабельном случае вариантов ещё больше

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

В мутабельном случае можно добавить индексирование для двоичного хипа на основе массивов как в базах данных. Для чистой структуры пока ничего не придумал)

А ты мог бы расписать подробнее чистый случай?

Но как они будут изменяться одновременно тогда?

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

Ближайшая аналогия таблица бд - она накрывается различными индексами, при это удаление строки из таблицы (в т.ч. по индексу) не требует ручного удаления записей из индексов.

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

у этой штуки может быть, что несколько значений с одинаковым ключом?(то есть аля multimap)

Так удаление же из priority_queue работает за logN, разве нет? Тогда худший случай не O(N), а O(NlogN) вроде как

я помню когда-то пытался такое решать. проблема в том, что тут пытаемся одно дерево по одному параметру, а другое по-другому. И получается каша-мала. Я когда-то так и не решил такое задание

Если это хип и хэш, то хэш обновляется дважды при каждом обмене элементов хипа. Тут сделали с индексами, но, если заменить массив на хэш, то должна получиться нужная структура (если считать стоимость обновление хэша за O(1), то асимптотическая сложность операций так и останется O(log n), хотя конечно возрастёт).

я что-то не совсем понял, как происходит удаление по значению

а если у меня несколько ключей с одинаковыми значениями? то какой элемент мне удалить? Все?

Посмотреть позицию элемента в хипе, используя хэш (хранить там отображение значений в индексы хипа). Удалить из хипа и из хэша.

для чистой я вижу следующее:

1. удалять не сразу, а как найдётся k элементов на удаление, тогда удаление k объектов будет n*log(k), вместо nk. Ассимптотика та же, но константу можно уменьшать

2. уменьшать $n$, например, храня информацию о том, какие элементы есть в ветке. Но тут неясно будет ли это хорошо ложиться на данные.

3. иметь 2 структуры значений и элементов. Когда достаёшь значение проверяешь не удалено ли оно, если удалено, то достаёшь следующее.

Во 1 и 3 надо внимательно следить за вариантом повторной вставки элемента.

В принципе в Haskell, вариант 3 можно изобразить храня в PSQ WeakRef от объектов хранимых в дереве значений, но тогда процедура доставания значения будет проще, но там есть свои проблемы.

Че то как то сложно...

КОнтейнер пар ключ-значение (например банальный список) не меняющий адреса элементов при модификации, дерево по ключам с пойнтерами на элементы контейнера и любой ассоциативный массив с пойнтерами на элементы контейнера не покатят?

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

ну так смотрите. У нас есть пары ключ-значение. То есть у нас может N ключей и у них одинаковое значение.Это будет худший случай. Пусть мы будем знать индекс в хипе. Но по любому удаление в хипе работает за logN, так как при каждом удалении происходит перебалансировка дерева. И получается, что пусть мы хотим удалить наше едиснтвенное значение. Значит мы должны удалить из дерева N ключей и N раз перебалансировать дерево. Итого O(NlogN)

понимаете, ТС же вроде хочет честно удаление, с освобождением памяти, а не установка знака валидности.

Пусть уж ТС определится чего он хочет - эффективности или экономии памяти;-)

Ладно, как вариант можно тупо держать контейнер пар в упорядоченном состоянии. Ну или завести контейнер указателей на пары и деражть его в упорядоченном состоянии, тогда дерево по ключам не нужно и перебалансировать ничего не нужно. Правда остается ассоциативный массив по значениям, удаление из которого тоже может лагать но тут уж можно взять классическую хэш таблицу. Двоичное дерево впрочем при случайном удалении тоже на перебалансировку меньше чем О(n) потребует.

Если делать совсем изящно, то что то вроде (сорри, я на плюсах сваяю):

struct Qcell{
   TKey key;
   std::map<TValue, std::list<Qcell>::iterator>::iterator v_ptr;
};

std::list<Qcell> queue;
std::map<TValue, std::list<Qcell>::iterator> values;

Дальше они ссылаются дург на друга, только надо глянуть не поедут ли итераторы при модификации контейнеров - я с std не оцень много работал, не помню.

Boost.Bimap подойдёт?

#include <boost/bimap.hpp>
#include <iostream>

int main() {
    boost::bimap<int, int> b;

    b.left.insert(std::pair<int, int>(2, 42));
    b.left.insert(std::pair<int, int>(3, 43));
    b.left.insert(std::pair<int, int>(1, 41));
    b.left.insert(std::pair<int, int>(4, 44));

    std::cout << b.left.begin()->first << std::endl;
    b.right.erase(41);
    std::cout << b.left.begin()->first << std::endl;
    b.right.erase(42);
    std::cout << b.left.begin()->first << std::endl;
    b.right.erase(43);
    std::cout << b.left.begin()->first << std::endl;
}

Эта структура должна позволять эффективно удалять заданный элемент по значению.

Сбалансированное дерево или хэш по значению.

Это должна быть очередь с приоритетами, так чтобы я мог эффективно извлечь элемент с минимальным ключом.

Сбалансированное дерево или хэш по ключу, в котором хранится значение.

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

очень интересно, спасибо. Ещё раз довод, что пора бы мне с бустом знакомиться.

А не подскажете насчёт асимптотик? а то офф. доки молчат и говорят, что раздел делается

да, от ТСа тоже хочу добиться более чёткого ТЗ.

А не подскажете насчёт асимптотик?

Понятия не имею, я о его существовании час назад узнал только.

Написано, что это обёртка вокруг Boost.MultiIndex. То есть можно ожидать чего-то похожего на std::set.

КОнтейнер пар ключ-значение (например банальный список) не меняющий адреса элементов при модификации, дерево по ключам с пойнтерами на элементы контейнера и любой ассоциативный массив с пойнтерами на элементы контейнера не покатят?

С эфимерной (мутабельном) структурой прокатило бы, если хранить информацию об удалении и её обновлять, но с персистентной вроде этот трюк не пройдёт, самый близкий к нему это WeakRef, но я не уверен, но там настоящие гарантии будут

Персистентность, кстати, ТС скорее всего действительно нужна, т.к. насколько я знаю задачу (очень обобщенно), то там эти структуры надо уметь эффективно форкать.

Но как они будут изменяться одновременно тогда?

Берешь 2 нужные структуры, суешь в них указатель на данные. Сами данные хранишь как тебе удобно. Например делаешь хэш/дерево для поиска по значению и очередь для поиска по приоритету. В объекте делаешь обратный указатель на элементы всех структур. Когда тебе надо добавить элемент, ты выделяешь память, суешь в дерево и в очередь указатель на объект, в объект суешь обратные указатели на элемент дерева и очереди. Когда нужно удалить объект, ищешь его в дереве, получаешь из него указатель на элемент в очереди, удаляешь элементы из дерева и очереди, удаляешь объект.

ну хз, он же нам ничего не говрил про то, что ему нужно знать историю изменения данных и получать доступ к какой-нибудь версии структуры быстро. И хранить это компактно. Вот ну ни единого намёка в ТЗ не было на персистентность:)

мне кажется, в Ваш план закралась неработоспособность. Со вставкой элемента всё ок, не спорю. Но ТС хочет запрос вида : удалить по значению какой-нибудь элемент. А если у нас ВСЕ ключи с одним и тем же элементом? Тогда удаление будет занимать NlogN времени. Тут нужно у ТСа уточнять ТЗ

а так да, Ваш способ рабочий

я даже предложу ещё улучшение : хип на фибоначчиевой кучи. что-то как-то сразу запамятовал про неё. но там константа огогого какая

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

Если хранить не пойнтеры/итераторы а номера ячеек в массиве, то и персистетность получится. Правда это означает де-факто свой менеджер памяти (точнее его подобие, очень легкий вариант) и ХЗ сколько доп.работы, но я что то подобное делал, правда для адаптивных сеток, там другие заморочки.

ФОркать fork-ом или ручками?

Эммм, я что-то не совсем понимаю, как получается персистентность, если будем хранить номера ячеек в массиве. Персистеностность это когда я у меня есть исходное дерево, и допустим я 2 раза удалил какие-то элементы и 1 раз что-то вставил. Тогда у меня будет 4 версии дерева : исходное, после удаления 1 элемента, после делета двух, после вставки.

Можно тупо это форкать за O(N), но это и времени(ну тут мемсетом можем поиграться иль ещё как-нибудь), да и памяти жрёт неимоверно просто. Поэтому мы должны как-то форкать только ветки, которые изменяются. Из персистентного я сам писал дерево отрезков - там это делается за счёт несложных игр с указателями на вершины форкнутых веток и указания корня текущего древа(стояла задача о нахождении К-той порядковой статистики на отрезке).

А как тут через сохранение индексов персистентность достигается? Что-то никак догнать не могу...

вообще, мне кажется, что то, то ему выше посоветовали boost/bimap и есть именно то, что доктор прописал

Два хипа с элементами (ключ, значение)? Первый хип упорядочен по ключу, второй по значению.

а как происходит синхронизация хипов?

не было, явно выделялось разделение между чистыми функциональными структурами и «императивными», для императивных вроде все достаточно очевидно, вот с функциональными уже сложнее и интереснее.

а как происходит синхронизация хипов?

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

пусть ТС чётко скажет, что ему надо. А усложнить себе задачу, чтобы при решении расширить себе сознание), так это мы всегда успеем.

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

как вариант, прикрутить фибоначчиевая куча + hash_map

математик-программист это даже страшнее чем философ.

я не дорос до матеметика, я это.. экс-физик наверное.

Йепрст, я через ваши термины с трудом продираюсь...

это по Окасаки, кстати не самая принятая терминология. Общее описание, искать книжку или аккуратно формулировать самому мне лень. Эфимерные структуры - структуры, в которых все модификации меняют структуру и возможности получить историю нет, если есть 2 «ссылки» на структуру, то изменение одной поменяет и другую. В противоположность этому персистентной структурой называют такую, в изменения, в которой не уничтожают предыдущие версии.

В общем если хочется дешевое клонирование структуры, и независимость при работе с такими структурами, то тогда «персистентный» подход может быть выгоден, хотя это практически всегда приводит к ухудшению асимптотик (ну или переходу от worst-case к амортизированным оценкам).

под форкать понимай, сделать версию структуры, что-то типа cow, плюс которая будет расшаривать часть вычислений (не знаю нужно и это), т.е. если ты

структуру данных с параметризованную ключем (с наличием порядка) и значением (допустимо предполагать наличие порядка). С операциями:

1. insert :: (Key, Value) -> () — вставить пару ключ-значение

2. pop :: (Key,Value) — получить значение с минимальным ключем

3. remove :: -> (Value) — удалить все элементы с заданным значением

Для операций 1,3 желательно быть O(lg(N)). Для операции 2 максимально быстрой (скорее всего O(1) или если никак, то O(lg(N))), где N это количество элементов в структуре.

Может ли в структуре одновременно находиться много значений с одним ключем - неизвестно.

Задача: (скорее всего, лучше дождаться ответа ТС) в системе моделирования событий хранить список следующих наступивших событий и долнительно возможность «отменять» события.

Эффективно в смысле, как минимум, со сложностью O(log n)

Тогда удаление будет занимать NlogN времени

Миссия выполнена.

А если у нас ВСЕ ключи с одним и тем же элементом?

Вангую, что ТС такой случай не рассматривает.

я отвечу кратко : это невозможно. Реализация пункта 3 просто невозможна при реализации первых двух. Вот вдогонку таблица : http://neerc.ifmo.ru/wiki/index.php?title=Поисковые_структуры_данных

Чтобы это решить, нужны какие-то оговорки. А по Вашему ТЗ нет, нельзя сделать то, что ТС хочет, к сожалению.

мне кажется, что ТС имел в виду удаление ВСЕХ элементов с заданным значением за logN, что невозможно.(если запросы у нас быстрые, то удалить всё мы и за N не можем).

А если это удаление только одного элемена за logN, то тогда mission completed уже давно :)

Какого типа ключ и какого типа сами даные для хранения? Обязательное условие на O(log n) или важна только скорость поиска? Обязательно ли условие для упорядоченивания ключей? Какое максимальное количество записей планируется? Десятки? Тысячи? Миллионы?

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

А так же, для какого процессора нужен код? какой у него размер кеша?

тут ТСа интересуют по идее асимптотические оптимизации, а не «под архитектуру» и экономия на спичках

из того, что я смог придумать. Если подойдет, то оптимальнее всего заюзать дерево Ван Эмде Боаса : быстро пашет, а удалять мы будем за N*w. Но это из разряда теории :)