Порридж В Ко-ливинге
Надо только поверх его сделать
Порридж В Ко-ливинге
ЧТобы уникальные элементы были
Evgeniy
https://leetcode.com/problems/lru-cache/discuss/595264/C-O(1)-time-solution-using-Dictionary-and-LinkedList
Порридж В Ко-ливинге
Viktor
ЧТобы уникальные элементы были
Я не очень понимаю откуда это требование про уникальные элементы.
Порридж В Ко-ливинге
А если удалять элемент из list то это не const,
Порридж В Ко-ливинге
По времени
Порридж В Ко-ливинге
Надо будет map создавать, да?
Evgeniy
константа
Evgeniy
А, ну да
Evgeniy
Приходится делать хэш, чтобы сразу находить, а не идти по всему списку
Порридж В Ко-ливинге
Тогда как удалять элемент по адресу?
Evgeniy
У записей хэштаблицы значения это ссылки на узлы связного списка. И у записей есть ключ
Evgeniy
По ключу находишь ссылку и удаляешь
Порридж В Ко-ливинге
Ну тогда это надо будет next и prev перевызывать
Evgeniy
Просто RemoveLast и всё
Evgeniy
А на вершину листа перекинуть:
_list.Remove(node)
_list.AddFirst(node)
Порридж В Ко-ливинге
Есть только l.remove_if(
Порридж В Ко-ливинге
Ну и l.remove по value
Evgeniy
тип имею в виду, в плюсах
Порридж В Ко-ливинге
Щас тот попробую
Порридж В Ко-ливинге
Через l.remove_if
Порридж В Ко-ливинге
Он типо рабочий
Порридж В Ко-ливинге
Я еще в C писал свои списки
Evgeniy
Видимо снова особенности обработки сишного кода в плюсах
Порридж В Ко-ливинге
readers.remove_if([r=&r](auto& x){return &x==r;});
Порридж В Ко-ливинге
https://stackoverflow.com/questions/44525580/remove-element-from-stdlist-by-reference
Порридж В Ко-ливинге
После JS
Порридж В Ко-ливинге
Где о таких проблемах вообще не слышно
Порридж В Ко-ливинге
(но там уже другие проблемы...)
Порридж В Ко-ливинге
Просто этих C++ компиляторов
Порридж В Ко-ливинге
У винды свой, у мака свой, у линуксов
Порридж В Ко-ливинге
Странно, где-то пишут, что там конст у листа
Evgeniy
Может от стандарта зависит?
Порридж В Ко-ливинге
http://www.cplusplus.com/reference/list/list/erase/
Порридж В Ко-ливинге
Вот тут написано линеар
Порридж В Ко-ливинге
В C++ не меняют обычно
Порридж В Ко-ливинге
Только уточняют ранее не оговоренное
Порридж В Ко-ливинге
Фигня какая-то
Evgeniy
вот смотри
Evgeniy
с С++11 началось
Evgeniy
const
Порридж В Ко-ливинге
Он начал возвращать размер и все
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Не вижу
Порридж В Ко-ливинге
Порридж В Ко-ливинге
const только первый и посл эл
Evgeniy
Так это обычный лист
Evgeniy
Не связный
Evgeniy
Там же просто кусок памяти
Evgeniy
Стоп, нет
Evgeniy
двусвязный список это
Evgeniy
https://ru.cppreference.com/w/cpp/container/list
Evgeniy
вот это
Evgeniy
А std::list не связный
Порридж В Ко-ливинге
?
Порридж В Ко-ливинге
В общем ты запутался
Evgeniy
Не, ошибся
Порридж В Ко-ливинге
В общем лист — в теории не может удалять за const
Порридж В Ко-ливинге
Т.к. это лист
Evgeniy
Удалять да
Порридж В Ко-ливинге
Да и добавлять куда надо тоже
Порридж В Ко-ливинге
Поэтому надо сделать мапу с адрессами
Порридж В Ко-ливинге
Я сделаю мапу
Evgeniy
Да, именно
Порридж В Ко-ливинге
Надо будет в ручную снимать указатели next и prev
Порридж В Ко-ливинге
Потом надо будет еще в ручную обновлять size и first и last