Структура данных типа очереди, позволяющая быстро определить позицию элемента. Есть?
Положим есть у меня большой список элементов (уникальных строк).
В него элементы могут добавляться в конец, перемещаться внутри этого списка (не обмениваться), и удаляться из начала.
Может знаете такую структуру данных, которая позволит мне быстро (без перебора всего списка) по элементу определить номер его позиции в таком списке, такая структура ДОЛЖНА позволять быстро перемещать элементы (с обсчетом измененых позиций других элементов).
Кол-во элементов порядка 5 млн.
Идеальный вариант когда:
Время добавления в хвост: O(1)
Время получения из головы: O(1)
Время определения позиции: O(1) или O(log n)
Время перемещения одного элемента из конца в начало: O(log n) или O(1)
Сергей , а что означает: "по элементу определить номер его позиции"?
Чтобы найти нужный инструмент, неплохо бы сперва представить себе его во всех красотах.
Какая цель перемещения элементов? А для чего нужно знание позиции? Всегда ли удаление происходит только из головы? Всегда ли добавление происходит в хвост?
Нужно ли выбранный элемент перемещать в сторону хвоста? Или перемещать нужно только в сторону головы?
Элементы в контейнере уникальны или имеются дубликаты? По ссылке ли хранятся элементы или по значению? Две разные инстанции элемента с одинаковым контентом будут разными или одинаковыми?
Пока на примете только бинарная куча и интрузивный лист. Но они оба могут не подойти тебе в зависимости от ответов на вопросы выше.
а что означает: "по элементу определить номер его позиции"?
Элемент - строка (ключ). Каждый элемент уникальен.
>Какая цель перемещения элементов?
Своего рода очередь с приоритетами, т.е. меняется приоритет элемента.
> А для чего нужно знание позиции?
В вебе обычно клиент заходит в админку и видит: Ваш "элемент" находится на № позиции, до начала обработки осталось "№ времени", заплатите "№ рублей" чтобы поднять "элемент".
> Всегда ли удаление происходит только из головы?
Да.
> Всегда ли добавление происходит в хвост?
Да. Но элемент может быть перещемен впоследствии в начало со сдвигом всех других элементов.
> Нужно ли выбранный элемент перемещать в сторону хвоста?
Скорее всего нет, в ТЗ не оговорено пока.
> Или перемещать нужно только в сторону головы?
Только в сторону головы.
> Элементы в контейнере уникальны или имеются дубликаты?
Уникальны.
> По ссылке ли хранятся элементы или по значению?
Уже не важно.
> Две разные инстанции элемента с одинаковым контентом будут разными или одинаковыми?
Одинаковыми. Элемент это всегда ключ-строка.
Сергей , почитай про бинарную кучу (Binary Heap / Priority Queue).
Это куча на линейном списке, всегда гарантирующая изъятие самого приоритетного элемента со своей вершины, вне зависимости от того, насколько давно элемент попал в нее.
В куче можно хранить не сам элемент, а интрузивную ячейку, в которой содержится как элемент, так и дополнительная информация для кучи. Любая информация, которую обновляет или использует сама куча.
Текущую позицию элемента в куче определить легко, как просто по его весу, пройдясь алгоритмом по куче, так и через интрузивную ячейку, которая может так же лежать в другом контейнере.
Я не оформляю рекомендацию как ответ т.к. не считаю что это тебе на 100% подойдет. Но этот примитив может помочь тебе думать в нужном направлении.
Из самого конца (последний элемент) в самое начало (сделать первым) - O(1), очевидно. Тупо сдвинуть указатели на начало и конец. А вот в общем случае, передвинуть и вставить "куда-то" - O(n), да, согласен.
Очередь, физически не перемещающая элементы (кольцевая или некое подобие std::deque) и позволяющая по указателю быстро определить позицию.
Плюс любой индекс (хэш- или деревянный), элементы которого — указатели на элементы очереди. Если элементы очереди unique_ptr, то указатели будут именно на unique_ptr! Для «мусорных» языков (C#, Java) вместо указателей можно придумать какие-то идентификационные коды — например, сочетание из номера в пуле массивов и номера в массиве.
Enqueue — вписываем элемент в индекс. Dequeue — удаляем из индекса. Обмен позициями — корректируем эти два элемента индекса.
Простой
Простой
Простой
