4

2つのベクトルがあります。1つは消去したいもう1つのベクトルのインデックスのベクトルです。現在、私は次のことを行っています。

#include <vector>
#include <iostream>
#include <string>

int main() {
        std::vector<std::string> my_vec;
        my_vec.push_back("one");
        my_vec.push_back("two");
        my_vec.push_back("three");
        my_vec.push_back("four");
        my_vec.push_back("five");
        my_vec.push_back("six");

        std::vector<int> remove_these;
        remove_these.push_back(0);
        remove_these.push_back(3);

        // remove the 1st and 4th elements
        my_vec.erase(my_vec.begin() + remove_these[1]);
        my_vec.erase(my_vec.begin() + remove_these[0]);

        my_vec.erase(remove_these.begin(), remove_these.end());

        for (std::vector<std::string>::iterator it = my_vec.begin(); it != my_vec.end(); ++it)
                std::cout << *it << std::endl;

        return 0;
}

しかし、これはエレガントで非効率的だと思います。さらに、ベクトルをソートして最後から開始するように注意する必要があると思いますremove_these（そのため、インデックス0の前にインデックス3を消去します）。消去コマンドを1つ欲しいのですが、

my_vec.erase(remove_these.begin(), remove_these.end());

my_vec.erase()しかしもちろん、イテレータが同じベクトルを参照することを期待しているため、これは機能しません。

4

3 に答える 3

6

標準シーケンスから要素を消去する既知のイディオムは、erase/remove イディオムです。remove最初に、保持したいすべての要素をシーケンスの前に移動するアルゴリズムを呼び出してから、シーケンスeraseの後ろにある削除された要素を呼び出します。C++11では、次のようになります。

std::vector< std::string > strings;
strings.erase(
    std::remove_if(
        strings.begin(), strings.end()
      , []( std::string const& s ) -> bool
        {
            return /*whether to remove this item or not*/;
        }
    )
  , strings.end()
);
于 2012-12-30T20:13:02.787 に答える
4 
    std::sort(remove_these.begin(), remove_these.end());

    int counter = 0;
    auto end = std::remove_if(my_vec.begin(), my_vec.end(),
                             [&](const std::string&) mutable {
        return std::binary_search(remove_these.begin(), remove_these.end(), counter++);
    });
    my_vec.erase(end, my_vec.end());

これは、現在の要素のインデックス（変数によって追跡される）がベクトルで見つかったremove_if場合にtrueを返すラムダ関数で使用されます。そのベクトルは、最適化として使用できるように並べ替えられます。削除する要素のリストが小さい場合は、並べ替えずにラムダで使用する方が速い場合があります。counterremove_thesebinary_search

        return std::find(remove_these.begin(), remove_these.end(), counter++) != remove_these.end();
于 2012-12-30T20:14:19.837 に答える
1

あなたの状況では、考慮に値する2つの問題があると思います。

  • 連続したインデックスを持つコンテナを使用しているため、要素が削除されるたびに、その後のすべての要素のインデックスが再作成されます（これが、サンプルコードで逆の順序で削除を行う必要がある理由です）。
  • そのコンテナはまた、その要素を連続して格納するため、削除すると再割り当てがトリガーされ、少なくとも要素のコピーが連続性の制約を満たすようになります。

これらの2つの問題を考えると、削除するのではなく、保持したい要素を新しいコンテナーにコピーすることが興味深い場合があります。あなたの場合、コピーオンライト戦略std::stringを使用する多くの実装があるので、要素のコピーは大きな問題ではないようですが、自分でそれを確認することをお勧めします。

考慮すべきもう1つのことは、削除するインデックスのセットをビットベクトルに適切に格納できることです。これはかなり効率的で、アルゴリズムを大幅に簡素化します。ただし、削除された要素の有効数を追跡する必要があります。

私は個人的に単純なループに行きますが、C++は同様の結果を達成するための多くの方法を提供します。ループバージョンは次のとおりです。

    std::vector<bool> remove_these(my_vec.size(), false):
    remove_these[0] = remove_these[4] = true;

    std::vector<std::string> my_result;
    my_result.reserve(my_vec.size() - 2);

    for (int i = 0; i < remove_these.size(); ++i)
        if (!remove_these[i])
             my_result.push_back(my_vec[i]);

reserveベクトルの塗りつぶし中に複数の再割り当てを回避するためにを使用していることに注意してください。

これで、上記のコードを関数でラップするだけで、事前にintベクトルをboolベクトルに変換できます。

template <typename IT>
void erase(std::vector<std::string> &my_vec, IT begin, IT end){
    std::vector<std::string> res;
    std::vector<bool> r(my_vec.size(), false);
    res.reserve(my_vec.size() - (end - begin));
    for (IT it = begin; it != end; ++it)
        r[*it] = true;
    for (int i = 0; i < r.size(); ++i)
        if (!r[i])
            res.push_back(my_vec[i]);
    my_vec = res;
}

それだけです。アルゴリズムの時間計算量は約O（N + M）my_vecです。ここで、NとMはとのサイズですremove_these。または、2番目のループを。に置き換えることもできますremove_if。

実際、stlが次のようなシーケンスを反復処理し、remove_ifその反復子のキーと値をパラメーターとして受け取る述語関数を呼び出す関数を提供している場合は、my_vec逆反復子とラムダを指定して指定されているかどうかを確認することで使用できます。キーはにありますremove_theseが、時間計算量は上記のソリューションよりも少し高くなります。

于 2012-12-30T22:31:32.960 に答える