5

ダミーの質問があります。私はいつも、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つずつトラバースする）？

4

5 に答える 5

14

次のように、イテレータの計算を一般的に行うことができます。

 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()操作になる可能性があることに注意してください(たとえば、前方専用のコンテナに実装された逆イテレータの場合は遅くなります)。

于 2011-11-08T14:58:35.063 に答える
6

ここで、「中間」とは、リスト内の任意のポイントを意味しますが、そのポイントを参照する反復子が既にある場合に限ります。そのため、挿入は、挿入ポイントの周りのいくつかのポインターを変更するだけの問題です。

挿入ポイントの反復子をまだ持っておらず、開始点や終了点のような単純な場所ではない場合、リストをたどってそれを見つけるには直線的な時間がかかります。

于 2011-11-08T15:03:02.327 に答える
1

リストの「途中」に挿入するとは、最初または最後以外の場所に挿入することを意味します。ただし、挿入を行うには、挿入ポイントへの反復子が必要です。このようなイテレータを取得すると、挿入時間は一定になりますが、最初にそのようなイテレータを取得することは別の問題です。

于 2011-11-08T15:03:38.470 に答える
1

「途中に挿入する」と言うとき、リストの先頭から目的のポイントに移動するための線形時間を節約することを本当に意味しますか (間にあるすべてのリンクされた要素を 1 つずつトラバースします)。

はい。
基本的に、リスト全体をナビゲートしたり、コンテンツをコピーしたりする必要はなく、新しい要素を挿入するためにポインタを変更するだけでよいことを意味します。したがって、リストをトラバースしたり、コンテナをコピーしたりする必要がないため、挿入は一定の時間です。

于 2011-11-08T14:58:54.590 に答える
1

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

于 2011-11-08T15:01:18.437 に答える