list - SGIslistとC++11 forward_listの違いは何ですか？

Question

私が何かを見逃していない限り、 SGIslistとC++11はどちらも私と同じように見えます。std::forward_listどちらも単一リンクリストを実装しています。

C ++標準委員会は名前slistを採用せず、代わりにC ++ 0xの標準ライブラリにコンテナを追加したときに新しい名前forward_listを選択したため、違いがあると思います。

Answer 1

大きな違いの1つstd::forward_listは、size()メンバー関数がないことですが、そうではありsgi::slistません。この動機は、O（N）size()に問題があることです。 N2543には、の設計上の決定に関する詳細がありforward_listます。

アップデート：

私は最近、この主題を詳しく調べる良い言い訳をしました。 slistまた、O（1）と思われるかもしれませんが、実際にはO（N）である他のメンバー関数もあります。これらには以下が含まれます：

iterator previous(iterator pos);
const_iterator previous(const_iterator pos) const;
iterator insert(iterator pos, const value_type& x);
iterator erase(iterator pos);
void splice(iterator position, slist& x);
void splice(iterator position, slist& x, iterator i);

つまり、あまり注意しないと、を使用してパフォーマンスに重大な問題が発生する可能性がありますslist。代わりにを使用するstd::forward_listと、単一リンクリストから期待されるO（1）パフォーマンスを確実に得ることができます。

Answer 2

簡単に言えば、sgi::slistとforward_listは非常に似ています。

違いは、forward_listにはsgi :: slistに含まれているsize（）メンバー関数がなく、forward_listにはsgi::slistに含まれていないemplace_afterメンバー関数が含まれていることです。また、forward_listは、sgi::slistのようにメンバーの挿入および消去機能を提供しません。

他の違いをご存知の場合は、遠慮なくお知らせください。

Answer 3

私は最近、別の違いに遭遇しました。このメソッドsplice_afterには、異なるインターフェースと異なる動作があります。

1）forward_list移動元のコンテナを2番目の引数として渡す必要があります。

void splice_after( const_iterator pos, forward_list& other,
                   const_iterator first, const_iterator last );

slist：

void splice_after(iterator pos, iterator before_first, iterator before_last)

これはオーバーロードについても同様です。

2）上記の過負荷に固有：最後のイテレータの解釈は異なります！slistが範囲[before_first+1、before_last + 1>を移動する場合、forward_listは範囲<first、last>を移動します。したがって、コードを変換するとき（たとえば、slistはGCCで非推奨になっているため）、必ずlast = before_last+1を使用してください。