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

Question

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

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/

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

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

1. Sever связь между «х» и «у»
2. Sever связь между «г» и list2.end()
3. Форма связь между «х» и list2.end()
4. Север связь между «а» и «б»
5. Форма связь между «а» и «у»
6. Форма связи между «y» и «b»

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

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

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

Answer 1

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

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

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

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

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

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