Есть ли способ извлечь узел из std::list, аналогичный тому, что делает std::map::extract?

Для своей задачи я использую std::list<Key> для поддержания порядка элементов в импровизированном кэше LRU. Итак, одна из частых операций — извлечение элемента списка и его возвращение в начало списка.

Очевидно, это можно реализовать, используя сначала std::list::erase, а затем std::list::push_front. Однако мне не нравится идея иметь дело с перераспределением памяти, когда все, что я хочу сделать, это переместить узел списка в другую позицию.

Это именно то, что метод extract позволяет нам делать для std::map, std::set и т. д.: извлекать узел, изменять его и возвращать обратно без перераспределения вообще.

Есть ли разумное объяснение, почему std::list не имеет той же функциональности, и есть ли обходной путь для имитации этого с помощью существующего API класса?


c++ c++17 stl stdmap stdlist
person Semisonic    schedule 24.04.2020    source источник
comment
Я не вижу причин, почему бы не расширить эту идею еще больше и иметь интрузивные контейнеры , такие как boost intrusive list и boost intrusive map в STL, и сделать неинтрузивный построенный поверх навязчивого .   -  person Alex Guteniev    schedule 24.04.2020
comment
Этот ответ актуален. Вы можете сделать это с помощью одной команды list.splice(list.begin(), list, iter), где iter указывает на элемент, который вы хотите переместить в начало.   -  person Daniel Langr    schedule 24.04.2020
comment
Вы также можете проверить сгенерированную сборку, которая просто переназначает соответствующие указатели: godbolt.org/z/eNAxpC .   -  person Daniel Langr    schedule 24.04.2020
comment
@DanielLangr Это интересно. В моем быстром исследовании показалось, что вставка была из одного списка в другой. Однако имеет смысл, что он будет работать в том же списке.   -  person Blastfurnace    schedule 24.04.2020
comment
@DanielLangr, ссылка eel.is, которую вы предоставили ниже, показывает, что одна из перегрузок splice действительно запрещает сплайсинг из списка в себя, тот, который берет все содержимое исходного списка. Так что вы не правы лишь отчасти.   -  person Semisonic    schedule 24.04.2020
comment
@Semisonic Разве ваш второй комментарий не был адресован Blastfurnance, а не мне? Я не предоставил никакой ссылки на eel.is и ничего не сказал об одинаковых/разных списках.   -  person Daniel Langr    schedule 24.04.2020

Ответы (1)


arrow_upward
4
arrow_downward

Существует функция-член std::list::splice, которая может быть вам нужна. Он работает с внутренними указателями узлов списка. Я не вижу способа вставки из/в один и тот же список, но вы можете вставить временный (пустой) std::list, а затем вставить обратно в начало исходного списка.

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

person Blastfurnace    schedule 24.04.2020
comment
splice подойдет, спасибо! Хотя это кажется хакерским. До сих пор не понимаю, что заставило разработчиков Стандарта пропустить передачу extract std::list - person Semisonic; 24.04.2020
comment
Я не знаю. Это, вероятно, один из тех, кто подает предложение, если вы хотите, чтобы это было так. - person Blastfurnace; 24.04.2020
comment
Обратите внимание, что эта функция имеет линейную сложность. - person Ayxan Haqverdili; 24.04.2020
comment
@Ayxan Я думаю, что это постоянное время для соединения одного узла. - person Blastfurnace; 24.04.2020
comment
Интересно. Я, должно быть, смешал это с какой-то другой функцией. Спасибо за ссылку - person Ayxan Haqverdili; 24.04.2020
comment
@Blastfurnace Получение итератора занимает линейное время, если оно у вас еще не есть. - person LIU Qingyuan; 24.04.2020
comment
@LIUQingyuan, я все равно собирался хранить итераторы в объекте std::unordered_map вместе со значениями кеша. Таким образом, с точки зрения сложности это решение является оптимальным, даже если бы у std::list был метод extract. - person Semisonic; 24.04.2020
comment
@Semisonic Я предполагаю, что цель добавления extract заключалась в том, чтобы разрешить изменение (постоянных) ключей элементов в set или map. С list такой необходимости нет. Но я понимаю вашу мотивацию. - person Daniel Langr; 24.04.2020