Стек с возможностью поиска

Question

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

Элементы маленькие (указатели), и моя главная задача - эффективность памяти, поэтому использование двух дополнительных структур данных (одна для поддержания порядка и одна для поиска) определенно не идеальна.

Answer 1

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

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

Answer 2

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

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