Сложность контейнеров std:: list:: сращивания и других списков

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

list<string> list1, list2;

list1.push_back("a");
list1.push_back("b");
list1.push_back("c"); // list1: "a", "b", "c"

list<string>::iterator iterator1 = list1.begin();
iterator1++: // points to "b"

list2.push_back("x");
list2.push_back("y");
list2.push_back("z"); // list2: "x", "y", "z"

list<string>::iterator iterator2 = list2.begin();
iterator2++; // points to "y"

list1.splice(iterator1, list2, iterator2, list2.end());

// list1: "a", "y", "z", "b", "c"
// list2: "x"

У меня вопрос о сложности функции сращивания. Согласно этому источнику:

http://www.cplusplus.com/reference/stl/list/splice/

Он должен иметь линейную сложность в диапазоне между первым и последним элементами, сплайсированными в (итератор2 и list2.end() в моем примере), и источник предполагает, что это из-за продвижения итератора. Я могу жить с этим, но я надеялся на постоянную сложность.

Мое предположение (до того, как я нашел этот источник) состояло в том, что функция сращивания делает что-то вроде этого:

Разделите ссылку между "x" и "y"
Разделите ссылку между "z" и list2.end()
Создайте связь между "x" и list2.end()
Разделите ссылку между "a" и "b"
Создайте связь между "a" и "y"
Создайте связь между "y" и "b"

Таким образом, восстановление обоих списков завершается целями.

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

Итак, мой вопрос: как спецификация С++ справляется с этим? Разрывает ли он и повторно формирует ссылки только в начальной и конечной точках сращивания или продвигается по каждой ссылке один за другим? Если последнее, какие-либо другие контейнеры списка (например, из QT) предоставляют первое? Мой код находится внутри внутреннего цикла программы моделирования, поэтому предоставление ему постоянной, а не линейной сложности было бы весьма ценным.

Ответ 1

Это была очень спорная тема во время стандартизации С++ 11. Проблема в том, что все стандартные контейнеры, включая списки, также имеют операцию size с постоянным временем.

До С++ 11 во многих реализациях выполнялось size линейное время и splice между разными постоянными временными списками. С++ 11 теперь требует, чтобы size был постоянным, а splice - линейным.

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

Нестандартный контейнер list может предоставить требуемую операцию, потому что, пока вам не нужен O (1) size, ваш аргумент правильный.

Что касается других библиотек... Я не знаю об этом, но Boost должен иметь его. (Я проверил, это не так, поэтому кто-то начнет работать!) Поскольку вы четко понимаете, как писать свои собственные, это может быть меньше усилий, чем борьба с такой большой библиотекой, как Qt.

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