中段のstd :: listにアクセス

Question

私にはダミー質問があります。私はいつもC++ std::listコンテナの最初と最後と中央に要素を挿入するための一定の時間があることをお読みください： std::listの真ん中に要素を直接挿入する正しい方法はどれですか？ これは多分でしょうか？私たちは「途中で挿入する」と言うとき

std::list<int> l; 
    l.push_back(10); 
    l.push_back(20); 
    l.push_back(30); 
    l.push_back(40); 
    l.push_back(50); 
    l.push_back(60); 
    l.insert(l.end()- l.begin() /2); //? is this 
    // inserting directly in the middle? 

私たちは本当に私たちは（間にリンクされているすべての要素を1つずつを横断する）所望の点に、リストの先頭から行くには線形時間を節約することを意味するのですか？

Answer 1

ここで、「中間」とは、すでにその点を参照しているイテレータを持っていれば、リスト内の任意の点を意味します。それで、挿入は、挿入ポイントの周りのいくつかのポインタを変更するだけの問題です。

挿入ポイントのイテレータをまだ持っていない場合は、開始点や終了点のような単純なものではないため、リストを歩き回って見つけることができます。

Answer 2

あなたは一般的にこのようなイテレータ数学行うことができます。

std::list<int>::iterator it = l.begin(); 
std::advance(it, std::distance(l.begin(), l.end())/2); 
l.insert(it, value); 

を。これは、（OutputIteratorまたはInputIteratorを除く）任意のイテレータ型のために動作します

もちろんそれは

を言うために、より効率的 方法です

std::advance(it, l.size()/2); 
l.insert(it, value); 

残念ながら、リストイテレータはランダムアクセスではないため、l.insert(l.begin + (l.size()/2), value)は機能しません。パフォーマンスの驚きを防ぐために、operator+が定義されていません。 std::advance()は、イテレータのタイプによってはの高価なオペレーションになる可能性があることを覚えておいてください（例：逆方向イテレータの場合は前方転送のみのコンテナに実装されています）。

Answer 3

「中間に挿入する」とは、リストの最初から目的のポイント（その間にあるすべてのリンクされた要素を1つずつトラバースする）に線形時間を保存するということですか？

はい。
基本的には、新しい要素を挿入したり、リスト全体を移動したり、内容をコピーしたりするためにポインタを変更する必要があることを意味します。リストをトラバースする必要やコンテナをコピーする必要がないため、

Answer 4

いいえ、「中に挿入する」とは、「リストの全体または不定部分を走査する基準に従って挿入ポイントを見つける」という意味ではありません。

Answer 5

リストの「中央」に挿入するとは、開始または終了以外のどこかに挿入することを意味します。しかし、挿入を行うには挿入ポイントのイテレータが必要です。このようなイテレータを使用すると、挿入時間は一定ですが、最初にそのようなイテレータを取得することは別の問題です。