std :: vector線形時間演算ではerase（）ですか？最後の要素は、（移動）を削除した後

Question

ページhttp://www.cplusplus.com/reference/vector/vector/erase/は

リニア（破壊）消去の要素の数を加えた要素の数 に述べています。

だから、

、私はいくつかの長さn（N> j）のベクトルからインデックスjで、たとえば、要素を削除していた場合 - それは、（O（n））は、一定または線形のでしょうか？

Jthの要素の後にpの要素がある場合は、O(p)の順になります - そうですか？あなたが提供されたリンクから

Answer 1

：（破壊）消去の要素の数を加えた要素の数 に

リニア最後の要素を削除した後（移動）

これは時にあることを意味std::vectorからN = 1個の要素を削除します。あなたのケースでは1に等しいデストラクターにNの呼び出しを行います。あなたの場合、それは(n-j-1)に等しいMの移動操作を行います。したがって、定数ではなく線形です。

したがって、std :: vector :: eraseの複雑さは、O(Deleted_Items_Count) + O(Moved_Items_Count)です。あなたのケースでは

：1*Destructor_Time + (n-j-1)*Moving_Time

---

一定の時間内でのベクターからアイテムを消去するために、あなたは、ベクター（例えばstd::vector::pop_back）の尾からそれらを消すこと

だからあなたがしたい場合時間cがかかります

auto linear_erase=[](auto& v, const size_t index){ 
    std::swap(v[index], v.back()); 
    v.pop_back(); 
}; 

Answer 2

ベクターからNの要素を削除する：ソートのは重要で消去一定の時間アプリケーションがM要素を反復処理し、各要素のデストラクタを呼び出し、残りの要素を、消去された要素を破棄することによって作成されたギャップにコピーする必要があるため、O(N)の複雑さです。

だから我々はN要素を持つベクトルを持っている、とpとqは定数であるため、O(1)であるあなたが言うことができ、O(q-p)時間の複雑さを取る範囲を破壊するよりも、私たちは、範囲(p,q]から要素を消去します。範囲(q,N]をコピー/移動する必要があります。 N-qは線形であるため、時間の複雑さはO(N)です。あなたは配列の末尾で終わる範囲を削除した場合

が一緒に私たちは、当然のO(N) + O(1) = O(N)

取得するには、/移動をコピーする要素がないので、複雑さがO(1)です。

Answer 3

私はここで、標準が最良の基準であることを知りました。

から23.3.11.1/1 [ベクター。概要]：

ベクトルは、最後に一定時間の挿入と削除操作をサポート（償却）するシーケンスコンテナです。途中での挿入と消去は線形時間を要します。

したがって、この場合、eraseは、定数でも線形時間でもありません。
それは主にあなたが行っている操作の種類によって異なります。それ以外の場合は線形だ

、あなたはベクトルの最後に消去されている場合には、一定のです

• を。