При переносе диапазона между разными контейнерами std::list через splice откуда берётся линейная сложность?
При переносе диапазона между разными объектами std::list сами узлы можно переподключить за постоянное число операций со связями. Однако реализация обычно должна пройти по диапазону, чтобы определить его длину и корректно обновить размеры двух контейнеров, поэтому сложность составляет O(n), где n — число переносимых элементов.
Для переноса одного элемента или всего списка сложность обычно O(1). Для диапазона внутри того же объекта списка стандарт допускает константную сложность, поскольку общий размер контейнера не меняется.
std::list построен на двусвязных узлах, каждый из которых хранит элемент и ссылки на соседние узлы. Такой подход предназначен для операций вставки, удаления и перемещения элементов без сдвига большого непрерывного массива объектов.
Операция splice использует это свойство: она передаёт узлы между списками, не копируя и не перемещая сами значения элементов. Это решает задачу эффективной передачи уже существующих объектов между совместимыми списками.
Наивно можно ожидать, что любой перенос диапазона через splice имеет сложность O(1): достаточно изменить несколько ссылок на начало и конец диапазона. Но у контейнера есть ещё состояние, в частности количество элементов, и его нужно поддерживать согласованным.
Если диапазон переносится между разными списками, размер исходного списка уменьшается, а размер целевого увеличивается. Без подсчёта числа узлов реализация не сможет корректно обновить оба размера за константное время, если отдельно не хранит дополнительную информацию о длине каждого диапазона.
Для диапазона из n узлов операция выполняет две логические части:
Первая часть занимает O(1): не требуется перемещать объекты или копировать их значения. Вторая часть при переносе между разными списками требует прохода по диапазону и занимает O(n). Поэтому итоговая сложность определяется подсчётом элементов.
У операции есть важные ограничения. Перенос возможен только между списками совместимого типа и с совместимыми аллокаторами; несовместимые аллокаторы нарушают предусловия операции. Итераторы и ссылки на перенесённые элементы сохраняются, но после операции относятся к целевому списку.
Это отличается от вставки диапазона в std::vector: там элементы могут потребоваться скопировать или переместить, а существующие итераторы и ссылки могут стать недействительными из-за перераспределения памяти. При этом std::list платит за эффективный splice плохой локальностью данных, дополнительной памятью на узлы и более медленным последовательным обходом.
Пусть планировщик хранит готовые задачи в одном списке, а задачи, выбранные для отдельного рабочего потока, нужно передать в другой список. Возможны три варианта:
Если задачи уже находятся в std::list, их нужно именно передать, а аллокаторы совместимы, выбирают splice. Для диапазона между разными списками следует учитывать линейный подсчёт длины, но это всё равно избегает перемещения тяжёлых объектов. Если важнее скорость обхода и компактность памяти, чем стабильность узлов, лучше изначально рассмотреть std::vector или другой непрерывный контейнер.
Почему перенастройка ссылок не определяет всю сложность операции?
Перенастройка связей действительно выполняется за O(1): достаточно соединить соседей удаляемого диапазона и вставить диапазон между соседними узлами в целевом месте. Но при переносе между разными списками требуется узнать размер диапазона, чтобы обновить два счётчика элементов. Поэтому общая сложность становится O(n).
Становятся ли недействительными итераторы на перенесённые элементы?
Нет, сами узлы не уничтожаются и не создаются заново. Итераторы, указатели и ссылки на перенесённые элементы продолжают обозначать те же элементы, но теперь эти элементы принадлежат целевому списку. Итератор конца исходного списка остаётся связанным с исходным контейнером, а итератор конца целевого — с целевым.
Почему splice не является универсальной заменой vector::insert?
splice работает только с узловым контейнером std::list и переносит уже существующие узлы. Он не объединяет произвольные диапазоны значений из любого контейнера, не улучшает локальность памяти и может потребовать линейного прохода для поиска позиции или подсчёта длины диапазона. Поэтому его преимущество проявляется при передаче элементов между списками, а не как общий способ быстрой вставки данных.