Splice_after реализация forward_list

Question

В forward_list есть функция splice_after ( для справки), в частности, функция № 3 в данной ссылке. Как можно было бы реализовать это, учитывая list однократно связан.

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

Answer 1

Я подозреваю, что вы неправильно прочитали несколько тонкую спецификацию диапазона, в которой говорится, что "(первый, последний)" перемещен, а не "[первый, последний)" (обратите внимание на открывающую скобку / скобку). То есть, как видно из названия, операция сращивания начинается только после первого объекта.

Реализация функции на самом деле довольно проста (если вы игнорируете постоянство итераторов и тот факт, что может потребоваться иметь дело с другими распределителями):

void splice_after(const_iterator pos, forward_list& other,
                  const_iterator first, const_iterator last) {
    node* f = first._Node->_Next;
    node* p = f;
    while (p->_Next != last._Node) { // last is not included: find its predecessor
        p = p->_Next;
    }
    first._Node->Next = last._Node;  // remove nodes from this
    p->_Next = pos._Node->_Next;     // hook the tail of the other list onto last
    pos._Node->_Next = f;            // hook the spliced elements onto pos
}

Эта операция имеет линейную сложность, потому что она должна найти предшественника last,

Answer 2

(сообщество-вики, пожалуйста, внесите свой вклад)

 A -> B -> C -> D -> E
           ^
           ^ pos points to C

в other список

 U -> V -> W -> X -> Y -> Z
      ^              ^
      ^ first        ^ last

Вызов .splice(pos, other, first, last)

Мы должны переместить W и X в верхний список. то есть все между, но не включая, first а также last, В итоге A->B->C->W->X->D->E наверху и U->V->Y->Z внизу.

auto copy_of_first_next = first->next;
first->next = last;
// the `other` list has now been emptied

auto copy_of_pos_next = pos->next;
pos -> next = first;
while(first->next != last) ++first;
// `first` now points just before `last`
first->next = copy_of_pos_next