1

近々テストがありますが、いくつかの問題には STL クラス テンプレート関数が含まれているようです。多くはアルゴリズムの複雑さを扱っているため、基本的な操作の複雑さを軽減しようとしています。私が混乱しているのは、挿入操作です。挿入操作は、特定のコンテナーを使用して、イテレーターが指す位置から開始して挿入を行うことができます。

vector<int> vector1;

for (int i=1; i<6; i++) vector1.push_back(i);

vector<int>::iterator it;

it = vector1.begin();

vector1.insert(it+2,10);

さて、この挿入操作は、ほとんどの挿入操作で直線的な時間がかかることを認識しています。ただし、単一のアイテムを挿入する場合、これにはまだ直線的な時間がかかりますか? リストSTLの場合、単一のアイテムを挿入するのに一定の時間がかかるため、これを尋ねます。これは、リストが動的な二重リンク循環チェーンであるためだと考えました。

vector は動的で連続したストレージ構造なので、vector[size-1] の前に挿入すると、挿入後のすべての項目を 1 単位上に移動する必要があるということですか?

さて、デキューです。私は、deque STL を、配列内のポインタが指す単一リンク チェーンのシステムと考えています。これは正しいです？この場合、前部または後部ではなく、両端キューへの単一の挿入は O(1) でしょうか?

ありがとう、たくさんの質問をしてすみません。

4

2 に答える 2

3

以下にいくつかの注意事項を示します。

  • あなたが示唆するように、への挿入には時間std::listがかかりO(1)ます。
  • あなたが示唆するように、 a への挿入std::vectorでは、ベクトルの残りのすべての要素を 1 スペース戻す必要があり、これにはO(n)時間がかかります。
  • 標準では、deques の特定の実装は必要ありませんが、フロントとバックへの挿入にO(1)時間がかかる必要があります。
  • ただし、コンテナーの途中に挿入する場合、deques は挿入時間を必要としません。O(1)
  • 余談O(1)ですが、コンテナの最後に挿入する場合、ベクトルは挿入時間のみを提供します。
  • cppreferenceは、deques の頻繁な実装方法であると感じていることについてコメントしています。一般的な実装は一連の固定長の配列であると言われています。したがって、たとえば 16 個の要素を格納できる配列があり、std::list(多かれ少なかれ) それらの配列があります。
  • 私の知る限り、実装はと同じように実装できます。ただし、これを行わなくてもパフォーマンスが向上する可能性があります。特定の実装でこれが行われた場合、deque の途中での挿入は O(1) になります。ただし、これは必須ではありません。std::dequesd::list
  • Aはランダム アクセス反復子を提供するため、std::dequeとして実装することはできません。std::listこれは、deque::at(4)そのイテレータを一定時間で提供する必要があることを意味します。A それstd::listはできません。

deque::insertジェネリックが になる理由についてのコメントに関してO(n)、ここに私の考えがあります。cppreference の両端キューの実装を使用すると仮定しましょう。

10 個の要素を持つ両端キューを作成しましょう。次々と挿入。両端キューが 4 つの要素の配列によって実装されていると仮定します。

そのため、deque は現在、次のように実装されています。

[ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, _, _ ]

後ろに要素を挿入しましょう。

[ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ]

先頭に要素を挿入しましょう

[ _, _, _, E] <-> [ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ]

これらの操作はすべて、O(1) としてどのように機能するかが理にかなっています。

配列の途中に要素を挿入するとどうなるでしょうか。

[ _, _, _, E] <-> [ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ]
                                      ^ I want to insert here!

そのためには、邪魔にならないように 7 つの要素をシフトする必要があります。これが、この操作が可能性が高い理由O(n)です。

于 2013-04-30T04:20:58.083 に答える
1

単一のアイテムをベクターに挿入したい場合でも、言及した理由により線形時間がかかります。

両端キューの実装は、実装者に固有です。ただし、前後ではない位置への挿入は、線形時間である可能性が最も高いです (一定時間ではありません)。

于 2013-04-30T04:20:19.147 に答える