c++ - ベクトルと stl のリスト - メソッドの削除

Question

std::listにはremoveメソッドがありますが、にstd::vectorはありません。その理由は何ですか？

score 4 · Accepted Answer

std::list<>::remove特定の基準を満たすリスト要素を物理的に破壊することによって実装できる物理的な削除方法です（物理的な破壊とは、要素の保存期間の終わりを意味します）。物理的な削除は、リストにのみ適用されます。のような配列には適用できませんstd::vector<>。配列の個々の要素の保存期間を物理的に終了することはできません。配列は、全体としてのみ作成および破棄できます。std::vector<>に似たものがないのはこのためstd::list<>::removeです。

変更可能なすべてのシーケンスに適用可能な普遍的な削除方法は、論理的な削除と呼ばれるものです。ターゲット要素は、シーケンス内のさらに下にある要素の値で値を上書きすることにより、シーケンスから「削除」されます。つまり、永続データを「左に」コピーすることにより、シーケンスがシフトされ、圧縮されます。このような論理的な削除は、のような独立した関数によって実装されstd::removeます。std::vector<>このような機能は、との両方に同等に適用できstd::list<>ます。

特定の要素の即時の物理的除去に基づくアプローチが適用される場合、前述の論理的除去と呼ばれる一般的なアプローチよりも効率的に機能します。そのため、のために特別に提供する価値がありましたstd::list<>。

score 3 · Accepted Answer

std::list::remove指定された値に一致するリスト内のすべての項目を削除します。

std::list<int> myList;
// fill it with numbers
myList.remove(10); // physically removes all instances of 10 from the list

同様の関数があり、std::list::remove_if他の述語を指定できます。

std::list::remove(要素を物理的に削除する) は、メモリ構造について知る必要があるため、メンバー関数である必要があります (つまり、更新する必要がある各アイテムの前のポインターと次のポインターを更新し、アイテムを削除する必要があります)。関数全体が線形時間で実行されます (リストの 1 回の反復で、要求されたすべての要素を削除できますが、残っているアイテムを指す反復子は無効になりません)。

から 1 つの要素を物理的に削除することはできませんstd::vector。ベクトル全体を再割り当てするか、削除されたアイテムの後にすべての要素を移動してsizeメンバーを調整します。その一連の操作の「最もクリーンな」実装は、次のことです

// within some instance of vector
void vector::remove(const T& t)
{
    erase(std::remove(t), end());
}

std::vector依存する必要が<algorithm>あるもの (現在は必要ないもの)。

複数の割り当てやコピーを必要とせずにアイテムを削除するには、「並べ替え」が必要です。(要素を物理的に削除するためにリストをソートする必要はありません)。

他の人が言っているのとは逆に、スピードとは何の関係もありません。これは、データがメモリにどのように格納されているかを知る必要があるアルゴリズムに関係しています。

std::remove補足として: これは、 (そして友人たちも) 操作対象のコンテナからアイテムを実際に取り出さないのと同様の理由です。削除されないすべてのものをコンテナの「前面」に移動するだけです。オブジェクトをコンテナーから実際に削除する方法を知らなければ、汎用アルゴリズムは実際に削除を行うことができません。

score 2 · Accepted Answer

両方のコンテナーの実装の詳細を検討してください。Avectorは、ストレージ用に連続したメモリブロックを提供する必要があります。インデックスn != N(Nベクトルの長さ) の要素を削除するには、からのすべての要素を移動n+1するN-1必要があります。<algorithm>ヘッダーのさまざまな関数は、std::removeやのようにその動作を実装しますstd::remove_if。これらが独立した関数であることの利点は、必要な反復子を提供する任意の型に対して機能できることです。

list一方、Aは連結リスト構造として実装されているため、次のようになります。

どこからでも要素をすばやく削除できます
イテレータを効率的に使用することは不可能です (内部構造を認識して操作する必要があるため)。

score 1 · Accepted Answer

一般的に STL のロジックは、「効率的に実行できる場合はクラスメンバーであり、非効率的である場合は外部関数です」です。

このようにして、クラスの「正しい」(つまり「効率的な」) 使用と「正しくない」(非効率的な) 使用を区別します。

たとえば、ランダムアクセス反復子には += 演算子があり、他の反復子はこのstd::advance関数を使用します。

そしてこの場合 - から要素を削除することstd::listは非常に効率的です。std::vector

score 1 · Accepted Answer

効率性と参照/ポインター/イテレーターの有効性がすべてです。listアイテムは、他のポインターやイテレーターに影響を与えることなく削除できます。vectorこれは、最も些細なケースを除いて、a およびその他のコンテナーには当てはまりません。外部戦略の使用を妨げるものは何もありませんが、優れた選択肢があります。

重複した質問に関する別のポスターから：

問題は、なぜ std::vector が操作を提供しないのかではなく、なぜ std::list がそれを提供するのかということです。STL の設計は、コンテナーとアルゴリズムをイテレーターによって分離することに重点を置いており、イテレーターに関してアルゴリズムを効率的に実装できる場合は常に、それがオプションです。

ただし、コンテナーの知識があれば、より効率的に実装できる特定の操作が存在する場合があります。これは、コンテナから要素を削除する場合です。remove-erase イディオムを使用するコストはコンテナーのサイズに比例しますが (これはあまり削減できません)、最悪の場合、これらの操作の 1 つを除いてすべてがオブジェクトのコピーであるという事実が隠されています (唯一の要素一致するものが最初です)、これらのコピーは非常に大きな隠れたコストを表す可能性があります。

操作を std::list のメソッドとして実装することにより、操作の複雑さは直線的になりますが、削除される要素のそれぞれに関連するコストは非常に低くなり、いくつかのポインターのコピーとメモリ内のノードの解放が発生します。同時に、リストの一部としての実装は、より強力な保証を提供できます。消去されない要素へのポインター、参照、および反復子は、操作で無効になりません。

特定のコンテナーに実装されるアルゴリズムの別の例は、std::list::sort です。これは、std::sort より効率的ではありませんが、ランダムアクセスイテレーターを必要としないマージソートを使用します。

したがって、基本的に、具体的なコンテナーで特定の実装を提供する強い理由がない限り、アルゴリズムはイテレーターを備えたフリー関数として実装されます。

score 0 · Accepted Answer

std::listリンクされたリストのように機能するように設計されています。つまり、一定時間の挿入と削除のために設計されています (最適化されていると言うかもしれません)。

std::vector配列のように一定時間アクセスできるように設計されています。したがって、ランダムアクセス用に最適化されています...しかし、挿入と削除は実際には「テール」または「エンド」でのみ行われることになっています。他の場所では、通常ははるかに遅くなります。

異なる目的を持つ異なるデータ構造...したがって、異なる操作。

c++ - ベクトルと stl のリスト - メソッドの削除

7 に答える 7

Related

Reference