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

Question

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

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

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

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

Answer 1

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

На рассмотрении, сращивание разрешено в том же списке. Не определено, чтобы склеить весь список для себя. Сочетание одного элемента в одном и том же списке - это нормально, а слияние диапазона элементов - это нормально, если позиция назначения не включена в диапазон сращивания. (Спасибо, Даниэль Лангр)