std :: list、イテレータのみを使ってリスト内のアイテムを移動する

Question

これは可能なはずのリンクリストについて知っているようですが、答えがある場所は見つけられませんでしたのでここで尋ねています。

同じリスト内の項目に対して2つのイテレータを指定します。イテレータ "frm"が指す項目を取り出し、イテレータ "to"が指す項目の前にリストに挿入したいと思います。

"frm"（ "frm"を削除する）を指すリスト内の項目のポインタを変更してから、 "to"を指す項目のポインタを変更するだけで、 "frm"を参照し、 "frm"ノード上のポインタを "to"を指すように変更する。

私はこれをどこでも見て、答えを見つけることができませんでした。

リスト内の項目のイテレータのみをリストにアクセスできないため、スプライスを使用できないことに注意してください。

template <typename T> 
void move(typename std::list<T>::iterator frm, typename std::list<T>::iterator to) { 
    //remove the item from the list at frm 

    //insert the item at frm before the item at to 
} 

Answer 1

イテレータは、データの一部を指し示すために必要な最小限の情報が含まれている、何が欠けていることは、リンクリストを事実は同様にそれと一緒に行く他の簿記を持っているので、基本的にlistクラスのようなものに見えるさ

template <typename Type> 
class list { 
    int size; // for O(1) size() 
    Type* head; 
    Type* tail; 

    class Iterator { 
     Type* element; 
     // no back pointer to list<Type>* 
    }; 
    ... 
}; 

リストから要素を削除するには、それらのデータ要素も更新する必要があります。そしてそれを行うためには、イテレータはリスト自体への後方ポインタを含んでいなければなりません。ほとんどのイテレータで提供されているインタフェースには必要ありません。また、STLのアルゴリズムは実際に操作するコンテナの簿記を修正するのではなく、要素を交換したり、並べ替えたりするだけです。

私はあなたを励ますは、イテレータが実際にそれが表すコンテナを修正するためにラップされている方法のアイデアを得るためだけでなく、std::back_inserterとstd::move_iteratorなどの施設に、<algorithm>ヘッダに見ました。

Answer 2

この実装は実装上定義されていますが、C++標準ではiter_swapを使用できますが、これは正確には行いません。これはリンクされたリストに保持されている値にポインタをスワップするために最適化されていますが、フルスワップを必要とせずにリスト内の項目を効果的に並べ替える方法を説明しました。

iter_swap() versus swap() -- what's the difference?