c++ - 速度 - vector erase all




ベクトルから要素を消去する (3)

私は、消去メソッドを使用してベクトルから要素をクリアしたい。 しかし、ここでの問題は、要素がベクトル内で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つコピーしたりせずにこれを行う方法はありますか?


  1. インデックスアクセスを使用して反復することができますが、

  2. O(n ^ 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());
}

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());

これをやっている理由によって、 std::setを使う方がstd :: vectorより良いアイデアかもしれません。

これは、各要素が1回だけ出現することを可能にする。 複数回追加すると、消去するインスタンスは1つだけになります。 これにより、消去操作が簡単になります。 消去操作は、ベクトルよりも時間の複雑さが低くなりますが、エレメントを追加することはセット上で遅くなりますので、あまり効果がないかもしれません。

これはもちろん、ベクトルに要素が追加された回数や要素が追加された順序に関心がある場合はうまくいきません。





erase