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

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

list list1, list2;

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

list::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::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. Разорвать связь между "x" и "y"
  2. Разорвать связь между "z" и list2.end()
  3. Сформировать связь между "x" и list2.end()
  4. Разорвать связь между "a" и "b"
  5. Сформировать связь между "a" и "y"
  6. Сформировать a связь между "y" и "b"

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

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

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

25
задан JBentley 13 April 2012 в 03:26
поделиться