std :: listの演算子[]がないのはなぜですか？

誰かがなぜstd :: listの演算子[]が実装されていないのか説明できますか？私はちょっと調べましたが、答えが見つかりませんでした。それは実装するのが難しくないでしょうか、何かが欠けていますか？std :: listの演算子[]がないのはなぜですか？

出典

2009-07-11 Gab Royer

インデックスで要素を取得するのは、リンクリストのO（n）操作で、これはstd::listです。だから、それが人々が積極的にそれを使用するように誘惑されるため、operator[]を提供することは詐欺的であろうと決定し、その後、次のようなコードを参照してくださいね：O（N^2）である

std::list<int> xs; 
for (int i = 0; i < xs.size(); ++i) { 
    int x = xs[i]; 
    ... 
}

- 非常に厄介なの。したがって、ISO C++標準では、vectorとdequeでは達成可能な償却された一定時間（23.1.1 [lib.sequence.reqmts]/12）でをサポートするすべてのSTLシーケンスを実行する必要があると述べていますが、listではありません。

あなたが実際にそういったことを必要とする場合のために、あなたはstd::advanceアルゴリズムを使用することができます

int iter = xs.begin(); 
std::advance(iter, i); 
int x = *iter;

出典

2009-07-11 02:02:27

基本的に、それは人々が間違いを犯さないように防ぐことですか？ –

+17

あなたが守ることができない約束をしないでください。 STLでは、演算子[]は任意の要素への効率的なアクセスを約束します。 – jalf

そしてC++の標準参照のためにPavelに感謝します！ –

実行者にとってはそれほど難しくありませんが、ほとんどの場合パフォーマンスがひどくなるため、実行時にはそれほど難しくありません。ユーザーに各リンクを強制的に渡すと、そこで起こっていることが「myList [102452]」より明らかになります。

出典

2009-07-11 01:59:23 florin

ビット演算子[]は、他のすべての場所で一定の時間演算です。 O（n）操作に同じ名前を付けると、一貫性がなく混乱することになります。 – dmckee

地図ではO（log n）ですが、あなたの意見が分かります。 –

マップでは明らかにポジションインデックスではありません。マップキーが整数の場合を除いて、ただしキー参照によるポジションアクセスが混乱している場合は、既に大きな問題があります;） –

を私は他に答えを見つけたと思うSO] [Extending std::list

」あなたのオペレータを投稿O（N）time "である - は、標準のstd :: list <>には含まれていません。 - マイケル Burr 12月14日17:29

それでも唯一の理由はありますか？

EDIT：それはパフォーマンスに関して厳密にはパフォーマンスの点で一貫性の問題ですが、

出典

2009-07-11 02:03:05

あなたはその理由が十分ではないという意味ですか？ :-) –

です。他の場所を見ると、.NETの 'LinkedList'はほとんど同じ理由でインデクサーを提供しません。それはあまりにも欺瞞的です。伝統的に、何かに位置インデクサがあるとき、操作はO（1）であると仮定されます。 –

は実際に、オペレータ[]または（INT）で少なくとも方法を提供しないする理由は2つの理由で、絶対にありません：

それは、二重リンクリストであるので、あなたはで移動する必要がありますほとんどのサイズ（）/ 2はイテレータをインデックスに追加しますが、内部的には固定イテレータを保持するコストは非常に低くなります。そして最後に、Qtライブラリは演算子[]とatを提供していますが、それを使ったパフォーマンスのコストはわかりません。
あなたがリンクされたアクセスの近くに "ランダムアクセス"を持っている場合は、リストが多くの使用可能なコンテナになるので、人に何かを使わないように強制するのは非常に悪いプログラミング習慣です。どのランタイムポイント。

出典

2013-02-25 16:57:14 Dusan

これは純粋にあなたの意見に基づいているのでしょうか、あるいは、あなたは 'std :: list :: operator []'のカスタム実装が効率的であることを示す良いテストシナリオを作成しましたか？（BTW、標準的なコンテナであるStroustrupによると 'std :: vector'が使われます）。 – Zeta

std :: listの演算子[]がないのはなぜですか？

答えて

関連する問題