3

forward_list関数splice_after（参照用）、具体的には、指定されたリンクの関数＃3があります。listが単独でリンクされていることを考慮して、それを実装するにはどうすればよいでしょうか。

演習として、実装するときに、前にノードに到達するまで（に接続できるように）、また前にノードに到達するまで（現在のリストのノードをノードに接続できるように）、リストを繰り返す必要がfirstありましたfirst。前）。これは私にはひどく効率的ではないようで、反復なしでそれを行うためのより良い方法があるかどうか疑問に思っていましたか？lastlastlast

4

2 に答える 2

3

「[first、last）」ではなく「（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。

于 2012-01-08T02:50:32.377 に答える
2

（community-wiki、貢献してください）

 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
于 2012-01-08T03:17:50.400 に答える