3

線形時間insert()の真ん中にたくさんのアイテムを配置するにはどうすればよいですか？deque

（挿入しているアイテムには、STLスタイルのイテレーターからはアクセスできません。）

4

4 に答える 4

7

単一の要素としてdeque::insert(iterator pos, const T&x)の位置を取る機能があります。このメソッドを使用すると、すべての要素を1つずつ挿入できます。によって簡単に取得できます（前に要素を挿入するインデックスがある場合）。このメソッドは、新しく挿入された要素のイテレータを返します。この返されたイテレータをインクリメントするだけで、次の位置を取得できます。posdeque::iteratorposdeque.begin()+indexinsert

deque::iterator it = myDeque.begin()+index;
while(n--) {
  it = myDeque.insert(it, currentElement);
  it++;
  currentElement = ... // However you get your next element ...
}

ただしO(n*k)、単一の要素の挿入は（iirc）線形時間演算iircであるため、これには時間がかかる場合があります。

2番目のオーバーロードはdeque::insert(iterator pos, InputIterator f, InputIterator l)次のとおりです。単純なポインターもSTL入力イテレーターの要件を満たすため、要素を含むT array[]長さのCスタイル配列があるn場合は、この配列からすべての要素を次のように挿入できます。

d.insert(pos, array, array+n);

この操作は線形時間で実行できますO(n+k)。これが標準によって保証されているかどうかはわかりませんが、ほとんどの実装で効率的に実行できると思います。

編集

私はすぐにMicrosoftの実装を確認しました。彼らは、push_backまたはのシーケンスによってそれpush_frontをpos行い、要素を最終的な場所に回転させて、上記のO(n+k)複雑さを保証します。もちろん、それは次のように「手作業で」行うこともできます。

size_type _Off = pos - d.begin();
size_type _Oldsize = d.size();
if (_Off <= d.size() / 2)
{   // closer to front, push to front then rotate
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  size_type _Num = d.size() - _Oldsize;
  std::reverse(d.begin(), d.begin() + _Num); // flip new stuff in place
  std::rotate(d.begin(), d.begin() + _Num, begin() + _Num + _Off);
}
else
{ // closer to back
  while (hasMoreElements())
    push_front(nextElement()); // prepend flipped

  std::rotate(begin() + _Off, begin() + _Oldsize, end());
}

（Microsoftの実装からコードをコピーし、deque::insertデバッグコードと例外処理を削除しました。

于 2011-10-22T20:36:29.423 に答える
1

挿入するアイテムのシーケンスを受け取るinsertメソッドを呼び出します。ここにリストされている3番目のメソッドを参照してください。

http://msdn.microsoft.com/en-us/library/zcww84w5(v=vs.71).aspx

また、挿入するアイテムにアクセスするための独自のSTLスタイルのイテレータを作成します。見る：

C++のカスタムイテレータ

于 2011-10-22T20:35:34.110 に答える
0

挿入点の後のすべての要素をベクトルに追加します。
挿入ポイント以降のすべての要素を削除します。
dequeに新しい範囲を追加します。
ベクトルをdequeに追加します。

これは、O（n ^ 2）ではなく、O（2n）の最悪のケースです。

于 2011-10-22T22:25:49.373 に答える
0

入力：

デキュー: lengthl = l,

新商品（m＝新商品数）

アルゴリズム:

新しい両端キューを作成する (1)

新しいアイテムを挿入する場所まで、元の両端キューからすべてのアイテムをコピーします (p)

新しいアイテムを追加する (m)

古い両端キューからアイテムを追加 (mp)

新しい両端キューを使用することもできますが、最悪の場合:

新しい両端キューを古い両端キューにコピーします (完全にクリアした後: ):

コスト (l+m)

したがって、最悪のコストは次のとおりです: origsize * 2 + newitems これは線形です。

「クリアデッキ」はここではカウントされませんが、線形でもあります (最悪の場合)。

于 2011-10-22T20:31:59.433 に答える