Splice_after реализация forward_list - PullRequest
Новая
       33

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

3 голосов
/ 08 января 2012

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

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

Ответы [ 2 ]

3 голосов
/ 08 января 2012

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

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

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.

2 голосов
/ 08 января 2012

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

 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
...