115

erase メソッドを使用してベクターから要素をクリアしたい。ただし、ここでの問題は、要素がベクトル内で 1 回だけ発生することが保証されていないことです。複数回存在する可能性があり、それらすべてをクリアする必要があります。私のコードは次のようなものです:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    std::vector<int>::iterator endIter = myNumbers_in.end();
    for(; iter != endIter; ++iter)
    {
        if(*iter == number_in)
        {
            myNumbers_in.erase(iter);
        }
    }
}

int main(int argc, char* argv[])
{
    std::vector<int> myNmbers;
    for(int i = 0; i < 2; ++i)
    {
        myNmbers.push_back(i);
        myNmbers.push_back(i);
    }

    erase(myNmbers, 1);

    return 0;
}

このコードは明らかにクラッシュします。これは、繰り返し処理中にベクターの末尾を変更しているためです。これを達成するための最良の方法は何ですか?つまり、ベクターを複数回繰り返したり、ベクターのコピーをもう 1 つ作成したりせずにこれを行う方法はありますか?

4

5 に答える 5

188

remove/erase イディオムを使用します。

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());

は、削除する値 ( ) とはremove異なる要素を圧縮し、その範囲の後の最初の要素にイテレータを返します。次に、これらの要素 (値は未指定) を削除します。number_invectorerase

于 2008-12-07T11:07:10.887 に答える
64

erase を呼び出すと、イテレータが無効になります。次を使用できます。

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    while (iter != myNumbers_in.end())
    {
        if (*iter == number_in)
        {
            iter = myNumbers_in.erase(iter);
        }
        else
        {
           ++iter;
        }
    }

}

または、 std::remove_ifをファンクターと std::vector::erase と共に使用することもできます。

struct Eraser
{
    Eraser(int number_in) : number_in(number_in) {}
    int number_in;
    bool operator()(int i) const
    {
        return i == number_in;
    }
};

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());

この場合、独自のファンクターを記述する代わりに、std::removeを使用できます。

std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());

C++11 では、ファンクターの代わりにラムダを使用できます。

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());

C++17 ではstd::experimental::eraseおよびstd::experimental::erase_ifも使用できます。C++20 では、これらは (最終的に) std::eraseおよびstd::erase_ifに名前が変更されました(注: Visual ではStudio 2019 をサポートするには、C++ 言語バージョンを最新の実験的バージョンに変更する必要があります):

std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda

また:

std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
于 2008-12-07T10:22:53.987 に答える
15
  1. インデックスアクセスを使用して反復できます。

  2. O(n^2) の複雑さを避けるために、2 つのインデックス、i - 現在のテスト インデックス、j - 次のアイテムを格納するためのインデックス、およびサイクルの最後にベクトルの新しいサイズを使用できます。

コード:

void erase(std::vector<int>& v, int num)
{
  size_t j = 0;
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] != num) v[j++] = v[i];
  }
  // trim vector to new size
  v.resize(j);
}

このような場合、反復子を無効にする必要はなく、複雑さは O(n) であり、コードは非常に簡潔であり、いくつかのヘルパー クラスを記述する必要はありませんが、場合によってはヘルパー クラスを使用するとより柔軟なコードが得られます。

eraseこのコードはメソッドを使用しませんが、タスクを解決します。

純粋な stl を使用すると、次の方法でこれを行うことができます (これは Motti の回答に似ています)。

#include <algorithm>

void erase(std::vector<int>& v, int num) {
    vector<int>::iterator it = remove(v.begin(), v.end(), num);
    v.erase(it, v.end());
}
于 2008-12-07T11:44:23.013 に答える
4

これを行う理由によっては、std::setを使用する方が std::vector よりも優れている場合があります。

各要素が 1 回だけ出現することを許可します。複数回追加しても、消去するインスタンスは 1 つだけです。これにより、消去操作が簡単になります。消去操作もベクトルよりも時間の複雑さが低くなりますが、セットでは要素の追加が遅くなるため、あまり利点がない可能性があります。

もちろん、要素がベクターに追加された回数や要素が追加された順序に関心がある場合、これは機能しません。

于 2008-12-07T11:18:49.040 に答える